自頂向下語法分析方法

1、習題 第5章 自頂向下語法分析方法一 課本練習部分（第99-101頁）5.15.45.6（2）（3）（4）5.7（1）（3）（5）參考答案：5.1（1）S =（T）=(T,S) =(S,S) =(a,S) = (a,(T) = (a,(T,S) = (a,(S,S) = (a,(a,S) = (a,(a,a)S = (T) = (T,S) = (S,S) = (T),S) = (T,S),S) = (T,S,S),S) =(S,S,S),S) = (T),S,S),S) = (T,S),S,S),S) = (S,S),S,S),S) = (a,S),S,S),S) = (a,a),S,S),S

2、) = (a,a), ,S),S) =(a,a), ,(T),S) = (a,a), ,(S),S) = (a,a), ,(a),S) = (a,a), ,(a),a)（2）改寫文法如下：Sa|(T)TSTT,ST|遞歸子程序為：S() if(SYM=a)P(a);else if(SYM=)P();else if(SYM=( ) GetSym(); P(T); match() ）； else Error(); T() P(S)；P(T)；T() if(SYM=,) match(,);？P(S);P(T);else if(SYM=()return;else error();(3)FIRST(S)

3、=a( FOLLOW(S)=#,) FIRST(T)=a( FOLLOW(T)=) FIRST(T)=, FOLLOW(T)=) SELECT(Sa)=a SELECT(S)= SELECT(S(T)=( SELECT(TST)= a( SELECT(T,ST)=, SELECT(T=)由于相同左部的SELECT集的交集為空，所以所改寫的文法是LL(1)的。寫出該文法的預測分析表：a(,)#Sa(T)TSTSTSTT,ST#OK？或者a(,)#S，N，N)T，NTTS，PTS，PTS，PTTS，N，P#OK(4)對符號串(a,a)#的分析過程步驟分析棧剩余輸入串所用產(chǎn)生式1#S(a,a)#S(

4、T)2#)T(a,a)#(匹配3#)Ta,a)#TST4#)TSa,a)#Sa5#)Taa,a)#a匹配6#)T,a)#T,ST7#)TS,a)#，匹配8#)TSa)#Sa9#)Taa)#a匹配10#)T)#T11#)#)匹配12#接受所以(a,a)#是G的句子。4.證明：FT(S)=a,b; FT(C)=a,b;FT(A)=a,b;FT(B)=a,b;FW(S)=#;FW(C)=$,a,b;FW(A)=$,a,b;FW(B)=$,a,b; ST(C-Ba)=b;ST(C-aB)=a;ST(A-a)=a;ST(A-aC)=a;ST(A-Abb)=b;ST(B-b)=b;ST(B-bC)=b;S

5、T(B-aBB)=a;由于：ST(A-a)=aST(A-aC)=a ST(B-b)=bST(B-bC)=b所以為非LL(1)文法。若通過提取公共左因子來改寫文法為： S-C$ C-bA|aB A-aD|bAA B-bD|aBB D-C|由于左部為D的規(guī)則式的選擇集相交：ST(D-C)=a,b;ST(D-)=a,b,$;故也不是LL(1)文法。5.6（2）B有相同左因子，所以該文法不是LL(1)的。 先將A的規(guī)則代入S的規(guī)則： SBaB|B 提左因子B，得 SB(aB|) 引入非終結(jié)符E及其規(guī)則得： SBE EaB| 再將D的規(guī)則代入B的規(guī)則： Bdb|b|d| 提左因子d得： Bd(b|)|b

6、| 引入非終結(jié)符F及其規(guī)則得： BdF|b| Fb| 故文法變換為： SBE BdF|b| EaB| Fb| 由于 SELECT(B)=a,# SELECT(E)=# SELECT(F)=a,# 故B，E和F的各自規(guī)則兩兩不相交，變換后的文法是LL(1)文法。 遞歸下降子程序此略。注意：若直接提取左因子D： BD(b|)并改寫為 BDH Hb|則文法改寫為：SABABa|BDEEb|Dd|但因為SELECT(ABa) SELECT(A)故此，僅直接提取左因子，文法仍不是LL(1)的。（3）SELECT集為： ST(S-aAaB)=aST(S-bAbB)=bST(A-S)=first(S)=a

7、bST(A-db)=dST(B-bB)=bST(B-a)=a因相同左部產(chǎn)生式的SELECT集不相交，所以為LL（1）文法。遞歸下降子程序為：S()if(SYM=a)GetSym();P(A);match(a);P(B); else if(SYM=b)GetSym();P(A);match(b);P(b);A()if(SYM=d)GetSym();match(b); else P(S);B()if(SYM=b)GetSym();P(B); else if(SYM=a) GetSym(); （4）因為文法具有左遞歸，所以不是LL(1)的。改寫該文法：Si|(E)ESEE+SE|-SE|計算新文法的

8、First集和Follow集。VFIRSTFOLLOWSi (# + -Ei ()E+ -)計算SELECT集:SELECT(Si)=iSELECT(S(E)=(SELECT(ESE)=i(SELECT(E+SE)=+SELECT(E-SE)=-SELECT(E)=)由此可以看出此文法是LL(1)的。構(gòu)造相應的遞歸下降識別器：P(S) if(SYM=i)match(i);else if(SYM=() match();P(E);match();P(E) P(S);P(E);P(E) if(SYM=+) match(+);P(S);P(E); else if(SYM=-) match(-);P(S

9、);P(E);else if(SYM=)returnelse error();7消除了左遞歸，提取了左公因子并不一定是LL(1)的。（1）改寫文法得：AbaB|BbaBbb|bb|a消除公共左因子得:AbaB|BbB|aBaBbb|b求其First集和Follow集：VFIRSTFOLLOWAb#Bab#bBab#b計算SELECT集:SELECT(AbaB)=bSELECT(A=#SELECT(BbB=bSELECT(Ba=aSELECT(BaBbb=aSELECT(Bb=b由此可見所改寫的文法是LL(1)的。(3)改寫文法得：SAa|bAbabAA-aabA|求以上狀態(tài)的First集和Fo

10、llow集：VFIRSTFOLLOWSb#AbaAaa求每個產(chǎn)生式的SELECT集合得：SELECT(SAa)=bSELECT(Sb)=b由此可見，此文法不是LL(1)的。（5)可以看出A有公共左因子。消去得：SAb|aaAaAAA|此時，已經(jīng)消除了左遞歸，并且沒有了公共左因子。但是 SELECT(SAb)=aSELECT(Saa)=a顯然文法不是LL(1)的。二 補充部分B5.1 設(shè)有文法G：A(A)A|e （1）求非終結(jié)符A的FIRST集和FOLLOW集；（2）說明G是LL(1)文法；（3）寫出相應的遞歸下降子程序。B5.1（1）FIRST(A)= ( FOLLOW(A)= #，) （2）

11、因為 SELECT(A(A)A)= ( SELECT(Ae)= #，) 規(guī)則的SELECT集互不相交， 故文法是LL(1)文法。 （3）文法 A(A)A|e 的遞歸下降子程序： A() if(SYM=() GetSym(); A(); match(); A(); else if(SYM!=# & SYM!=) ERROR();？ B5.2 對于簡化的C聲明文法G：declaration type var-listtype int | floatvar-list identifier , var-list | identifier其中，非終結(jié)符（斜體）集為 declaration ，type ，

12、var-list ，identifier（其規(guī)則省略） ，終結(jié)符集為 int ， float ，,（逗號） （1）提取規(guī)則的公共左因子； （2）為所得文法的非終結(jié)符求FIRST集和FOLLOW集； （3）說明所得文法是LL(1)文法； （4）為所得文法構(gòu)造預測分析表（LL(1)分析矩陣）； （5）寫出輸入串 int x,y,z的分析過程。B5.2 對于文法 declaration type var-listtype int | floatvar-list identifier , var-list | identifier （1）提取公共左因子：var-list identifier （, v

13、ar-list | e ） （2）FIRST(declaration) = int, floatFIRST(type) = int, floatFIRST(var-list) = identifier FOLLOW(declaration) = # FOLLOW(type) = FIRST(var-list) = identifier FOLLOW(var-list) = FOLLOW(declaration) = # （3）只有type不止一個候選式 ：int | float，且Select集不相交，故文法是LL(1)的。 （4）文法簡記為：D TVT i | f （i和f分別為int和fl

14、oat的簡記符）V IX （I為identifier的簡記符）X ,V | eLL(1)分析表:ifI,#DVTPVTPTeNeNVXNXVNeP#OK （5）int x,y,z的LL(1)分析過程：步驟符號棧S輸入流T1#Dint x,y,z#2#VTint x,y,z#3#Vx,y,z#4#X,y,z#5#Vy,z#6#X,z#7#Vz#8#X#9#B5.3 對于文法G：AaAa|e （1）說明該文法不是LL(1)文法； （2）假設(shè)某人構(gòu)造A的遞歸子程序為void A（） if （SYM = a） GetSym（）； A(); if (SYM = a) GetSym（）； else ERR

15、PR(); else if (SYM != #) ERROR; 說明該子程序不能正確運行。 參考答案：B5.1（1）FIRST(A)= ( FOLLOW(A)= #，) （2）因為 SELECT(A(A)A)= ( SELECT(Ae)= #，) 規(guī)則的SELECT集互不相交， 故文法是LL(1)文法。 （3）文法 A(A)A|e 的遞歸下降子程序： A() if(SYM=() GetSym(); A(); match(); A(); else if(SYM!=# & SYM!=) ERROR(); B5.2 對于文法 declaration type var-listtype int | f

16、loatvar-list identifier , var-list | identifier （1）提取公共左因子：var-list identifier （, var-list | e ） （2）FIRST(declaration) = int, floatFIRST(type) = int, floatFIRST(var-list) = identifier FOLLOW(declaration) = # FOLLOW(type) = FIRST(var-list) = identifier FOLLOW(var-list) = FOLLOW(declaration) = # （3）只有

17、type不止一個候選式 ：int | float，且Select集不相交，故文法是LL(1)的。 （4）文法簡記為：D TVT i | f （i和f分別為int和float的簡記符）V IX （I為identifier的簡記符）X ,V | eLL(1)分析表:ifI,#DVTPVTPTeNeNVXNXVNeP#OK （5）int x,y,z的LL(1)分析過程：步驟符號棧S輸入流T1#Dint x,y,z#2#VTint x,y,z#3#Vx,y,z#4#X,y,z#5#Vy,z#6#X,z#7#Vz#8#X#9#B5.3 對于文法A(A)A|e a. FIRST(A)= (, e ) FOLLOW(A)= #, b. Select(A(A)A)=() Select(Ae)=#,) = 該文法是LL(1)的。B5.3 對于文法G：AaAa|e （1） FIRST(A)= a ) FOLLO