第四章语法分析课件.ppt

1、章语法分析章语法分析第四章第四章 语法分析语法分析v本章内容本章内容v上下文无关文法上下文无关文法v自上而下分析和自下而上分析自上而下分析和自下而上分析v围绕分析器的自动生成展开围绕分析器的自动生成展开词词 法法分析器分析器记记 号号取下一个取下一个记号记号源程序源程序分析分析树树前端的前端的其余部分其余部分分析器分析器中间中间表示表示符号表符号表上下文无关文法 上下文无关文法上下文无关文法 上下文无关文法的定义上下文无关文法的定义正则式能定义一些简单的语言，能表示给定结正则式能定义一些简单的语言，能表示给定结构的固定次数的重复或者没有指定次数的重构的固定次数的重复或者没有指定次数的重复复例：

2、例： (), ()*正则式不能用于描述配对或嵌套的结构正则式不能用于描述配对或嵌套的结构例：配对括号串的集合例：配对括号串的集合例：例： 是和的串是和的串 上下文无关文法上下文无关文法v上下文无关文法是四元组（上下文无关文法是四元组（ , , , ）v : 终结符集合终结符集合v : 非终结符集合非终结符集合v : 开始符号，非终结符中的一个开始符号，非终结符中的一个v : 产生式集合，产生式集合， 产生式形式产生式形式 : v例例 ( , , , , (, ), , , , )v ()v v 上下文无关文法上下文无关文法v简化表示简化表示v () () v v简化表示简化表示v ( ) (

3、) v 上下文无关文法上下文无关文法v文法书写上的约定v终结符v字母表中的小写字母，如 ，v黑体串，如 , v数字 , , , v标点符号，如括号，逗号等v运算符号，如, 等v非终结符v字母表中的大写字母，如, , v字母，并且通常代表开始符号v小写字母的名字（斜体），如, 上下文无关文法上下文无关文法v文法书写上的约定v字母表中后面的大写字母，如，可以是终结符或非终结符v字母表中后面的小写字母，如， 可代表终结符号串v小写希腊字母，如，可代表文法的符号串v对于 ， ，. 可以写成v 上下文无关文法上下文无关文法 推导（自顶向下） 把产生式看成重写规则，把符号串中的非终结符用其产生式右部的串来

4、代替例 ( ) () ( ) ( ) ( ) 概念 *、 ，于是 * * ， 且 , 则 * 上下文无关文法上下文无关文法 推导推导 概念概念上下文无关语言上下文无关语言, 且、是任意符号串，则且、是任意符号串，则 由上下文无关文法生成的语言是上下文无关语由上下文无关文法生成的语言是上下文无关语言言等价的文法等价的文法如果两个文法产生同样的语言，则两个文法等如果两个文法产生同样的语言，则两个文法等价价句型句型文法的开始符为，文法的开始符为， *， 可能含有非终结可能含有非终结符，则符，则叫做文法的句型。叫做文法的句型。 上下文无关文法上下文无关文法v例例 ( ) v最左推导最左推导v () (

5、 )v ( ) ( )v最右推导最右推导v () ( )v ( ) ( ) 上下文无关文法上下文无关文法 分析树分析树例例 ( ) () 上下文无关文法上下文无关文法 二义性 两个不同的最左推导 上下文无关文法上下文无关文法 二义性 两棵不同的语法树EEE*+EEidididEEidE*+EEidid语言和文法语言和文法 v文法的优点文法的优点 v文法给出了精确的，易于理解的语法说明文法给出了精确的，易于理解的语法说明v自动产生高效的分析器自动产生高效的分析器v可以给语言定义出层次结构可以给语言定义出层次结构v以文法为基础的语言的实现便于语言的修改以文法为基础的语言的实现便于语言的修改v文法的

6、问题文法的问题v文法只能描述编程语言的大部分语法，不能文法只能描述编程语言的大部分语法，不能描述语言中上下文有关的语法特征描述语言中上下文有关的语法特征 语言和文法语言和文法 正则式和上下文无关文法的比较正则式和上下文无关文法的比较正则式正则式()*文法文法 12开始开始a0abb 语言和文法语言和文法 分离词法分析器理由分离词法分析器理由为什么要用正则式定义词法为什么要用正则式定义词法 词法规则非常简单，不必用上下文无关文法词法规则非常简单，不必用上下文无关文法对于词法记号，正则式描述简洁且易于理解对于词法记号，正则式描述简洁且易于理解从正则式构造出的词法分析器效率高从正则式构造出的词法分析

7、器效率高 语言和文法语言和文法 v从软件工程角度看，词法分析和语法分析的从软件工程角度看，词法分析和语法分析的分离有如下好处分离有如下好处v简化设计简化设计v编译器的效率会改进编译器的效率会改进v编译器的可移植性加强编译器的可移植性加强v便于编译器前端的模块划分便于编译器前端的模块划分 语言和文法语言和文法 v能否把词法分析并入到语法分析中，直接从能否把词法分析并入到语法分析中，直接从字符流进行语法分析字符流进行语法分析v若把词法分析和语法分析合在一起，则必须若把词法分析和语法分析合在一起，则必须将语言的注解和空白的规则反映在文法中，将语言的注解和空白的规则反映在文法中，文法将大大复杂文法将大

8、大复杂v注解和空白由自己来处理的分析器，比注解注解和空白由自己来处理的分析器，比注解和空格已由词法分析器删除的分析器要复杂和空格已由词法分析器删除的分析器要复杂得多得多 语言和文法语言和文法 验证文法产生的语言验证文法产生的语言 : () () 配对的括号串的集合配对的括号串的集合 语言和文法语言和文法 验证文法产生的语言验证文法产生的语言 : () () 配对的括号串的集合配对的括号串的集合按推导步数进行归纳：推出的是配对括号串按推导步数进行归纳：推出的是配对括号串归纳基础：归纳基础： 归纳假设：少于步的推导都产生配对的括号串归纳假设：少于步的推导都产生配对的括号串归纳步骤：步的最左推导如下

9、：归纳步骤：步的最左推导如下： () * () * () 语言和文法语言和文法 验证文法产生的语言验证文法产生的语言 : () () 配对的括号串的集合配对的括号串的集合按串长进行归纳：配对括号串可由推出按串长进行归纳：配对括号串可由推出归纳基础：归纳基础： 归纳假设：长度小于的都可以从推导出来归纳假设：长度小于的都可以从推导出来归纳步骤：考虑长度为归纳步骤：考虑长度为( )的的 () () * () * () 语言和文法语言和文法 适当的表达式文法适当的表达式文法用一种层次观点看待表达式用一种层次观点看待表达式 () 语言和文法语言和文法 适当的表达式文法适当的表达式文法用一种层次观点看待表

10、达式用一种层次观点看待表达式 () () 文法文法 () 语言和文法语言和文法 ()expridtermfactorididterm*termfactorfactor*exprexpr+idfactortermididterm*termfactorfactor 分析树分析树 分析树分析树 语言和文法语言和文法 消除二义性消除二义性 句型：句型： 两个最左推导：两个最左推导： 语言和文法语言和文法 v 无二义的文法无二义的文法v v v v v v v v 语言和文法语言和文法 消除左递归消除左递归消除左递归消除左递归 语言和文法语言和文法 消除左递归消除左递归文法左递归文法左递归 直接左递归直

11、接左递归 串的特点串的特点 . . . 消除直接左递归消除直接左递归 语言和文法语言和文法 v例例 算术表达文法算术表达文法v （ . . . ）v （ . . . ）v ( ) v消除左递归后文法消除左递归后文法v v v v v ( ) 语言和文法语言和文法 v非直接左递归非直接左递归v v v先变换成直接左递归先变换成直接左递归v v v再消除左递归再消除左递归v v v 语言和文法语言和文法 提左因子提左因子有左因子的文法有左因子的文法 提左因子提左因子 语言和文法语言和文法 v例 悬空的文法 v v v v提左因子v v v v 形式语言 产生式形式为： 产生式形式为： , , 产生

12、式形式为： 型语言 由 型文法定义 型语言 由 型文法定义 型语言 由 型文法定义 产生式形式为： 型语言 由 型文法定义又称 无限制文法！又称 上下文有关文法！又称 上下文无关文法！又称 正规文法！【注】 四类语言为 包含关系，且有 ；编译处理中，主要应用后两种文法！乔姆斯基v艾弗拉姆诺姆乔姆斯基（英语： ，年月日）v美国哲学家、语言学家、认知学家、逻辑学家、政治评论家。乔姆斯基是麻省理工学院语言学的荣誉退休教授，他的生成语法被认为是世纪理论语言学研究上的重要贡献。句法结构v句法结构是乔姆斯基介绍转换生成语法的语言学理论的逻辑结构一书的精华版。这一理论认为说话的方式（词序）遵循一定的句法，这

13、种句法是以形式的语法为特征的，具体而言就是一种不受语境影响并带有转换生成规则的语法。v儿童被假定为天生具有适用于所有人类语言的基本语法结构的知识。这种与生俱来的知识通常被称作普遍语法。练习v文法v v产生的语言是什么？该文法是否有二义性？v下面的二义文法描述命题验算公式的语法，为他写一个等价的非二义文法v ()练习v文法v * () v产生字母表上所有不含的正则式。为该文法写一个等价的非二义文法。练习v考虑文法S-(L) | aL-L,S | Sv建立句子(a,(a,a)和(a,(a,a),(a,a)的分析树v为（a）的两个句子构造最左推导v为（a）的两个句子构造最右推导v这个文法产生的语言是什么？