南京大学：《编译原理》课程教学资源（PPT课件讲稿）第四章 语法分析（戴新宇）

书四章语法分析 南京大学计算机系 戴新宇 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