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

1、編譯原理習(xí)題參考答案（一）zpli 2004-3-7version 1.1Page 1 of 7編譯原理習(xí)題參考答案（一）編譯原理習(xí)題參考答案（一）Bug report:.c nOr find:電一樓二樓全球計(jì)算實(shí)驗(yàn)室李兆鵬第二章2.3敘述由下列正規(guī)式描述的語(yǔ)言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開始和結(jié)尾，而且長(zhǎng)度大于等于2的0、1串b）所有0,1串（含空串）c）倒數(shù)第三位是

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

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

4、答案（一）zpli 2004-3-7version 1.1Page # of 7編譯原理習(xí)題參考答案（一）3個(gè)不同的狀態(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的轉(zhuǎn)換表：子集構(gòu)造法應(yīng)用于狀態(tài)輸入符號(hào)a bA BCB BCC BCzpli 2004-3-7version 1.1Page # of 7編譯原理習(xí)題參考答案(一)2.11我們可以從正規(guī)式的最簡(jiǎn)DFA同構(gòu)來證明兩個(gè)正規(guī)式等價(jià)。使用這種技術(shù)，證明下面正規(guī)式等價(jià)。(a) (a|b)*(b) (a*

5、|b*)*(c) (£|a)b*)*An swer:(c ) NFA見2.7 (c)用子集構(gòu)造法化簡(jiǎn)得DFA見2.8。最簡(jiǎn)的DFA為:Startzpli 2004-3-7version 1.1Page 5 of 7編譯原理習(xí)題參考答案(一)zpli 2004-3-7version 1.1Page # of 7編譯原理習(xí)題參考答案(一)同理可求出(b)正規(guī)式對(duì)應(yīng)的最簡(jiǎn) DFA亦是如此，故(b)(c) 等價(jià)。2.15修改算法2.4,使之盡可能少使用&轉(zhuǎn)換，并保持所產(chǎn)生的NFA只有一個(gè)接收狀態(tài)An swer:算法.4改進(jìn)(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)合并成一個(gè)狀態(tài)j。start izpli 2004-3-7version 1.1Page # of 7編譯原理習(xí)題參考答案(一)zpli 2004-3-7version 1.1Page # of 7編譯原理習(xí)題參考答案(一)注意：必須保留一個(gè)i和f,否則可能在算法遞歸產(chǎn)生NFA過程中會(huì)出問題zpli 2004-3-7version 1.1Page # of 7編譯原理習(xí)題參考答案(一)zpli 2004-3-7version 1.1Page # of 7編譯原理習(xí)題參考答案(一)第三章3.2考慮文法S aSbS

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

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

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

10、每個(gè)語(yǔ)言設(shè)計(jì)一個(gè)文法，其中哪些語(yǔ)言是正規(guī)的?(a) 每個(gè)a后面至少有一個(gè)b跟隨的所有串(b) a和b的個(gè)數(shù)相等的所有串An swer: S abS| bS |£該語(yǔ)言是正規(guī)，對(duì)應(yīng)的正規(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)消除習(xí)題3.1文法的左遞歸(b)為(a)的文法構(gòu)造預(yù)測(cè)分析器An swer: S (L) | aLS L1+L1 ，&

11、3;(b)上述文法的預(yù)測(cè)分析器為： 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