编译原理课后答案(陈火旺)

编译原理课后答案(陈火旺)

第二章

P36-6

(1)

L(G1)是0~9组成的数字串

(2)

最左推导:

N ND NDD NDDD DDDD 0DDD 01DD 012D 0127N ND DD 3D 34

N ND NDD DDD 5DD 56D 568

最右推导:

N ND N7 ND7 N27 ND27 N127 D127 0127N ND N4 D4 34

N ND N8 ND8 N68 D68 568

P36-7

G(S) O 1|3|5|7|9N 2|4|6|8|OD 0|NS O|AOA AD|N

P36-8

文法：

E T|E T|E TT F|T*F|T/F F (E)|i

最左推导:

E E T T T F T i T i T*F i F*F i i*F i i*iE T T*F F*F i*F i*(E) i*(E T) i*(T T) i*(F T) i*(i T) i*(i F) i*(i i)

最右推导:

E E T E T*F E T*i E F*i E i*i T i*i F i*i i i*iE T F*T F*F F*(E) F*(E T) F*(E F) F*(E i) F*(T i) F*(F i) F*(i i) i*(i i)

语法树：/********************************

编译原理课后答案(陈火旺)

E

E+

T

E+TF

TFi

Fi

i

i+i+i

*****************/

P36-9

句子iiiei有两个语法树： S iSeS iSei iiSei iiiei

S iS iiSeS iiSei iiiei

P36-10

/**************

S TS|TT (S)|( )

***************/

P36-11

/*************** L1:

S ACA aAb|ab C cC|

L2:

S ABA aA|

B bBc|bc

L3:

E

E

E+T

E

-T

T

T*F

E

-TF

F

Fi

TFi

i

i

Fi

i

i-i-i

i+i*i

编译原理课后答案(陈火旺)

S ABA aAb| B aBb|

L4:

S A|BA 0A1| B 1B0|A

***************/

第三章习题参考答案

P64–7

(1)

确定化：

最小化：

编译原理课后答案(陈火旺)

{0,1,2,3,4,5},{6}

{0,1,2,3,4,5} {1,3,5} {0,1,2,3,4,5} {1,2,4,6}{0,1,2,3,4},{5},{6}{0,1,2,3,4} {1,3,5}

00

1

{0,1,2,3},{4},{5},{6}

{0,1,2,3} {1,3} {0,1,2,3} {1,2,4}

01

{0,1},{2,3}{4},{5},{6}

{0,1} {1} {0,1} {1,2}{2,3} {3} {2,3} {4}

01

{0},{1},{2,3},{4},{5},{6}

1

P64

–8

(1) (1|0)01

*

(2)

(1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)(0|5)|(0|5)

*

(3)

01(0|101)|10(0|101)

*

*

*

*

*

*

P64–12

(a)

确定化：

编译原理课后答案(陈火旺)

给状态编号：

最小化：

{0,1

},{

2,3}

{0,1} {1} {0,1} {2}

ab

{2,3} {0,3} {2,3} {3}

ab

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

(b)

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

编译原理课后答案(陈火旺)

最小化： {{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}

a

P64–14

(2):

编译原理课后答案(陈火旺)

最小化：

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}

第四章

P81–1

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

G (S)S a|^|(T)T ST T ,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 )={)} 预测分析表

是LL(1)文法

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)文法.

编译原理课后答案(陈火旺)

(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

编译原理课后答案(陈火旺)

end;

begin

advance; E;

if sym=')' then advance else error end

else error

P81–3

/***************

(1) 是，满足三个条件。

(2) 不是，对于A不满足条件3。 (3) 不是，A、B均不满足条件3。 (4) 是，满足三个条件。 ***************/

第五章

P133–1

E E T E T*F 短语: E+T*F, T*F,

直接短语: T*F 句柄: T*F

P133–2

文法：

S a|^|(T)T T,S|S

(1)

最左推导:

S (T) (T,S) (S,S) …… 此处隐藏：3958字，全部文档内容请下载后查看。喜欢就下载吧 ……