编译原理(龙书)习题答案(chap2-3)市公开课一等奖省赛课微课金奖课件.pptx

,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,*,*,第二章 一个简单语法制导翻译器,2.2.1 考虑下面上下文无关文法：,1）试说明怎样使用该文法生成串,最左推导,第1页,2）试为这个串结构一棵语法分析树。,3）该文法生成语言是什么？,以a为变量，+和*为二元操作符,后缀表示式,集合,第2页,2.2.2 下面各个文法生成什么语言？,1）,2）,以a为变量，+和为二元操作符,前缀表示式,集合,第3页,3）,括号匹配，包含空串,4）,由相同数目标a和b组成字符串集合，或者空串,5）,以a为变量，包含+，连接，*和括号四种运算表示式集合,第4页,2.2.3 练习2.2.2中哪些文法含有二义性？,3）4）5）含有二义性。,以5）为例进行说明：,给定字符串,a+a+a,，对应着两棵分析树：,第5页,2.2.6 为罗马数字构建一个上下文无关文法。,第6页,第三章 词法分析,3.2.2 试描述以下正则表示式定义语言：,1）,以a开头和结尾且,最少包含两个字符,a,b字符串集合,2）,由a和b组成任意字符串集合,第7页,3）,倒数第三个字符为a任意a,b字符串集合,4）,包含3个ba,b字符串集合,5）,包含偶数个a和偶数个ba,b字符串集合,第8页,3.2.5 试写出以下语言正则定义：,1）包含5个元音全部小写字母串，这些串中元音按次序出现。,X：除五个元音外全部小写字母集合。,2）全部由按词典递增序排列小写字母组成串。,第9页,3）注释，即/*和*/之间串，且串中没有不在双引号（“）中*/。,/*(,*,|,*/,|,(*),)*/,8）全部由a和b组成且不含子串abb串。,9）全部由a和b组成且不含子序列abb串。,第10页,X：*,Y：/,Z：,第11页,3.6.1 将下列图中NFA转换为DFA。,DFA转换表：DFA状态图：,（a|b）*,状态,a,b,+,A0,1,2,3,A,A,第12页,3.6.3 使用算法3.25和3.20将以下正则表示式转换成DFA。,2）,依据算法3.25得到NFA：,第13页,依据算法3.20结构DFA：,DFA转换表：,DFA状态图：,状态,a,b,+,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,11,B,B,B,C,C,C,第14页,4）,依据算法3.25得到NFA：,第15页,DFA转换表：,DFA状态图：,状态,a,b,-A0,B0,1,C0,2,+D0,3,+E0,1,3,+F0,2,3,B,B,B,E,E,E,A,C,D,D,F,D,第16页,