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

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

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

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

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

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

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

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

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

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

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

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

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

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

2）全部由按詞典遞增序排列小寫(xiě)字母組成串。第9頁(yè)3）注釋?zhuān)?*和*/之間串，且串中沒(méi)有不在雙引號(hào)（“）中*/。

/\*([^*"]|\*[^/]|\"([^"]*)\")*\*/8）全部由a和b組成且不含子串a(chǎn)bb串。9）全部由a和b組成且不含子序列abb串。第10頁(yè)X：[^*"]Y：[^/]Z：[^"]第11頁(yè)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頁(yè)3.6.3使用算法3.25和3.20將以下正則表示式轉(zhuǎn)換成DFA。2）

依據(jù)算法3.25得到NFA：第13頁(yè)依據(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頁(yè)4）依據(jù)算法3.25得到NFA：第15頁(yè)DFA轉(zhuǎn)換表：DFA狀態(tài)圖：狀態(tài)ab-A{0}B{0,1}C{0