編譯原理(龍書)習(xí)題答案(chap2-3)市公開課一等獎(jiǎng)省賽課微課金獎(jiǎng)?wù)n件

第二章一個(gè)簡單語法制導(dǎo)翻譯器2.2.1考慮下面上下文無關(guān)文法：1）試說明怎樣使用該文法生成串最左推導(dǎo)第1頁2）試為這個(gè)串結(jié)構(gòu)一棵語法分析樹。3）該文法生成語言是什么？

以a為變量，+和*為二元操作符后綴表示式集合第2頁2.2.2下面各個(gè)文法生成什么語言？1）2）

以a為變量，+和－為二元操作符前綴表示式集合第3頁3）

括號(hào)匹配，包含空串4）

由相同數(shù)目標(biāo)a和b組成字符串集合，或者空串5）

以a為變量，包含+，連接，*和括號(hào)四種運(yùn)算表示式集合第4頁2.2.3練習(xí)2.2.2中哪些文法含有二義性？

3）4）5）含有二義性。 以5）為例進(jìn)行說明：給定字符串a(chǎn)+a+a，對(duì)應(yīng)著兩棵分析樹：第5頁2.2.6為羅馬數(shù)字構(gòu)建一個(gè)上下文無關(guān)文法。第6頁第三章詞法分析3.2.2試描述以下正則表示式定義語言：1）

以a開頭和結(jié)尾且最少包含兩個(gè)字符a,b字符串集合2）

由a和b組成任意字符串集合第7頁3）

倒數(shù)第三個(gè)字符為a任意a,b字符串集合4）

包含3個(gè)ba,b字符串集合5）

包含偶數(shù)個(gè)a和偶數(shù)個(gè)ba,b字符串集合第8頁3.2.5試寫出以下語言正則定義：1）包含5個(gè)元音全部小寫字母串，這些串中元音按次序出現(xiàn)。

X：除五個(gè)元音外全部小寫字母集合。

2）全部由按詞典遞增序排列小寫字母組成串。第9頁3）注釋，即/*和*/之間串，且串中沒有不在雙引號(hào)（“）中*/。

/\*([^*"]|\*[^/]|\"([^"]*)\")*\*/8）全部由a和b組成且不含子串a(chǎn)bb串。9）全部由a和b組成且不含子序列abb串。第10頁X：[^*"]Y：[^/]Z：[^"]第11頁3.6.1將下列圖中NFA轉(zhuǎn)換為DFA。

DFA轉(zhuǎn)換表：DFA狀態(tài)圖：

（a|b）*狀態(tài)ab+A{0,1,2,3}AA第12頁3.6.3使用算法3.25和3.20將以下正則表示式轉(zhuǎn)換成DFA。2）

依據(jù)算法3.25得到NFA：第13頁依據(jù)算法3.20結(jié)構(gòu)DFA：DFA轉(zhuǎn)換表：DFA狀態(tài)圖：狀態(tài)ab+A{0,1,2,3,5,6,7,9,10,11}+B{1,2,3,4,5,6,7,9,10,11}+C{1,2,3,5,6,7,8,9,10,11}BBBCCC第14頁4）依據(jù)算法3.25得到NFA：第15頁DFA轉(zhuǎn)換表：DFA狀態(tài)圖：狀態(tài)ab-A{0}B{0,1}C{0