編譯原理計(jì)算題

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

⑴畫(huà)出DAG圖；⑵假設(shè)只有L在基本塊出口之后還被引用，請(qǐng)寫(xiě)出優(yōu)化后的四元式序列。（6分）15、（8分）化簡(jiǎn)文法G[S]S—ASe|BCaD|aD|ACA—Cb|DBSC—bC|dB—AcD—aD16、（12分）設(shè)Li{a,b,c}*是滿足下述條件的符號(hào)串構(gòu)成的語(yǔ)言:（1） 若出現(xiàn)a，則其后至少緊跟兩個(gè)c；（2） 若出現(xiàn)b，其后至少緊跟一個(gè)c。試構(gòu)造識(shí)別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分）將下面的條件語(yǔ)句表示成逆波蘭式和四元式序列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、寫(xiě)一個(gè)文法，使其語(yǔ)言是奇數(shù)集，且每個(gè)奇數(shù)不以0開(kāi)頭。(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)消除左遞歸和回溯；計(jì)算每個(gè)非終結(jié)符的FIRST和FOLLOW；構(gòu)造預(yù)測(cè)分析表。解：(1)S—(L)|aS'SJS|￡L—SL'LJSL'|￡評(píng)分細(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)評(píng)分細(xì)則：控制結(jié)構(gòu)4分，其它3分。4、已知文法G(E)E—T|E+TT—F|T*FF-(E)|i給出句型(T*F+i)的最右推導(dǎo)及畫(huà)出語(yǔ)法樹(shù);給出句型(T*F+i)的短語(yǔ)、素短語(yǔ)。(7分)解：(1)最右推導(dǎo)：ETF(E)(E+T)(E+F)(E+i)(T+i)(T*F+i)(2)短語(yǔ)：(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假定它們將用于條件控制語(yǔ)句中，請(qǐng)改寫(xiě)文法，使之適合進(jìn)行語(yǔ)法制導(dǎo)翻譯和實(shí)現(xiàn)回填；寫(xiě)出改寫(xiě)后的短個(gè)產(chǎn)生式的語(yǔ)義動(dòng)作。(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畫(huà)出DAG圖；假設(shè)基本塊出口時(shí)只有A,B還被引用，請(qǐng)寫(xiě)出優(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寫(xiě)出句子((a,a),a)的規(guī)范歸約過(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)并畫(huà)出語(yǔ)法樹(shù)；⑵給出句型((T,S),a)的短語(yǔ)、直接短語(yǔ)、句柄。(8分)11、把語(yǔ)句ifx>0Ay>0thenz:=x+yelsebeginx:=x+2;y:=y+3END;翻譯成四元式序列。(6分)12、 設(shè)某語(yǔ)言的for語(yǔ)句的形式為fori:=E(1)TOE(2)doS其語(yǔ)義解釋為i:=E(1);LIMIT:=E(2);again:ifi<=LIMITthenBEGINS;i:=i+1;gotoagainEND;⑴寫(xiě)出適合語(yǔ)法制導(dǎo)翻譯的產(chǎn)生式；⑵寫(xiě)出每個(gè)產(chǎn)生式對(duì)應(yīng)的語(yǔ)義動(dòng)作。(6分)13、 設(shè)文法G(S):S—S+aF|aF|+aFFf*aF|*a⑴消除左遞歸和回溯；⑵構(gòu)造相應(yīng)的FIRST和FOLLOW集合；⑶構(gòu)造預(yù)測(cè)分析表(10分)14、對(duì)以下基本塊T1:=2T2:=A-BT3:=A+BT4:=T2*T3T5:=3*T1T6:=A-BL:=A+BT7:=T6*LT8:=T5*4M:=T8+T7L:=M⑴畫(huà)出DAG圖；⑵假設(shè)只有L在基本塊出口之后還被引用，請(qǐng)寫(xiě)出優(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))語(yǔ)法樹(shù)：(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)⑵(每個(gè)語(yǔ)義動(dòng)作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、 化簡(jiǎn)后：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