1 ? ? 1 Y X 0 确定化： {X,1,Y} {1,Y} {2} φ 给状态编号： 0 1 2 3 0
0 1 0 1 1 1 3 1 2 2 3 3 0 {1,Y} {1,Y} {1,Y} φ 1 {2} {2} φ φ 0 1 0 1 1 2 3 1 0 最小化：
0 1 1 1 1 3 0 0 0
第四章
P81–1
(1) 按照T,S的顺序消除左递归 递归子程序： procedure S; begin
if 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?; begin
if sym=','
then begin
advance; S;T?
end
end; 其中:
sym:是输入串指针IP所指的符号 advance:是把IP调至下一个输入符号 error:是出错诊察程序 (2)
FIRST(S)={a,^,(} FIRST(T)={a,^,(} FIRST(T?)={,,?} FOLLOW(S)={),,,#} FOLLOW(T)={)} FOLLOW(T?)={)} 预测分析表
S T a ^ ( ) , # 是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) E + * ( ) a b ^ # E' T T' F F' P (4)
procedure E; begin
编译原理第三版课后习题解答
