编译原理(龙书)习题答案(chap2-3)

第二章一个简单的语法制导翻译器2.2.1考虑下面的上下文无关文法：1）试说明如何使用该文法生成串aSSSSS||aaaaaaSaaSSaSSSSSS最左推导2）试为这个串构造一棵语法分析树。3）该文法生成的语言是什么？以a为变量，+和*为二元操作符的后缀表达式的集合2.2.2下面的各个文法生成什么语言？1）2）以a为变量，+和－为二元操作符的前缀表达式的集合10|10SSaSSSSS||}1|10{nnn3）括号的匹配，包括空串4）由相同数目的a和b组成的字符串的集合，或者空串5）以a为变量，包括+，连接，*和括号四种运算的表达式的集合|)(SSSS||SaSbSbSaS)(||||SSSSSSaS2.2.3练习2.2.2中哪些文法具有二义性？3）4）5）具有二义性。以5）为例进行说明：给定字符串a+a+a，对应着两棵分析树：2.2.6为罗马数字构建一个上下文无关文法。||||||||||||||||||||ThousandsMThousandsCCCCCCsLowHundredCMsLowHundredDCDsLowHundredHundredsXXXXXXLowTensXCLowTensLXLLowTensTensIIIIIILowOnesIXLowOnesVIVLowOnesOnesalRomanNumerOnesTensHundredsThousandsalRomanNumer第三章词法分析3.2.2试描述下列正则表达式定义的语言：1）以a开头和结尾且至少包含两个字符的a,b字符串的集合2）由a和b组成的任意字符串的集合abaa*)|(**))|((ba3）倒数第三个字符为a的任意的a,b字符串的集合4）包含3个b的a,b字符串的集合5）包含偶数个a和偶数个b的a,b字符串的集合)|)(|(*)|(babaaba****bababaa*)*)|)(|(*)|)(|((*)|(bbaabaabbbaabaabbbaa3.2.5试写出下列语言的正则定义：1）包含5个元音的所有小写字母串，这些串中的元音按顺序出现。X：除五个元音外的所有小写字母的集合。2）所有由按词典递增序排列的小写字母组成的串。***zba**)|(*)|(*)|(*)|(*)|(uXuXooXiiXeeXaaX3）注释，即/*和*/之间的串，且串中没有不在双引号（“）中的*/。/\*([^*]|\*[^/]|\([^]*)\)*\*/8）所有由a和b组成且不含子串abb的串。9）所有由a和b组成且不含子序列abb的串。*)|(*abab|*)|(**abaab*)|(**ababX：[^*]Y：[^/]Z：[^]3.6.1将下图中的NFA转换为DFA。DFA的转换表：DFA的状态图：（a|b）*状态ab+A{0,1,2,3}AA3.6.3使用算法3.25和3.20将下列正则表达式转换成DFA。2）根据算法3.25得到NFA：**)|*(ba根据算法3.20构造DFA：DFA的转换表：DFA的状态图：状态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}BBBCCC4）根据算法3.25得到NFA：*)|(*)|(baabbbaDFA的转换表：DFA的状态图：状态ab-A{0}B{0,1}C{0,2}+D{0,3}+E{0,1,3}+F{0,2,3}BBBEEEACDDFD