第三语法分析.pptx

13.1 语法分析的若干问题语法分析器的两个重要作用：根据词法分析器提供的记号流，为语法正确的输入构造分析树（或语法树），这是本章重点，在以后各节中详细讨论；检查输入中的语法（可能包括词法）错误，并调用出错处理器进行适当处理，下边简单介绍语法错误处理的基本原则，而在以后的讨论中忽略此问题。第1页/共107页23.1 语法分析的若干问题语法错误的处理原则1.源程序中可能出现的错误两类：语法错误和语义错误词法错误如非法字符或拼写错关键字、标识符等intege20times语法错误指结构出错，如少分号、begin/end不配对等beginx:=a+by:=x;静态语义错误：如类型不一致、参数不匹配等a,b:integer;x:array1.10ofinteger;x:=a+b;动态语义错误(逻辑错误)：如死循环、除数为变量零等while(t).;a:=a/b;第2页/共107页33.1 语法分析的若干问题大多数错误的诊断和恢复集中在语法分析阶段。一个原因是大多数错误是语法错误，另一个原因是语法分析方法的准确性，它们能以非常有效的方法诊断语法错误。编译时想要准确诊断语义或逻辑错误有时是很困难的。2.语法错误处理的目标对语法错误的处理，一般希望达到以下基本目标：清楚而准确地报告错误的出现，地点正确、不漏报、不错报也不多报；迅速地从每个错误中恢复过来（以便分析继续进行）；不应使对语法正确的源程序的分析速度降低太多。第3页/共107页43.1 语法分析的若干问题3.语法错误的基本恢复策略紧急方式恢复：抛弃若干输入，直到遇到同步记号。短语级恢复：采用串替换的方式对剩余输入进行局部纠正（抛弃插入）。出错产生式：用出错产生式捕捉错误（预测错误）。预置型的短语级恢复方式。全局纠正：对错误输入序列x，找相近序列y，使得x变换成y所需的修改、插入、删除次数最少。第4页/共107页53.1 语法分析的若干问题例3.1下述两条是有语法错误的语句，其中第一条赋值句结束时忘记加分号，采用紧急恢复方式和短语级恢复方式的可能结果分别如下所示。x:=a+by:=c+d;紧急方式：x:=a+b+d;-丢弃b后若干记号，直到遇到+短语级恢复：x:=a+b;-加入分号，使之成为一个赋值句y:=c+d;第5页/共107页63.2 上下文无关文法(CFG)CFG的定义与表示上下文无关文法，ContextFreeGrammar，CFG定义3.1CFG是一个四元组：G=（N，T，P，S），其中（1）N是非终结符（Nonterminals）的有限集合；（2）T是终结符（Terminals）的有限集合，且NT=；（3）P是产生式（Productions）的有限集合，形如：A，其中AN（左部），(NT)*（右部），若=，则称A为空产生式（也可以记为A）；（4）S是非终结符，称为文法的开始符号（Startsymbol）。第6页/共107页73.2 上下文无关文法(CFG)例3.2简单算术表达式的上下文无关文法可表示如下：N=E T=+，*，(，)，-，idS=EP:EE+E（1）EE*E（2）E（E）（3）(G3.1)E-E（4）Eid（5）1.产生式的一般读法记号读作“定义为”或者“可导出”。“EE+E”表述为“算术表达式定义为两个算术表达式相加”；或者“一个算术表达式加上另一个算术表达式，仍然是一个算术表达式”。第7页/共107页83.2 上下文无关文法(CFG)2.由产生式集表示CFG前提：若文法正确结论：文法开始符号S是第一个产生式的左部；N是可以出现在产生式左边符号的记号集合；T是绝不出现在产生式左边符号的记号集合；P:EE+E（1）EE*E（2）E（E）（3）E-E（4）Eid（5）产生式表示也被称为巴克斯范式（Backus-NaurForm，BNF），其中用:=表示S=EN=ET=+，*，(，)，-，id第8页/共107页93.2 上下文无关文法(CFG)3.终结符与非终结符书写上的区分(a)用大小写区分：Eid(b)用区分：EidEE+E(c)用区分：+教材约定：大写英文字母A、B、C表示非终结符；小写英文字母a、b、c表示终结符；小写希腊字母、表示任意文法符号序列第9页/共107页103.2 上下文无关文法(CFG)4.产生式的缩写形式当多个产生式的左部非终结符相同时，可合并为一个产生式。新的产生式的左部是此非终结符，右部是所有原来右部的或运算（并集合）。例3.3G3.1可以重写为如下形式：E E+E（1）|E*E（2）|（E）（3）(G3.2)|-E（4）|id（5）用“|”连接的每个右部称为一个候选项，具有平等的权利。BNF如何表示？P:E E+E(1)E E*E(2)E (E)(3)E -E(4)E id(5)第10页/共107页113.2 上下文无关文法(CFG)CFG产生语言的基本方法推导CFG（产生式）通过推导的方法产生语言。通俗地讲，产生式产生语言的过程是从开始符号S开始，对产生式左部的非终结符反复地使用产生式：将产生式左部的非终结符替换为右部的文法符号序列（展开产生式，用标记=表示），直到得到一个终结符序列。例3.4用(G3.2)产生终结符序列-(id+id)可如下：EE+E（1）|E*E（2）|（E）（3）(G3.2)|-E（4）|id（5）E=-E by(4)=-(E)by(3)=-(E+E)by(1)=-(id+E)by(5)=-(id+id)by(5)第11页/共107页123.2 上下文无关文法(CFG)定义3.2利用产生式产生句子的过程中，将产生式A的右部代替文法符号序列A中的A得到的过程，称A直接推导出，记作：A=。若对于任意文法符号序列1，2，.n，均有1=2=.=n，则称此过程为零步或多步推导，记为：1=*n，其中1=n的情况为零步推导。若1n，即推导过程中至少使用一次产生式，则称此过程为至少一步推导，记为：1=+n。两点注意：，有=*，即推导具有自反性；若=*，=*，则=*，即推导具有传递性。第12页/共107页133.2 上下文无关文法(CFG)定义3.3由CFGG所产生的语言L(G)被定义为:L(G)=S=+andT*，L(G)称为上下文无关语言(ContextFreeLanguage,CFL)，称为句子。若S=*，(NT)*，则称为G的一个句型。定义3.4在推导过程中，若每次直接推导均替换句型中最左边的非终结符，则称为最左推导，由最左推导产生的句型被称为左句型。类似可定义最右推导与右句型，最右推导也被称为规范推导。E=-E=-(E)=-(E+E)=-(id+E)=-(id+id)1234566是句子，所有i(i=1.6)均是句型。第13页/共107页14上次课总结语法分析器作用语法错误处理CFG的定义与表示推导(最左、最右推导)、句子、句型第14页/共107页153.2 上下文无关文法(CFG)推导、分析树与语法树E=-E=-(E)=-(E+E)=-(id+E)=-(id+id)推导产生句子的方式不直观。分析树是推导的图形直观表示，同时反映语言结构的实质和推导过程。定义3.5 对CFG G的句型，分析树被定义为具有下述性质的一棵树。（1）根由开始符号所标记；（2）每个叶子由一个终结符、非终结符、或标记；（3）每个内部结点由一个非终结符标记；（4）若A是某内部节点的标记，且X1，X2，.，Xn是该节点从左到右所有孩子的标记，则AX1X2.Xn是一个产生式。若A，则标记为A的结点可以仅有一个标记为的孩子。第15页/共107页163.2 上下文无关文法(CFG)分析树与语言和文法的关系：每一直接推导(每个产生式)，对应一棵仅有父子关系的子树，即产生式左部非终结符“长出”右部的孩子；分析树的叶子，从左到右构成G的一个句型。若叶子仅由终结符标记，则构成一个句子。例3.5再考察-(id+id)的推导过程。E=-E=-(E)=-(E+E)=-(id+E)=-(id+id)最左推导和最右推导的中间过程对应的分析树可能不同，但最终的分析树相同，因为最终是同一个句子第16页/共107页173.2 上下文无关文法(CFG)分析树既反映了产生句型的推导过程，又反映了句型的结构。在更多的情况下，仅关注句型结构，而忽略推导过程。定义3.6对CFGG的句型，表达式的语法树被定义为具有下述性质的一棵树:（1）根与内部节点由表达式中的操作符标记；（2）叶子由表达式中的操作数标记；（3）用于改变运算优先级和结合性的括弧，被隐含在语法树的结构中。语法树与分析树的最根本区别在于内部节点（包括根节点）：分析树的内部节点是非终结符；语法树的内部节点是操作符（运算符）；或者说语法树中省略了反映分析过程的非终结符。第17页/共107页183.2 上下文无关文法(CFG)例3.6句子-(id+id)和句型ifCthens1elses2分析树：左部非终结符“产生”右部文法符号序列；语法树：操作符(运算)作用于操作数(运算对象)；习惯上它们分别被称为具体语法树和抽象语法树。第18页/共107页193.2 上下文无关文法(CFG)二义性与二义性的消除二义性问题：一个句子可能对应多于一棵分析树例3.7文法G3.2为EE+E|E*E|（E）|-E|id句子id+id*id和id+id+id可能的分析树有：第19页/共107页203.2 上下文无关文法(CFG)定义3.7若文法G对同一句子产生不止一棵分析树，则称G是二义的。原因：在产生句子的过程中某些直接推导有多于一种选择注意：1.一个句子有多于一棵分析树，仅与文法和句子有关，与采用的推导方法无关；2.文法中缺少对文法符号优先级和结合性的规定。“悬空（dangling）else”问题S ifCthenS(1)|ifCthenSelseS(2)|id:=E(3)(G3.3)CE=E|EE(4).(6)EE+E|-E|id|n(7).(10)第20页/共107页213.2 上下文无关文法(CFG)例3.8条件语句ifx0thenx:=5elsex:=-5if x0 then x:=5 else x:=-5else与离它远的then匹配if x0 then x:=5 else x:=-5else与离它近的then匹配第21页/共107页223.2 上下文无关文法(CFG)文法二义不能说明它所产生的语言一定是二义的。消除语言二义有两种方法：改写二义文法为非二义文法；规定二义文法中符号的优先级和结合性。改写例3.9与G3.2等价的非二义文法：EE+T|TTT*F|F(G3.4)F（E）|-F|id问题：如何改写？EE+E|E*E|（E）(G3.2)|-E|id第22页/共107页233.2 上下文无关文法(CFG)观察结论：新引入的非终结符限制每一步直接推导均有唯一选择；最终分析树的形状，仅与文法有关，而与推导方法无关；非终结符的引入，增加了推导步骤(分析树增高)；越接近S的文法符号的优先级越低。(如EE+T)对于AA，若A在终结符左边出现(即终结符在中)，则A产生式具有左结合性质。改写二义文法的关键步骤：1.引入新的非终结符，增加一个子结构并提高一级优先级；2.递归非终结符在终结符左边，运算具有左结合性，否则具有右结合性。第23页/共107页243.2 上下文无关文法(CFG)例3.10改写二义文法G3.2为G3.4：引入新的非终结符，增加一个子结构并提高一级优先级；递归非终结符在终结符左边，运算具有左结合性，否则具有右结合性。1.优先级：+*(),-,id2.结合性：左结合+,*右结合-无结合id3.非终结符与运算：E:+（E产生式，左递归）T:*（T产生式，左递归）F:-,(),id（F产生式，右递归）E E+E(1)|E*E(2)|（E）(3)|-E(4)|id(5)E E+T|TT T*F|FF (E)|-F|id第24页/共107页253.2 上下文无关文法(CFG)“悬空else”问题：在复合if语句中，可能then多于else，使得else不知与哪个then结合。一般原则是右结合，即else与左边最靠近的then结合。改写文法的根据是将S分为完全匹配(MS)和不完全匹配(UMS)两类，并且在UMS中规定else右结合。SMS(1)|UMS(2)MSifCthenMSelseMS(3)|id:=E(4)UMSifCthenS(5)|ifCthenMSelseUMS(6)CE=E|EE(7).(9)EE+T|T(10).(11)T(E)|-T|id|n(12).(15)S if C then S|if C then S else S|id:=EC E=E|EEE E+E|-E|id|n第25页/共107页263.2 上下文无关文法(CFG)SMS|UMS(1).(2)MSifCthenMSelseMS|id:=E(3).(4)UMSifCthenS|ifCthenMSelseUMS(5).(6)(G3.5)CE=E|EE(7).(9)EE+T|T(10).(11)T（E）|-T|id|n(12).(15)if x0 then x:=5 else x:=-5第26页/共107页273.2 上下文无关文法(CFG)SMS|UMS(1).(2)MSifCthenMSelseMS|id:=E(3).(4)UMSifCthenS|ifCthenMSelseUMS(5).(6)(G3.5)CE=E|EE(7).(9)EE+T|T(10).(11)T（E）|-T|id|n(12).(15)if x0 then x:=5 else x:=-5第27页/共107页283.2 上下文无关文法(CFG)规定优先级和结合性二义文法的优点：1.比非二义文法容易理解；2.分析效率高(分析树低，直接推导步骤少)。YACC为二义文法规定优先级和结合性：%left+%left*%right-EE+E|E*E|（E）|-E|idE E+T|TT T*F|FF (E)|-F|id第28页/共107页293.2 上下文无关文法(CFG)修改语言的语法1.明确给出结束标志，如Ada中用endif，于是有：ifx0thenx:=5;endif;elsex:=-5;endif;ifx0thenx:=5;elsex:=-5;endif;endif;if x0thenx:=5;endif;elsex:=-5;endif;2.给表达式加括号，如Pascal中逻辑和算术运算：(a+b)(c*d)if x0then x:=5;else x:=-5;end if;end if;第29页/共107页303.3 语言与文法简介文法的重要作用：1.给出精确、易于理解的语言结构说明；2.以文法为基础的语言，便于加入新的、或修改、删除旧的语言结构；3.有些类别的文法，可以自动生成高效的分析器。本节从理论的角度对文法进行简单地讨论。讨论建立在形式语言与自动机的理论之上，且仅引用结论而忽略数学的证明，有兴趣的同学可以参阅相关文献。希望通过本节的讨论，对文法的分类和它们在编译器构造中的作用有一定的了解，同时初步窥探计算机科学的理论基础。第30页/共107页313.3 语言与文法简介正规式与上下文无关文法1.正规式到CFG的转换推论3.1正规式描述的语言结构均可用CFG描述，反之不一定从正规式到CFG的对应关系：构造正规式的NFA；若0为初态，则A0为开始符号；对于move(i,a)=j，引入产生式AiaAj；对于move(i,)=j，引入产生式AiAj；若i是终态，则引入产生式Ai。例3.11从正规式r=(a|b)*abb的NFA构造CFG：A0aA0|bA0|aA1A1bA2A2bA3A3经验的方法：A HTH|Ha|HbT abb第31页/共107页323.3 语言与文法简介2.为什么用正规式而不用CFG描述词法？词法规则简单，用正规式描述已足够；正规式的表示比CFG更直观、简洁、易于理解；有限自动机的构造比下推自动机简单，且分析效率高；区分词法和语法，为编译器前端的模块划分提供方便。贯穿词法分析和语法分析始终的思想：语言的描述和语言的识别是表示一个语言的两个不同侧面，二者缺一不可；（语言、文法、自动机）用正规式和CFG描述的语言，对应的识别方法（自动机）不同；正规式适合描述线性结构，如标识符、关键字、注释等；CFG适合描述具有嵌套（层次）性质的非线性结构，如不同结构的句子if-then-else、while-do等。第32页/共107页333.3 语言与文法简介上下文有关语言ContextSensitiveLanguage,CSL程序设计语言中除了CFG可以描述的结构之外，还有一些是CFG无法描述的所谓上下文有关的结构。典型的这类语言结构包括：变量的声明与引用、过程调用时形参与实参的一致性检查等。描述它们的文法被称为上下文有关文法（ContextSensitiveGrammar,CSG）。第33页/共107页343.3 语言与文法简介例3.12不能用CFG描述的语言：L1=c|(a|b)*(标识符声明与引用一致性的抽象)L2=anbmcndm|n1和m1(形参与实参一致性的抽象)L3=anbncn|n1(计数问题的抽象)相近的CFL：L1=cr|(a|b)*L2=anbmcmdn|n1,m1L2=anbncmdm|n1,m1L3=ambmcn|m,n1SaSa|bSb|cSaSd|aAd AbAc|bcSAB AaAb|ab BcBd|cdAAC AaAb|ab CcC|c第34页/共107页35上次课总结分析树语法树二义性与二义性的消除原因：文法符号缺乏优先级和结合性消除方法改写二义文法为非二义文法为文法符号规定优先级和结合性改变语言的结构或书写方式正规式到CFG的转换上下文有关语言第35页/共107页363.3 语言与文法简介计数问题L3=anbncn|n1CSLL3=ambmcn|m,n1CFLL3=akbmcn|k，m，n1正规集命题：L3不是正规集，因为构造不出可以识别L3的DFA。证明：（反证）假设L3是正规集，则可构造n个状态的DFAD，它接受L3；考察D读完，a，aa，.，an，分别到达S0，S1，.，Sn，共有n+1个状态。根据鸽巢原理，序列中至少有两个状态相同，设Si=Sj（ji），因为aibickL3，所以存在路径aibick。但是D中也有路径ajbick，矛盾。故L3不是正规集。AAC AaAb|ab CcC|ca+b+c+S0SiSkfaibickaj-i第36页/共107页373.3 语言与文法简介形式语言与自动机简介定义3.8若文法G=(N，T，P，S)的每个产生式中，均有(NT)*，且至少含有一个非终结符，(NT)*，则称G为0型文法。对0型文法施加以下第i条限制，即得到i型文法。1.G的任何产生式（S除外）满足|；2.G的任何产生式形如A，其中AN，(NT)*；3.G的任何产生式形如Aa或者AaB(或者ABa)，其中A和BN，aT。文文 法法语语 言言自自 动动 机机短语文法(0型)短语结构语言图灵机CSG(1型)CSL线性界线自动机CFG(2型)CFL下推自动机正规文法(3型)正规集有限自动机第37页/共107页383.3 语言与文法简介再考察L3：L3=anbncn|n1例3.15L3可用下述CSG描述：SaSBC(1)SaBC(2)CBBC(3)aBab(4)bBbb(5)bCbc(6)cCcc(7)CSG、CFG、正规式能力递减，但是能力越强的文法，其文法设计和自动机的构造越困难，因此语法分析仅用到CFG（除特别指出，文法即指CFG）句子akbkck 的推导：S=.=ak-1S(BC)k-1(by 1)=ak(BC)k(by 2)=.=akBkCk(by 3)=akbBk-1Ck(by 4)=.=akbkCk(by 5)=akbkcCk-1(by 6)=.=akbkck(by 7)第38页/共107页393.4 自上而下语法分析自上而下分析的一般方法用推导的方法分析输入序列：对输入序列，从S开始进行最左推导，直到得到一个合法句子或非法结构；从左到右扫描输入序列，试图用一切可能的方法，自上而下建立它的分析树；一种试探的过程，反复使用不同产生式，谋求与输入序列匹配；例3.16用下述文法分析输入序列=cad：S cAdA ab|a第39页/共107页403.4 自上而下语法分析问题：若有A1|2，公共左因子，则会虚假匹配和大量回溯；造成分析效率低、语义动作难以恢复、以及出错位置的报告不确切等。若有AA，左递归，则死循环使分析无法进行下去。重写文法：消除左递归，以避免陷入死循环；提取左因子，以避免回溯。消除左递归定义3.9若文法G中的非终结符A，对某个文法符号序列存在推导A=+A，则称G是左递归的。若G中有形如AA的产生式，则称该产生式对A直接左递归。第40页/共107页413.4 自上而下语法分析1.消除文法的直接左递归考虑：AA|产生的语言：*替换为：AAAA|消除了一个直接左递归算法3.1消除直接左递归输入G中所有的A产生式(含直接左递归)输出等价的不含直接左递归的G方法首先，整理A产生式为如下形式：AA1|A2|.|Am|1|2|.|n其中i非空，j均不以A开始。用下述产生式代替A产生式A1A|2A|.|nAA1A|2A|.|mA|若i为空，则形成一个有环的A产生式第41页/共107页423.4 自上而下语法分析例3.17消除算术表达式文法的直接左递归：EE+E|E*E|(E)|-E|id(G3.2)E TE(1)E+TE|(2)T FT(3)(G3.4)T*FT|(4)F(E)|-F|id(5).(7)EE+T|TTT*F|F (G3.4)F(E)|-F|id第42页/共107页433.4 自上而下语法分析2.消除文法的左递归算法3.2消除左递归输入无回路文法G输出无左递归的等价文法G方法将非终结符合理排序：A1，A2，.，An;for iin2.nloopforjin1.i-1loop用Aj1|2|.|k的右部替换每个形如AiAj产生式中的Aj,得到新产生式：Ai1|2|.|k;消除Ai产生式中的直接左递归;endloop;endloop;核心思想：将不是直接左递归的非终结符右部展开到其他产生式中注意：若G产生句子的过程中出现A=+A，则无法消除左递归第43页/共107页443.4 自上而下语法分析核心思想：将不是直接左递归的符号右部展开到其他产生式关键步骤：合理排序非终结符：A1，A2，.，An;用Aj1|2|.|k右部替换AiAj中的Aj，得到Ai1|2|.|k；消除Ai产生式中的直接左递归；例3.18用算法3.2消除文法SAa|bAAc|Sd|中的左递归。将S的右部展开在A中，得到：AAc|Aad|bd|消除新产生式中的直接左递归，得到：SAa|bAbdA|A(G3.8)AcA|adA|第44页/共107页453.4 自上而下语法分析3.提取左因子ScAdAab|a当不确定用A产生式的哪个候选项替换A时，可以重写A产生式来推迟这种决定，直到看见足够的输入，能正确决定所需选择为止。这一过程被称为提取左因子，它类似于有限自动机的确定化。将：A1|2替换为：AAA1|2等价于：A(1|2)第45页/共107页463.4 自上而下语法分析算法3.3提取文法的左因子输入文法G输出等价的无左因子文法G方法重复过程，直到所有A产生式候选项中不再有公共前缀：重排A产生式：A1|2|.|n|；并用AA|和A1|2|.|n取代原A产生式。例3.20考察悬空else文法：SiCtS|iCtSeS|aCb用算法3.3提取左因子，得到如下文法：SiCtSS|aSeS|Cb既有左递归又含左因子？先消除左递归。第46页/共107页473.4 自上而下语法分析4.递归下降分析直接以程序的方式模拟产生式产生语言的过程；每个产生式对应一个子程序，产生式右边的非终结符对应子程序调用，终结符则与输入序列匹配；它对文法的限制是不能有公共左因子和左递归；它是一种非形式化的方法，只要能写出子程序，用什么样的方法和步骤均可。一种稳妥的方法构造文法的状态转换图并且化简；将转换图转化为EBNF表示；从EBNF构造子程序。第47页/共107页483.4 自上而下语法分析1.构造状态转换图且化简递归下降分析的文法：LE;L|EE+T|E-T|TTT*F|T/F|TmodF|FF(E)|id|num每个非终结符对应一个状态转换图：为非终结符A建立一个初态和一个终态；为AX1X2.Xn构造从初态到终态的路径，边标记为X1，X2，.，Xn。根据识别同一集合的原则，化简转换图。消除左递归后的等价文法:L E;L|E T E E+T E|-T E|T F T T*F T|/F T|mod F T|F (E)|id|num第48页/共107页493.4 自上而下语法分析L E;L|E T EE+T E|-T E|T F TT*F T|/F T|mod F T|F (E)|id|num第49页/共107页503.4 自上而下语法分析状态图的化简原则 标记为A的边可等价为标记的边转向A转换图的初态；边连接的两个状态可以合并（FA的确定化思想）；标记相同的路径可以合并；不可区分的状态可以合并（DFA的最小化思想）。第50页/共107页513.4 自上而下语法分析2.文法的扩展BNF（EBNF）表示：重复0或若干次（while）：可选择（if或while）|：括弧()之内的或关系（case）()：改变运算的优先级和结合性EBNF表示：LE;ET(+|-)TTF(*|/|mod)FF(E)|id|num第51页/共107页523.4 自上而下语法分析3.递归下降子程序procedureLisbeginlookahead:=lexan;while(lookahead/=eof)loopE;match(;);endloop;endL;procedureEisbeginT;whilelookahead(+|-)loopmatch(lookahead);T;endloop;endE;procedure F isbegin case lookahead is (:match();E;match();id :match(id);num:match(num);others:error(syntax error2);end case;end F;L E;E T (+|-)T T F (*|/|mod)F F (E)|id|num 第52页/共107页533.4 自上而下语法分析如果不消除左递归：若存在产生式EE+id，则E的递归下降子程序如下：procedureEisbeginE;match(+);-永不执行match(id);-永不执行endE;此程序永不停机。同样，文法中的公共左因子也会给递归下降分析造成困难。第53页/共107页543.4 自上而下语法分析形式语言与自动机简介自上而下分析：自上而下/从左到右(不能有左递归/左因子)消除左递归提取左因子递归下降分析第54页/共107页553.4 自上而下语法分析预测分析器非递归预测分析器的工作模式预测分析器的核心概念：1.分析方法：格局与格局变换2.分析表+驱动器（模拟算法）3.预测分析表的构造4.LL（文法、语言、分析器）第55页/共107页563.4 自上而下语法分析1.预测分析表LE;L|ETEE+TE|-TE|TFTT*FT|/FT|modFT|F(E)|id|num分析表MA,a的内容：若当前栈顶是非终结符A，下一输入终结符是a，则MA,a指示下一步动作。idnum+-*/mod();#LE;LE;LE;LETETETEE+TE-TETFTFTFTT*FT/FT mod FTFidnum(E)第56页/共107页573.4 自上而下语法分析2.工作方式放幻灯的方式：每张“幻灯片”称为一个格局。从初始格局开始，经过格局变化，最终到达接收格局，表明分析成功；或者到达出错格局，表明发现语法错误。格局：三元组，(栈内容top，剩余输入ip，改变格局的动作)改变格局的动作：匹配终结符：若top=ip(但#)，则pop且next(ip)；展开非终结符：若top=X且MX,a=(X)，则pop且push()；报告分析成功：若top=ip=#，则分析成功并结束；报告出错：其它情况，调用错误恢复例程。第57页/共107页583.驱动器算法算法3.4非递归的预测分析输入输入序列和文法G的预测分析表M输出若L(G)，得到的一个最左推导；否则指出一个错误方法初始格局为:（#S，#，分析器的第一个动作）令ip指向#中的第一个终结符，top指向S;loopx:=top;a:=ip;ifxTthenifx=athenpop(x);next(ip);-匹配终结符elseerror(1);endif;-出错：栈顶终结符不是aelseifMx,a=XY1Y2.Ykthenpop(X);push(YkYk-1.Y2Y1);-展开非终结符elseerror(2);endif;-出错：产生式不匹配endif;exitwhenx=#;-分析成功endloop;第58页/共107页594.用预测分析器分析句子栈当前剩余输入动作含义#Lid+id*id;#pop(L),push(E;L)(LE;L)#L;Eid+id*id;#pop(E),push(TE)(ETE)#L;ETid+id*id;#pop(T),push(FT)(TFT)#L;ETFid+id*id;#pop(F),push(id)(Fid)#L;ETidid+id*id;#pop(id),next(ip)id#L;ET+id*id;#pop(T)(T)#L;E+id*id;#pop(E),push(+TE)(E+TE)#L;ET+id*id;#pop(+),next(ip)+#L;ETid*id;#pop(T),push(FT)(TFT)#L;ETFid*id;#pop(F),push(id)(Fid)#L;ETidid*id;#pop(id),next(ip)id#L;ET*id;#pop(T),push(*FT)(T*FT)#L;ETF*id;#pop(*),next(ip)*#L;ETFid;#pop(F),push(id)(Fid)#L;ETidid;#pop(id),next(ip)id#L;ET;#pop(T)(T)#L;E;#pop(E)(E)#L;#pop(;),next(ip);#L#pop(L)(L)#正确结束第59页/共107页60上次课总结预测分析器下推自动机符号栈、分析表、驱动器格局与格局的变换第60页/共107页613.4 自上而下语法分析构造预测分析表1.首先构造FIRST集合与FOLLOW集合；2.然后根据两个集合构造预测分析表。定义3.10文法符号序列的FIRST集合为:FIRST()=a|=*a.，aT，若=*，则FIRST()定义3.11非终结符A的FOLLOW集合如下:FOLLOW(A)=a|S=*.Aa.，aT，若A是某句型的最右符号，则#FOLLOW(A)。通俗地讲，的FIRST集合就是从开始可导出的文法符号序列中的开头终结符。而A的FOLLOW集合，就是从开始符号可以导出的所有含A的文法符号序列中A之后的终结符。例如：FIRST(E)=(，id,num，FOLLOW(E)=)，;L E;L|E TEE+T E|-T E|T FTT*F T|/FT|mod FT|F(E)|id|num 第61页/共107页623.4 自上而下语法分析算法3.5计算X的FIRST集合输入文法符号X输出X的FIRST集合方法应用下述规则：若XT，则FIRST(X)=X；若X是非终结符且有X，则加入到FIRST(X)；若X是非终结符且有XY1Y2.Yk，并设Y0=，Yk+1=。那么对所有j(0jk)，若aFIRST(Yj+1)且FIRST(Yj),则加入a到FIRST(X)。FIRST(X1X2.Xn)的计算方法与算法3.5中步骤3类似，即是所有FIRST(Xi)(i=1,2,.,k)的并集，其中k为第一个具有性质不属于FIRST(Xk)或kn的文法符号，若kn，则FIRST(X1X2.Xn)考虑：FIRST(E)=FIRST(TE)=FIRST(FTE)=(，id,numL E;L|E TEE+T E|-T E|T FTT*F T|/FT|mod FT|F(E)|id|num 第62页/共107页633.4 自上而下语法分析算法3.6计算所有非终结符的FOLLOW集合输入文法G输出G中所有非终结符的FOLLOW集合方法应用下述规则:加入#到FOLLOW(S)，其中S是开始符号，#是输入结束标记若有产生式AB，则除外，FIRST()的全体加入到FOLLOW(B)。若有产生式AB或AB而FIRST()，则FOLLOW(A)的全体加入到FOLLOW(B)。步骤3的理解：若 S=*Aaa紧跟A之后则=*Baa也紧跟B之后因为FIRST()使得B成为A产生式右部最右的文法符号即对任何aFOLLOW(A)，均有aFOLLOW(B)，反之不然。第63页/共107页643.4 自上而下语法分析例3.22计算非终结符的FIRST与FOLLOW。提示：自下而上计算FIRST，自上而下计算FOLLOWFIRST(F)=(idnumFIRST(T)=*/modFIRST(T)=FIRST(F)=(idnumFIRST(E)=+-FIRST(E)=FIRST(T)=FIRST(F)=(idnumFIRST(L)=FIRST(E)=(idnumFOLLOW(L)=#FOLLOW(E)=);FOLLOW(E)=);FOLLOW(T)=+-;)FOLLOW(T)=+-;)FOLLOW(F)=+-*/mod);L E;L|E TEE+T E|-T E|T FTT*F T|/FT|mod FT|F(E)|id|num 第64页/共107页653.4 自上而下语法分析算法3.7构造预测分析表输入文法G输出分析表M方法应用下述规则对文法的每个产生式A，执行2和3；对FIRST()的每个终结符a，加入到MA，a；若FIRST()，则FOLLOW(A)每个终结符b（包括#），加入到MA，b；M中其它没有定义的条目均是error。MA，a指导下一步动作：1.若当前栈顶为A，当前输入为a，则规则2表示下一步动作是展开A，因为aFIRST()，展开后下一次正好匹配a。2.若当前栈顶为A，当前输入为b且bFOLLOW(A)，则规则3表示下一步动作是展开A，即栈顶弹出A，继续分析A之后的部分，因为bFOLLOW(A)，弹出A后下一次正好匹配A的后继b第65页/共107页663.4 自上而下语法分析FIRST(F/T/E)=(idnumFIRST(T)=*/modFIRST(E)=+-FIRST(L)=(idnumFOLLOW(L)=#FOLLOW(E/E)=);FOLLOW(T/T)=+-;)FOLLOW(F)=+-*/mod);idnum+-*/mod();#LEETTF对FIRST()的每个终结符a，加入到MA，a；若FIRST()，则FOLLOW(A)每个终结符b(包括#)，加入到MA，b；E;LE;LE;LTETETE+TE-TEFTFTFT*FT/FTmod FTidnum(E)L E;L|E TEE+T E|-T E|T FTT*F T|/FT|mod FT|F(E)|id|num 第66页/共107页673.4 自上而下语法分析LL(1)文法MA,a的作用：指导产生式产生句子（指导推导）问题：是否分析表MA,a中都最多有一个条目？例3.23二义文法的预测分析表：文法：SiCtSS|aSeS|CbFIRST与FOLLOW集合：FIRST(C)=bFIRST(S)=,eFIRST(S)=i,aFOLLOW(S)=#,eFOLLOW(S)=#,eFOLLOW(C)=tabeit#SSCaiCtSSesb第67页/共107页683.4 自上而下语法分析定义3.12文法G被称为是LL(1)文法，当且仅当为它构造的预测分析表中不含多重定义的条目。由此分析表所组成的分析器被称为LL(