编译原理课后答案

第二章 高级语言及其语法描述

4．令+、*和↑代表加，乘和乘幂，按如下的非标准优先级和结合性质的约定，计算1+1*2↑2*1↑2的值：

（1） 优先顺序（从高至低）为+，*和↑，同级优先采用左结合。 （2） 优先顺序为↑，+，*，同级优先采用右结合。 解：（1）1+1*2↑2*1↑2=2*2↑1*1↑2=4↑1↑2=4↑2=16 （2）1+1*2↑2*1↑2=1+1*2*1=2*2*1=2*2=4

6．令文法G6为 N→D|ND

D→0|1|2|3|4|5|6|7|8|9 （1） G6 的语言L（G6）是什么？

（2） 给出句子0127、34和568的最左推导和最右推导。 解：（1）L（G6）=｛a|a∈∑+,∑=﹛0,1,2,3,4,5,6,7,8,9｝｝

（2）N ＝＞ND＝＞ NDD＝＞ NDDD＝＞ DDDD＝＞ 0DDD＝＞ 01DD＝＞ 012D＝＞ 0127 N＝＞ ND＝＞ N7＝＞ ND7＝＞ N27＝＞ ND27＝＞ N127＝＞ D127＝＞ 0127 N＝＞ ND＝＞ DD＝＞ 3D＝＞ 34 N＝＞ ND＝＞ N4＝＞ D4 ＝＞34

N＝＞ ND＝＞ NDD＝＞ DDD＝＞ 5DD＝＞ 56D＝＞ 568 N＝＞ ND＝＞ N8＝＞ ND8＝＞ N68＝＞ D68＝＞ 568

7．写一个文法，使其语言是奇数集，且每个奇数不以0开头。 解：A→SN, S→+|-|∑, N→D|MD

D→1|3|5|7|9, M→MB|1|2|3|4|5|6|7|8|9 B→0|1|2|3|4|5|6|7|8|9 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)语法树：/********************************

1

EEE+TE+TE+TFTT*FTFiFFiFiiiii+i+ii-i-i*****************/

9．证明下面的文法是二义的：

S→ iSeS|iS|I

解：因为iiiiei有两种最左推导，所以此文法是二义的。

10．把下面文法改写为无二义的：

S→SS|(S)|()

解：S→ ST|T, T→ (S)|()

11．给出下面语言的相应文法

L1=｛anbnci|n≥1,i≥0｝ L2=｛aibncn|n≥1,i≥0｝ L3=｛anbnambm|n,m≥0｝ L4=｛1n0m1m0n|n,m≥0｝ 解：（1）S→ AB|A A→ aAb|ab B→ c|cB

(2) S→ AB|B A→ a|aA B→ bBc|bc (3) S→ AB|A|B|∑

A→ aAb|ab B→ aBb|ab (4) S→ 1S0|0A1

A→ 0A1|01

2

EE-TE-TFTFiFiii+i*i

第三章

词法分析

7.构造下列正规式的相应的DFA 1(0|1)*101

1(1010*|1(010)*1)*0 0*10*10*10*

(00|11)*((01|10)(00|11)*(01|10)(00|11)*)* 解答：

（1）1(0|1)*101

I {X} {A,B,C} {B,C} {B,C,D} {B,C,E} {B,C,D,y}

S A B C D E F

(2) 1(1010*|1(010)*1)*0

I {X} {A,B,C} {y} {D,H,I,L} {E,J} {B,C} {B,C,F,G,K} {B,C,G,I,L,y} {B,C,G,J,y} {D,H,I,K,L} {E,J,y} {E,I,J,L} {J} I0 Ф { B,C} { B,C} { B,C,E} { B,C} {B,C,E} 0 C C E C E I0 Ф {y} Ф {E,J} Ф {y} {B,C,G,I,L,y} {B,C,G,J,y} {B,C,G, y} {E,I,J,L} Ф {J} Ф 3

I1 {A,B,C}

{ B,C,D} { B,C,D} { B,C,D} {B,C,D,y} { B,C,D} 1 B D D D F D I1 {A,B,C} {D,H,I,L} Ф {B,C}

{B,C,F,G,K} {D,H,I,L} {D,H,I,L}

{B,C,D,H,I,L } {D,H,I,L} {B,C}

{B,C,F,G,K } {B,C,F,G,K } {K}

{K} {I,L} Ф {I,L} {J} {B,C}

8.给出下面正规表达式

（1）以01结尾的二进制数串 （2）能被5整除的十进制整数

（3）包含奇数个1或者奇数个0的二进制数串

（4）英文字母组成的所有符号串，要求符号串中的字母按照字典序排列。 （7）不包含子串abb的由a和b组成的符号串的全体。 解答：

*

（1） （0|1）01

*

（2） (1|2|…|9)(0|1|2|…|9)(0|5)|0|5

*****

（3） 01(01010)

***

（4） AB…Z

**

(7) b(a|ab)

9.对下面的情况给出DFA以及正规表达式。 （1）{0，1}上的含有子串010的所有串。 （2）{0，1}上不含子串010的所有串。 解答：

**

（1）（0|1）010（0|1） （2）1*(0|1*|1)*1*

12 将图3.8的（a）和(b)分别确定化和最少化。

解：1 确定化

a b

｛0｝ ｛0,1｝ ｛1｝ ｛0,1｝ ｛0,1｝ ｛1｝ ｛1｝ ｛0｝ __

令A=｛0｝ B=｛0，1｝ C=｛1｝ 则状态转换图为：

2 最少化

首先，所有状态可分为 终态集{A B} 非终态集{C}

其次，考察{A B}，由于{A B}由a到{B}，由b到{C}，所以不可分，令A={A B} 则最少化后的状态转换图为：

4

14 构造一个DFA，它接受∑＝｛0,1｝上所有满足下列条件的字符串，每个1都有0直接跟在右边。

解：1 正规式为： （0|10）﹡

2 由正规式转化为NFA：

3 由NFA到DFA：

0 1 {X} {X} {b} {b} {X} __ 令A={X} B={b} 则状态转换图为：

4 最少化

终态集{A} 非终态集{B}

显然不可再划分，则最简的DFA即为：

15 给定右线性文法G：

S→0S|1S|1A|0B A→1C|1 B→0C|0

C→0C|1C|1|0

求出一个与G等价的左线性文法。

解：1 由右线性文法构造NFA：

2 从NFA中构造左线性文法： F→A1|B0|C0|C1 A→S1|1 B→S0|0

C→C0|C1|A1|B0 S→S0|S1|1|0

5

第四章 语法分析－自上而下分析

1. 考虑下面文法 G1: S→a|∧|(T) T→T,S|S

(1)消去G1的左递归，然后对每个非终结符写出不带回溯的递归子程序。 (2)经过改写的文法是否是LL（1）的？给出它的预测分析表。 解答：

（1）消去G1的左递归：S→a|∧|(T)

T→ST’

T’ →,ST’|ε

递归子程序： PROCEDURE S;

IF sym=’a’ THEN ADVANCE

ELSE IF sym=’ ∧’ THEN ADVANCE ELSE IF sym=’ (’ THEN BEGIN ADVANCE T;

IF sym=’ )’ THEN ADVANCE ELSE ERROR END ELSE ERROR;

PROCEDURE T; BEGIN S;T’ END;

PROCEDURE S;

IF sym=’ ,’ THEN BEGIN ADVANCE S;T’ END;

（2）是LL（1）文法。

FIRST(S)={ a,∧,( } FIRST(T)={ a,∧,( } FIRST(T’)={ ,,ε } FOLLOW(S)={ #, , , ε, ) } FOLLOW(T)={ ) } FOLLOW(T’)={ ) }

预测分析表如下：

6

S T T’

2.文法：

a S→a T→ST’ , T’ →,ST’ ∧ S→∧ T→ST’ ( S→ (T) T→ST’ ） T’ →ε # 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,^,+,),#}=φ

7

FIRST((E))∩FIRST(a) ∩FIRST(b) ∩FIRST(^)=φ 所以,该文法式LL(1)文法. (3)

E E' T T' F F' P + * ( ) a b ^ # ETE' ETE' ETE' ETE' EE E E TFT FPF TFT TFT TFT FPF FPF FPF T TT T TT TT TT T 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

8

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 begin

advance; E;

if sym=')' then advance else error end

else error end;

3.下面文法那些是LL（1）文法？

（1）S →Abc A →a|ε B→b|ε

没有左递归且FIRST 候选集不冲突且

FIRST(A)∩FOLLOW(A)={ a, ε} ∩ { b }=Ф FIRST(B)∩FOLLOW(B)={ b, ε} ∩ { c }=Ф 所以该文法为LL（1）文法

（2）S →Ab A →a|B|ε B→b|ε

FIRST(B)＝{ b, ε} ∩ FIRST(ε) ={ε} ≠Ф 所以该文法不是LL（1）文法

（3）S →ABBA A →a |ε B→b|ε

没有左递归且FIRST 候选集不冲突

FIRST(A)∩FOLLOW(A)={ a, ε} ∩{b,#} =Ф FIRST(B)∩FOLLOW(B)={ b, ε}∩{b,a,#} ≠Ф 所以该文法不是LL（1）文法

(4) S →aSe|B B →bBe |C C→cCe|d

没有左递归且FIRST 候选集不冲突 所以该文法为LL（1）文法

9

4.Expr→_Expr

Expr→(Expr)| Var ExprTail ExprTail→_ Expr|ε Var→id VarTail VarTail→(Expr)| ε （1）构造LL（1）分析表

（2）给出对句子id_ _id((id)) 的分析过程

解答：（1）FIRST(Expr)={_ , ( , id } FIRST(ExprTail)={_ , ε } FIRST(Var)={id} FIRST(VarTail)={ ( , ε}

FOLLOW(Expr)={# , ) } FOLLOW(ExprTail) ={# , ) } FOLLOW(Var) ={_ , # , ) } FOLLOW(VarTail) ={_ , # , ) }

预测分析表如下： Expr — Expr→_Expr id ( ） # Expr→Var Expr→ExprTail (Expr) Var→VarTail id VarTail→(Expr) ExprTail ExprTail→_ Expr Var VarTail VarTail→ε ExprTail→ε ExprTail→ε VarTail→ε

(3) 对句子id_ _((id)) 的分析过程：

步骤 符号栈 输入串 所用产生式 0 ＃Expr id_ _id((id))＃

1 # ExprTail Var id_ _id((id))＃ Expr→Var ExprTail 2 # ExprTail VarTail id id_ _id((id))＃ Var→id VarTail

3 # ExprTail VarTail _ _id((id))＃

4 # ExprTail _ _id((id))＃ VarTail→ε

10

5 6 7 8 9 10 11 12 13 14 15 16

# Expr_

_ _id((id))＃ ExprTail→_ Expr _id((id))＃

_id((id))＃ Expr→_Expr id((id))＃

id((id))＃ Expr→Var ExprTail

# Expr # Expr_ # Expr # ExprTail Var

17 18 19 20 21 22 23

# ExprTail VarTail id id((id))＃ Var→id VarTail # ExprTail VarTail ((id))＃

# ExprTail )Expr( ((id))＃ VarTail→(Expr) # ExprTail )Expr (id))＃

# ExprTail ) )Expr( (id))＃ Expr→(Expr) # ExprTail ) )Expr id))＃

# ExprTail ) )

ExprTail Var id))＃ Expr→Var ExprTail

# ExprTail ) )

ExprTail VarTail id id))＃ Var→id VarTail # ExprTail ) )

ExprTail VarTail ))＃

# ExprTail ) )

ExprTail ))＃ VarTail→ε

# ExprTail ) ) ))＃ ExprTail→ε # ExprTail ) # ExprTail #

)＃

ExprTail→ε 分析成功 第五章

# #

1. EETET*F 短语: E+T*F, T*F, 直接短语: T*F 句柄: T*F

2 （1）(a, ( a, a ) ) 的最左推导：S => ( T ) =>( T,S ) => ( S,S ) =>(a,S ) =>( a,( T ) ) => ( a,( T,S ) ) => ( a,(S,S ) ) => ( a,( a ,S ) ) => ( a,( a ,a ) )

最右推导：S => ( T ) =>( T,S ) => ( T, (T) ) =>( T, (T, S) ) =>( T, (T, a) ) =>( T,

11

(S, a) ) => ( T,(S, a ) ) => ( T,( a ,a ) ) => (S,( a ,a ) ) => ( a,( a ,a ) )

(((a, a),^,(a)),a) 的最左推导：：S => ( T ) =>( T,S ) => ( S,S ) =>( ( T ) ,S ) => (( T,S ),S ) => (( T,S，S ),S ) =>(( S,S，S ),S ) =>(( ( T ),S，S ),S ) =>(( ( T,S ),S，S ),S ) =>(( ( S,S ),S，S ),S ) =>(( ( a, S ),S，S ),S ) =>(( ( a, a ),S，S ),S ) =>(( ( a ,a ),^，S ),S ) =>(( ( a ,a ),^ ，a ),S ) =>(( ( a ,a ),^ ，a ),a )

最右推导：S => ( T ) =>( T,S ) =>( T, a ) =>( S ,a ) =>( (T) , a ) =>( (T, S) , a ) =>( (T, ( T )) , a ) =>( (T, ( a )) , a ) =>( (T, S, ( a )) , a ) =>( (T, ^, ( a )) , a ) =>( (S, ^, ( a )) , a ) =>( ((T), ^, ( a )) , a ) =>( ((T,S), ^, ( a )) , a ) =>( ((T ,a), ^, ( a )) , a ) =>( ((S ,a), ^, ( a )) , a ) =>( ((a ,a), ^, ( a )) , a )

(2) (((a, a),^,(a)),a)的规范规约及每一步的句柄为： (((a, a),^,(a)),a) a ( ((S ,a), ^, ( a )) , a ) S ( ((T ,a), ^, ( a )) , a ) a ( ((T,S), ^, ( a )) , a ) T,S ( ((T), ^, ( a )) , a ) (T) ( (S, ^, ( a )) , a ) S ( (T, ^, ( a )) , a ) ^ ( (T, S, ( a )) , a ) T,S ( (T, ( a )) , a ) a ((T,(S)),a) S

( (T, ( T )) , a ) (T) ( (T, S) , a ) T,S ( (T) , a ) (T) ( S ,a ) S ( T, a ) a ( T,S ) T,S ( T ) (T) S

步骤 符号栈 输入串 动作 0 # (((a, a),^,(a)),a)# 预备 1 #( ((a, a),^,(a)),a)# 进 2 #(( (a, a),^,(a)),a)# 进 3 #((( a, a),^,(a)),a)# 进 4 #(((a , a),^,(a)),a)# 进

5 #(((S , a),^,(a)),a)# 规约 S→a

6 #(((T , a),^,(a)),a)# 规约T

12

→S

7 #(((T, 8 #(((T, a 9 #(((T,S 10 #(((T 11 #(((T) 12 #((S 13 #((T 14 #((T, 15 #((T,^ 16 #((T,S →^

17 #((T T,S

18 #((T, 19 #((T,( 20 #((T,(a 21 #((T,(S 22 #((T,(T 23 #((T,(T) 24 #((T,S 25 #((T 26 #((T) 27 #(S 28 #(T 29 #(T, 30 #(T, a 31 #(T, S 32 #(T 33 #(T) 34 #S 35 #S 语法树：

(

14 T

( T ) 12

a),^,(a)),a)# ),^,(a)),a)# ),^,(a)),a)# ),^,(a)),a)# ,^,(a)),a)# ,^,(a)),a)# ,^,(a)),a)# ^,(a)),a)# ,(a)),a)# ,(a)),a)# ,(a)),a)#

(a)),a)# a)),a)# )),a)# )),a)# )),a)# ),a)# ),a)# ),a)# ,a)# ,a)# a)# a)# )# )# )# # # # S 17 T ) 16 , S 15 S 13 a 13

进 进 规约 S→a 规约T→T,S 进

规约S→(T) 规约TS 进

进

规约S

规约T→

进 进 进

规约S→a 规约T→S 进 规约S→(T) 规约T→T,S 进

规约S→(T) 规约T→S 进 进 规约S→a 规约T→T,S 进

规约S→(T) 接受

（ T ）

8 T , S 11 6 T , S 7

( T ) 10 S 5 ^ S 9 ( T ) 4 a T , S 3 2

S a 1 a

其中的编号指示的结点为每一步规约所形成的语法树的根结点。

3（1） FIRSTVT(S)={a,^,(}

FIRSTVT(T)={,,a,^,(} LASTVT(S)={a,^,)} LASTVT(T)={,,a,^,)}

(2) a ^ ( ) ,

a < < ^ < < ( < < ) > > = > > , > > < > > G6是算符文法，并且是算符优先文法

(3)优先函数 f g a 4 5 ^ 4 5 ( 2 5 ) 4 2 , 4 3 也可以最后指定f (#) ,g (#) 的值。

14

（4）算符优先分析过程。

步骤 符号栈 输入串 动作 0 # (a,(a ,a))# 预备 1 #( a,(a ,a))# 进 2 #(a ,(a ,a))# 进

3 #(S ,(a ,a))# 规约S→a 4 #(S, (a ,a))# 进 5 #(S,( a ,a))# 进 6 #(S,(a ,a))# 进

7 #(S,(S ,a))# 规约S→a 8 #(S,(S, a))# 进 9 #(S,(S,a ))# 进

10 #(S,(S,S ))# 规约S→a 11 #(S,(T ))# 规约T→T,S 12 #(S,(T) )# 进

13 #(S,S )# 规约S→(T) 14 #(T )# 规约T→T,S 15 #(T) # 进

16 #S # 规约S→(T) 17 #S # 接受

5.拓广的文法为：S’→S , S→AS, S→b ,A→SA, A→a, (1) 所有的 LR(0)项目：

0.SS 1.SS 2.SAS 3.SAS 4.SAS 5.Sb 6.Sb 7.ASA 8.ASA 9.ASA 10.Aa 11.Aa （2）LR(0)项目集规范族：

I0 S’→·S , S→·AS , S→·b , A→·SA , A→·a

I0 S I 1 S’→S· , S→A·S , S→b· , A→S·A, A→a· , A→·SA

A I 2 S→A·S, , S→·AS , S→·b , A→·SA , A→·a a I 3 A→a· b I 4 S→b·

I 1 S I 5 A→S·A, A→·SA , A→·a , S→·AS , S→·b

A I 6 A→SA· , S→A·S , S→·AS , S→·b , A→·SA , A→·a, a (I 3) b (I 4)

I 2 S I 7 S→AS· , A→S·A, A→·SA , A→·a, S→·AS, S→·b,

A( I 2 )

15

a (I 3 ) b (I 4 )

I 5 S (I 5) A (I 6) a (I 3) b (I 4) I 6 S (I 7) A (I 2 ) a (I 3) b (I 4)

I 7 S (I 5) A (I 6) a (I 3) b (I 4)

(3) I 1 中存在移进规约冲突S’→S· ， A→·a ， S→·b 但是FOLLOW(S’)＝{#} 所以该冲突可以消除

I 6中存在移进规约冲突：A→SA· ，S→·b ，A→·a 但是FOLLOW(A)＝{b, a } 所以该冲突不可以消除。

I 7中存在移进规约冲突：S→AS· ，A→·a ，S→·b但是FOLLOW(S)＝{a , b ,# } 所以该冲突不可以消除。 所以该文法不是SLR文法。

（4）

I0 [S’→·S , # ] , [S→·AS , # ] ,[ S→·b , # ], [ A→·SA ,a/b ] ,[ A→·a ,a/b]

I0 S I 1 [ S’→S·,# ] , [S→A·S,a/b] , [S→b·,a/b ] , [A→S·A, a /b ],

[A→a· , a/b] , [ A→·SA, a/b]

A I 2 [S→A·S, #] , [S→·AS , #], [ S→·b , #], [A→·SA ,a/b ],[ A→·a, a/b ]

a I 3 : [ A→a·,a/b], b I 4 [ S→b·,#]

I 1 S I 5 [A→S·A, a/b ], [A→·SA , a/b ],[ A→·a , a/b ],[ S→·AS , a/b ],

[ S→·b, a/b ]

A I 6 [A→SA·,a/b ], [ S→A·S , a/b ], [ S→·AS , a/b ], [S→·b , a/b ],

[A→·SA , a/b ], [A→·a, a/b ]

a (I 3)

b I7 [S→b·, a/b ]

I 2 S I 8 [ S→AS·,#] , [A→S·A, a/b ], [A→·SA ,a/b] , [A→·a, a/b] , [S

→·AS, a/b], [ S→·b, a/b]

A I 9 [ S→A·S , #/a/b ], [ S→·AS , #/a/b ] , [S→·b ,#/ a/b ], [A→·SA ,

a/b ], [A→·a, a/b ]

a (I 3 )

b I 10 [S→b·, #/a/b ]

I 5 S (I 5) A (I 6) a (I 3) b (I 7)

I 6 S I 11 : [ S→AS·, a/b] , [A→S·A, a/b ], [A→·SA , a/b ], [A→·a, a/b ] ,

A I 12 : [ S→A·S , a/b ], [ S→·AS , a/b ], [ S→·b, a/b], [A→·SA , a/b ],

[A→·a, a/b ]

16

a (I 3) b (I 7)

I 8 S( I 5 ) A( I 6 ) a( I 3) b( I 7)

I 9 S I 13 : [ S→AS·, #/a/b] , [A→S·A, a/b ], [A→·SA , a/b ], [A→·a, a/b ] , [ S→·AS ,a/b ] , [S→·b , a/b ] A (I 9 ) a (I 3 ) b (I 10 )

I 11 S( I 5 ) A( I 6 ) a( I 3) b( I 7)

I 12 S( I 11 ) A( I 12 )

a( I 3) b( I 7)

I 13 S( I 5 ) A( I 6 ) a( I 3) b( I 7)

I 6, I 11, I 13 中存在移进规约冲突，所以该文法不是LR(1)的和LALR的。

(附上网络版的答案) (2)

1

S A  8 7 9 S     a 10 0

   A S 3 2  

d 5

确定化： {0,2,5,7,10} {1,2,5,7,8,10} S {1,2,5,7,8,10} {2,5,7,8,10} A {2,3,5,7,10} {2,3,5,7,9,10} 17

11 4 6 a {11} {11} b {6} {6}

{2,3,5,7,10} {2,5,7,8,10} {2,3,5,7,9,10} {2,4,5,7,8,10} {11} {6} {2,4,5,7,8,10} {2,5,7,8,10} {2,4,5,7,8,10} {2,5,7,8,10} φ φ {2,3,5,7,10} {2,3,5,7,9,10} {2,3,5,7,10} {2,3,5,7,9,10} φ φ {11} {11} {11} {11} φ φ {6} {6} {6} {6} φ φ

A S

5:ASA 6:ASA 3:SS SAS SAS S A a ASA SAS Sb

ASA ASA Sb b Aa Aa ASA

Aa SAS

Sb

S a A S b S A b a A

4:SAS 7:SAS 0:SS

SAS SAS ASA A S SAS Sb Sb

ASA ASA Sb b Aa Aa ASA Aa

a a b b a

1:Aa 2:Sb

DFA

构造LR(0)项目集规范族也可以用GO函数来计算得到。所得到的项目集规范族与上图中的项目集一样:

I0={SS，SAS，Sb，ASA，Aa} GO(I0，a)={ Aa}=I1 GO(I0，b)={ Sb}=I2

GO(I0，S)={ SS，ASA，ASA，Aa，SAS，Sb}=I3 GO(I0，A)={ SAS，SAS，Sb，ASA，Aa}=I4

18

GO(I3，a)={ Aa}=I1 GO(I3，b)={ Sb}=I2

GO(I3，S)={ ASA，SAS，Sb，ASA，Aa}=I5

GO(I3，A)={ ASA，SAS，SAS，Sb，ASA，Aa}=I6 GO(I4，a)={ Aa}=I1 GO(I4，b)={ Sb}=I2

GO(I4，S)={ SAS，ASA，SAS，Sb，ASA，Aa}=I7 GO(I4，A)={ SAS，SAS，Sb，ASA，Aa}=I4 GO(I5，a)={ Aa}=I1 GO(I5，b)={ Sb}=I2

GO(I5，S)={ ASA，SAS，Sb，ASA，Aa}=I5

GO(I5，A)={ ASA，SAS，SAS，Sb，ASA，Aa}=I6 GO(I6，a)={ Aa}=I1 GO(I6，b)={ Sb}=I2

GO(I6，S)={ SAS，ASA，SAS，Sb，ASA，Aa}=I7 GO(I6，A)={ SAS，SAS，Sb，ASA，Aa}=I4 GO(I7，a)={ Aa}=I1 GO(I7，b)={ Sb}=I2

GO(I7，S)={ ASA，SAS，Sb，ASA，Aa}=I5

GO(I7，A)={ ASA，SAS，SAS，Sb，ASA，Aa}=I6 项目集规范族为C={I1，I2，I3，I4，I5，I6，I7}

(3)不是SLR文法

状态3，6，7有移进归约冲突

状态3：FOLLOW(S’)={#}不包含a,b

状态6：FOLLOW(S)={#,a,b}包含a,b,；移进归约冲突无法消解 状态7：FOLLOW(A)={a,b}包含a,b；移进归约冲突消解 所以不是SLR文法。

(4) 构造例如LR(1)项目集规范族 见下图： 对于状态5，因为包含项目[AAS a/b]，所以遇到搜索符号a或b时，应该用AAS归约。又因为状态5包含项目[Aa a/b]，所以遇到搜索符号a时，应该移进。因此存在“移进-归约”矛盾，所以这个文法不是LR(1)文法。

19

b b b 1： 5： 8： SS #ASA a/bSAS a/b A ASA a/bSAS a/bSAS a/b A A ASA a/bSAS a/bSb a/b Aa a/bSb a/bASA a/b SAS a/bASA a/bAa a/b S Sb a/bAa a/b a a S S a S 3： 0： 3： a a A a Aa a/b A SS # SAS #/a/b9： 6： Sb #/a/b SAS a/bASA a/b S ASA a/bASA a/bASA a/b b 4： ASA a/b Aa a/bSb #/a/bAa a/b Aa a/b SAS a/b S SAS a/bSb a/b A b Sb a/b a a S b b 2： 7： SAS #/a/bSAS #/a/b ASA a/bSAS #/a/b ASA a/bSb #/a/b10： S b Aa a/bSb a/b ASA a/b SAS a/bAa a/b Sb a/b A A 5：

20

8. FIRST（AaAb）={ a }, FIRST( BbBa) ={ b },

FIRST(AaAb) ∩FIRST( BbBa) =Ф

且不含左递归，所以该文法是LL(1)的。

拓广文法为S’ →S ,S →AaAb , S→BbBa , A→ε ,B→ ε.

LR(0)项目为：1. S’ →·S ，2. S’ →S· ，3. S →·AaAb , 4. S →A·aAb ,

5. S →Aa·Ab , 6. S →AaA·b , 7. S →AaAb· , 8. S→·BbBa , 9. S→B·bBa , 10. S→Bb·Ba , 11. S→BbB·a , 12. S→BbBa· , 13. A→·，14. B→ ·

LR(0)项目集规范族为： I0 ：：S’ →·S , S →·AaAb , A→·，S→·BbBa , B→ · I1 ：S’ →S· I2 ：S →A·aAb I3 ：S→B·bBa

I4 ：S →Aa·Ab , A→· I5 ：S→Bb·Ba , B→ · I6 ：S →AaA·b I7 ：S→BbB·a I8 ：S →AaAb· I9 ：S→BbBa·

I0 中存在规约－规约冲突，而FOLLOW( A)={a ,b} FOLLOW( B)={a ,b},消除不了，所以该文法不是SLR的是LR(1)的。

第六章 P1–5

(1)

EE1＋T {if (E1.type = int) and (T.type = int ) then E.type := int else E.type := real} ET {E.type := T.type} Tnum.num {T.type := real} Tnum {T.type := int} (2)

21

P1–7

SL1|L2

{S.val:=L1.val+(L2.val/2

L2.length)}

SL {S.val:=L.val}

LL1B {L.val:=2*L1.val + B.val; L.length:=L1.length+1} LB {L.val:=B.c;

L.length :=1} B0 {B.c:=0} B1 {B.c:=1} ***********************/

第七章

P217–1 a*(-b+c) a+b*(c+d/e) -a+b*(-c+d)

ab@c+* abcde/+*+ a@bc@d+*+

A(CD) ACD

(AB)(CD) ABC@D ABCD@E

(AB)(CDE)

if (x+y)*z =0 then (a+b)↑c else a↑b↑c xy+z*0= ab+c↑abc↑↑ ￥ 或 xy+z*0= P1 jez ab+c↑ P2 jump abc↑↑

P1 P2

P217–3

-(a+b)*(c+d)-(a+b+c)的 三元式序列: (1) +, a, b (2) @, (1), - (3) +, c, d (4) *, (2), (3)

22

(5) +, a, b (6) +, (5), c (7) -, (4), (6) 间接三元式序列: 三元式表： (1) +, a, b (2) @, (1), - (3) +, c, d (4) *, (2), (3) (5) +, (1), c (6) -, (4), (5) 间接码表： (1) (2) (3) (4) (1) (5) (6)

四元式序列: (1) (2) (3) (4) (5) (6) (7)

+, a, b, T1 @, T1, -, T2 +, c, d, T3 *, T2, T3, T4 +, a, b, T5 +, T5, c, T6 -, T4, T6, T7

P218–4

自下而上分析过程中把赋值句翻译成四元式的步骤:A:=B*(-C+D) 步骤 输入串 栈 PLACE 四元式 (1) A:=B*(-C+D)

(2) :=B*(-C+D) i A (3) B*(-C+D) i:= A- (4) *(-C+D) i:=i A-B

(5) *(-C+D) i:=E A-B (6) *(-C+D) i:=E A-B (7) (-C+D) i:=E* A-B- (8) -C+D) i:=E*( A-B-- (9) C+D) i:=E*(- A-B--- (10) (11) (12)

+D) +D) +D)

i:=E*(-i i:=E*(-E i:=E*(E

A-B---C A-B---C A-B--T

1(@,C,-, T)

123

(13) (14) (15) (16) (17) (18) (19)

D) )

i:=E*(E+

A-B--T-

111 i:=E*(E+i A-B--T-D

i:=E*(E+E A-B--T-D (+,T,D,T) i:=E(E i:=E*(E) i:=E+E i:=E

A-B--T A-B--T- A-B-T A-T

32212) )

2(*,B,T,T) (:=,T,-,A)

323

(20) A

产生的四元式： (@,C,-, T) (+,T,D,T)

12(*,B,T,T) (:=,T,-,A)

3231P218–5

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

设A ：10*20，B、C、D：20，宽度为w＝4 则 T1:= i * 20 T1:=T1+j T2:=A–84 T3:=4*T1

Tn:=T2[T3] //这一步是多余的 T4:= i + j T5:=B–4 T6:=4*T4 T7:=T5[T6] T8:= i * 20 T8:=T8+j T9:=A–84 T10:=4*T8 T11:=T9[T10] T12:= i + j T13:=D–4 T14:=4*T12 T15:= T13[T14] T16:=T11+T15 T17:=C–4 T18:=4*T16 T19:=T17[T18] T20:=T7+T19 Tn:=T20

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

24

P218–6

100. (jnz, A, -, 0) 101. (j, -, -, 102) 102. (jnz, B, -, 104) 103. (j, -, -, 0) 104. (jnz, C, -, 103) 105. (j, -, -, 106) 106. (jnz, D, -, 104) --假链链首 107. (j, -, -, 100) --真链链首 假链：{106,104，103} 真链：{107,100} P218–7

100. (j<, A, C, 102) 101. (j, -, -, 0) 102. (j<, B, D, 104) 103. (j, -, -, 101) 104. (j=, A, ‘1’, 106) 105. (j, -, -, 109) 106. (+, C, ‘1’, T1) 107. (:=, T1, -, C) 108. (j, -, -, 100) 109. (j≤, A, D, 111) 110. (j, -, -, 100) 111. (+, A, ‘2’, T2) 112. (:=, T2, -, A) 113. (j, -, -, 109) 114. (j, -, - 100) P219–12

/******************** (1)

MAXINT – 5 MAXINT – 4 MAXINT – 3 MAXINT – 2 MAXINT – 1 MAXINT

(2)翻译模式 方法1：

25

for E1 := E2 to E3 do S

SF do MS1FFor I:E1 to E2IidM

SF do MS1

{backpatch(S1.nextlist,nextquad);

backpatch(F.truelist,M.quad);

emit(F.place ‘:=’F.place ‘+’1);

emit(‘j,’F.place ‘,’F.end ‘,’M.quad); S.nextlist := F.falselist; }

{F.falselist:= makelist(nextquad);

FFor I:E1 to E2

Iid

****************/ 方法2：

S→ for id:=E1 to E2 do S1 S→ F S1

F→ for id:=E1 to E2 do Fforid:E1toE2do

M

emit(‘j>,’E1.place ‘,’E2.place ‘,0’); emit(I.Place ‘:=’E1.place); F.truelist := makelist(nextquad); emit(‘j,-,-,-’); F.place := I.place; F.end := E2.place; }

{p:=lookup(id.name); if p <> nil then I.place := p else error}

{M.quad := nextquad}

{

INITIAL=NEWTEMP; emit(‘:=，’E1.PLACE’， -，’ INITIAL); FINAL=NEWTEMP; emit(‘:=，’E2.PLACE’， -，’ FINAL); p:= nextquad+2;

emit(‘j,’ INITIAL ‘,’ FINAL ’,’ p); F.nextlist:=makelist(nextquad); emit(‘j,－,－,－’);

F.place:=lookup(id.name);

26

if F.placenil then

emit(F.place ‘:=’ INITIAL) F.quad:=nextquad; F.final:=FINAL; }

SFS1 {

backpatch(S1.nextlist, nextquad) p:=nextquad+2;

emit(‘j,’ F.place‘,’ F.final ’,’ p );

S.nextlist := merge(F.nextlist, makelist(nextquad)); emit(‘j,－,－,－’); emit(‘succ，’ F.place ’， -，’ F.place); emit(‘j,－,－,’ F.quad);

第七章补充练习

int A[1:5][1:10];

写出下列程序段的三地址形式的中间代码。其中其实地址为Base， 100

for(i=0;ia=b*i+4; if(a>100) {

while((b<10)&&(b>1)) {

a=a+5; b=b+1; } } else {

A[3][i]=b*i+1; a=A[3][i]; b=b+1; } }

27

100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131

i=0

goto 103

i=i+1 (again)

if iif a>100 goto 110 goto 120

if b<10 goto 112 (While) goto 119(102) if b>1 goto 114 goto 119(102) T3=a+5 a=T3 T4=b+1 b=T4

goto 110 goto 102

T5=b*I （else） T6=T5+1 T7=3*10 T8=T7+i T9=T8*4 (Vap)

T10=base-44 （Bap） T10[T9]=T6 a= T10[T9] T11=b+1; b=T11+1

Goto 102( again) (for循环的出口) }

第九章

P270–9

(1) 传名

即当过程调用时，其作用相当于把被调用段的过程体抄到调用出现处，但必须将其中出现的任一形式参数都代之以相应的实在参数。 A:=2; B:=3;

28

A:=A+1; A:=A+(A+B); print A; ∴A=9 (2) 传地址

即当程序控制转入被调用段后，被调用段首先把实在参数抄进相应的形式参数的形式单元中，过程体对形参的任何引用或赋值都被处理成对形式单元的间接访问。当被调用段工作完毕返回时，形式单元（都是指示器）所指的实参单元就持有所希望的值。 ①A:=2;B:=3;T:=A+B

②把T,A,A的地址抄进已知单元J1,J2,J3

③x:＝J1;y:=J2;z:=J3 //把实参地址抄进形式单元，且J2=J3 ④Y↑:=y↑+1

Z↑:=z↑+x↑ // Y↑：对y的间接访问 Z↑：对z的间接访问 ⑤print A A=8

(3) 得结果

每个形参均对应两个单元，第一个存放实参地址，第二个存放实参值，在过程体中对形参的任何引用或赋值都看成是对它的第二个单元的直接访问，但在过程工作完毕返回前必须把第二个单元的内容放到第一个单元所指的那个实参单元中 ①A:=2;B:=3;T:=A+B

②把T,A,A的地址抄进已知单元J1,J2,J3 ③x1:=J1;x2:=T; y1:=J2;y2:=A;

z1:=J3;z2:=A; //将实参的地址和值分别放进两个形式单元中 ④y2:=y2+1; z2:=z2+x2; //对形参第二个单元的直接访问

⑤x1↑：＝x2; y1↑:=y2; z1↑:=z2 //返回前把第二个单元的内容存放到第一个单元所

指的实参地址中

⑥print A A=7

(4) 传值

即被调用段开始工作时，首先把实参的值写进相应的形参单元中，然后就好像使用局部变量一样使用这些形式单元 A:=2; B:=3; x:=A+B y:=A z:=A y:=y+1 z:=z+x print A A=2

过程调用不改变A的值

29

第十章

P306-1

P306-2

read A,B F:=1

C:=A*A B1 D:=B*B

if CE:=E+F B2 write E halt

---------------------------

L1: E:=B*B

F:=F+2

E:=E+F B3 write E

if E>100 goto L2

30

BBBBB

--------------------------- halt B4 ---------------------------

L2: F:=F-1

goto L1 B5 ---------------------------

基本块为B1、B2、B3、B4、B5 P307-4

I:=1 read J,K A:=K*I B:=J*I T:=K*100 L: C:=A*B write C A:=A+K B:=B+J if AB2有回路，所以{B2}是循环，B2既是入口节点，又是出口节点 （1） 代码外提：不存在不变运算，故无代码外提 （2） 强度削弱：A:=K*I B:=J*I *→+

（3） 删除基本归纳变量：I<100 可以用A<100*K或B<100*J代替

31

P307-5

A:=0

I:=1

B:=J+1

C:=B+I

T:=B+100

L1’: A:=C+A

if C=T goto L2

C:=C+1

goto L1’

L2’:

{B2,B3}是循环，B2是入口节点，也是出口节点 （1） 代码外提：B:=J+1 （2） 删除归纳变量

32