編譯原理 試題解答

《編譯原理 試題解答》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、一、簡答題（15分）1.編譯程序與解釋程序有何區(qū)別？2.何謂素短語？3.過程調(diào)用時，主調(diào)程序與被調(diào)程序之間的信息傳遞有哪些方式？4.何謂語法制導(dǎo)翻譯？5.何謂算符文法？二、選擇題（10分）1.描述一個語言的文法是（）A.唯一的B.不唯一的C.可能唯一，也可能不唯一2.若文法G定義的語言是無限集，則文法必然是（）A.前后文無關(guān)文法B.正規(guī)文法C.二義性文法D.遞歸文法3.數(shù)組的內(nèi)情向量中肯定不含數(shù)組的（）信息A.維數(shù)B.類型C.各維的上下界D.各維的界差4.簡單優(yōu)先分析每次歸約的是（）A.最左直接短語B.直接短語C.最左素短語D.控制結(jié)點(diǎn)5.最

2、適合動態(tài)建立數(shù)據(jù)實(shí)體的內(nèi)存分配方式是（）A.棧式分配B.堆式分配C.編譯時預(yù)先分配D.以上三種均可三、（10分）給定文法G=（{S,L}，{a，（，）}，{S→(L)

3、aL→L,S

4、S}，S）。給出句型”(S,(a))”的推導(dǎo)和語法樹并指出此句型的所有短語、直接短語、句柄和素短語。四、（12分）設(shè)語言L是由奇數(shù)個a和偶數(shù)（可以是0）個b組成的符號串之集。1.構(gòu)造識別L的DFA；2.給出定義L的正規(guī)文法；五、（10分）將文法G[S]：S→[AA→AS

5、B]B→Bi

6、i改寫為等價的LL(1)文法，并給出相應(yīng)的LL(1)分析表。六、（20分）給定文

7、法G[S]：S→(S)

8、a1.構(gòu)造識別文法G[S]活前綴的LR(1)項(xiàng)目的DFA；2.構(gòu)造LR(1)分析表；3.合并同心集，構(gòu)造LALR(1)分析表。七、（8分）某語言算術(shù)表達(dá)式的文法定義為E→E+E

9、i

10、ifBthenEelseE其中，第三個候選式稱為條件算術(shù)表達(dá)式，B為布爾表達(dá)式，then及else后的E均為算術(shù)表達(dá)式（即簡單算術(shù)表達(dá)式或條件表達(dá)式），其語義為，當(dāng)B為真時，表達(dá)式的值取then后的E的值，否則取else的E的值。假定所有表達(dá)式是整型的，試將下面關(guān)于條件算術(shù)表達(dá)式的屬性翻譯文法填寫完全：?八、（8分）給定PASCAL程序語句

11、whilea>bdoifa>0thena:=a-1elsea:=a+1;?1.將該語句翻譯成逆波蘭式；2.給出編譯程序掃描到then處及分號處時所得的四元式序列。九、(7分)用DAG圖對下面的基本塊進(jìn)行優(yōu)化（假定出基本塊后只有A、G、L是活躍的）：A=B*CD=B/CE=2*3F=E+2G=B*CK=E+FG=K*KL=B/C試題答案參考答案：一、簡答題（15分）1.編譯程序與解釋程序有何區(qū)別？答：二者的工作方法不同，后者是邊解釋邊執(zhí)行，解釋所得的代碼并不保存；前者是先將高級語言翻譯感情上標(biāo)代碼，將其保存到指定的空間中，待需要時再執(zhí)行之，甚至

12、可以在案一個機(jī)器上編譯，而在另一臺機(jī)器上執(zhí)行。2.何謂素短語？答：素短語是滿足下述條件的短語：（1）它至少含有一個終結(jié)符號（2）滿足條件（1）的“最小”短語3.過程調(diào)用時，主調(diào)程序與被調(diào)程序之間的信息傳遞有哪些方式？答：形式參數(shù)與實(shí)在參數(shù)結(jié)合方式傳遞（簡稱參數(shù)傳遞）、返回值傳遞、共享數(shù)據(jù)區(qū)傳遞。4.何謂語法制導(dǎo)翻譯？答：語法制導(dǎo)翻譯是對前后文無關(guān)文法的擴(kuò)充，即對文法中的每個產(chǎn)生式都附加一個語義動作或語義子程序，且在語法分析過程中，每當(dāng)需要使用一個產(chǎn)生式進(jìn)行推導(dǎo)或歸約時，語法分析程序除執(zhí)行相應(yīng)的語法分析動作外，還要執(zhí)行相應(yīng)的語義動作或調(diào)用相應(yīng)的

13、語義子程序，完成相應(yīng)的語義分析和翻譯工作。5.何謂算符文法？答：當(dāng)一個文法的所有產(chǎn)生式的右部均不出現(xiàn)兩個非終結(jié)符號相鄰的情況時，該就被稱為算符文法。二、選擇題（10分）1.描述一個語言的文法是（B）A.唯一的B.不唯一的C.可能唯一，也可能不唯一2.若文法G定義的語言是無限集，則文法必然是（D）A.前后文無關(guān)文法B.正規(guī)文法C.二義性文法D.遞歸文法3.數(shù)組的內(nèi)情向量中肯定不含數(shù)組的（B）信息A.維數(shù)B.類型C.各維的上下界D.各維的界差4.簡單優(yōu)先分析每次歸約的是（C）A.最左直接短語B.直接短語C.最左素短語D.控制結(jié)點(diǎn)5.最適合動態(tài)建立

14、數(shù)據(jù)實(shí)體的內(nèi)存分配方式是（B）A.棧式分配B.堆式分配C.編譯時預(yù)先分配D.以上三種均可三、（10分）給定文法G=（{S,L}，{a，（，）}，{S→(L)

15、aL→L,S

16、S}，S）。給出句型”(S,(a))”的推導(dǎo)和語法樹并指出此句型的所有短語、直接短語、句柄和素短語。?解：ST(L)T(L,S)T(L,(L))T(L,(S))T(L,(a))T(S,(a))短語有：“a”,“(a)”,“S”，“S,(a)”，“（S,(a)）”。直接短語有：”S”，“a”句柄：“S”素短語：“a“語法樹略。四、（12分）設(shè)語言L是由奇數(shù)個a和偶數(shù)（可以是0

17、）個b組成的符號串之集。1.構(gòu)造識別L的DFA；2.給出定義L的正規(guī)文法；解：1。見圖：2．S?aA

18、bBA?aS

19、bC

20、eB?bS

21、aCC?bA

22、aB五、（10分