编译原理课件 - 西安电子科技大学个人主页系统 我的西电 …

1上次课内容回顾CFG的定义与表示推导(最左、最右推导)、句子、句型分析树，语法树词词词词词词词词词词词词词词词词词词词词词词词词词词词词词词词词词词词词词词词词词词词词23.2上下文无关文法(CFG)二义性的存在二义性问题：一个句子可能对应多于一棵分析树[例3.7]文法G3.2为E→E+E|E*E|（E）|-E|id句子id+id*id和id+id+id可能的分析树有：EE*EE+Eidid(a)先进行+运算idEE+EE+Eididid(c)+左结合(d)+右结合EE+EidE+Eidid(b)先进行*运算ididE+EE*EidE33.2上下文无关文法(CFG)消除语言二义有两种方法：①改写二义文法为非二义文法；②规定二义文法中符号的优先级和结合性。43.2上下文无关文法(CFG)①改写基本思想：通过引入新的非终结符，使原来分辨不清的结构受到约束，从而使得对任意一个句子，仅能构造一棵分析树。[例3.9]与G3.2等价的非二义文法：E→E+T|TT→T*F|F(G3.4)F→（E）|-F|idE→E+E|E*E|（E）(G3.2)|-E|id53.2上下文无关文法(CFG)[例3.9]与G3.2等价的非二义文法：E→E+T|TT→T*F|F(G3.4)F→（E）|-F|idEE+TTT*FFFididididEE+TE+TFTFidFidid+id*id（左右推导）id+id+id（左右推导）63.2上下文无关文法(CFG)观察结论：新引入的非终结符限制每一步直接推导均有唯一选择；最终分析树的形状，仅与文法有关，而与推导方法无关；推导仅改变分析树节点生成的顺序，文法才决定生什么样的节点。非终结符的引入，增加了推导步骤(分析树增高)，从而降低了分析的效率；7idEE+TE+TFTFidFidEE+EE+Eididid(c)+左结合(d)+右结合EE+EidE+EididEE*EE+Eidid(a)先进行+运算id(b)先进行*运算ididE+EE*EidEEE+TTT*FFFididid83.2上下文无关文法(CFG)观察结论：越接近S的文法符号的优先级越低。(+，*，（），-)E→E+T|TT→T*F|F(G3.4)F→（E）|-F|id93.2上下文无关文法(CFG)观察结论：对于A→αAβ（具有递归关系），若A在终结符左边出现(即终结符在β中)，则A产生式具有左结合性质。E→E+T若A在终结符右边出现(即终结符在α中)，则A产生式具有右结合性质。E→T+E103.2上下文无关文法(CFG)改写二义文法的关键步骤：1.引入新的非终结符，增加一个子结构并提高一级优先级；2.递归非终结符在终结符左边，运算具有左结合性，否则具有右结合性。113.2上下文无关文法(CFG)[例3.10]改写二义文法G3.2为G3.4：①引入新的非终结符，增加一个子结构并提高一级优先级；②递归非终结符在终结符左边，运算具有左结合性，否则具有右结合性。1.优先级：[+][*][(),-,id]2.结合性：左结合[+,*]右结合[-]无结合[id]3.非终结符与运算：E:+（左结合）T:*（左结合）F:-,(),id（右结合）E→E+E(1)|E*E(2)|（E）(3)|-E(4)|id(5)E→E+T|TT→T*F|FF→(E)|-F|id123.2上下文无关文法(CFG)“悬空else”问题：在复合if语句中，可能then多于else，使得else不知与哪个then结合。一般原则是右结合，即else与左边最靠近的then结合。改写文法的根据是将S分为完全匹配(MS)和不完全匹配(UMS)两类，并且在UMS中规定else右结合。S→MS(1)|UMS(2)MS→ifCthenMSelseMS(3)|id:=E(4)UMS→ifCthenS(5)|ifCthenMSelseUMS(6)C→E=E|EE|EE(7)...(9)E→E+T|T(10)...(11)T→(E)|-T|id|n(12)...(15)S→ifCthenS|ifCthenSelseS|id:=EC→E=E|EE|EEE→E+E|-E|id|n133.2上下文无关文法(CFG)S→MS|UMS(1)...(2)MS→ifCthenMSelseMS|id:=E(3)...(4)UMS→ifCthenS|ifCthenMSelseUMS(5)...(6)(G3.5)C→E=E|EE|EE(7)...(9)E→E+T|T(10)...(11)T→（E）|-T|id|n(12)...(15)ifx3thenifx0thenx:=5elsex:=-5UMSSifCthenSx3MSifCthenMSelseMSx0x:=5x:=-5143.2上下文无关文法(CFG)S→MS|UMS(1)...(2)MS→ifCthenMSelseMS|id:=E(3)...(4)UMS→ifCthenS|ifCthenMSelseUMS(5)...(6)(G3.5)C→E=E|EE|EE(7)...(9)E→E+T|T(10)...(11)T→（E）|-T|id|n(12)...(15)ifx3thenifx0thenx:=5elsex:=-5MSSifCthenMSelseMS?UMSSifCthenMSelseUMS?x3x3ifx3thenifx0thenx:=5elsex:=-5153.2上下文无关文法(CFG)②规定优先级和结合性二义文法的优点：1.比非二义文法容易理解；2.分析效率高(分析树低，直接推导步骤少)。YACC为二义文法规定优先级和结合性：%left'+'%left'*'%right'-'E→E+E|E*E|（E）|-E|idEE+TTT*FFFidididE→E+T|TT→T*F|FF→(E)|-F|idididE+EE*EidE163.2上下文无关文法(CFG)③修改语言的语法1.明确给出结束标志，如Ada中用endif，于是有：ifx3thenifx0thenx:=5;endif;elsex:=-5;endif;ifx3thenifx0thenx:=5;elsex:=-5;endif;endif;ifx3thenifx0thenx:=5;endif;elsex:=-5;endif;2.通过括号来表达优先级ifx3thenifx0thenx:=5;elsex:=-5;endif;endif;17InherentAmbiguityItwouldbeniceifforeveryambiguousgrammar,thereweresomewayto“fix”theambiguity,aswedidforthepreviousgrammar.Unfortunately,certainCFL’sareinherentlyambiguous,meaningthateverygrammarforthelanguageisambiguous.183.3语言与文法简介文法的重要作用：1.给出精确、易于理解的语言结构说明；2.以文法为基础的语言，便于加入新的、或修改、删除旧的语言结构；3.有些类别的文法，可以自动生成高效的分析器。本节从理论的角度对文法进行简单地讨论。讨论建立在形式语言与自动机的理论之上，且仅引用结论而忽略数学的证明，有兴趣的同学可以参阅相关文献。希望通过本节的讨论，对文法的分类和它们在编译器构造中的作用有一定的了解，同时初步窥探计算机科学的理论基础。193.3语言与文法简介正规式与上下文无关文法1.正规式到CFG的转换推论3.1正规式描述的语言结构均可用CFG描述，反之不一定从正规式到CFG的对应关系：①构造正规式的NFA；②若0为初态，则A0为开始符号；③对于move(i,a)=j，引入产生式Ai→aAj；④对于move(i,ε)=j，引入产生式Ai→Aj；⑤若i是终态，则引入产生式Ai→ε。[例3.11]从正规式r=(a|b)*abb的NFA构造CFG：A0→aA0|bA0|aA1A1→bA2A2→bA3A3→ε经验的方法：A→HTH→ε|aH|bHT→abb0123abbab203.3语言与文法简介2.为什么用正规式而不用CFG描述词法？①词法规则简单，用正规式描述已足够；②正规式的表示比CFG更直观、简洁、易于理解；③有限自动机的构造比下推自动机简单，且分析效率高；④区分词法和语法，为编译器前端的模块划分提供方便。贯穿词法分析和语法分析始终的思想：①语言的描述和语言的识别是表示一个语言的两个不同侧面，二者缺一不可；（语言、文法、自动机）②用正规式和CFG描述的语言，对应的识别方法（自动机）不同；③正规式适合描述线性结构，如标识符、关键字、注释等；CFG适合描述具有嵌套（层次）性质的非线性结构，如不同结构的句子if-then-else、while-do等。21内容总结二义性与二义性的消除原因：文法符号缺乏优先级和结合性消除方法①改写二义文法为非二义文法②为文法符号规定优先级和结合性③改变语言的结构或书写方式正规式到CFG的转换上下文有关语言22作业P136:3.5,3.6,3.7