第四章语法分析课件.ppt

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