編譯原理計算題

編譯原理計算題1、寫一個文法，使其語言是奇數(shù)集，且每個奇數(shù)不以0開頭。(5分)2、 設(shè)文法G(S)：Sf(L)|aS|aL-L,S|S消除左遞歸和回溯；計算每個非終結(jié)符的FIRST和FOLLOW；構(gòu)造預(yù)測分析表。3、 Whilea>0Vb<0doBeginX：=X+1；ifa>0thena：=a—lelseb：=b+lEnd；翻譯成四元式序列。(7分)4、 已知文法G(E)E-T|E+TT-F|T*FF-(E)|i(1)給出句型(T*F+i)的最右推導(dǎo)及畫出語法樹；⑵給出句型(T*F+i)的短語、素短語。(7分)5、設(shè)布爾表達(dá)式的文法為E—E(1)VE(2)E-E(1)AE(2)E—i假定它們將用于條件控制語句中，請(1)改寫文法，使之適合進(jìn)行語法制導(dǎo)翻譯和實現(xiàn)回填；(2)寫出改寫后的短個產(chǎn)生式的語義動作。(6分)6、設(shè)有基本塊Tl：=2T2：=10/TT3：=S—RT4：=S+RA：=T2*T4B：AT5：=S+RT6：=T3*T5B：=T6⑴畫出DAG圖；(2)假設(shè)基本塊出口時只有A,B還被引用，請寫出優(yōu)化后的四元序列。(6分)7、已知文法G(S)S—a|Al(T)寫出句子((a,a),a)的規(guī)范歸約過程及每一步的句柄。8、已知文法G(S):S-a|(T)T-T,S|S的優(yōu)先關(guān)系表如下:關(guān)系a()aJJ(<<=<)>><<>>請計算出該優(yōu)先關(guān)系表所對應(yīng)的優(yōu)先函數(shù)表。9、寫一個文法,使其語言是偶數(shù)集,且每個偶數(shù)不以0開頭。(5分)10、已知文法G(S):S—a|Al(T)T—T,S|S⑴給出句子(a,(a,a))的最左推導(dǎo)并畫出語法樹；⑵給出句型((T,S),a)的短語、直接短語、句柄。(8分)11、把語句ifx>0Ay>0thenz:=x+yelsebeginx:=x+2;y:=y+3END;翻譯成四元式序列。(6分)12、設(shè)某語言的for語句的形式為fori:=E(1)TOE(2)doS其語義解釋為i:=E(1);LIMIT:=E(2);again:ifi<=LIMITthenBEGINS;i:=i+1;gotoagainEND;⑴寫出適合語法制導(dǎo)翻譯的產(chǎn)生式；⑵寫出每個產(chǎn)生式對應(yīng)的語義動作。(6分)13、設(shè)文法G(S):S—S+aF|aF|+aFFf*aF|*a⑴消除左遞歸和回溯；⑵構(gòu)造相應(yīng)的FIRST和FOLLOW集合;⑶構(gòu)造預(yù)測分析表(10分)14、對以下基本塊T1:=2T2:=A-BT3:=A+BT4:=T2*T3T5:=3*T1T6:=A-BL:=A+BT7:=T6*LT8:=T5*4M:=T8+T7L:=M

⑴畫出DAG圖；⑵假設(shè)只有L在基本塊出口之后還被引用，請寫出優(yōu)化后的四元式序列。（6分）15、（8分）化簡文法G[S]S—ASe|BCaD|aD|ACA—Cb|DBSC—bC|dB—AcD—aD16、（12分）設(shè)Li{a,b,c}*是滿足下述條件的符號串構(gòu)成的語言:（1） 若出現(xiàn)a，則其后至少緊跟兩個c；（2） 若出現(xiàn)b，其后至少緊跟一個c。試構(gòu)造識別L的最小化的DFA，并給出描述L的正規(guī)表達(dá)式。-qbP|q17、（12分）已給文法G[S]:S-SaP|-qbP|q將G[S]改造成LL（1）文法，并給出LL（1）分析表。18、（12分）給定文法G[S]:S-Aa|dAb|Bb|dBaA-cB構(gòu)造文法G[S]的LR（1）分析表。19、（8分）將下面的條件語句表示成逆波蘭式和四元式序列ifa>bthenx:=a+b*celsex:=b-a;

20、(8分)給定基本塊：A:=3*5B:=E+FC:=A+12D:=E+FA:=D+12C:=C+1E:=E+FE是活躍的，給出用DAG圖完成優(yōu)假定出基本塊后，只有AE是活躍的，給出用DAG圖完成優(yōu)1、寫一個文法，使其語言是奇數(shù)集，且每個奇數(shù)不以0開頭。(5分)解：文法G(N)：N—AB|BA—AC|DB—l|3|5|7|9D—B|2|4I6I8CfO|D (5分)2、設(shè)文法G(S)：Sf(L)|aS|aL—L,SIS(1)消除左遞歸和回溯；計算每個非終結(jié)符的FIRST和FOLLOW；構(gòu)造預(yù)測分析表。解：(1)S—(L)|aS'SJS|￡L—SL'LJSL'|￡評分細(xì)則：消除左遞歸2分,提公共因子2分。

FIRST)S)={(,a}FIRST(S')={,FIRST)S)={(,a}FIRST(S')={,a,￡}FIRST(L)={(,a}FIRST(L')={,,￡}FIRST(L')={,,￡}FOLLOW(L'〕={)}3、Whilea>0VbVOdoBeginX：=X+1；ifa>0thena：=a—1elseb：=b+1End；翻譯成四元式序列。(7分)解：(j>，a，0，5)(j，－，－，3)(jV,b,0,5)(j，－，－，15)(+,x,1,T1)(:=,T1,—,x)(j>,a,0,9)(j，—，—，12)(—，a，1，T2)(：=，T2，—，a)(j，—，—，1)(＋，b，1，T3)(：=，T3，—，b)(j，—，—，1)(15)評分細(xì)則：控制結(jié)構(gòu)4分，其它3分。4、已知文法G(E)E—T|E+TT—F|T*FF-(E)|i給出句型(T*F+i)的最右推導(dǎo)及畫出語法樹;給出句型(T*F+i)的短語、素短語。(7分)解：(1)最右推導(dǎo)：ETF(E)(E+T)(E+F)(E+i)(T+i)(T*F+i)(2)短語：(T*F+i)，T*F+i，T*F，i (2分)(1分)(1分)5、設(shè)布爾表達(dá)式的文法為E—E(1)VE(2)E—E(1)AE(2)E—i假定它們將用于條件控制語句中，請改寫文法，使之適合進(jìn)行語法制導(dǎo)翻譯和實現(xiàn)回填；寫出改寫后的短個產(chǎn)生式的語義動作。(6分)解：(1)E0—E(1)E—E0E(2)EA—E(1)E—EAE(2)E—i (3分)(2)E—E(1){BACKPATCH(E(1)?FC,NXQ)；EO?TC：=E(1)?TC}E—E0E(2){E?FC：=E(2)?FC；E?TC：=MERG(EO?TC,E(2)?TC)}EA—E(1){BACKPATCH(E(1)?TC,NXQ)；E0?FC：=E(1)?FC}E—EAE(2){E?TC：=E(2)?TC；E?FC：=MERG(EA?FC,E(2)?FC}E—i{E?TC：=NXQ；E?FC：=NXQ+1；GEN(jn2,entry(i),－0)；GEN(j,－,－,0) (3分)6、設(shè)有基本塊T1：=2T2：=10/TT3：=S-RT4：=S+RA：=T2*T4B：AT5：=S+RT6：=T3*T5B：=T6畫出DAG圖；假設(shè)基本塊出口時只有A,B還被引用，請寫出優(yōu)化后的四元序列。(6分)

解：(l)DAG：(2)優(yōu)化后的四元式T3：=S—RT4：=S+RA：=5*T4(3分)B：=T3(3分)7、已知文法G(S)S—a|Al(T)T—T,SIS寫出句子((a,a),a)的規(guī)范歸約過程及每一步的句柄。句型歸約規(guī)則((a,a)句型歸約規(guī)則((a,a),a)S—a((S,a),a)T—S((T,a),a)S—a((T,S),a)T—T,S((S),a)T—S((T),a)S—S(T)(S,a)T—S(T,a)S—a(T,S)T—T,S(T)S—(T)句柄aSaT,SS(T)SaT,S(T)(4分)8、答：優(yōu)先函數(shù)表如下f函數(shù)2分，g函數(shù)2分)10、已知文法G(S):S—a|Al(T)T—T,S|S⑴給出句子(a,(a,a))的最左推導(dǎo)并畫出語法樹；⑵給出句型((T,S),a)的短語、直接短語、句柄。(8分)11、把語句ifx>0Ay>0thenz:=x+yelsebeginx:=x+2;y:=y+3END;翻譯成四元式序列。(6分)12、 設(shè)某語言的for語句的形式為fori:=E(1)TOE(2)doS其語義解釋為i:=E(1);LIMIT:=E(2);again:ifi<=LIMITthenBEGINS;i:=i+1;gotoagainEND;⑴寫出適合語法制導(dǎo)翻譯的產(chǎn)生式；⑵寫出每個產(chǎn)生式對應(yīng)的語義動作。(6分)13、 設(shè)文法G(S):S—S+aF|aF|+aFFf*aF|*a⑴消除左遞歸和回溯；⑵構(gòu)造相應(yīng)的FIRST和FOLLOW集合；⑶構(gòu)造預(yù)測分析表(10分)14、對以下基本塊T1:=2T2:=A-BT3:=A+BT4:=T2*T3T5:=3*T1T6:=A-BL:=A+BT7:=T6*LT8:=T5*4M:=T8+T7L:=M⑴畫出DAG圖；⑵假設(shè)只有L在基本塊出口之后還被引用，請寫出優(yōu)化后的四元式序列。(6分)9、答：文法G(S):S-AB|B|A0A—AD|CB-2|4|6|8Cfl|3|5|7|9|B

D-O|C10、答：最左推導(dǎo)：(2分)S=>(T)=>(T,S)=>(S,S)=>(a,S)=>(a,(T))=>(a,(T,S))=>(a,(S,S))=>(a,(a,S))=>(a,(a,a))語法樹：(2分，此處略)11、答：⑴(j>,x,0,3)⑵(j,-,-,8)⑶(j>,y,0,5)⑷(j,-,-,8)⑸(+,x,y,T1)⑹(:=,T1,-,Z)⑺(j,-,-,12)⑻(+,x,2,T2)⑼(:=,t2,-,X)⑽(+,Y,3,t3)(:=,T3,-,y)(12)(控制結(jié)構(gòu)3分，其它3分)12、答：⑴(2分)Fffori:=E(1)toE(2)doS-FS(1)⑵(每個語義動作2分)F-fori:=E(1)toE(2)do{GEN(:=,E(1).place,-,entry(i));F.place:=entry(i);LIMIT:=Newtemp;GEN(:=,E(2).place,-,LIMIT);:=NXQ;F.QUAD:=q;GEN(jW,entry(i),LIMIT,q+2)F.chain:=NXQ;G)j,-,-,0)}S-FS(1){BACKPATCH(S(1).chain,NXQ);GEN(+,F.place,1,F.place);GEN(j,-,-,F.QUAD);S.chain:=F.chain}13、答:⑴(消除左遞歸2分，提公共左因子2分)S-aFS'1+aFS'S'f+aFS'|￡F_*aF'F'—F|￡⑵(3分)FIRST(S)二{a,+}FOLLOW(S)二{#}FIRST(S')二{+,￡}FOLLOW(S')二{#}FIRST(F)={*}FOLLOW(F)二{+,#}FIRST(F')={*,￡)FOLLOW(F')二{+,#}⑶(3分)一a+*#SS-aFS'S-+aFS'一一S'一S'-+aFS'一S'-eF一一F—*aF'一F'一F'-eF'—FF'-e14、 答：⑴DAG（3分，此處略）⑵四元式序列：（3分）T2:=A-BT3:=A+BT4:=T2*T3L:=T4+2415、 化簡后：S—ASe|ACA—CbC—bC|d16、 DFA如圖所示。相應(yīng)的正規(guī)式為（c|acc|bc）*。217、改造后的文法：S-PS'S'-aPS'lfS'|eP-qP'P'-bP|e各候選式的FIRST集，各非終結(jié)符的FOLLOW集為產(chǎn)生式FIRST集FOLLOW集

SfPS'{q}{#}S'faPS'ffS'fe{a}{f}{e}{#}PfqP'{q}{a,f,#}P'fbPfe{e}{a,f,#}LL(1)分析表為bf■1ssnaPS1fS1ETP1EE■MP1：'E18、分析表如下圖所示狀巒JETTONGOTCiabcdasA