编译原理第三版课后习题解答

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