第四章语法分析课件

单击编辑母版标题样式,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击编辑母版标题样式,*,章语法分析,章语法分析,1,第四章 语法分析,本章内容,上下文无关文法,自上而下分析和自下而上分析,围绕分析器的自动生成展开,词 法,分析器,记 号,取下一个记号,源程序,分析树,前端的,其余部分,分析器,中间表示,符号表,第四章 语法分析本章内容词 法记 号取下一个记号源程,2,上下文无关文法,上下文无关文法,3,上下文无关文法,上下文无关文法的定义,正则式能定义一些简单的语言，能表示给定结构的固定次数的重复或者没有指定次数的重复,例： (), ()*,正则式不能用于描述配对或嵌套的结构,例：配对括号串的集合,例： 是和的串,上下文无关文法 上下文无关文法的定义,4,上下文无关文法,上下文无关文法是四元组（ , , , ）,: 终结符集合,: 非终结符集合,: 开始符号，非终结符中的一个,:产生式集合， 产生式形式 : ,例 ( , , , , (, ), , , , ), (), , ,上下文无关文法上下文无关文法是四元组（ , , , ）,5,上下文无关文法,简化表示, () , ,简化表示, ( ) , ,上下文无关文法简化表示,6,上下文无关文法,文法书写上的约定,终结符,字母表中的小写字母，如 ，,黑体串，如 ,数字 , , ,标点符号，如括号，逗号等,运算符号，如, 等,非终结符,字母表中的大写字母，如, ,字母，并且通常代表开始符号,小写字母的名字（斜体），如,上下文无关文法文法书写上的约定,7,上下文无关文法,文法书写上的约定,字母表中后面的大写字母，如，可以是终结符或非终结符,字母表中后面的小写字母，如， 可代表终结符号串,小写希腊字母，如，可代表文法的符号串,对于 ， ，. 可以写成, ,上下文无关文法文法书写上的约定,8,上下文无关文法,推导（自顶向下）,把产生式看成重写规则，把符号串中的非终结符用其产生式右部的串来代替,例 ( ) , () ( ) ( ) ( ),概念,*、 ，于是, *, * ， 且 , 则 * ,上下文无关文法 推导（自顶向下）,9,上下文无关文法,推导,概念,上下文无关语言, 且、是任意符号串，则 ,由上下文无关文法生成的语言是上下文无关语言,等价的文法,如果两个文法产生同样的语言，则两个文法等价,句型,文法的开始符为， *， 可能含有非终结符，则叫做文法的句型。,上下文无关文法 推导,10,上下文无关文法,例 ( ) ,最左推导, () ( ), ( ) ( ),最右推导, () ( ), ( ) ( ),上下文无关文法例 ( ) ,11,上下文无关文法,分析树,例 ( ) ,(,),上下文无关文法 分析树(),12,上下文无关文法,二义性 , , , , , ,两个不同的最左推导,上下文无关文法 二义性 ,13,上下文无关文法,二义性 , , , , , ,两棵不同的语法树,E,E,E,*,+,E,E,id,id,id,E,E,id,E,*,+,E,E,id,id,上下文无关文法 二义性 EEE*+EEididi,14,语言和文法,文法的优点,文法给出了精确的，易于理解的语法说明,自动产生高效的分析器,可以给语言定义出层次结构,以文法为基础的语言的实现便于语言的修改,文法的问题,文法只能描述编程语言的大部分语法，不能描述语言中上下文有关的语法特征,语言和文法 文法的优点,15,语言和文法,正则式和上下文无关文法的比较,正则式,()*,文法, ,1,2,开始,a,0,a,b,b,语言和文法 正则式和上下文无关文法的比较12开始a0ab,16,语言和文法,分离词法分析器理由,为什么要用正则式定义词法,词法规则非常简单，不必用上下文无关文法,对于词法记号，正则式描述简洁且易于理解,从正则式构造出的词法分析器效率高,语言和文法 分离词法分析器理由,17,语言和文法,从软件工程角度看，词法分析和语法分析的分离有如下好处,简化设计,编译器的效率会改进,编译器的可移植性加强,便于编译器前端的模块划分,语言和文法 从软件工程角度看，词法分析和语法分析的分离有如,18,语言和文法,能否把词法分析并入到语法分析中，直接从字符流进行语法分析,若把词法分析和语法分析合在一起，则必须将语言的注解和空白的规则反映在文法中，文法将大大复杂,注解和空白由自己来处理的分析器，比注解和空格已由词法分析器删除的分析器要复杂得多,语言和文法 能否把词法分析并入到语法分析中，直接从字符流进,19,语言和文法,验证文法产生的语言,: () () 配对的括号串的集合,语言和文法 验证文法产生的语言,20,语言和文法,验证文法产生的语言,: () () 配对的括号串的集合,按推导步数进行归纳：推出的是配对括号串,归纳基础： ,归纳假设：少于步的推导都产生配对的括号串,归纳步骤：步的最左推导如下：, () * () * (),语言和文法 验证文法产生的语言,21,语言和文法,验证文法产生的语言,: () () 配对的括号串的集合,按串长进行归纳：配对括号串可由推出,归纳基础： ,归纳假设：长度小于的都可以从推导出来,归纳步骤：考虑长度为( )的 (), () * () * (),语言和文法 验证文法产生的语言,22,语言和文法,适当的表达式文法,用一种层次观点看待表达式, () ,语言和文法 适当的表达式文法,23,语言和文法,适当的表达式文法,用一种层次观点看待表达式, () , (),文法, , (),语言和文法 适当的表达式文法,24,语言和文法, , (),expr,id,term,factor,id,id,term,*,term,factor,factor,*,expr,expr,+,id,factor,term,id,id,term,*,term,factor,factor,分析树, ,分析树,语言和文法 expridtermfacto,25,语言和文法,消除二义性,句型：,两个最左推导：,语言和文法 消除二义性,26,语言和文法,无二义的文法,语言和文法 无二义的文法,27,语言和文法,消除左递归,消除左递归, , , ,语言和文法 消除左递归,28,语言和文法,消除左递归,文法左递归,直接左递归,串的特点 . . .,消除直接左递归, , ,语言和文法 消除左递归,29,语言和文法,例 算术表达文法, （ . . . ）, （ . . . ）, ( ),消除左递归后文法, , , , , ( ),语言和文法 例 算术表达文法,30,语言和文法,非直接左递归, ,先变换成直接左递归, ,再消除左递归, , ,语言和文法 非直接左递归,31,语言和文法,提左因子,有左因子的文法, ,提左因子, , ,语言和文法 提左因子,32,语言和文法,例 悬空的文法,提左因子,语言和文法 例 悬空的文法,33,形式语言,产生式形式为： ,产生式形式为： , , ,产生式形式为： , 型语言 由 型文法定义, 型语言 由 型文法定义, 型语言 由 型文法定义,产生式形式为： , 型语言 由 型文法定义,又称 无限制文法！,又称,上下文有关文法！,又称,上下文无关文法！,又称 正规文法！,【注】 四类语言为 包含关系，且有 ；,编译处理中，主要应用后两种文法！,形式语言 产生式形式为： 产生式形式为： , ,34,乔姆斯基,艾弗拉姆诺姆乔姆斯基（英语： ，年月日）,美国哲学家、语言学家、认知学家、逻辑学家、政治评论家。乔姆斯基是麻省理工学院语言学的荣誉退休教授，他的生成语法被认为是世纪理论语言学研究上的重要贡献。,乔姆斯基艾弗拉姆诺姆乔姆斯基（英语： ，年月日）,35,句法结构,句法结构是乔姆斯基介绍转换生成语法的语言学理论的逻辑结构一书的精华版。这一理论认为说话的方式（词序）遵循一定的句法，这种句法是以形式的语法为特征的，具体而言就是一种不受语境影响并带有转换生成规则的语法。,儿童被假定为天生具有适用于所有人类语言的基本语法结构的知识。这种与生俱来的知识通常被称作普遍语法。,句法结构句法结构是乔姆斯基介绍转换生成语法的语言学理论,36,练习,文法, ,产生的语言是什么？该文法是否有二义性？,下面的二义文法描述命题验算公式的语法，为他写一个等价的非二义文法, (),练习文法,37,练习,文法, * (),产生字母表上所有不含的正则式。为该文法写一个等价的非二义文法。,练习文法,38,练习,考虑文法,S-(L) | a,L-L,S | S,建立句子,(a,(a,a),和,(a,(a,a),(a,a),的分析树,为（,a,）的两个句子构造最左推导,为（,a,）的两个句子构造最右推导,这个文法产生的语言是什么？,练习考虑文法,39,