编译原理课后答案（陈火旺）

课后答案网 http://www.khdaw.com

φ 给状态编号：

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

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

课后答案网 http://www.khdaw.com

课后答案网 http://www.khdaw.com

最小化：

{{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} 课后答案网 http://www.khdaw.com

课后答案网 http://www.khdaw.com

{1,Y} {2} φ 给状态编号： 0 1 2 3 0 1 1 1 3 1 2 2 3 3 {1,Y} {1,Y} φ {2} φ φ 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='('

课后答案网 http://www.khdaw.com

课后答案网 http://www.khdaw.com

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

文法：

课后答案网 http://www.khdaw.com