编译原理课后习题第三版答案

第二章
P366
(1)
0~9组成数字串
(2)
左推导

右推导

P367
G(S)

P368
文法：

左推导

右推导

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

*****************
P369
句子iiiei两语法树：


P3610
**************

***************
P3611
***************
L1

L2

L3

L4

***************
第三章题参考答案
P64–7
(1)
X
Y


X
1
2
3
4
Y
5
0

1 1 0 1


1
确定化：

0
1
{X}
φ
{123}
φ
φ
φ
{123}
{23}
{234}
{23}
{23}
{234}
{234}
{235}
{234}
{235}
{23}
{234Y}
{234Y}
{235}
{234}

0

3
2
0
1 0

1
0 0 1 1 0
6
5
4
0 1
0
1
1 1
化：

0

0
2
1

1
0 0 1 0
5
4
3
0 1
0
1
1 1

P64–8
(1)

(2)

(3)

P64–12
(a)
a

1
0
ab

a

确定化：

a
b
{0}
{01}
{1}
{01}
{01}
{1}
{1}
{0}
φ
φ
φ
φ

状态编号：

a
b
0
1
2
1
1
2
2
0
3
3
3
3

a

1
0
a


a b b b
3
2

b

a

化：


a a

2
1
0
b b

a
b


(b)
0
3
2
b b a

a b
a
a b
5
4
1
b a
a a

已确定化进行化
化：


0
2
1
b b a

a b

a

P64–14
(1) 0
1
0
1

0

(2)

Y
X



2


0
1
Y
1
X



0

确定化：

0
1
{X1Y}
{1Y}
{2}
{1Y}
{1Y}
{2}
{2}
{1Y}
φ
φ
φ
φ
状态编号：

0
1
0
1
2
1
1
2
2
1
3
3
3
3
0
1
0

0
1 0
3
2
1 1
1

0
化：

0
3
1
0
1 1 1

0
0
第四章
P81–1
(1) TS序消左递

递子程序：
procedure S
begin
if sym＇a＇ or sym＇^＇
then abvance
else if sym＇(＇
then begin
advanceT
if sym＇)＇ then advance
else error
end
else error
end
procedure T
begin
S
end
procedure
begin
if sym＇＇
then begin
advance
S
end
end
中
sym输入串指针IP指符号
advanceIP调输入符号
error出错诊察程序
(2)
FIRST(S){a^(}
FIRST(T){a^(}
FIRST(){}
FOLLOW(S){)#}
FOLLOW(T){)}
FOLLOW(){)}
预测分析表

a
^
(
)

#
S






T













LL(1)文法
P81–2
文法：

(1)
FIRST(E){(ab^}
FIRST(E＇){+ε}
FIRST(T){(ab^}
FIRST(T＇){(ab^ε}
FIRST(F){(ab^}
FIRST(F＇){*ε}
FIRST(P){(ab^}
FOLLOW(E){#)}
FOLLOW(E＇){#)}
FOLLOW(T){+)#}
FOLLOW(T＇){+)#}
FOLLOW(F){(ab^+)#}
FOLLOW(F＇){(ab^+)#}
FOLLOW(P){*(ab^+)#}
(2)
考虑列产生式

FIRST(+E)∩FIRST(ε){+}∩{ε}φ
FIRST(+E)∩FOLLOW(E＇){+}∩{#)}φ
FIRST(T)∩FIRST(ε){(ab^}∩{ε}φ
FIRST(T)∩FOLLOW(T＇){(ab^}∩{+)#}φ
FIRST(*F＇)∩FIRST(ε){*}∩{ε}φ
FIRST(*F＇)∩FOLLOW(F＇){*}∩{(ab^+)#}φ
FIRST((E))∩FIRST(a) ∩FIRST(b) ∩FIRST(^)φ
该文法式LL(1)文法
(3)

+
*
(
)
a
b
^
#
E








E＇








T








T＇








F








F＇








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
begin
advance E
if sym＇)＇ then advance
else error
end
else error
end
P81–3
***************
(1) 满足三条件
(2) A满足条件3
(3) AB均满足条件3
(4) 满足三条件
***************
第五章
P133–1

短语 E+T*F T*F
直接短语 T*F
句柄 T*F
P133–2
文法：

(1)
左推导

右推导

(2)
(((aa)^(a))a)
(((Sa)^(a))a)
(((Ta)^(a))a)
(((TS)^(a))a)
(((T)^(a))a)
((S^(a))a)
((T^(a))a)
((TS(a))a)
((T(a))a)
((T(S))a)
((T(T))a)
((TS)a)
((T)a)
(Sa)
(TS)
(T)
S
移进约程：
步骤 栈 输入串 动作
0 # (((aa)^(a))a)# 预备
1 #( ((aa)^(a))a)# 进
2 #(( (aa)^(a))a)# 进
3 #((( aa)^(a))a)# 进
4 #(((a a)^(a))a)# 进
5 #(((S a)^(a))a)#
6 #(((T a)^(a))a)#
7 #(((T a)^(a))a)# 进
8 #(((Ta )^(a))a)# 进
9 #(((TS )^(a))a)#
10 #(((T )^(a))a)#
11 #(((T) ^(a))a)# 进
12 #((S ^(a))a)#
13 #((T ^(a))a)#
14 #((T ^(a))a)# 进
15 #((T^ (a))a)# 进
16 #((TS (a))a)#
17 #((T (a))a)#
18 #((T (a))a)# 进
19 #((T( a))a)# 进
20 #((T(a ))a)# 进
21 #((T(S ))a)#
22 #((T(T ))a)#
23 #((T(T) )a)# 进
24 #((TS )a)#
25 #((T )a)#
26 #((T) a)# 进
27 #(S a)#
28 #(T a)#
29 #(T a)# 进
30 #(Ta )# 进
31 #(TS )#
32 #(T )#
33 #(T) # 进
34 #S #
P133–3
(1)
FIRSTVT(S){a^(}
FIRSTVT(T){a^(}
LASTVT(S){a^)}
LASTVT(T){a^)}
(2)

a
^
(
)

a



>
>
^



>
>
(
<
<
<

<
)



>
>

<
<
<
>
>
算符文法算符优先文法
(3)优先函数


a
^
(
)

f
4
4
2
4
4
g
5
5
5
2
3






（4）
栈 输入字符串 动作
# （a(aa)）# 预备
#( a (aa))# 进
#(a (aa))# 进
#(t (aa))#
#（t (aa)）# 进
#（t（ aa））# 进
#（t（a a））# 进
#（t（t a））#
#（t（t a））# 进
#（t（ta ））# 进
#（t（ts ））#
#（t（t ））#
#（t（t） ）# 进
#（ts ）#
#（t ）#
#（t ） # 进
# s #
success
P134–5
(1)
0 1 2 3
4 5 6 7
8 9 10 11
(2)
1



9
8
7
S A
S

11
10
0
a


4
3
2

A S



d 5
6




确定化：

S
A
a
b
{025710}
{1257810}
{235710}
{11}
{6}
{1257810}
{257810}
{2357910}
{11}
{6}
{235710}
{2457810}
{235710}
{11}
{6}
{257810}
{257810}
{2357910}
{11}
{6}
{2357910}
{2457810}
{235710}
{11}
{6}
{2457810}
{257810}
{2357910}
{11}
{6}
{11}
φ
φ
φ
φ
{6}
φ
φ
φ
φ


A S
3




5




6







S A a

b



S a A S b S A b
a A
4




0




7







A S

b


a a b b a
2
1





DFA
构造LR(0)项目集规范族GO函数计算项目集规范族图中项目集样
{}
GO(a){ }
GO(b){ }
GO(S){ }
GO(A){ }
GO(a){ }
GO(b){ }
GO(S){ }
GO(A){ }
GO(a){ }
GO(b){ }
GO(S){ }
GO(A){ }
GO(a){ }
GO(b){ }
GO(S){ }
GO(A){ }
GO(a){ }
GO(b){ }
GO(S){ }
GO(A){ }
GO(a){ }
GO(b){ }
GO(S){ }
GO(A){ }
项目集规范族C{}
(3)SLR文法
状态367移进约突
状态3：FOLLOW(S’){#}包含ab
状态6：FOLLOW(S){#ab}包含ab移进约突法消解
状态7：FOLLOW(A){ab}包含ab移进约突消解
SLR文法
(4) 构造例LR(1)项目集规范族
见图：
状态5包含项目[]遇搜索符号ab时应该约状态5包含项目[]遇搜索符号a时应该移进存移进约矛盾文法LR(1)文法


b b b
8：

1：

5：



A
A A


S
a
a S
3：

S a S
3：

0：


a a A a
A
6：

9：



4：

S
b


S
A b

a a S b b
7：

2：




10：


S b



A
A
5：



第六章
********************第六章会点难
P164–5
(1)
EE1＋T {if (E1type int) and (Ttype int )
then Etype int
else Etype real}
ET {Etype Ttype}
Tnumnum {Ttype real}
Tnum {Ttype int}
(2)
P164–7
SL1|L2 {SvalL1val+(L2val2)}
SL {SvalLval}
LL1B {Lval2*L1val + Bval
LlengthL1length+1}
LB {LvalBc
Llength 1}
B0 {Bc0}
B1 {Bc1}
***********************
第七章
P217–1
a*(b+c) ab@c+*
a+b*(c+de) abcde+*+
a+b*(c+d) a@bc@d+*+



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)
(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) + a b
(2) @
(3) + c d
(4) *
(5) + a b
(6) + c
(7)
P218–4
分析程中赋值句翻译成四元式步骤AB*(C+D)
步骤 输入串 栈 PLACE 四元式
(1) AB*(C+D)
(2) B*(C+D) i A
(3) B*(C+D) i A
(4) *(C+D) ii AB
(5) *(C+D) iE AB
(6) *(C+D) iE AB
(7) (C+D) iE* AB
(8) C+D) iE*( AB
(9) C+D) iE*( AB
(10) +D) iE*(i ABC
(11) +D) iE*(E ABC (@C )
(12) +D) iE*(E AB
(13) D) iE*(E+ AB
(14) ) iE*(E+i ABD
(15) ) iE*(E+E ABD (+D)
(16) ) iE(E AB
(17) iE*(E) AB
(18) iE+E AB (*B)
(19) iE A (A)
(20) A
产生四元式：
(@C )
(+D)
(*B)
(A)
P218–5
****************
设A ：10*20BCD：20宽度w＝4
T1 i * 20
T1T1+j
T2A–84
T34*T1
TnT2[T3] 步余
T4 i + j
T5B–4
T64*T4
T7T5[T6]
T8 i * 20
T8T8+j
T9A–84
T104*T8
T11T9[T10]
T12 i + j
T13D–4
T144*T12
T15 T13[T14]
T16T11+T15
T17C–4
T184*T16
T19T17[T18]
T20T7+T19
TnT20
******************
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) 真链链首
假链：{106104103}
真链：{107100}
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：
for E1 E2 to E3 do S

{backpatch(S1nextlistnextquad)
backpatch(FtruelistMquad)
emit(Fplace ’Fplace +’1)
emit(j’Fplace ’Fend ’Mquad)
Snextlist Ffalselist
}
{Ffalselist makelist(nextquad)
emit(j>’E1place ’E2place 0’)
emit(IPlace ’E1place)
Ftruelist makelist(nextquad)
emit(j’)
Fplace Iplace
Fend E2place
}
{plookup(idname)
if p <> nil then
Iplace p
else error}
{Mquad nextquad}
****************
方法2：
S→ for idE1 to E2 do S1
S→ F S1
F→ for idE1 to E2 do
do
{
INITIALNEWTEMP
emit(’E1PLACE’ ’ INITIAL)
FINALNEWTEMP
emit(’E2PLACE’ ’ FINAL)
p nextquad+2
emit(j£’ INITIAL ’ FINAL ’’ p)
Fnextlistmakelist(nextquad)
emit(j－－－’)
 Fplacelookup(idname)
if Fplace¹nil then
emit(Fplace ’ INITIAL)
 Fquadnextquad
FfinalFINAL
}

{
backpatch(S1nextlist nextquad)
pnextquad+2
emit(j¹’ Fplace’ Ffinal ’’ p )
Snextlist merge(Fnextlist makelist(nextquad))
emit(j－－－’)
 emit(succ’ Fplace ’ ’ Fplace)
emit(j－－’ Fquad)
 }
第九章
P270–9
(1) 传名
程调时作相调段程体抄调出现处必须中出现形式参数代相应实参数
A2
B3
AA+1
AA+(A+B)
print A
∴A9
(2) 传址
程序控制转入调段调段首先实参数抄进相应形式参数形式单元中程体形参引赋值处理成形式单元间接访问调段工作完毕返回时形式单元（指示器）指实参单元持希值
①A2B3TA+B
②TAA址抄进已知单元J1J2J3
③x＝J1yJ2zJ3 实参址抄进形式单元J2J3
④Y↑y↑+1
Z↑z↑+x↑ Y↑：y间接访问
Z↑：z间接访问
⑤print A
A8
(3) 结果
形参均应两单元第存放实参址第二存放实参值程体中形参引赋值成第二单元直接访问程工作完毕返回前必须第二单元容放第单元指实参单元中
①A2B3TA+B
②TAA址抄进已知单元J1J2J3
③x1J1x2T
y1J2y2A
z1J3z2A 实参址值分放进两形式单元中
④y2y2+1 z2z2+x2 形参第二单元直接访问
⑤x1↑：＝x2 y1↑y2 z1↑z2 返回前第二单元容存放第单元指实参址中
⑥print A
A7
(4) 传值
调段开始工作时首先实参值写进相应形参单元中然局部变量样形式单元
A2
B3
xA+B
yA
zA
yy+1
zz+x
print A
A2
程调改变A值
第十章
P3061

P3062
read AB
B1
F1
CA*A
DB*B
B3
B2
if C
EA*A
FF+1
B5
B4
EE+F
write E
halt

EB*B
FF+2
EE+F
write E
if E>100 goto

halt

FF1
goto


基块
P3074
I1
read JK

AK*I
BJ*I
TK*100

L CA*B
write C
AA+K
BB+J
if Ahalt

B2回路{B2}循环B2入口节点出口节点
（1） 代码外提：存变运算代码外提
（2） 强度削弱：AK*I BJ*I *→+
（3） 删基纳变量：I<100 A<100*KB<100*J代
A0
I1

L1’ AC+A
if CR goto L2
CC+1
goto L1’
L2’
BJ+1
CB+I
RB+100



P3075

A0
I1

L1’ AC+A
if CT goto L2
CC+1
goto L1’
L2’
BJ+1
CB+I
TB+100























{B2B3}循环B2入口节点出口节点
（1） 代码外提：BJ+1
（2） 删纳变量
（3） 文档香网(httpswwwxiangdangnet)户传

《香当网》用户分享的内容，不代表《香当网》观点或立场，请自行判断内容的真实性和可靠性！
该内容是文档的文本内容，更好的格式请下载文档