《编译原理 备课 课件 Compiler Theory07 - syn - full》由会员分享，可在线阅读，更多相关《编译原理 备课 课件 Compiler Theory07 - syn - full（295页珍藏版）》请在金锄头文库上搜索。
1、 计算机科学与技术学院编译原理第四章 语法分析第四章语法分析v本章内容上下文无关文法自上而下分析和自下而上分析围绕分析器的自动生成展开词 法分析器记 号取下一个记号源程序分析树前端的其余部分分析器中间表示符号表4.1上下文无关文法4.1.1上下文无关文法的定义正规式能定义一些简单的语言，能表示给定结构的固定次数的重复或者没有指定次数的重复例：a(ba)5,a(ba)*正规式不能用于描述配对或嵌套的结构例1：配对括号串的集合例2：wcw | w是a和b的串 4.1上下文无关文法v上下文无关文法是四元组（VT ,VN ,S,P）VT : 终结符集合VN: 非终结符集合S : 开始符号，非终结符中的
2、一个P :产生式集合， 产生式形式 : A v例 (id,+,(,),expr,op,expr,P )exprexpropexpr expr (expr)expr expr expridop +op 4.1上下文无关文法v简化表示exprexpropexpr | (expr)|expr | idop +|v简化表示E E A E | (E ) | E | idA +|4.1上下文无关文法4.1.2 推导 把产生式看成重写规则，把符号串中的非终结符用其产生式右部的串来代替v例 E E + E |E E|(E)|E|id E E (E)(E +E)(id+E)(id+id)v概念上下文无关语言、等
3、价的文法、句型v记号S *、S +w 4.1上下文无关文法v例E E + E |E E|(E)|E|id v最左推导E lmE lm(E)lm(E +E)lm(id+E)lm (id+id)v最右推导（规范推导）E rmE rm(E)rm(E +E)rm(E+id)rm (id+id)4.1上下文无关文法4.1.3分析树v例E E + E |E E|(E)|E|idEE()EEE+idid4.1上下文无关文法4.1.4二义性EE EEE+Eid EEE+EidE+EidE+Eidid+Eidid+Eidid+ididid+id两个不同的最左推导4.1上下文无关文法4.1.4二义性EE EEE+
4、Eid EEE+EidE+EidE+Eidid+Eidid+Eidid+ididid+id两棵不同的语法树EEE*+EEidididEEidE*+EEidid4.2语言和文法 v文法的优点文法给出了精确的，易于理解的语法说明自动产生高效的分析器可以给语言定义出层次结构以文法为基础的语言的实现便于语言的修改v文法的问题文法只能描述编程语言的大部分语法，不能描述语言中上下文有关的语法特征4.2 语言和文法 4.2.1 正规式和上下文无关文法的比较v正规式(a|b)*abv文法A0aA0|b A0|aA1A1bA2A212开始a0abb4.2 语言和文法 4.2.2分离词法分析器理由v为什么要用正规
5、式定义词法词法规则非常简单，不必用上下文无关文法对于词法记号，正规式描述简洁且易于理解从正规式构造出的词法分析器效率高4.2 语言和文法 v从软件工程角度看，词法分析和语法分析的分离有如下好处简化设计编译器的效率会改进编译器的可移植性加强便于编译器前端的模块划分 4.2 语言和文法 v能否把词法分析并入到语法分析中，直接从字符流进行语法分析若把词法分析和语法分析合在一起，则必须将语言的注解和空白的规则反映在文法中，文法将大大复杂注解和空白由自己来处理的分析器，比注解和空格已由词法分析器删除的分析器要复杂得多4.2 语言和文法 4.2.3 验证文法产生的语言G : S(S)S|L(G)=配对的括
6、号串的集合4.2 语言和文法 4.2.3 验证文法产生的语言G : S(S)S|L(G)=配对的括号串的集合v按推导步数进行归纳：推出的是配对括号串归纳基础：S归纳假设：少于n步的推导都产生配对的括号串归纳步骤：n步的最左推导如下：S(S)S*(x)S*(x)y4.2 语言和文法 4.2.3 验证文法产生的语言G : S(S)S|L(G)=配对的括号串的集合v按串长进行归纳：配对括号串可由S推出归纳基础：S归纳假设：长度小于2n的都可以从S推导出来归纳步骤：考虑长度为2n(n 1)的w =(x)yS(S)S*(x)S*(x)y4.2 语言和文法 4.2.4适当的表达式文法v用一种层次观点看待表
7、达式idid(id+id)+idid+id4.2 语言和文法 4.2.4适当的表达式文法v用一种层次观点看待表达式idid(id+id)+idid+ididid(id+id)v文法exprexpr+term|termtermterm factor|factorfactorid|(expr)4.2 语言和文法 exprexpr+term|termtermterm factor|factorfactorid|(expr)expridtermfactorididterm*termfactorfactor*exprexpr+idfactortermididterm*termfactorfactorid
8、 + id id分析树 id id id分析树 4.2 语言和文法 4.2.5消除二义性stmtifexprthenstmt|ifexprthenstmtelsestmt|otherv句型：ifexprthenifexprthenstmtelsestmtv两个最左推导：stmt ifexprthenstmt ifexprthenifexprthenstmtelsestmtstmt ifexprthenstmtelsestmt ifexprthenifexprthenstmtelsestmt4.2 语言和文法 v 无二义的文法stmtmatched_stmt|unmatched_stmtmatc
9、hed_stmtifexprthenmatched_stmtelsematched_stmt|otherunmatched_stmtif exprthenstmt|ifexprthenmatched_stmtelseunmatched_stmt4.2 语言和文法 4.2.6消除左递归v文法左递归A+Av直接左递归AA |串的特点 . . . v消除直接左递归A AA A|4.2 语言和文法 v例算术表达文法EE+T|T（T+T.+T）TTF |F（FF .F ）F(E)|id消除左递归后文法 ETE E+TE| TFT T F T |F(E)|id4.2 语言和文法 v非直接左递归SAa|bA
10、Sd|v先变换成直接左递归S Aa | bAAad | bd|v再消除左递归S Aa | bA bd A| AA adA| 4.2 语言和文法 4.2.7 提左因子v有左因子的文法A1 | 2v提左因子A AA 1 | 2 4.2 语言和文法 v例 悬空else的文法 stmtifexprthenstmtelsestmt|ifexprthenstmt|other提左因子stmtifexprthenstmtoptional_else_part|otheroptional_else_part elsestmt|4.2 语言和文法 4.2.8 非上下文无关的语言构造vL1=wcw | w属于(a |
11、 b)*标识符的声明应先于其引用的抽象vL2=anbmcndm|n 0,m 0形参个数和实参个数应该相同的抽象vL3=anbncn|n 0早先排版描述的一个现象的抽象begin：5个字母键，5个回退键，5个下划线键4.2 语言和文法 vL1=wcwR | w(a|b)* S aSa | bSb | c vL2=anbmcmdn|n 1,m 1SaSd | aAdA bAc | bcvL2=anbncmdm|n 1，m 1S ABA aAb | abB cBd | cd4.2 语言和文法 vL3=anbn|n 1S aSb | abvL3是不能用正规式描述的语言的一个范例 若存在接受L3的DFA
12、D，状态数为k个设D读完, a, aa, ,ak 分别到达状态s0,s1, ,sk至少有两个状态相同，例如是si和sj，则ajbi属于L3sifs0标记为ai的路径标记为bi的路径标记为aj i的路径 4.2 语言和文法 4.2.9 形式语言鸟瞰v文法G =(VT , VN, S,P)v0型文法：， , (VN VT)*,| |14.2 语言和文法 4.2.9 形式语言鸟瞰v文法G =(VT , VN, S,P)v0型文法：， , (VN VT)*,| |1v短语文法4.2 语言和文法 4.2.9 形式语言鸟瞰v文法G =(VT , VN, S,P)v0型文法：， , (VN VT)*,| |
13、1v1型文法：| |，但S可以例外v短语文法4.2 语言和文法 4.2.9 形式语言鸟瞰v文法G =(VT , VN, S,P)v0型文法：， , (VN VT)*,| |1v1型文法：| |，但S可以例外v短语文法、上下文有关文法4.2 语言和文法 4.2.9 形式语言鸟瞰v文法G =(VT , VN, S,P)v0型文法：， , (VN VT)*,| |1v1型文法：| |，但S可以例外v2型文法：A，AVN , (VN VT)*v短语文法、上下文有关文法4.2 语言和文法 4.2.9 形式语言鸟瞰v文法G =(VT , VN, S,P)v0型文法：， , (VN VT)*,| |1v1型
14、文法：| |，但S可以例外v2型文法：A，AVN , (VN VT)*v短语文法、上下文有关文法、上下文无关文法4.2 语言和文法 4.2.9 形式语言鸟瞰v文法G =(VT , VN, S,P)v0型文法：， , (VN VT)*,| |1v1型文法：| |，但S可以例外v2型文法：A，AVN , (VN VT)*v3型文法：A aB或A a，A, BVN ,a VTv短语文法、上下文有关文法、上下文无关文法4.2 语言和文法 4.2.9 形式语言鸟瞰v文法G =(VT , VN, S,P)v0型文法：， , (VN VT)*,| |1v1型文法：| |，但S可以例外v2型文法：A，AVN
15、, (VN VT)*v3型文法：A aB或A a，A, BVN ,a VTv短语文法、上下文有关文法、上下文无关文法、正规文法4.2 语言和文法 v例 L3anbncn|n 1的上下文有关文法S aSBCS aBCCBBCaB abbB bbbC bccC ccanbncn的推导过程如下：S *an-1S(BC)n1用S aSBC n-1次S +an(BC)n用S aBC 1次S +anBnCn 用CBBC交换相邻的CBS +anbBn1Cn 用aBab1次S +anbnCn用bB bb n-1次S +anbncCn-1用bC bc 1次S +anbncn 用cCcc n-1次4.3 自上而下
16、分析 4.3.1自上而下分析的一般方法v例 文法 S aCb C cd | c为输入串w=acb建立分析树SaCbSaCbcdSaCbc不能处理左递归4.3 自上而下分析v不能处理左递归的例子算术表达文法EE+T|TTTF |FF(E)|idEE+TE+TE+T 4.3 自上而下分析 4.3.1自上而下分析的一般方法v例 文法 S aCb C cd | c为输入串w=acb建立分析树SSSaCbaaCCbbcdc不能处理左递归、复杂的回溯技术4.3 自上而下分析 4.3.1自上而下分析的一般方法v例 文法 S aCb C cd | c为输入串w=acb建立分析树SSSaCbaaCCbbcdc不能处理左递归、复杂的回溯技术、回溯导致语义工作推倒重来4.3 自上而下分析 4.3.1自上而下分析的一般方法v例 文法 S aCb C cd | c为输入串w=acb建立分析树SSSaCbaaCCbbcdc不能处理左递归、复杂的回溯技术、回溯导致语义工作推倒重来、难以报告出错的确切位置4.3 自上而下分析 4.3.1自上而下分析的一般方法v例 文法 S aCb C cd | c为输入串w=acb建
