《編譯原理》西北工業(yè)大學(xué)第三版課后答案

1、目錄目錄第一章習(xí)題解答............................................................................................................................1第二章習(xí)題解答.............................................................................

2、...............................................22.構(gòu)造產(chǎn)生下列語(yǔ)言的文法............................................................................................23.描述語(yǔ)言特點(diǎn)..........................................................

3、.....................................................37.解：...............................................................................................................................510.證明：因?yàn)榇嬖诰渥樱篴bc，它對(duì)應(yīng)有兩個(gè)語(yǔ)法樹(shù)（或最右推導(dǎo)）：

4、.................711.解：.............................................................................................................................715.消除下列文法中的無(wú)用產(chǎn)生式和單產(chǎn)生式..................................................

5、..........10第三章習(xí)題解答..........................................................................................................................10第四章習(xí)題解答......................................................................

6、....................................................24第四章習(xí)題參考答案第四章習(xí)題參考答案............................................................................................................2435解：..................................

7、.........................................................................................3736解：...........................................................................................................................40

8、37解：...........................................................................................................................4238解：.......................................................................................

9、....................................4339解：識(shí)別活前綴的DFA及LR(0)分析表：..............................................................5040解：求LR(1)項(xiàng)目集和狀態(tài)轉(zhuǎn)換表：......................................................................5441解

10、：...........................................................................................................................5542解：..........................................................................................

11、.................................59第五章習(xí)題解答..........................................................................................................................645.8解：.................................................

12、........................................................................65第一章第一章習(xí)題解答習(xí)題解答1.解：源程序是指以某種程序設(shè)計(jì)語(yǔ)言所編寫(xiě)的程序。目標(biāo)程序是指編譯程序（或解釋程序）將源程序處理加工而得的另一種語(yǔ)言（目標(biāo)語(yǔ)言）的程序。翻譯程序是將某種語(yǔ)言翻譯成另一種語(yǔ)言的程序的統(tǒng)稱。編譯程序與解釋程序均為翻譯程序，但二者工作方法不同。解釋程序的特點(diǎn)是并不先將高

13、級(jí)語(yǔ)言程序全部翻譯成機(jī)器代碼，而是每讀入一條高級(jí)語(yǔ)言程序語(yǔ)句，就用解釋程序?qū)⑵浞g成一段機(jī)器指令并執(zhí)行之，然后再讀入下一條語(yǔ)句繼續(xù)進(jìn)行解釋、執(zhí)行，如此反復(fù)。即邊解釋邊執(zhí)行，翻譯所得的指令序列并不保存。編譯程序的特點(diǎn)是先將高級(jí)語(yǔ)言程序翻譯成機(jī)器語(yǔ)言程序，將其保存到指定的空間中，在用戶需要時(shí)再執(zhí)行之。即先翻譯、后執(zhí)行。2.解：一般說(shuō)來(lái)，編譯程序主要由詞法分析程序、語(yǔ)法分析程序、語(yǔ)義分析程序、中間代碼生成程序、代碼優(yōu)化程序、目標(biāo)代碼生成程序、

14、信息表管理程序、錯(cuò)誤檢查處理程序組成。（5）任何不是以0打頭的所有奇整數(shù)所組成的集合解：G(S)=(SABIJ0123456789S→J|IBJB→0B|IB|eI→J|2|4|6|8J→1|3|5|7|9S)（6）所有偶數(shù)個(gè)0和偶數(shù)個(gè)1所組成的符號(hào)串集合解：對(duì)應(yīng)文法為S→0A|1B|e，A→0S|1CB→0C|1SC→1A|0B3.描述語(yǔ)言特點(diǎn)描述語(yǔ)言特點(diǎn)（1）S→10S0S→aAA→bAA→a解：本文法構(gòu)成的語(yǔ)言集為：L(G)=(1

15、0)nabma0n|nm≥0。（2）S→SSS→1A0A→1A0A→ε解：L(G)=1n10n11n20n2…1nm0nm|n1n2…nm≥0；且n1n2…nm不全為零該語(yǔ)言特點(diǎn)是：產(chǎn)生的句子中，0、1個(gè)數(shù)相同，并且若干相接的1后必然緊接數(shù)量相同連續(xù)的0。（3）S→1AS→B0A→1AA→CB→B0B→CC→1C0C→ε解：本文法構(gòu)成的語(yǔ)言集為：L(G)=1p1n0n|p≥1n≥0∪1n0n0q|q≥1n≥0，特點(diǎn)是具有1p1n0n或1

16、n0n0q形式，進(jìn)一步，可知其具有形式1n0mnm≥0且nm0。（4）S→bAdcA→AGSG→εA→a解：可知，S=…=baSndcn≥0該語(yǔ)言特點(diǎn)是：產(chǎn)生的句子中，是以ba開(kāi)頭dc結(jié)尾的串且ba、dc個(gè)數(shù)相同。（5）S→aSSS→a解：L(G)=a(2n1)|n≥1可知：奇數(shù)個(gè)a4.解：此文法產(chǎn)生的語(yǔ)言是：以終結(jié)符a1、a2…an為運(yùn)算對(duì)象，以∧、∨、~為運(yùn)算符，以[、]為分隔符的布爾表達(dá)式串5.5.1解：由于此文法包含以下規(guī)則：A