编译原理（蒋立源）部分习题答案

、（1）L（G6）={0,1,2,......,9}+ （2）最左推导： N=>ND=>NDD=>NDDD=>DDDD=>0DDD=>01DD=>012D=>0127 N=>ND=>DD=>3D=>34 N=>ND=>NDD=>DDD=>5DD=>56D=>568 最右推导： N=>ND =>N7=>ND7=>N27=>ND27=>N127=>D127=>0127 N=>ND=>N4=>D4=>34 N=>ND=>N8=>ND8=>N68=>D68=>568 7、Ｇ：S→ABC | AC | C A→1|2|3|4|5|6|7|8|9 B→BB|0|1|2|3|4|5|6|7|8|9 C→1|3|5|7|9 8、（1）最左推导： E=>E+T=>T+T=>F+T=>i+T=>i+T*F=>i+F*F=>i+i*F=>i+i*i E=>T=>T*F=>F*F=>i*F=>i*(E)=>i*(E+T)=>i*(T+T)=>i*(F+T)=>i*(i+T)=>i*(i+F)=>i*(i+i) 最右推导： E=>E+T=>E+T*F=>E+T*i=>E+F*i=>E+i*i=>T+i*i=>F+i*i=>i+i*i E=>T=>T*F=>T*(E)=>T*(E+T)=>T*(E+F)=>T*(E+i)=>T*(T+i)=>T*(F+i)=>T*(i+i)=>F*(i+i)=>i*(i+i) (2) 9、证明：该文法存在一个句子iiiei有两棵不同语法分析树，如下所示，因此该文法是二义的。 11、 第3章 词法分析 7、构造下列正规式相应的DFA：1(0|1)*101 解： （1）构造NFA： （2）确定化： 构造状态转换矩阵如下： 重命名： I I0 I1 {X} _ {1} {1} {1} {1,2} {1,2} {1,3} {1,2} {1,3} {1} {1,2,Y} {1,2,Y} {1,3} {1,2} S 0 1 0 1 1 1 2 2 3 2 3 1 4 4 3 2 画出状态转换图： （注：已是最简） 8、（1）（0|1）*01 （2）（0|1|2|3|4|5|6|7|8|9）(1|2|3|4|5|6|7|8|9)*(0|5)|0|5 （3）（10*1|0）*10*|（01*0|1）*01* （4）a*b*c*......z* 9、（1） 正规式（0|1）*（010）（0|1）* NFA: 构造状态转换矩阵： 重命名： I I0 I1 {X} {X,0} {X} {X,0} {X,0} {X,1} {X,1} {X,0,Y} {X} {X,0,Y} {X,0,Y} {X,1,Y| {X,1,Y} {X,0,Y} {X,Y} {X,Y} {X,0,Y} {X,Y} S 0 1 0 1 0 1 1 2 2 3 0 3 3 4 4 3 5 5 3 5 画出DFA： 最少化后： 12、（a）构造状态转换矩阵： 重命名： I Ia Ib {0} {0，1} {1} {0，1} {0，1} {1} {1} {0} —— S a b 0 1 2 1 1 2 2 0 _ 重命名： 画出确定化后的有限自动机：