完美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??? 专业整理 知识分享
编译原理第三版课后习题答案解析
