編譯原理-第5章習(xí)題解答

1、精選優(yōu)質(zhì)文檔-傾情為你奉上專心-專注-專業(yè)第五章 習(xí)題解答5.1 設(shè)一 NDPDA 識(shí)別由下述 CFG 定義的語言，試給出這個(gè) NDPDA 的完整形式描述。SSASCSAAaAbCDcDDd5.2 消除下列文法的左遞歸： GA: ABXCZW BAbBc CAxByCp GE: EET+ETT TTF*TF/F F(E)i GX: XYaZbc Y ZdXef ZXeYfa GA: ABa|Aa|cBBb|Ab|d 5.3 設(shè)文法 G： : = |ifthen|ifthenelse i|+ |* |()試構(gòu)造該文法的遞歸下降子程序。 5.4 設(shè)文法 GE： E TE E + E T FT T

2、T F PF F *F精選優(yōu)質(zhì)文檔-傾情為你奉上專心-專注-專業(yè) P (E) a 構(gòu)造該文法的遞歸下降分析程序； 求該文法的每一個(gè)非終結(jié)符的 FIRST 集合和 FOLLOW 集合； 構(gòu)造該文法的 LL（1）分析表，并判斷此文法是否為 LL（1）文法。 5.5 設(shè)文法 GS： S SbAaA B Sb A Bc 將此文法改寫為 LL（1）文法； 求文法的每一個(gè)非終結(jié)符的 FIRST 集合和 FOLLOW 集合； 構(gòu)造相應(yīng)的 LL（1）分析表。 5.6 設(shè)文法 GS： S aABbcd A ASd B SAheC C SfCg D aBD 求每一個(gè)非終結(jié)符的 FOLLOW 集合； 對(duì)每一個(gè)非終結(jié)

3、符的產(chǎn)生式選擇，構(gòu)造 FIRST 集合； 該文法是 LL（1）文法。 5.7 設(shè)文法 GE： E AaBb A cAeB B bd 試畫出其自上而下分析程序框圖。第五章習(xí)題參考答案5.1 解：NDPDA M=(Q,H,q0,F,Z0)Q=q=a,b,c,dH=S,A,C,D,a,b,c,dq0=qF=qZ0=S: (q,S)=(q,SASC),(q,)(q,A)=(q,Aa),(q,b)(q,C)=(q,DCD)(q,D)=(q,d)(q,a,a)=(q,)(q,b,b)=(q,)(q,c,c)=(q,)(q,d,d)=(q,)精選優(yōu)質(zhì)文檔-傾情為你奉上專心-專注-專業(yè)5.2 解： 利用消除左

4、遞歸的算法，將非終結(jié)符排序?yàn)?U1=A，U2=B，U3=C， 則 i=1,j=0 時(shí)，對(duì)文法無影響。 i=2,j=1 時(shí)，因?yàn)?Ui=BAb，Uj=ABx|Cz|w 所以將 B 改寫為 BBxb|Czb|wb|Bc 消除產(chǎn)生式 B 的左遞歸： BCzbB|wbB BxbB|cB| i=3,j=1 時(shí)，因?yàn)?Ui=CAx，Uj=ABx|Cz|w 所以將 C 改寫為 CBxx|Czx|wx|By|Cp j=2 時(shí)，因?yàn)?Ui=CBxx|By，Uj=BCzbB|wbB 所以將產(chǎn)生式 C 改寫為 CCZbBxx|CzbBy|wbBxx|wbBy|Czx|wx|Cp 消除產(chǎn)生式 C 的左遞歸： CwbB

5、xxC|wbByC|wxCCzbBxxC|zbByC|zxC|pC| 所以，文法消除左遞歸后變?yōu)?ABx|Cz|w BCzbB|wbB BxbB|cB| CwbBxxC|wbByC|wxC CzbBxxC|zbByC|zxC|pC| 利用消除左遞歸的算法，將非終結(jié)符排序?yàn)椋篣1=E，U2=T，U3=F 則 i=1,j=0 時(shí)，無代入。 消除產(chǎn)生式 E 的左遞歸： ET(T+|T-) i=2,j=1 時(shí)，無代入。 消除產(chǎn)生式 T 的左遞歸： TF*|F/F i=3,j=1 時(shí)，無代入，也無產(chǎn)生式左遞歸，不改寫產(chǎn)生式。 所以，文法消除左遞歸后變?yōu)?ET(T+|T-) TF*|F/F F(E)|I

6、利用消除左遞歸的算法，將非終結(jié)符排序?yàn)? U1=X，U2=Y，U3=Z 則 i=1,j=0 時(shí)，無代入 i=2,j=1 時(shí)，因?yàn)?Ui=YZd|Xe|f，Uj=XYa|Zb|c 所以將 Y 改寫為 YZd|Yae|Zbe|ce|f 消除左遞歸，得到 YZdY|ZbeY|ceY|fY YaeY| i=3,j=1 時(shí)，因?yàn)?Ui=ZXe|Yf|a，Uj=XYa|Zb|c 所以將 Z 改寫為 ZYae|Zbe|ce|Yf|a j=2 時(shí), Ui=ZYae|Yf, Uj= YZdY|ZbeY|ceY|fY精選優(yōu)質(zhì)文檔-傾情為你奉上專心-專注-專業(yè)所以將 Z 改寫為 ZZdYae|ZbeYae|ceYa

7、e|fYae|ZdYf|ZbeYf|ceYf|fYf|Zbe|ce|a對(duì) Z 消除左遞歸得到： ZceYaeZ|fYae Z|ceYf Z|fYf Z|ce Z|a ZZdYae Z|beYae Z| dYf Z|beYf Z|be Z| 所以，文法消除左遞歸以后變?yōu)椋篨Ya|Zb|cYZdY|ZbeY|ceY|fYYaeY|ZceYaeZ|fYae Z|ceYf Z|fYf Z|ce Z|a ZZdYae Z|beYae Z| dYf Z|beYf Z|be Z| 利用消除左遞歸的算法，將非終結(jié)符排序?yàn)?U1=A， U2=B則i=1, j=0 時(shí)，由于產(chǎn)生式 ABa|Aa|c 存在直接左遞歸

8、，將其修改為 ABaA|cA AaA| i=2,j=1 時(shí)，因?yàn)?Ui=BAb，Uj=ABaA|cA，所以將產(chǎn)生式 B 修改為 BBb|BaAb|cAb|d 消除產(chǎn)生式 B 的左遞歸，得 BcAbB|dB BbB|aAbB| 所以文法消除左遞歸后變?yōu)锳BaA|cAAaA| BcAbB|dBBbB|aAbB| 5.3 解：首先改寫文法，使其滿足遞歸下降分析法對(duì)文法的要求。對(duì)產(chǎn)生式提取最左公共因子得 : = |ifthen else| 對(duì)產(chǎn)生式、消除左遞歸得 +| *| 得到等價(jià)的文法： :=|ifthen else| i +| 精選優(yōu)質(zhì)文檔-傾情為你奉上專心-專注-專業(yè) *| |() 構(gòu)造該文法

9、的遞歸下降分析程序如下： PROCEDURE ； BEGIN IF SYM IN FIRST() THEN BEGIN ； IF SYM=:= THEN BEGIN READAWORD； END ELSE ERROR END ELSE IF SYM=if THEN BEGIN READAWORD； ； IF SYM=then THEN BEGIN READAWORD； ； END ELSE ERROR END ELSE ERROR END； PROCEDURE ； BEGIN IF SYM=else THEN BEGIN READAWORD； END ELSE IF NOT (SYM IN F

10、OLLOW() THEN ERROR END； PROCEDURE ； BEGIN IF SYM=i/* i 表示標(biāo)識(shí)符 */精選優(yōu)質(zhì)文檔-傾情為你奉上專心-專注-專業(yè) THEN READAWORD ELSE ERROR END； PROCEDURE ； BEGIN ； END； PROCEDURE ； BEGIN IF SYM=+ THEN BEGIN READAWORD； ； END ELSE IF NOT (SYM IN FOLLOW() THEN ERROR END； PROCEDURE ； BEGIN ； END； PROCEDURE ； BEGIN IF SYM=* THEN BE

11、GIN READAWORD； END ELSE IF NOT (SYM IN FOLLOW() THEN ERROR END； PROCEDURE ； BEGIN IF SYM=( THEN BEGIN READAWORD；精選優(yōu)質(zhì)文檔-傾情為你奉上專心-專注-專業(yè) ； IF (SYM=) THEN READAWORD ELSE ERROR END ELSE IF SYM IN FIRST() THEN ELSE ERROR END；5.4 解：(1)步驟和方法與 5.3 中類似，略。(2)根據(jù) FIRST、FOLLOW 集合的求法可以得到：FIRST(E)=(,a, ; FIRST(E)=+

12、,FIRST(T)=(,a, ; FIRST(T)=(,a, ,FIRST(F)=(,a, ;FIRST(F)=*,FIRST(P)=(,a, .FOLLOW(E)=),$; FOLLOW(E)=),$;FOLLOW(T)=+,),$; FOLLOW(T)=+,),$;FOLLOW(F)=(,a,+,),$; FOLLOW(F)=(,a,+,),$;FOLLOW(P)=(,a,+,),$,*; (3)根據(jù)求得的 FIRST、FOLLOW 集合可以得到 SELECT 集合，進(jìn)而構(gòu)造出 LL(1)分析表如下：+*()a$EETEETEETEEE+EEEETTFTTFTTFTTTTTTTTTTTTF

13、FPFFPFFPFFPFFFFF*FFFFFFPP(E)PaP空白處為 ERROR。表中每一元素的表達(dá)式都是唯一的，因此該文法是 LL(1)文法。5.5 解:(1) 改寫文法為 LL(1)文法。因?yàn)?SSbA|aA 有左遞歸，故將其改寫為 SaAbA文法變?yōu)榫x優(yōu)質(zhì)文檔-傾情為你奉上專心-專注-專業(yè) SaAbA BSb ABc這樣的文法滿足 LL(1)文法的條件。(2) 文法每一個(gè)非終結(jié)符號(hào)的 FIRST 集合為 FIRST(S)=a FIRST(A)=a FIRST(B)=a文法每一個(gè)非終結(jié)符號(hào)的 FOLLOW 集合為因?yàn)?S 為開始符號(hào)，且有產(chǎn)生式 SaAbA 和 BSb所以 FOLLOW

14、(S)=#FIRST(b)=#，b因?yàn)?SaAbA所以 FOLLOW(A)= FOLLOWSFIRST(bA)=#，b因?yàn)?ABc所以 FOLLOW(B)=FIRSTc=c(3) 構(gòu)造相應(yīng)的 LL(1)分析表因?yàn)?FIRST(aAbA)=a所以 MS,a= “ SaAbA”因?yàn)?FIRST(A)=a 所以 MA,a= “ ABc ”因?yàn)?FIRST(B)=a所以 MB,a= “BSb ”文法 GS的分析表如下表所示(空白處是 ERROR)。abc#SSaAbAAABcBBSb文法 GS的分析表5.6 解：首先將文法壓縮，得到 SaABbcd| AASd| BSAh|eC| CSf|Cg| (1

15、) 求每一個(gè)非終結(jié)符號(hào)的 FOLLOW 集合：因?yàn)?S 為開始符號(hào)，且有產(chǎn)生式 AASd，BSAh，CSf所以 FOLLOW(S)=#FIRST(d)FIRST(Ah)FIRST(f)=#，d，a，h，f因?yàn)?SaABbcd，AASd，BSAh所以 FOLLOW(A)=FIRSTBbcdFIRSTSdFIRSTh=b，a，d，h，e因?yàn)?SaABbcd 所以 FOLLOW(B)=FIRSTbcd=b因?yàn)?BeC，CCg所以 FOLLOW(C)=FOLLOW(B)FIRST(g)=b，g(2) 對(duì)每一個(gè)非終結(jié)符號(hào)的產(chǎn)生式選擇，構(gòu)造 FIRST 集合對(duì) S：FIRST(aABbcd)=a FIRST()=精選優(yōu)質(zhì)文檔-傾情為你奉上專心-專注-專業(yè)對(duì) A：FIRST(ASd)=a，d FIRST()=對(duì) B：FIRST(SAh)=a，d，h FIRST(eC)=e FIRST()=對(duì) C：FIRST(Sf)=a，f FIRST(Cg)=a，f，g FIRST()=(3) 由于存在產(chǎn)生式 CSf|Cg| FIRST(Sf)FIRST(Cg)=a，fa，f，g所以該文法不是 LL(1)文法。 5.7 解：因?yàn)樵撐姆o左遞歸，且對(duì)每一個(gè)非終結(jié)符號(hào)，其右部各候選式的首終結(jié)符號(hào)集合兩兩互不相交，所以可以采用自上而下分析方法