西安电子科技大学《编译原理》.ppt

编译原理,西安电子科技大学软件工程研究所刘坚,3.4自上而下语法分析,对任何一个输入序列，从S开始进行最左推导，直到得到一个合法的句子或发现一个非法结构。在推导的过程中试图用一切可能的方法，自上而下、从左到右为输入序列建立分析树。分析是一种试探的过程，是反复使用不同产生式谋求与输入序列匹配的过程。,主要内容：自上而下分析对文法的限制预测分析方法递归下降子程序方法（结合上机作业）LL(1)：文法、语言、分析器,自上而下分析对文法的限制有哪些限制如何将一个不满足限制的文法改造为满足限制的文法,文法G产生句子的基本方法推导：从S开始反复用产生式的右部替换其左部（父亲长出儿子）分析树从左到右的叶子序列句型,用推导的方法分析输入序列（记号流）：,3,3.4.1自上而下分析对文法的限制,例3.20用下述文法分析输入序列=cad：,(G)：ScAdAab|a,问题：若有A1|2(公共左因子)，则会虚假匹配(回溯)；从而造成分析效率低、语义动作难以恢复、以及出错位置的报告不确切等。若有AA(左递归)，则死循环使分析无法进行下去。,重写文法：消除左递归，以避免陷入死循环；提取左因子，以避免回溯。,4,3.4.2消除左递归,消除文法的直接左递归考虑：AA|产生的语言：*替换为：AAAA|消除一个直接左递归（等价）,方法首先整理A产生式为如下形式：AA1|A2|.|Am|1|2|.|n其中i非空，j均不以A开始。,若i为空，则形成一个有环的A产生式,算法3.1消除直接左递归输入G中所有的A产生式(含直接左递归)输出等价的不含直接左递归的G,然后用下述产生式代替A产生式：A1A|2A|.|nAA1A|2A|.|mA|,5,消除文法的直接左递归(续1),例3.17用算法3.1消除算术表达式文法的直接左递归：,ETE(1)E+TE|(2)(G3.4)TFT(3)T*FT|(4)F(E)|-F|id(5).(7),EE+T|TTT*F|F(G3.4)F(E)|-F|id,替换：AA|为：AAAA|,关键：将实际文法符号对应到A、和具体到E产生式：E+T|TA,6,消除文法的直接左递归(续2),输入序列：id+id*id,改写的代价,EE+T|TTT*F|FF(E)|-F|id(G3.4),ETE(1)E+TE|(2)TFT(3)T*FT|(4)F(E)|-F|id(5).(7)(G3.4),结束,EE+E|E*E|(E)|-E|id(G3.2),7,消除文法的左递归,文法：SAa|bAAc|Sd|S是左递归的(但不是直接左递归)因为：S=Aa=Sda,核心思想：将不是直接左递归的非终结符右部展开到其他产生式中。,8,消除文法的左递归（续1）,例3.18用算法3.2消除文法(SAa|bAAc|Sd|)中的左递归。,核心思想：将不是直接左递归的非终结符右部展开到其他产生式,将S的右部展开在A中，得到：AAc|Aad|bd|消除新产生式中的直接左递归，得到：,SAa|bAbdA|A(G3.8)AcA|adA|,9,3.4.3提取左因子,当不确定用A产生式的哪个候选项替换A时，可以重写A产生式来推迟这种决定，直到看见足够的输入，能正确决定所需选择为止。这一过程被称为提取左因子，它类似于有限自动机的确定化。,公共前缀：A1|2,将：A1|2替换为：AAA1|2它等价于：A(1|2),ScAdAab|a,10,3.4.3提取左因子（续1）,算法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,11,课程小结,自上而下分析对文法的限制：不能有左递归和左因子消除左递归：左递归与直接左递归（定义3.9）基本公式（替换AA|为AAAA|）利用基本公式消除直接左递归（算法3.1）消除左递归（算法3.2）提取左因子：合并公共前缀（算法3.3）,特别提示：仅自上而下分析要求文法没有左递归和左因子；任何分析均要求文法无二义；消除文法二义性有两种方法：改写文法为等价的非二义文法规定文法符号的优先级与结合性，限制分析到唯一选择,结束,12,3.4.4预测分析器3.4.4.1预测分析器的工作模式,主要学习内容：1.分析方法：格局与格局变换2.分析器组成：预测分析表+驱动器（模拟算法）3.预测分析表的构造4.LL(1)：文法、语言、分析器,13,预测分析表,LE;L|ETEE+TE|-TE|TFTT*FT|/FT|modFT|F(E)|id|num,文法：,LE;L|EE+T|E-T|TTT*F|T/F|TmodF|FF(E)|id|num,MA,a的内容：若当前栈顶是非终结符A，下一输入终结符是a，则MA,a指示下一步动作。,分析表(MA,a)：,14,工作方式,放幻灯片：每张“幻灯片”称为一个格局。分析从某个初始格局开始，经过一系列的格局变化，最终到达接收格局，表明分析成功；或者到达出错格局，表明发现一个语法错误。,格局：格局是一个三元组（栈内容，当前剩余输入，改变格局的动作）topip,改变格局的动作：匹配终结符：若top=ip(但#)，则pop且next(ip)；展开非终结符：若top=X且MX,ip=(X)，则pop且push()；报告分析成功：若top=ip=#，则分析成功并结束；报告出错：其它情况，调用错误恢复例程。,15,驱动器算法,算法3.4非递归的预测分析输入输入序列和文法G的预测分析表M输出若L(G)，得到的一个最左推导；否则指出一个错误方法初始格局为:（#S，#，分析器的第一个动作）,格局：（top，ip，动作）,ifxTthenifx=athenpop(x);next(ip);-匹配终结符elseerror(1);-报错：栈顶终结符不是aendif;,elseifMx,a=XY1Y2.Ykthenpop(X);push(YkYk-1.Y2Y1);-展开产生式elseerror(2);-报错：产生式不匹配endif;,exitwhenx=#;-分析成功,16,用预测分析器分析:id+id*id;#,loopx:=top;a:=ip;ifxTthenifx=athenpop(x);next(ip);-匹配终结符elseerror(1);-报错：栈顶终结符不是aendif;elseifMx,a=XY1Y2.Ykthenpop(X);push(YkYk-1.Y2Y1);-展开产生式elseerror(2);-报错：产生式不匹配endif;endif;exitwhenx=#;-分析成功endloop;,17,id+id*id;#分析过程,栈当前剩余输入动作推导所用产生式#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)(F*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)#pop(#)next(ip)正确结束,18,本次内容：,下次内容：构造预测分析表递归下降子程序方法（结合上机作业）LL(1)：文法、语言、分析器,自上而下分析对文法的要求：消除左递归：基本公式与算法提取左因子：基本公式与算法预测分析方法：基本分析方法：格局与格局变换改变格局的四个动作：匹配、展开、接受、报错分析器的组成：预测分析表与模拟算法,结束,