编译原理参考练习题目.docVIP

1、写出非负整数的正规表达式。 例子：1234或0或1023 0123或－123 非法 非负整数→数字|非0数字整数 整数→数字|整数数字 数字→0|1|2|…|9 非0数字→1|2|…|9 2、写出以非5数字为开头的所有非负整数之集的正规表达式。 例子：1234或0或1023 0123或5123 非法 解：D=1|2|…|9 E=1|2|3|4|6|7|8|9 L=0|E(0|D)* 8、把下列NDFA转化为DFA: 解：A1设改为A,B,C 状态 a b +1 2 2 2,3 -2,3 2 2,3 A2设改为A,B状态 15、写出下面DFA的正规表达式 得到确定DFA： 最小化DFA： 得到正规表达式： 结果：ab(a|b)* 1、构造下列正则式相应的DA: (1)1(0|1)*101 (2)1(1010*|1(010)*1)*0 (3)a((a|b)*|ab*a)b (4)b((ab)*|bb)*ab 解：1） 2、已知NDFA=({x,y,z},{0,1},M,{x},{z}), 其中:M(x,0)={z},M(y,0)={x,y}, M(z,0)={x,z}, M(x,1)={x}, M(y,1)=Φ,M(z,1)={y}, 构造相应的DFA。 1:写出状态转换矩阵 确定自动机： 1、设有文法G[N]: N→D|ND D→0|1|2|…|9 (1)试写出021和4321的最右推导和最左推导。 解:(1)021的最左推导： N(ND(NDD(DDD(0DD (02D( 021 021的最右推导： N(ND(N1(ND1(N21 (D21(021 解:4321的最左推导： N(ND(NDD(NDDD(DDDD (4DDD(43DD(432D(4321 4321的最右推导： N(ND(N1(ND1(N21 (ND21(N321(D321(4321 3、设有文法G[E]: E→T|E+T|E-T T→F|T*F|T/F F→i|(E) (1)试写出i*i/(i+i*i)的语法树。 (2)试写出句型T*F*(T+i)的最右推导。 解：(1)??i*i/(i+i*i)的语法树：（见下页） (2)最右推导 E(T(T*F(T*(E)(T*(E+T) (T*(E+F)(T*(E+i)(T*(T+i) ( T*F*(T+i) 5、对下面的文法G: E→TE’ E’→+E|ε T→FT’ T’→T|ε F→PF’ F’→*F’|ε P→(E)|A|B|∧ A→a B→b (1)计算这个文法的每个非终结符的First集和follow集。 解：first(E)=first(T)=first(F) =first(P)={(,a,b,∧} first(E’)={+,ε} first(T’)=first(T)∪{ε} ={(,a,b,∧,ε} first(F’)= {*,ε} follow(E)=follow(E’)∪{ }}∪{#}={),#} follow(E’)= follow(E)= {),#} follow(T) = first(E’)-ε∪follow(E)∪follow(T’) ={+,),#} follow(T’)=follow(T)={+, ), #} follow(F)=first(T’)- ε∪follow(T) ={(,a,b,∧,+,),#} follow(F’)=follow(F) ={(,a,b,∧,+,),#} follow(P)=first(F’) -ε∪follow(F) ={*,(,a,b,∧,+, ),#} 三、化简下列自动机。 解： 化为确定自动机： 2和4等价，3和(4,5)等价 例子：设有正则表达式e为：(a|b)*(aa|bb)(a|b)* 构造确定有穷自动机A，使L(A)=L(e) 解：求e的转换系统 首先，利用求(闭包的方法转化为确定自动机。得出如下表格： Move([s，3，1]，a)=(3，5) (-closure(3，5)=[1，3，5] 得到确定自动机如下图： 化简后如下图，其中3，4，5，6四个状态等价。 求first(X)的算法：(X∈VN∪VT) 1、若X∈V