資源描述：
《編譯原理 試題》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫(kù)。
1、P788.構(gòu)造一個(gè)DFA，他接受正規(guī)式（a
2、ba）*定義的字符串。解：狀態(tài)轉(zhuǎn)換，如表所示對(duì)上表簡(jiǎn)化，得表如下abS,1,Z1,Z21,Z1,Z221,Zab11P95消除以下文法的左遞歸，并構(gòu)造文法分析表，應(yīng)用上述預(yù)測(cè)分析表分析輸入串i*i。E→E+T
3、TT→T*F
4、FF→(E)
5、i解：(1)E→E+T
6、T＝>E→TE’E’→+TE’
7、εT→T*F
8、F＝>T→FT’T’→*FT’
9、εF→(E)
10、I＝>(E)
11、i(2)E→TE’FIRST(TE’)={i,(}FOLLOW(E)={),#}E’→+TE’FIRST(+TE’)={+}FOLLOW(E’)={),#}E’→
12、εFIRST(ε)={ε}T→FT’FIRST(FT’)={(,i}FOLLOW(T)={+,),#}T’→*FT’FIRST(*FT’)={*}FOLLOW(T’)={+,),#}T’→εFIRST(ε)={ε}F→（E）FIRST((E))={(}FOLLOW(F)={*,+,),#}F→iFIRST(i)={i}得預(yù)測(cè)分析表i+*（）#EE→TE’E→TE’E’E’→+TE’E’→εE’→εTT→FT’T→FT’T’T’→εT’→*FT’T’→εT’→εFF→iF→（E）(3)應(yīng)用上述預(yù)測(cè)分析表分析輸入串i*i將步驟細(xì)列于下表步驟序號(hào)符號(hào)棧輸入串查表項(xiàng)調(diào)用產(chǎn)生式
13、/匹配/出錯(cuò)0#Ei*i#M[E,i]E→TE’1#E’Ti*i#M[T,i]T→FT’2#E’T’Fi*i#M[F,i]F→i3#E’T’ii*i#匹配成功4#E’T’*i#M[T’,*]T’→*FT’5#E’T’F**i#匹配成功6#E’T’Fi#M[F,i]F→i7#E’T’ii#匹配成功8#E’T’#M[T’,#]T’→ε9#E’#M[E’,#]E’→ε10##分析成功（匹配）P1324.給定文法G4(S);S→a
14、∧
15、（T）T→T,S
16、S(1)計(jì)算該文法的FIRSTVT集合和LASTVT集合。(2)計(jì)算該文法的優(yōu)先關(guān)系。(3)給出輸入串（a，（a，a））的算
17、符優(yōu)先分析過(guò)程。解：(1)FIRSTVT和LASTVT集合如下：FIRSTVT(S)={a，∧，（}FIRSTVT（T）={，，a，∧，（}LASTVT(S)={a，∧，)}LASTVT(T)={,,a,∧,)}棧優(yōu)先關(guān)系輸入字符串動(dòng)作#<（a，（a，a））#移進(jìn)#（，（a，a））#歸約#（N1<，（a，a））#移進(jìn)#（N1，<（a，a））#移進(jìn)#（N1，（，a））#歸約#（N1，（N2<，a））#移進(jìn)#（N1，（N2，））#歸約#（N1，（N2，N3>））#歸約#（
18、N1,(N4≈））#移進(jìn)#（N1,(N4)>）#歸約#（N1,N4>）#歸約#（N1≈）#移進(jìn)#（N1）>#歸約#S#Success(2)構(gòu)造優(yōu)先關(guān)系（3）分析過(guò)程a∧（），a>>∧>>（<<<≈<）>>，<<<>>PPTP145翻譯條件嵌套語(yǔ)句：IfathenifbthenA:=2elseA:=3ElseifcthenA=4ElseA=5翻譯成四元式為：可得四元式：(1)(jnz,a,_,3)(2)(j,_,_,9)(3)(jnz,b,_,5)(4)(j,_,_,7)(5)(:=,2,_,A)(6)(j,_,_,0)(7)(:=,3,_,A)(8)(j,_,_,6)
19、(9)(jnz,c,_,11)(10)(j,_,_,13)(11)(:=,4,_,A)(12)(j,_,_,8)(13)(:=,5,_,A)P1339.文法G9(S)S→DbBD→dD→εB→aB→BbaB→ε(1)構(gòu)造LR（1）項(xiàng)目集規(guī)范簇，識(shí)別該文法所產(chǎn)生的活前綴的DFA。(2)構(gòu)造LR(1)分析表。(3)給出用分析器分子句子baba#的過(guò)程。解：（1）拓廣文法為G9(S’):S’→SS→DbBD→dD→εB→aB→BbaB→ε構(gòu)造LR（1）項(xiàng)目集規(guī)范簇，識(shí)別該文法所產(chǎn)生的活前綴的DFA，如圖所示：I0:S’→?S#SS→?DbB#I1：S’→S?#D→?dbDD
20、→?bI2：S→D?Bb#dbI4:S→Db?B#BI6：S→DbB?#I3:D→d?bB→?a#/bB→B?BA#/bB→?Bba#/bbB→?#/bI7:B→Bb?a#/baaI5:B→a?#/bI8:B→Bba?#/b（2）LR（1）分析表：（3）穿baba#的分析過(guò)程如下：ACTIONGOTObda#SBD0r3S3121acc2S43r24r6S5r665r4r46S7r17S88r5r5步驟狀態(tài)符號(hào)輸入串00#baba#102#Dbaba#2024#DbAba#30245#Dbaba#40246#DbBba#502467#DbBba#60
