精品文档
最小化：
{{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} .
Y 0 {1,Y} 1 {2} 精品文档
{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='('
.
精品文档
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) T?ST? T?ST? T?ST? S?a S?^ T? 是LL(1)文法
T??? T??,ST? P81–2
文法：
.
精品文档
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' .
+ * ( E?TE' ) a b ^ 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??? 精品文档
F F' P F?PF? F?PF? F?PF? F?PF? F??? F??*F? F??? F??? F??? F??? F??? F??? P?(E) P?a P?b P?^ (4)
procedure E; begin
if sym='(' or sym='a' or sym='b' or sym='^' then begin T; E' end else error end
procedure E'; begin
if sym='+'
then begin advance; E end
else if sym<>')' and sym<>'#' then error end
procedure T; begin
if sym='(' or sym='a' or sym='b' or sym='^' then begin F; T' end else error end
procedure T'; begin
if sym='(' or sym='a' or sym='b' or sym='^' then T
else if sym='*' then error end
procedure F; begin
if sym='(' or sym='a' or sym='b' or sym='^' then begin P; F' end else error end
procedure F'; begin
if sym='*'
then begin advance; F' end end
procedure P; begin
if sym='a' or sym='b' or sym='^' then advance
else if sym='(' then
.