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

完美WORD格式

φ 给状态编号：

0 1 2 3 φ φ a 1 1 0 3 b 2 2 3 3

a

a 0 1

a b b b

b 2 3

a

最小化：

{0,1},{2,3}{0,1}?{1} {0,1}?{2}ab{2,3}?{0,3} {2,3}?{3}

ab{0,1},{2},{3}

a a

b b 1 2 0 a b (b)

b b a 2 3 0

a b a a b b a 4 5 1 a a

已经确定化了,进行最小化

专业整理 知识分享

完美WORD格式

最小化：

{{0,1}, {2,3,4,5}}{0,1}a?{1} {0,1}b?{2,4}{2,3,4,5}a?{1,3,0,5} {2,3,4,5}b?{2,3,4,5}{2,4}a?{1,0} {2,4}b?{3,5}{3,5}a?{3,5} {3,5}b?{2,4}{{0,1},{2,4},{3,5}}{0,1}a?{1} {0,1}b?{2,4}{2,4}a?{1,0} {2,4}b?{3,5}{3,5}a?{3,5} {3,5}b?{2,4}

b b a 1 2 0

a b

a

P64–14

(1) 0 1 0 0 (2):

X (010|)* 1 Y

2

0 1 ? ? 1 X

0

确定化： {X,1,Y} 0 {1,Y} Y 1 {2} 专业整理 知识分享

完美WORD格式

{1,Y} {2} φ 给状态编号： 0 1 2 3 {1,Y} {1,Y} φ 0 1 1 1 3 {2} φ φ 1 2 2 3 3 0

0 1 0 1 0 1 1 1 2 3

0 最小化：

{0,1},{2,3}{0,1}0?{1} {0,1}1?{2}{2,3}0?{1,3} {2,3}1?{3}{0,1},{2},{3}

0 1 1 1 1 3 0 0 0 第四章

P81–1

(1) 按照T,S的顺序消除左递归

G?(S)S?a|^|(T) ?T?STT??,ST?|?递归子程序：

procedure S; begin

if sym='a' or sym='^' then abvance else if sym='('

专业整理 知识分享

完美WORD格式

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 ^ ( ) , # S?(T) S?a S?^ T?ST? T?ST? T?ST? T? 是LL(1)文法

T??? T??,ST? P81–2

文法：

专业整理 知识分享

完美WORD格式

E?TE?E???E|?T?FT?T??T|?F?PF?F??*F?|?P?(E)|a|b|^

(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)

考虑下列产生式:

E???E|?T??T|?F??*F?|?P?(E)|^|a|b

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 E' T T' + * ( ) a b ^ # E?TE' E?TE' E?TE' E?TE' E???E E??? E??? T?FT? T?FT? T?FT? T?FT? T??? T??T T??? T??T T??T T??T T??? 专业整理 知识分享