編譯原理期末試題及答案

1、第第 頁共6頁四、對于文法G(E):(8分)EBTIE+TT.f|t*fFB(E)li.寫出句型(1*尸包的最右推導(dǎo)并畫出語法樹。.寫出上述句型的短語，直接短語、句柄和素短語。(4分)F(F(E)/1E+T(E+i)(T+i)(T*F+i)(4分)短語：(T*F+i),T*F+i,T*F,i直接短語：T*F,i句柄：T*F素短語：T*F,i九、(9分)設(shè)已構(gòu)造出文法G(S)：(1)SBB(2)BaBAclcABblbBSala解：S-abcSIbcSIcS,S-abcSI.試構(gòu)造與下面G(S)等價的無左遞歸的文法。G(S)：SSa|Nb|cNSd|Ne|f解：S-fNbSIcS,S-aSIdN

2、bSI,N-eNI.設(shè)有文法G(S)：SaBc|bABAaAb|bBb|D口求各產(chǎn)生式的FIRST集，F(xiàn)OLLOW(A)和FOLLOW(B),以及各產(chǎn)生式的SELECT集。構(gòu)造LL(1)分析表，并分析符號串baabbb是否是。解：(1)FIRST(aBc)=a,FIRST(bAB)=bFIRST(aAb)=a,A-b:FIRST(A-b)=b,B-b:FIRST(b)=b,FIRST()=FOLLOW(A)=b,#,FOOLOW(B)=c,#SELECT(S-aBc)=a,SELECT(S-bAB)=b,SELECT(A-aAb)=a,SELECT(A-b)=b,SELECT(B-b)=b,S

3、ELECT(B-)=c,#因此，所得的LL(1)分析表如表A-4所示。表A-4LL(1)分析表弋VN輸入符號abc#SSaBcSbABAAaAbAbBBbBB(2)分析符號串baabbb成功，baabbb是該文法的句子，如圖A-16所示。步驟1符號棧#S輸入串baabbb#所用的產(chǎn)生式SbAB2#BAbbaabbb#3#BAaabbb#AaAb4#BbAaaabbb#5#BbAabbb#AaAb6#BbbAaabbb#7#BbbAbbb#Ab8#Bbbbbbb#9#Bbbbb#10#Bbb#11#B#Be12#成功圖A-16識別串baabbb的過程4.已知文法G(S)：Sa|(T)TT,S|S

4、給出句子(a,a),a)的最左推導(dǎo)并畫出語法口；口給出句型(T,a,(T)所有的短語、直接短語、素短語、最左素短語、句柄和活前綴。解：(1)最左推導(dǎo):S.(T).(T,S).(S,S)(a,S).(a,(T).(a,(T,S)(a,(S,S)(a,(a,S)(a,(a,a)語法樹：如圖A-16所示。圖A-16(a,(a,a)的語法樹(2)句型(。a,(T)的短語、直接短語、素短語、最左素短語、句柄、活前綴及語法樹(圖A-17)。短語：aIIT,aII(T)IIT,a,(T)II(T,a,(T)直接短語：aII(T)素短語：aII(T)最左素短語：a句柄：a活前綴：II(II(TII(T,II(T,a圖的語法樹AI2:Sa，S.aAbA.1A0AIo：S，SSaSaAbS.bS.bBaI3：S.bSbBaBIBOBI1：S?S.JL：S-aAb.8I5：A.1A0I：A.1AO.O、A.lAOkA-.1I12：A.1AO.I6：SBbBaI,0：S.bBa.a/1I7：B.1BOB.IBO、B.,B171,：B-1BO,J_O,I13：B-1BO.，B-rL：S.aAb項目集族和DFA、a+*+、a*+、a+*+、句子aa的規(guī)范歸約過程：步驟符號棧輸入串動作O#b(aa)b#預(yù)備1#b(aa)b#移進2#b(aa)b#移進3#b(aa)b#移進4#b(Aa)b#歸約5#b(Ma)b