当前位置:文档之家› 编译原理第三版课后答案

编译原理第三版课后答案

编译原理课后题答案第二章P36-6(1)L G()1是0~9组成的数字串(2)最左推导:最右推导:P36-7G(S)P36-8文法:最左推导:最右推导:语法树:/*************************************************/P36-9句子iiiei有两个语法树:P36-10/*****************************/P36-11/***************L1:L2:L3:L4:***************/第三章习题参考答案P64–7(1)最小化:P64–8(1) (2) (3)P64–12(a)aa,b a 0给状态编号:aaa b b b最小化:a ab ba b (b)已经确定化了,进行最小化最小化:P64–14(1) 01 0 (2):(|)*0101εε0 00 YY最小化: 01 1 1 0 0第四章P81–1(1) 按照T,S 的顺序消除左递归 递归子程序: procedure S; beginif sym='a' or sym='^' then abvance else if sym='(' then begin advance;T;if sym=')' then advance; else error; end else error end;procedure T; begin S; T end;procedure 'T;beginif sym=','then beginadvance;S;'Tendend;其中:sym:是输入串指针IP所指的符号advance:是把IP调至下一个输入符号error:是出错诊察程序(2)FIRST(S)={a,^,(}FIRST(T)={a,^,(}FIRST('T)={,,ε}FOLLOW(S)={),,,#}FOLLOW(T)={)}FOLLOW('T)={)}预测分析表是LL(1)文法P81–2文法:(1)FIRST(E)={(,a,b,^}FIRST(E')={+,ε}FIRST(T)={(,a,b,^}FIRST(T')={(,a,b,^,ε}FIRST(F)={(,a,b,^}FIRST(F')={*,ε}FIRST(P)={(,a,b,^}FOLLOW(E)={#,)}FOLLOW(E')={#,)}FOLLOW(T)={+,),#}FOLLOW(T')={+,),#}FOLLOW(F)={(,a,b,^,+,),#} FOLLOW(F')={(,a,b,^,+,),#} FOLLOW(P)={*,(,a,b,^,+,),#} (2)考虑下列产生式:FIRST(+E)∩FIRST(ε)={+}∩{ε}=φFIRST(+E)∩FOLLOW(E')={+}∩{#,)}=φFIRST(T)∩FIRST(ε)={(,a,b,^}∩{ε}=φFIRST(T)∩FOLLOW(T')={(,a,b,^}∩{+,),#}=φFIRST(*F')∩FIRST(ε)={*}∩{ε}=φFIRST(*F')∩FOLLOW(F')={*}∩{(,a,b,^,+,),#}=φFIRST((E))∩FIRST(a) ∩FIRST(b) ∩FIRST(^)=φ所以,该文法式LL(1)文法.(3)(4)procedure E;beginif sym='(' or sym='a' or sym='b' or sym='^' then begin T; E' endelse errorendprocedure E';beginif sym='+'then begin advance; E endelse if sym<>')' and sym<>'#' then error endprocedure T;beginif sym='(' or sym='a' or sym='b' or sym='^' then begin F; T' endelse errorendprocedure T';beginif sym='(' or sym='a' or sym='b' or sym='^' then Telse if sym='*' then errorendprocedure F;beginif sym='(' or sym='a' or sym='b' or sym='^' then begin P; F' endelse errorendprocedure F';beginif sym='*'then begin advance; F' endendprocedure P;beginif sym='a' or sym='b' or sym='^'then advanceelse if sym='(' thenbeginadvance; E;if sym=')' then advanceelse errorendelse errorend;P81–3/***************(1)是,满足三个条件。

(2)不是,对于A不满足条件3。

(3)不是,A、B均不满足条件3。

(4)是,满足三个条件。

***************/第五章P133–1短语: E+T*F, T*F,直接短语: T*F句柄: T*FP133–2文法:(1)最左推导:最右推导:(2)(((a,a),^,(a)),a)(((S,a),^,(a)),a)(((T,a),^,(a)),a)(((T,S),^,(a)),a)(((T),^,(a)),a)((S,^,(a)),a)((T,^,(a)),a)((T,S,(a)),a)((T,(a)),a)((T,(S)),a)((T,(T)),a)((T,S),a)((T),a)(S,a)(T,S)(T)S“移进-归约”过程:步骤栈输入串动作0 # (((a,a),^,(a)),a)# 预备1 #( ((a,a),^,(a)),a)# 进2 #(( (a,a),^,(a)),a)# 进3 #((( a,a),^,(a)),a)# 进4 #(((a ,a),^,(a)),a)# 进5 #(((S ,a),^,(a)),a)# 归6 #(((T ,a),^,(a)),a)# 归7 #(((T, a),^,(a)),a)# 进8 #(((T,a ),^,(a)),a)# 进9 #(((T,S ),^,(a)),a)# 归10 #(((T ),^,(a)),a)# 归11 #(((T) ,^,(a)),a)# 进12 #((S ,^,(a)),a)# 归13 #((T ,^,(a)),a)# 归14 #((T, ^,(a)),a)# 进15 #((T,^ ,(a)),a)# 进16 #((T,S ,(a)),a)# 归17 #((T ,(a)),a)# 归18 #((T, (a)),a)# 进19 #((T,( a)),a)# 进20 #((T,(a )),a)# 进21 #((T,(S )),a)# 归22 #((T,(T )),a)# 归23 #((T,(T) ),a)# 进24 #((T,S ),a)# 归25 #((T ),a)# 归26 #((T) ,a)# 进27 #(S ,a)# 归28 #(T ,a)# 归29 #(T, a)# 进30 #(T,a )# 进31 #(T,S )# 归32 #(T )# 归33 #(T) # 进34 #S # 归P133–3(1)FIRSTVT(S)={a,^,(}FIRSTVT(T)={,,a,^,(}LASTVT(S)={a,^,)}LASTVT(T)={,,a,^,)}G是算符文法,并且是算符优先文法6(4)栈输入字符串动作# (a,(a,a))# 预备#( a, (a,a))# 进#(a , (a,a))# 进#(t , (a,a))# 归#(t, (a,a))# 进#(t,(a,a))# 进#(t,(a ,a))# 进#(t,(t ,a))# 归#(t,(t, a))# 进#(t,(t,a ))# 进#(t,(t,s ))# 归#(t,(t ))# 归#(t,(t ) )# 进 #(t,s )# 归 #(t )# 归 #(t ) # 进 # s#归successP134–5(1)0.'→⋅S S 1.'→⋅S S 2.S AS →⋅ 3.S A S →⋅ 4.S AS →⋅ 5.S b →⋅ 6.S b →⋅ 7.A SA →⋅ 8.A S A →⋅ 9.A SA →⋅ 10.A a →⋅ 11.A a →⋅ (2)ba ab b a构造LR(0)项目集规范族也可以用GO 函数来计算得到。

所得到的项目集规范族与上图中的项目集一样:0I ={'→⋅S S ,S AS →⋅,S b →⋅,A SA →⋅,A a →⋅}GO(0I ,a)={ A a →⋅}=1IGO(0I ,b)={ S b →⋅}=2IGO(0I ,S)={ '→⋅S S ,A S A →⋅,A SA →⋅,A a →⋅,S AS →⋅,S b →⋅}=3I GO(0I ,A)={ S A S →⋅,S AS →⋅,S b →⋅,A SA →⋅,A a →⋅}=4IGO(3I ,a)={ A a →⋅}=1IGO(3I ,b)={ S b →⋅}=2IGO(3I ,S)={ A S A →⋅,S AS →⋅,S b →⋅,A SA →⋅,A a →⋅}=5IGO(3I ,A)={ A SA →⋅,S A S →⋅,S AS →⋅,S b →⋅,A SA →⋅,A a →⋅}=6I GO(4I ,a)={ A a →⋅}=1IGO(4I ,b)={ S b →⋅}=2IGO(4I ,S)={ S AS →⋅,A S A →⋅,S AS →⋅,S b →⋅,A SA →⋅,A a →⋅}=7I GO(4I ,A)={ S A S →⋅,S AS →⋅,S b →⋅,A SA →⋅,A a →⋅}=4IGO(5I ,a)={ A a →⋅}=1IGO(5I ,b)={ S b →⋅}=2IGO(5I ,S)={ A S A →⋅,S AS →⋅,S b →⋅,A SA →⋅,A a →⋅}=5IGO(5I ,A)={ A SA →⋅,S A S →⋅,S AS →⋅,S b →⋅,A SA →⋅,A a →⋅}=6I GO(6I ,a)={ A a →⋅}=1IGO(6I ,b)={ S b →⋅}=2IGO(6I ,S)={ S AS →⋅,A S A →⋅,S AS →⋅,S b →⋅,A SA →⋅,A a →⋅}=7I GO(6I ,A)={ S A S →⋅,S AS →⋅,S b →⋅,A SA →⋅,A a →⋅}=4IGO(7I ,a)={ A a →⋅}=1IGO(7I ,b)={ S b →⋅}=2IGO(7I ,S)={ A S A →⋅,S AS →⋅,S b →⋅,A SA →⋅,A a →⋅}=5IGO(7I ,A)={ A SA →⋅,S A S →⋅,S AS →⋅,S b →⋅,A SA →⋅,A a →⋅}=6I 项目集规范族为C={1I ,2I ,3I ,4I ,5I ,6I ,7I }(3)不是SLR 文法状态3,6,7有移进归约冲突状态3:FOLLOW(S’)={#}不包含a,b状态6:FOLLOW(S)={#,a,b}包含a,b,;移进归约冲突无法消解状态7:FOLLOW(A)={a,b}包含a,b ;移进归约冲突消解所以不是SLR 文法。

相关主题