1、第二章第二章 一個簡單的語法制導翻譯器一個簡單的語法制導翻譯器2.2.1 考慮下面的上下文無關文法：1）試說明如何使用該文法生成串aSSSSS| | aaaaaaSaaSSaSSSSSS 最左推導最左推導2）試為這個串構造一棵語法分析樹。3）該文法生成的語言是什么？以a為變量，+和*為二元操作符的后綴表達式的集合2.2.2 下面的各個文法生成什么語言？1）2）以a為變量，+和為二元操作符的前綴表達式的集合1 0| 1 0 SS aSSSSS| | 1|10nnn3）括號的匹配，包括空串4）由相同數目的a和b組成的字符串的集合，或者空串5）以a為變量，包括+，連接，*和括號四種運算的表達式的集合

2、| ) ( SSSS | | SaSbSbSaS ) ( | |SSSSSSaS2.2.3 練習2.2.2中哪些文法具有二義性？3） 4） 5）具有二義性。以5）為例進行說明： 給定字符串 a+a+a ，對應著兩棵分析樹：2.2.6 為羅馬數字構建一個上下文無關文法。| | | | | ThousandsMThousandsCCCCCCsLowHundredCMsLowHundredDCDsLowHundredHundredsXXXXXXLowTensXCLowTensLXLLowTensTensIIIIIILowOnesIXLowOnesVIVLowOnesOnesalRomanNumerO

3、nesTensHundredsThousandsalRomanNumer第三章第三章 詞法分析詞法分析3.2.2 試描述下列正則表達式定義的語言：1） 以a開頭和結尾且至少包含兩個字符的a,b字符串的集合2） 由a和b組成的任意字符串的集合abaa*)|(*)|(ba3） 倒數第三個字符為a的任意的a,b字符串的集合4） 包含3個b的a,b字符串的集合5） 包含偶數個a和偶數個b的a,b字符串的集合)|)(|(*)|(babaaba*bababaa*)*)|)(|(*)|)(|(*)|(bbaabaabbbaabaabbbaa3.2.5 試寫出下列語言的正則定義：1）包含5個元音的所有小寫字母

4、串，這些串中的元音按順序出現。 X：除五個元音外的所有小寫字母的集合。 2）所有由按詞典遞增序排列的小寫字母組成的串。*zba*)|(*)|(*)|(*)|(*)|(uXuXooXiiXeeXaaX3）注釋，即/*和*/之間的串，且串中沒有不在雙引號（“）中的*/。/* (* | */ | (*)* */8）所有由a和b組成且不含子串abb的串。9）所有由a和b組成且不含子序列abb的串。*)|(*abab| *)|(*abaab*)|(*ababX：*Y：/Z：3.6.1 將下圖中的NFA轉換為DFA。DFA的轉換表： DFA的狀態圖： （a|b）*狀態狀態ab+A0,1,2,3AA3.6.3 使用算法3.25和3.20將下列正則表達式轉換成DFA。2）根據算法3.25得到NFA：*)|*(ba根據算法3.20構造DFA：DFA的轉換表：DFA的狀態圖：狀態狀態ab+A0,1,2,3,5,6,7,9,10,11+B1,2,3,4,5,6,7,9,10,11+C1,2,3,5,6,7,8,9,10,11BBBCCC4）根據算法3.25得到NFA：*)|(*)|