书四章语法分析 南京大学计算机系 戴新宇 2019-3
南京大学计算机系 戴新宇 2019-3 1
概要 ●语法分析器 上下文无关文法 ●语法分析技术 自顶向下 自底向上 语法分析器生成工具
概要 语法分析器 上下文无关文法 语法分析技术 自顶向下 自底向上 语法分析器生成工具 2
引言 程序设计语言源程序的构成 文法:一种用于描述程序设计语言语法的表示方法,能 够自然地描述程序设计语言构造的层次化语法结构 文法给出了一个程序设计语言的精确易懂的语法规约 可以基于文法构造语法分析器,帮助确定源程序的语法结构 ●语法结构有助于把源程序翻译为正确的目标代码,以及检测 导语法错误。 文法的扩展性 ● Standard c++ Grammar ava sE7 grammar
引言 程序设计语言源程序的构成 文法：一种用于描述程序设计语言语法的表示方法，能 够自然地描述程序设计语言构造的层次化语法结构。 文法给出了一个程序设计语言的精确易懂的语法规约 可以基于文法构造语法分析器，帮助确定源程序的语法结构 语法结构有助于把源程序翻译为正确的目标代码，以及检测 导语法错误。 文法的扩展性 Standard C++ Grammar Java SE7 Grammar 3
语法分析器(What) ●输入:词法分析器输出的词法单元序列 输出:语法树表示 ●语法分析器的类型: 通用型(CKY, Earley) 自顶向下:通常处理LL文法 自底向上:通常处理LR文法
语法分析器（What） 输入：词法分析器输出的词法单元序列 输出：语法树表示 语法分析器的类型： 通用型(CKY，Earley) 自顶向下：通常处理LL文法 自底向上：通常处理LR文法 4
语法分析器(Why) 源程序 词法词法单元 语法 语法 前端的中间表示 分析器 分析器1分析树 其余部分 获取下 个词法单元 符号表 语法分析器功能: 验证输入源程序的合法性,并输出良构程序的语法结构 对于病构的程序,能够报告语法错误,并进行错误回复 写入符号表,类型检查,语义分析,翻译生成中间代码等往往和语 分析过程容绩成,塞践中往往和语法分析放入一个模块,图上
语法分析器（Why） 语法分析器功能： 验证输入源程序的合法性，并输出良构程序的语法结构 对于病构的程序，能够报告语法错误，并进行错误回复 写入符号表，类型检查，语义分析，翻译生成中间代码等往往和语 法分析过程交错完成，实践中往往和语法分析放入一个模块，图上 用“前端的其余部分”表示上述活动。 5
文法 ●本书特指上下文无关文法( Context free grammar, CFG ●程序设计语言中往往存在嵌套结构 ●上下文无关文法是一种能够很好描述程序设计语言的 表示方法 stmt if expr ) stmt else stmt expr Stmt→
文法 本书特指上下文无关文法（Context Free Grammar, CFG） 程序设计语言中往往存在嵌套结构 上下文无关文法是一种能够很好描述程序设计语言的 表示方法 stmt → if ( expr ) stmt else stmt expr → …… stmt → …… 6
CFG的定义 一个CFG由以下几个部分构成 终结符号 组成串的基本符号,与“词法单元名字”同义 ·非终结符号 语法变量,表示特定串的集合 给出了语言的层次结构,这种层次结构是语法分析和翻译的关键 个开始符号 某个特定的非终结符号,其表示的串集合是这个文法生成的语言 一组产生式 描述将终结符合和非终结符号组合成串的方法 产生式左部(头)是一个非终结符号 符号“→” 个由零个或多个终结符号与非终结符号组成的产生式右部(体)
CFG的定义 一个CFG由以下几个部分构成 终结符号 组成串的基本符号，与“词法单元名字”同义 非终结符号 语法变量，表示特定串的集合 给出了语言的层次结构，这种层次结构是语法分析和翻译的关键 一个开始符号 某个特定的非终结符号，其表示的串集合是这个文法生成的语言 一组产生式 描述将终结符合和非终结符号组合成串的方法 产生式左部（头）是一个非终结符号 符号 “→” 一个由零个或多个终结符号与非终结符号组成的产生式右部（体） 7
用于描述算术表达式的文法定义 S-> NP VP VP->VNP epression erpression term NP-> NAME expression expression- term NP->ART N e pression→term NAME-> John term→term* factor V->ate term term/factor ART-> the N-> cat term actor actoN expression factor→id
用于描述算术表达式的文法定义 8 S -> NP VP VP -> V NP NP -> NAME NP -> ART N NAME -> John V -> ate ART -> the N -> cat
符号表示约定 终结符号:ab+3id 非终结符号:ABC.,S,stmt 文法符号:XY E→→E+T|E-T|T 终结符号串:vw T→T*F|T/F|F 文法符号串:aβ F→(E)lid ●不同可选体:a,a,a ●开始符号:S
符号表示约定 终结符号：a b + 3 id… 非终结符号: A B C…, S, stmt 文法符号: X Y … 终结符号串:u v w… 文法符号串:α β… 不同可选体: α1 α2 α3… 开始符号: S 9
推导 ●产生式又可称为重写规则( Rewriting rule ●从开始符号出发,每个重写步骤把一个非终结符号替换为 它的某个产生式的体。 eg.E→E→-(E)→-(id),称为从E到-(id)的推导。 这个推导说明了-(id是表达式E的一个实例,或者说由E产 ●推导的一般性定义: 假设一个产生式A→y,aAβ→aβ,符号→ 表示“通过一步推导出
推导 产生式又可称为重写规则（Rewriting rule） 从开始符号出发，每个重写步骤把一个非终结符号替换为 它的某个产生式的体。 e.g. E -E –(E) –(id) ， 称为从E到-(id)的推导。 这个推导说明了–(id)是表达式E的一个实例，或者说由E产 生。 推导的一般性定义： 假设一个产生式A→ γ，αAβ αγβ ，符号 表示“通过一步推导出”。 10
