編譯原理答案++陳意云+高等教育出版社

1、編譯原理習題參考答案（一）zpli 2004-3-7version 1.1Page 1 of 7編譯原理習題參考答案（一）編譯原理習題參考答案（一）Bug report:.c nOr find:電一樓二樓全球計算實驗室李兆鵬第二章2.3敘述由下列正規(guī)式描述的語言a) 0(0| 1)*0b) (技)1*)*c) (0|1)*0(0|1)(0|1)d) 0*10*10*10*e) (00|11)*(01|10)(00|11)*(01|10)(00|11)*)*An swer:a）以0開始和結尾，而且長度大于等于2的0、1串b）所有0,1串（含空串）c）倒數(shù)第三位是

2、0的0、1串d）僅含3個1的0、1串e）偶數(shù)個0和偶數(shù)個1的0、1串（含空串）2.4為下列語言寫出正規(guī)定義：f）由偶數(shù)個0和偶數(shù)個1構成的所有0和1的串g）由偶數(shù)個0和奇數(shù)個1構成的所有0和1的串An swer:標準答案見 編譯原理習題精選P1-P2 1.1 &1.2 題給出它們處理輸入串a(chǎn)babbab的2.7用算法2.4為下列正規(guī)式構造非確定的有限自動機,轉換序列c) ( e|a ) b*) d)(a|b)*abb(a|b)*An swer:c)NFA :輸入串a(chǎn)babbab的轉換序列：0 1456789 145678 789 1456789 10Or 0 1456789 14567

3、89 1236789 1456789 10d) NFA:eezpli 2004-3-7version 1.1Page 3 of 7編譯原理習題參考答案（一）zpli 2004-3-7version 1.1Page # of 7編譯原理習題參考答案（一）輸入串a(chǎn)babbab的轉換序列：0 1236 1456 789 10 11 12 13 16 11 14 15 16 172.8用算法2.2把習題2.7的NFA變換成DFA。給出它們處理輸入串a(chǎn)babbab的狀態(tài)轉 換序列。An swer:/針對 2.7 (c)zpli 2004-3-7version 1.1Page # of 7編譯原理習題參考

4、答案（一）zpli 2004-3-7version 1.1Page # of 7編譯原理習題參考答案（一）3個不同的狀態(tài)集合：A = 0, 1,2, 3, 4, 6, 7, 9, 10B = 1,2, 3, 4, 5, 6, 7, 9, 10C = 1,2, 3, 4, 6, 7, 8, 9, 10NFA的轉換表：子集構造法應用于狀態(tài)輸入符號a bA BCB BCC BCzpli 2004-3-7version 1.1Page # of 7編譯原理習題參考答案(一)2.11我們可以從正規(guī)式的最簡DFA同構來證明兩個正規(guī)式等價。使用這種技術，證明下面正規(guī)式等價。(a) (a|b)*(b) (a*

5、|b*)*(c) (£|a)b*)*An swer:(c ) NFA見2.7 (c)用子集構造法化簡得DFA見2.8。最簡的DFA為:Startzpli 2004-3-7version 1.1Page 5 of 7編譯原理習題參考答案(一)zpli 2004-3-7version 1.1Page # of 7編譯原理習題參考答案(一)同理可求出(b)正規(guī)式對應的最簡 DFA亦是如此，故(b)(c) 等價。2.15修改算法2.4,使之盡可能少使用&轉換，并保持所產(chǎn)生的NFA只有一個接收狀態(tài)An swer:算法.4改進(a)N(s)N(t)開始狀態(tài)合并作為N(s|t)的開始狀態(tài)N

6、(s)N(t)接受狀態(tài)合并作為N(s|t)的接受狀態(tài)(C)N(s)開始狀態(tài)與接受狀態(tài)合并成一個狀態(tài)j。start izpli 2004-3-7version 1.1Page # of 7編譯原理習題參考答案(一)zpli 2004-3-7version 1.1Page # of 7編譯原理習題參考答案(一)注意：必須保留一個i和f,否則可能在算法遞歸產(chǎn)生NFA過程中會出問題zpli 2004-3-7version 1.1Page # of 7編譯原理習題參考答案(一)zpli 2004-3-7version 1.1Page # of 7編譯原理習題參考答案(一)第三章3.2考慮文法S aSbS

7、 | bSaS |£(a) 為句子abab構造兩個不同的最左推導，以此說明該文法是二義的(b) 為abab構造對應的最右推導。(c) 為abab構造對應的分析樹。(d) 這個文法產(chǎn)生的語言是什么？An swer:S? Im aSbSS ? Im aSbS? Im abS? Im abSaSbS? Im abaSb S? Im abaSbS? Im ababS? Im ababS? Im abab - CD? Imabab-可知，對于句子abab存在兩個不 冋的最左推導， 所以該文法是二義的(b)(d )；?rm aSbS?rmaSb?rmabSaS b?rmabSab?rmabab(

8、c )I?rm aSbS?rmaSbaSbS?rmaSbaSb?rmaSbab?rmabab該文法產(chǎn)生a、b個數(shù)相等的ab串(含空串)3.4文法R>R | ' R | RR | R* | (R) | a | b產(chǎn)生字母表a,b上所有不含&的正規(guī)式。注意，第一條豎線是正規(guī)式的符號“或”，而 不是文法產(chǎn)生式右部各選擇之間的分隔符，另外“*”在這兒是一個普通的終結符。該文法是二義的。(b) 為該文法寫一個等價的非二義的文法。它給予算符*、鏈接和|的優(yōu)先級和結合性同2.2節(jié)中定義的一致。(c) 按上面兩個文法構造句子ab|b*a 的分析樹。An s wer:(b) 標準答案見編譯

9、原理習題精選P17(c) 原文法的分析樹：/文法二義，存在多個分析樹Rbbzpli 2004-3-7version 1.1Page 7 of 7編譯原理習題參考答案(一)zpli 2004-3-7version 1.1Page # of 7編譯原理習題參考答案(一)無二義文法的分析樹zpli 2004-3-7version 1.1Page # of 7編譯原理習題參考答案(一)zpli 2004-3-7version 1.1Page # of 7編譯原理習題參考答案(一)zpli 2004-3-7version 1.1Page # of 7編譯原理習題參考答案（一）3.6為字母表a,b上的下列

10、每個語言設計一個文法，其中哪些語言是正規(guī)的?(a) 每個a后面至少有一個b跟隨的所有串(b) a和b的個數(shù)相等的所有串An swer: S abS| bS |£該語言是正規(guī)，對應的正規(guī)式是(ab|b)*(b) 解法一：S aSbS | bSaS |£解法二：S -aB | bA |£A aS | bAAB 侮 | aBB解法三：S -abS | aSb | Sab | baS | bSa | Sba |該文法不是正規(guī)的。3.8(a)消除習題3.1文法的左遞歸(b)為(a)的文法構造預測分析器An swer: S (L) | aLS L1+L1 ，&

11、3;(b)上述文法的預測分析器為： procedure match(t:toke n);beginif lookahead = t the n lookahead := n exttoke n()else error() en d;procedure s;beginif lookahead = (' thenbeginmatch( (' ); L(); match( ')') endelse if lookahead = a' thenmatch( a')else error()en d;procedure L;beginS()；L1()en d;procedure L1;beginif lookahead =, ' thenbeginmatch( , ' ); S(); L1()e