編譯原理第六章答案

第6章自底向上優(yōu)先分析已知文法G[S]為:S->a|A|(T)WT,S|S計(jì)算G[S]的FIRSTVT和LASTVTo構(gòu)造G[S]的算符優(yōu)先關(guān)系表并說明G[S]是否為算符優(yōu)先文法。計(jì)算G[S]的優(yōu)先函數(shù)。⑷給岀輸入串(弘a)#和(①(a,a))#的算符優(yōu)先分析過程。答案：文法展開為：STaS->AST(T)TTT,STTS(1)FIRSTVT-LASTVT表:

非終結(jié)符FIRSTVT集LASTVT集S(aA0{aA)}T{aA(J{aA)J3）算符優(yōu)先關(guān)系衣:aA)aa>>>A>>>(<<<<)>>><<<>>11<<<表中無多重人口所以是算符優(yōu)先（OPG）文法。友情提示：記得增加拓廣文法S'T#S#,所以#FIRSTVT（S）,LASTVT(S)#o（3）對應(yīng)的算符優(yōu)先函數(shù)為:a()■Af■1■221g331131(4)對輸入小(&a)字的算符優(yōu)先分析過程為棧(STACK)當(dāng)前輸入字符(CHAR)剩余輸入串(INPUT.STRING)動(dòng)作(ACTION)(a.a)MoveinaMovein#(aa)#Reduce:S—a#(Na)#Moveina)#Movein#(N.a)Reduce:S—#(N,N)Reduce:T*T.S#(N)Movein#(N)Rednce:S—(T)#NSuccess!對輸入串(色(a,a))#的算符優(yōu)先分析過程為:棧(STACK)當(dāng)前字符(CHAR)剩余輸入串(INPUT_STRING)動(dòng)作(ACTION)岸(a.(a.a))ttMovein做a?(a&))#Movein#(a■(a.a))#Reduce:Sa#(N■(a>a))苻Movein#(N?(a.a))#Movein并(N?(a?a))#Moveiu#(N.(a<a))#Reduce:S—>a做N?(N■a))#Moveiu樣(N?(Na))#Moveiii#(N.(N,a)曲Reduce:Sa#(N.(N,N)Reduce:TT.S#(N.(N))#Movein#(N.(N))Reduce:S—(T)#(N.N)Reduce:T—T.S#(N)#Movein件(N)二Reduce:S~*(T)#N#Success!第2題已知文法G[S]為:S->a|A|(T)WT,S|S(1)給岀(a,(a,a))和(弘a)的最右推導(dǎo)，和規(guī)范歸約過程。⑵將⑴和題1中的⑷進(jìn)行比較給岀算符優(yōu)先歸約和規(guī)范歸約的區(qū)別。答案：(1)(n.a)的最右推導(dǎo)過程為:S=>(T)二〉(T.S)n(T.a)=>(S.a)=5>(a.a)(a,(a.a))的最右推導(dǎo)過程為：S=>(T)=>(T、S)=(「(功=>(T.(T.a))二〉(T.(S.a))=5>(T.(a.a))二乂S?(a.a))(a.(a?a))的規(guī)范歸約過程:步驟棧輸入動(dòng)作1(a, (a.a))#移進(jìn)2n(a.(a.a))#移進(jìn)3.(a.a))#歸約，S"a4#(S.(a.a))#歸約，LTS5#(T.(a.a))#移進(jìn)6#(T,(a.a))#移進(jìn)#(T,(a.a))#移進(jìn)8#(T.(a?a))#歸約,STa9#(T.(S?2片歸約，TTS10#(T.(T?a))#移進(jìn)11#(T.(T.a))#移進(jìn)12#(T,(T.a))#歸約，S今813#(T.(T.S歸約，TT.S14#(T.(T移進(jìn)15#(T,(T)斤歸約，S9(T)16#(T.S移進(jìn)17#(T.S)歸約，T->T.S18#(T)歸約，S°(T)19#s接受(a?)的規(guī)范歸約過程:步驟輸入動(dòng)作1111>(a.a)#移進(jìn)2a.a)#移進(jìn)3.a)#歸約，si4#(s?a)#歸約，TTS■#(T?a)#移進(jìn)6#(T?移進(jìn)7#(T.a歸約，SI8#(TS片!)」約，TTT>S9#(T移進(jìn)10#(T)n歸約，S今(T)11Hs接受(2)算符優(yōu)先文法在歸約過程中只考慮終結(jié)符之間的優(yōu)先關(guān)系從而確定可歸約串，而與非終結(jié)符無關(guān)，只需知道把當(dāng)前可歸約串歸約為某一個(gè)非終結(jié)符，不必知道該非終結(jié)符的名字是什么，因此去掉了單非終結(jié)符的歸約。規(guī)范歸約的可歸約串是句柄，并且必須準(zhǔn)確寫出可歸約串歸約為哪個(gè)非終結(jié)符。第3題:有文法G[S]:SDVVDTViTTDF|T+FFn)V*|(⑴ 給出(+(i(的規(guī)范推導(dǎo)。⑵ 指出句型F+Fi(的短語，句柄，素短語。⑶G[S]是否為OPG?若是，給出(1)中句子的分析過程。I答案:V/I、ViT(1)S=>V=>ViT=)ViF=>Vi(=)Ti(=)T+Fi(=>T+(i(=)F+(i(=>(+(i(]](2｝句型F+Fi(的語法樹： _ /、I短語：F,F+F,(,F+Fi(句柄：F素短語：( :+F(F(3)FIRSTVTLASTVTFIRSTVTLASTVTsi,+?)?(i,+,%(VT+?(.*F*?(算符優(yōu)先關(guān)系

?+*()#■1*—->*()*<三因?yàn)樵撐姆ㄊ荗P,同時(shí)任意兩個(gè)終結(jié)符的優(yōu)先關(guān)系唯一，所以該文法為OPGo(+(i(的分析過程步驟棧優(yōu)先關(guān)系當(dāng)前符號剩余輸入串移進(jìn)或歸約1((~(ifi：移進(jìn)2#((店++(if.'i歸約3#F(i(#移進(jìn)4+?i梓移進(jìn)5#F+((為i?f歸約6#F+F+耳i■(片歸約r/■v-F■移進(jìn)8#Fii?：2移進(jìn)9弄Fi(ft歸約10ftFiFft歸約11n接受文法G[S]為:STS；GIGGTGCT)IHHTaI(S)TTT+SIS(1)構(gòu)造G[S]的算符優(yōu)先關(guān)系表，并判斷G[S]是否為算符優(yōu)先文法。給岀句型a(T+S);H；(S)的短語、句柄、素短語和最左素短語。給岀a;(a+a)和Q+a)的分析過程，說明它們是否為G[S]的句子。給岀(3)中輸入串的最右推導(dǎo)，分別說明兩輸入串是否為G[S]的句子。⑸由⑶和⑷說明了算符優(yōu)先分析的哪些缺點(diǎn)o〔符優(yōu)先分析過程和規(guī)范歸約過程都是最右推導(dǎo)的逆過程嗎？答案:(1)構(gòu)造文法G[S]的算符優(yōu)先關(guān)系矩陣:()af()a+?><??>?〉<?<?<?<??>?><?<??>二??>?>?><?<?<?<??><??>?>?>■?>?>二?在匕衷中可看出終結(jié)符之何的優(yōu)先關(guān)系是唯-的，或稱G[S]的篦符優(yōu)先關(guān)系矩陣不含多重入口，丙此，G[S]是一個(gè)算符優(yōu)先文法。短語：a相對H.GT+S相對Ta(T+S)相對G、SH相對Ga(T+S);H相對S(S)相對H.Ga(T+S);H;(S)相對S句柄：a(2)素短語：T+S-最左素短語：T+S(3)對輸入邱(3P)#的分析過程如F：步驟棧當(dāng)前符號剩余輸入岀移進(jìn)或0」約(1)(移進(jìn)(2)ap)#移進(jìn)(3)有Q+a)#歸約⑷#(N—a)#移進(jìn)(5)#(N+a沖移進(jìn)(6)#(N+a)ft歸約(7)有(N+N)歸約(8)#(N)移進(jìn)(9)H(N)it歸約(10)n分析成功說明定它的句子。⑷試用規(guī)范推導(dǎo):SnG二〉H二〉(S)由此往下S不可能推導(dǎo)岀a+a,所以(a+a)不是G[S]的句子。(5)結(jié)果說明：由于算符優(yōu)先分析法去抻了單非終結(jié)符之間的歸約，盡管在分析過程