5_语法分析

第五章自顶向下语法分析5.1确定的自顶向下分析思想5.2LL（1）文法的判断5.3某些非LL(1)到LL（1）的等价变换5.4不确定的自顶向下分析思想5.5确定的自顶向下分析方法22功能：根据文法规则，从源程序单词符号串中识别出语法成分，并进行语法检查。基本任务：识别符号串S是否为某语法成分分析方法：自顶向下分析5.1确定的自顶向下分析思想3若ZS则SL(G[Z])否则SL(G[Z])+G[Z]存在主要问题:左递归问题回溯问题主要方法:•递归子程序法•LL分析法自顶向下分析算法的基本思想为：例1：若有文法G1[S]：S→pA|qBA→cAd|aB→dB|b输入串：w=pccadd#,’#’结束符。S=pA=pcAd=pccAdd=pccaddSpAcAdcAda例2：S→Ap|BqA→cA|aB→dB|b输入串：w=ccap#,’#’结束符。S=Ap=cAp=ccAp=ccap定义5.1设G[S]:FIRST(α)={a｜α=aβ，a∈ＶT,α,β∈Ｖ*}若αε，则ε∈FIRST(α)**例3：S→aA|dA→bAS|ε输入串：w=abd#S=aA=abAS=abS=abd定义2:设G[S]=(VT,VN,S,P)是上下文无关文法,A∈VN,S是开始符号,则FOLLOW(A)={a|S*μAβ，且a∈VT,a∈FIRST(β),μ∈VT*,β∈V+}–规定#∈FOLLOW(S)‘#’作为输入串的结束符(句子括号)定义3：给定上下文无关文法A→α，A∈Bn，αB*若αε，SELECT(A→α)=FIRST(α)若αε，SELECT(A→α)=（FIRST(α)–{ε}）∪FOLLOW(A)**定义4：一个LL(1)文无关文法的充要条件为：对每一个非终结符A的两个不同产生式，A→α，A→β满足：SELECT(A→α)∩SELECT(A→β)=Ф例：S→aAS|bA→bA|ε判断该文法是否为LL(1)文法？SELECT(S→aAS)={a}SELECT(S→b)={b}SELECT(A→bA)={b}SELECT(A→ε)={a,b}所以：SELECT(S→aAS)={a}∩SELECT(S→b)={b}=ФSELECT(A→bA)={b}∩SELECT(A→ε)={b}1010设α=X1X2...Xn,Xi∈VnVt求FIRST(α)=?首先求出组成α的每一个符号Xi的FIRST集合(1)若Xi∈Vt，则FIRST(Xi)={Xi}(2)若Xi∈Vn且Xi→a…..|ε，a∈Vt则FIRST(Xi)={a，ε}(Ⅰ)集合FIRST的算法5.2LL（1)文法的判别1111(3)若Xi∈Vn且Xi→Y1Y2…Yk，则按如下顺序计算FIRST(Xi)若FIRST(Xi)FIRST(Y1)–{ε}；若ε∈FIRST(Y1)则将FIRST(Y2)-{ε}加入FIRST(Xi)；若ε∈FIRST(Y1)ε∈FIRST(Y2)则将FIRST(Y3)-{ε}加入FIRST(Xi)........若ε∈FIRST(Yk-1)则将FIRST(Yk)-{ε}加入FIRST(Xi)若ε∈FIRST(Y1)～FIRST(Yk)则将ε加入FIRST(Xi)注意：要顺序往下做，一旦不满足条件，过程就要中断进行得到FIRST(Xi)，即可求出FIRST(α)。1212(Ⅱ)构造集合FOLLOW的算法(1)若S为识别符号,则把“#”加入FOLLOW(S)中(2)若A→αBβ(β≠ε),则把FIRST(β)-{ε}加入FOLLOW(B)(3)若A→αB或A→αBβ，且βε则把FOLLOW(A)加入FOLLOW(B)*注：FOLLOW集合中不能有ε设S,A,B∈Vn,算法：连续使用以下规则，直至FOLLOW集合不再扩大例：S→AB|bCA→b|εB→aD|εC→AD|bD→aS|c判断该文法是否为LL（1）的FIRSTFOLLOWSa,b,ε#Ab,ε#,a,cBa,ε#Ca,b,c#Da,c#Select（S→AB）={a,b,#}Select（S→bC）={b}Select(A→b)={b}Select(A→ε)={#,a,c}Select(B→aD)={a}Select(B→ε)={#}Select(C→AD)={a,b,c}Select(C→b)={b}Select(D→aS)={a}Select(D→c)={c}自顶向下分析方法的基本缺点：不能处理具有左递归性的文法自顶向下分析为什么不能处理左递归文法？文法G，存在A∈Vn，ifA==A…,则G为左递归文法+1．左递归文法：左递归文法回溯问题15151、消除直接左公共因子:1515i)已知A→α|αβ解：A→α(β|ε)A→αA’A’→β|εii)已知A→αβ1|αβ2|…|αβn解：A→α（β1|β2|…|βn）得：A→αA’A’→β1|β2|…|βn5.3某些非LL(1)到LL（1）的等价变换16162、将左递归规则改为右递归规则若：P→P|则可改写为：P→P’P’→P’|ε例2已知G[E]：E::=T*F|T/F|FT::=F|T*F|T/F解：左递归改为右递归得：E::=T*F|T/F|FT::=FT’T’::=*FT’|/FT’|ε1717例：文法G[s]为S→Qc|cQ→Rb|bR→Sa|a非终结符顺序重新排列R→Sa|aQ→Rb|bS→Qc|c该文法是无直接左递归，但有间接左递归SQcRbcSabc∴SSabc+1.检查规则R是否存在直接左递归R→Sa|a2.把R代入Q的有关选择，改写规则QQ→Sab|ab|b3.检查Q是否直接左递归4.把Q代入S的右部选择S→Sabc|abc|bc|c5.消除S的直接左递归S→(abc|bc|c)S’S’→abcS’|ε最后得到文法为:S→(abc|bc|c)S’S’→abcS’|εQ→Sab|ab|bR→Sa|a1818最后得到的文法:S→(abc|bc|c)S’S’→abcS’|εQ→Sab|ab|bR→Sa|a可以看出其中关于Q和R的规则是多余的规则∴经过压缩后S→abcS’|bcS’|cS’S’→abcS’|ε可以证明改写前后的文法是等价的应该指出,由于对非终结符的排序不同,最后得到的文法在形式上可能是不一样的,但是不难证明它们的等价.5.4不确定的自顶向下分析思想19191、由于相同左部的产生式的右部的FIRST的交集不为空而引起的回溯2、由于相同左部的产生式的右部能=ε的产生式，且该非终结符的FOLLOW集中含有其它产生式右部的FIRST。3、由于文法含有左递归*2．回溯问题2020什么是回溯?分析工作要部分地或全部地退回去重做叫回溯造成回溯的条件：文法中，对于某个非终结符号的规则其右部有多个选择，并根据所面临的输入符号不能准确的确定所要选择时，就可能出现回溯。回溯带来的问题：严重的效率低，只有在理论上的意义而无实际意义A::=1|2|32121效率低的原因1)语法分析要重做2)语法处理工作要推倒重来为避免回溯，对文法的要求是FIRST(αi)∩FIRST(αj)=φ(ij)**5.5.1递归子程序法（递归下降分析法）具体做法：对语法的每一个非终结符都编一个分析程序，根据文法和当时的输入符号预测到要用某个非终结符去匹配输入串时，就调用该非终结符的分析程序。下面我们可以通过举例说明如何根据文法构造该文法的语法分析程序5.5确定的自顶向下分析方法2323例：文法G[Z]Z→(A)|aAbA→dZ|Ad|e1.检查并改写文法Z→(A)|abA→dZA’|eA’A’→dA’|ε改写后无左递归且首符集不相交：{(}∩{a}=φ{d}∩{e}=φ2.检查文法的递归性因此，Z和A的分析程序要编成递归子程序Z¨·A¨·¨·Z¨·∴Z¨·Z¨·A¨·Z¨·¨·A¨·∴A¨·A¨·++递归子程序法对应的是最左推导过程24243.算法框图非终结符号的分析子程序功能是：用规则右部符号串去匹配输入串。以下是以框图形式给出的子程序:25入口(sYm)=‘(’读符号(sYm)=‘)’(sYm)=‘a’出口读符号AerrorerrorTTF读符号YA(sYm)=‘b’FFFTZ→(A)|aAbA→dZA’|eA’A’=dA’|ε.要注意子程序之间的接口,在程序编制时进入某个非终结符的分析程序时其所要分析的语法成分的第一个符号已读入sYm中.递归子程序法对应的是最左推导过程Z的子程序算法2626入口(sYm)=‘d’读符号A’(sYm)=‘e’ZerrorTF读符号YFZ→(A)|aAbA→dZA’|eA’A’=dA’|εA’A的子程序算法2727说明要注意子程序之间的接口,在程序编制时进入某个非终结符的分析程序时其所要分析的语法成分的第一个符号已读入sYm中.递归子程序法对应的是最左推导过程用递归子程序法构造语法分析程序的例子28例：文法G[E]E::=E+T|TT::=T*F|FF::=(E)|i请用自顶向下的方法分析是否字符串i+i*i∈L(G[E])。E::=TE’E’::=+TE’|εT::=FT’T’::=*FT’|εF::=(E)|i改写后的文法为:2929语法分析程序所要调用的子程序:nextsYm:词法分析程序,每调用一次读进一个单词,单词的类别码放在sYm中.error:出错处理程序.3030voidE(){T();E’();}voidE’(){ifsYm=‘+’{nextsYm;T();E’();}}voidT(){F();T’();}voidT’(){ifsYm=‘*’{nextsYm;F();T’();}}E::=TE’E’::=+TE’|εT::=FT’T’::=*FT’|εF::=(E)|ivoidF(){ifsYm=‘(’{nextsYm;E();ifsYm=‘)’nextsYm;else“error”;elseifsYm=‘i’nextsYm;else“error”;}5.5.2预测分析法3131LL－自左向右扫描、自左向右的分析和匹配输入串。分析过程表现为最左推导的性质。此过程有三部分组成:分析表执行程序(总控程序）符号栈（分析栈）#执行程序分析表#符号栈输入串在实际语言中，每一种语法成分都有确定的左右界符，为了研究问题方便，统一以‘＃’表示。1、LL分析程序构造及分析过程3232M[A,a]=A→αi表示当要用A去匹配输入串时，且当前输入符号为a时，可用A的第i个选择去匹配。即当αi≠ε时，有αia…;当αi＝ε时，则a为A的后继符号。*M[A,a]=error表示当用A去匹配输入串时，若当前输入符号为a，则不能匹配，表示无Aa…,或a不是A的后继符号.*（1）预测分析表：二维矩阵MA→αiαi∈B*M[A,a]=A∈Bnerrora∈Btor#3333（2）符号栈:有四种情况#E符号栈•开始状态E#xxxxxx#•工作状态#…..X符号栈X….#a……#查分析表得：X∈Bn,M[X,a]=X→αiXa…X∈Bn,X=a+3434•出错状态•结束状态#…..X符号栈X….#a……#查分析表得：X∈Bn,M[X,a]=error无Xa…X∈Bn,Xa+#符号栈##3535执行程序主要实现如下操作:1.把#和文法识别符号E推进栈,并读入输入串的第一个符a,重复下述过程直到正常结束或出错.2.测定栈顶符号X和当前输入符号a,执行如下操作:(1)若X=a=#，分析成功，停止。E匹配输入串成功.(2)若X=a≠#，把X推出栈，再读入下一个符号。(3)若X∈Bn，查分析表M（详细步骤见下页）（3）执行程序#…..X符号栈X….#a……#3636(3)若X∈Vn，查分析表M。a)M[X,a]=X→ABW则将X弹出栈，将ABW压入注：A在栈顶（最左推导）b)M[X,a]=error转出错处理c)M[X,a]=X::=ε---a为X的后继符号则将X弹出栈（不读下一符号）继续分析。#…..X#…..WBAX….#ABW….#3737分析表