自顶向下分析法实用教案

1、会计学1自顶向下分析法自顶向下分析法第一页，共57页。一一. .功能功能(gngn(gngnng)ng)第1页/共57页第二页，共57页。自上而下分析法：自上而下分析法：从文法的开始符号出发，寻找从文法的开始符号出发，寻找(xnzho)(xnzho)与输入符与输入符号串匹配的推导，或者说，为输入串寻找号串匹配的推导，或者说，为输入串寻找(xnzho)(xnzho)一个最左推导。一个最左推导。自下而上分析法：自下而上分析法：从输入符号串开始，逐步进行归约，直至归约到从输入符号串开始，逐步进行归约，直至归约到文法的开始符号。文法的开始符号。 第2页/共57页第三页，共57页。语法分析语法分析自上而

2、下分析自上而下分析自下而上分析自下而上分析确定的确定的不确定的不确定的算法优先分析法算法优先分析法递归下降子程序法递归下降子程序法预测分析法预测分析法LRLR分析法分析法第3页/共57页第四页，共57页。4.2.1 4.2.1 不确定不确定(qudng)(qudng)的自顶向下分析的自顶向下分析4.2.2 4.2.2 文法左递归和回溯的消除文法左递归和回溯的消除4.2.3 LL(1)4.2.3 LL(1)文法文法4.2.4 4.2.4 非非LL(1)LL(1)文法到文法到LL(1)LL(1)文法的等价变换文法的等价变换4.2.5 4.2.5 确定确定(qudng)(qudng)的自顶向下分析方

3、法的自顶向下分析方法第4页/共57页第五页，共57页。第5页/共57页第六页，共57页。1.若若G(文法文法)有左递归，则分析不能正常进行。故有左递归，则分析不能正常进行。故必须先消除文法的左递归；必须先消除文法的左递归；2. 分析过程是反复进行试探的过程，故难免会出现分析过程是反复进行试探的过程，故难免会出现大量的回溯大量的回溯(hu s)。特别是当。特别是当wL(G)时时,只有只有在穷举完所有的试探后才能拒绝在穷举完所有的试探后才能拒绝w。 因此，消因此，消除回溯除回溯(hu s)是是分析的另一目标分析的另一目标.3.当拒绝当拒绝w时时,才能知道才能知道w不是句子不是句子,不知出何错及出不

4、知出何错及出在何处在何处4.2.1 不确定不确定(qudng)的自顶向下分析的自顶向下分析第6页/共57页第七页，共57页。Sx*yIPSx*yIPAxySx*yIPAxySx*yIPAxy*Sx*yIPAxy*Sx*yIPAxy*Sx*yIPAxy*由于由于(yuy)A(yuy)A的两条产生式：的两条产生式：AA* * * 和和AA* * 右部开始符号相同，从而右部开始符号相同，从而引起回溯引起回溯4.2.1 不确定不确定(qudng)的自顶向下分析的自顶向下分析（续）（续）第7页/共57页第八页，共57页。 基本思想：从文法的开始(kish)符出发，如能根据当前的输入符号（单词符号）唯一地

5、确定选用哪个产生式进行推导，则分析是确定的。 对语言(yyn)的文法要求：文法是无左递归的和无回溯的。4.2.1 不确定不确定(qudng)的自顶向下分析（续）的自顶向下分析（续）非确定非确定 方法是一种带回溯的方法是一种带回溯的 方法，其分析效率低方法，其分析效率低，代价高，在编译程序时不常用。通常使用的是，代价高，在编译程序时不常用。通常使用的是确定的确定的自顶自顶向下向下分析分析法。法。第8页/共57页第九页，共57页。1.采用扩充采用扩充BNF法消除文法法消除文法(wnf)直接左递归直接左递归第9页/共57页第十页，共57页。v例例1 设文法设文法GE：EE+T|E-T|Tv T T*

6、E|T/F |F v F(E)|id v 利用利用(lyng)扩展扩展BNF表示法改写文法表示法改写文法GE改为：改为：vET+T|-T vTF*F|/F vF(E)|idv例例2 文法文法 l |l |d 。v 利用利用(lyng)扩展扩展BNF表示法改写文法为表示法改写文法为 ll|d第10页/共57页第十一页，共57页。2.把直接把直接(zhji)左递归改为直接左递归改为直接(zhji)右递归右递归第11页/共57页第十二页，共57页。v例例1 设有文法设有文法(wnf)GE：EE+T|E-T|Tv T T*E|T/F |F v F(E)|id v消去非终结符消去非终结符E,T的直接左递

7、归后，文法的直接左递归后，文法(wnf)GE 为：为：vETE vE + TE |-TE | vTFT vT *FT |/FT | vF (E)|id4.2.2 文法的左递归和回溯文法的左递归和回溯(hu s)的消除的消除（续）（续）第12页/共57页第十三页，共57页。（3）化简由（）化简由（2）得到）得到(d do)的文法的文法（2） for (i=1;i=n;i+) for(j=1;j=i-1;j+) 用用Ai 1r | 2r | | k r替代替代 形如形如Ai Ajr的规则的规则,其中其中 Aj 1 | 2 | | k 是关于是关于Aj的全部规则的全部规则; 消除消除Ai规则的直接左

8、递归规则的直接左递归; （1） 以某种顺序将文法非终结符排列以某种顺序将文法非终结符排列A1 ,A2 An+第13页/共57页第十四页，共57页。例：例：v文法文法(wnf)G:SQc | cQRb | bRSa | aR Qca | ca | aR Rbca | bca | ca | aR (bca | ca | a)R R bcaR |n最终最终(zu zhn)文法：文法：nSQc | cnQRb | bnR bca R | ca R | aRnR bcaR |设设VN排序排序(pi x)为为A1= S、 A2 = Q、 A3 = RAi=A3 = R,Aj =A1 = S ,Ai Ajr

9、Ai=A3 = R,Aj =A2 = Q ,Ai AjrAi=A1 = S for (i=1;i=n;i+) for(j=1;j* S 得得 $ FOLLOW(S) 由由S=aA=abAS=abbASS=abbASaA =abbASd FOLLOW(S)=$,a,d 由由S=* aA 得得$ FOLLOW(A) 由由S=* abAS=* abAaA 得得 a FOLLOW(A) =* abAd 得得 d FOLLOW(A) FOLLOW(A)=$,a,d第21页/共57页第二十二页，共57页。第22页/共57页第二十三页，共57页。W(A) W(A) 第23页/共57页第二十四页，共57页。第

10、24页/共57页第二十五页，共57页。若若*,则则SELECT(A)=FIRST()若若=*, 则则SELECT(A)=(FIRST()-)FOLLOW(A)说明：说明： 对于产生式对于产生式A与与A，若，若 SELECT(A)SELECT(A)=，则一定，则一定可以进行可以进行(jnxng)确定的自顶向下分析确定的自顶向下分析例例 G3S: SaA Sd AbAS ASELECT(SaA)=FIRST(aA)=aSELECT(Sd)=FIRST(d)=dSELECT(AbAS)=FIRST(bAS)=bSELECT(A)=FOLLOW(A)=$,a,d第25页/共57页第二十六页，共57页。

11、第26页/共57页第二十七页，共57页。SELECT(SaAS)= aSELECT(Sb)= bSELECT(AbA)= bSELECT(A)=Follow(A)= a,b由于由于SELECT(AbA)SELECT(A)=b，所以文法所以文法(wnf)GS不是不是LL(1)文法文法(wnf)，当，当A遇输遇输入符入符b时，不能确定选时，不能确定选AbA还是还是A去推导。去推导。第27页/共57页第二十八页，共57页。第28页/共57页第二十九页，共57页。第29页/共57页第三十页，共57页。第30页/共57页第三十一页，共57页。v对于一个满足对于一个满足LL(1)条件的文法，可以对其输入串

12、条件的文法，可以对其输入串进行有效的无回溯的自上而下分析。假设要用非进行有效的无回溯的自上而下分析。假设要用非终结符终结符A进行匹配，面临的输入符号为进行匹配，面临的输入符号为a，A的所的所有产生式为：有产生式为：vA 1 | 2 | | nv1. 若若aFIRST( i)，则指派，则指派 i执行匹配任务；执行匹配任务；v2. 若若a不属于任何一个候选首符号集，则：不属于任何一个候选首符号集，则：v (1) 若若属于某个属于某个FIRST(i )且且 aFOLLOW(A)， 则让则让A与与自动匹配。自动匹配。v (2) 否则，无法识别否则，无法识别(shbi)字符字符a，出现语法错，出现语法错

13、误。误。第31页/共57页第三十二页，共57页。2. 对非对非LL(1) 进行等价变换进行等价变换提取左公共因子提取左公共因子消除左递归消除左递归注意注意(zh y)：变换后的文法不一定是：变换后的文法不一定是LL(1)文法，文法，文法不含左递归和左公共因子只是文法不含左递归和左公共因子只是LL(1)文法的必要文法的必要条件。条件。第32页/共57页第三十三页，共57页。第33页/共57页第三十四页，共57页。第34页/共57页第三十五页，共57页。第35页/共57页第三十六页，共57页。4.2.5 确定确定(qudng)的自顶向下分析方法的自顶向下分析方法（续）（续）第36页/共57页第三十

14、七页，共57页。第37页/共57页第三十八页，共57页。p特点特点p优点：简单直观、易于构造优点：简单直观、易于构造p缺点：对文法要求高，必须满足缺点：对文法要求高，必须满足LL(1)文法；文法；递归调用多，速度慢，占用空间多递归调用多，速度慢，占用空间多p几个全局几个全局(qunj)过程和变量过程和变量pScanner()：读取输入串指针：读取输入串指针IP指向的一个输指向的一个输入符号。入符号。psym：IP当前所指的输入符号。当前所指的输入符号。perror()：出错处理子程序。：出错处理子程序。第38页/共57页第三十九页，共57页。例例1 1 设有文法设有文法(wnf)GS(wnf)

15、GSSa|Sa|（T T）TTTT，S|SS|S构造识别该文法构造识别该文法(wnf)(wnf)句子的递归句子的递归下降分析程序下降分析程序1.消除消除(xioch)左递归得左递归得 G:S Sa|（T）TSTT , ST| 2.2.判断改写后的文法是否为判断改写后的文法是否为LL(1)LL(1)文法，即可否文法，即可否(k fu)(k fu)用递归下降分析法。用递归下降分析法。SELECT(Sa ) = a SELECT(Sa ) = a SELECT(S ) = SELECT(S ) = SELECT(S (T) ) = ( SELECT(S (T) ) = ( SELECT(T, ST)

16、 = , SELECT(T, ST) = , SELECT(T ) = SELECT(T ) = FOLLOW(T)= ) FOLLOW(T)= ) 无相交情况无相交情况G是是LL(1)文法文法第39页/共57页第四十页，共57页。Sa|（T）TSTT , ST| 3.3.递归下降递归下降(xijing)(xijing)分析程序如下：分析程序如下：main()main() Scaner(); Scaner(); S(); S(); if(sym=$) if(sym=$) printf(“success”);printf(“success”); else printf(“fail”); else

17、 printf(“fail”); S( ) S( ) if(sym=a|sym=)if(sym=a|sym=)Scaner();Scaner(); else if (sym=() else if (sym=() Scaner(); T(); if(sym=) Scaner(); else error();else error();T( ) S( ); T( );T( ) if(sym=,) Scaner( );S( );T( ); else if(sym!=) error();第40页/共57页第四十一页，共57页。E（）（）if(sym FIRST(TE) T（）；（）；E （）；（）； e

18、lseif(sym FIRST(BC)B（）（）; C（）；（）；else error();第41页/共57页第四十二页，共57页。E（）（） T（）；（）； E （）；（）；T（）（） F（）；（）； T （）；（）；第42页/共57页第四十三页，共57页。E （）（） if(sym=+) Scanner()； T()；E (); elseif (symFollww(E) return; else error();T （）（） if(sym=*) Scanner()； F()；T (); elseif (symFollww(T) return; else error();第43页/共57页第

19、四十四页，共57页。F（）（） if(sym=i) Scanner(); elseif(sym=() Scanner();E()； if(sym=) Scanner();else error(); else error(); 第44页/共57页第四十五页，共57页。主程序主程序:main() Sanner(); E(); if(sym=$) printf(“success”); else printf(“fail”);第45页/共57页第四十六页，共57页。预测分析器（预测分析程序）由三个部分组成：预测分析器（预测分析程序）由三个部分组成：总控程序：控制分析过程的进行。总控程序：控制分析过程的

20、进行。分析栈：存放从文法开始符号出发的自顶向下推导分析栈：存放从文法开始符号出发的自顶向下推导(tudo)过程中替换当前非终结符某规则右部符合串。开始时放入过程中替换当前非终结符某规则右部符合串。开始时放入$和文法开始符，结束时栈应是空的。和文法开始符，结束时栈应是空的。预测分析表：是一张二维表，元素预测分析表：是一张二维表，元素MA,a的内容是当非终结的内容是当非终结符符A面临输入符号面临输入符号a（终结符或（终结符或$）时应选取的产生式，当）时应选取的产生式，当无产生式时，元素内容为出错处理。无产生式时，元素内容为出错处理。第46页/共57页第四十七页，共57页。分析栈分析栈缓冲区缓冲区预

21、测分析器预测分析器存放待分析的输入存放待分析的输入(shr)符号串，以右界符符号串，以右界符$结束结束第47页/共57页第四十八页，共57页。q总控程序根据现行栈顶符号总控程序根据现行栈顶符号X和当前输入符号和当前输入符号a，执行下列，执行下列(xili)三种操作之一三种操作之一:q1. 若若Xa$，则宣布分析成功，停止分析，则宣布分析成功，停止分析。q2. 若若Xa $，则把，则把X从从STACK栈顶弹出栈顶弹出，然后读取下一个输入符号。，然后读取下一个输入符号。第48页/共57页第四十九页，共57页。3. 若若X是一个非终结符，则查看分析是一个非终结符，则查看分析(fnx)表表M。 若若M

22、X，a中存放着关于中存放着关于X的一个产生式，的一个产生式，把把X弹出弹出STACK栈顶，把产生式的右部符号栈顶，把产生式的右部符号串按反序一一压入串按反序一一压入STACK栈栈(若右部符号为若右部符号为，则意味不压什么东西进栈，则意味不压什么东西进栈)。在把产生式。在把产生式的右部符号压入栈的同时应做这个产生式相的右部符号压入栈的同时应做这个产生式相应的语义动作。应的语义动作。若若MX，a中存放着中存放着“出错标志出错标志”，则调用出，则调用出错诊察程序错诊察程序ERROR。推导(tudo)第49页/共57页第五十页，共57页。MX,a有产生有产生(chnshng)式？式？弹出栈顶符放入弹出

23、栈顶符放入XNYYNNNN YY Y把把$和文法开始符和文法开始符S压入分析栈压入分析栈;当前输入符送当前输入符送a规则右部规则右部反序反序进栈。进栈。不进栈不进栈XVT ?X=$ ? X=a ?X=a?读 下 一 输读 下 一 输入符到入符到a出错出错结束结束出错出错预测预测(yc)分析程序流分析程序流程程 第50页/共57页第五十一页，共57页。第51页/共57页第五十二页，共57页。方法二：方法二：(1)(1)判定判定(pndng)(pndng)文法是否为文法是否为LL(1)LL(1)？(2)(2)计算文法计算文法G G中每一非终结符中每一非终结符FIRSTFIRST和和FOLLOWFO

24、LLOW(3)(3)对文法的每个规则对文法的每个规则AA，若，若a aFIRST()FIRST() 则置则置MA,a= AMA,a= A； 若若FIRST( ) FIRST( ) ， 则置则置MA,b= AMA,b= A，其中其中b b FOLLOW(A ),FOLLOW(A ),(4)(4)把分析表中无定义的把分析表中无定义的MA,aMA,a标上出错标记。标上出错标记。3 预测预测(yc)分析表的构造方法（续）分析表的构造方法（续）第52页/共57页第五十三页，共57页。（1）消除）消除G的左递归得到的左递归得到(d do)文法文法 GETE E+TE TFT T*FTF(E)i（2）求出每个产生）求出每个产生(chnshng)式的式的select集集,G是是LL(1)文法文法 SELECT(ETE ) = (,i SELECT(E+TE ) = + SELECT(E ) = ),$ SELECT(TFT ) = (,i SELECT(T*FT ) = * SELECT(T ) =