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

1、目錄目錄第一章習題解答............................................................................................................................1第二章習題解答.............................................................................

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

3、.....................................................37.解：...............................................................................................................................510.證明：因為存在句子：abc，它對應有兩個語法樹（或最右推導）：

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

5、..........10第三章習題解答..........................................................................................................................10第四章習題解答......................................................................

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

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

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

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

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

11、.................................59第五章習題解答..........................................................................................................................645.8解：.................................................

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

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

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

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

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