admin 管理员组文章数量: 1184232
2025年1月1日发(作者：c语言使用malloc的头文件)
目录
P36-62
P36-72
P36-82
P36-92
P36-102
P36-112
P64–72
P64–83
P64–123
P64–144
P81–15
P81–26
P81–38
P133–18
P133–28
P133–310
P134–511
P164–513
P164–713
P217–114
P217–314
P218–415
P218–515
P218–616
P218–716
P219–1217
P270–918
.
/ 21
1
.
P36-6
<1>
L(G
1
)
是0~9组成的数字串
<2>
最左推导:
最右推导:
P36-7
G
P36-8
文法：
最左推导:
最右推导:
语法树：/********************************
*****************/
P36-9
句子iiiei有两个语法树：
P36-10
/**************
***************/
P36-11
/***************
L1:
L2:
L3:
L4:
***************/
第三章习题参考答案
P64–7
<1>
1(01|)
*
101
X
Y
0
1
1 0 1
1
X 1 2 3 4
确定化：
2 / 21
5
Y
.
{X}
φ
{1,2,3}
{2,3}
{2,3,4}
{2,3,5}
{2,3,4,Y}
0
φ
φ
{2,3}
{2,3}
{2,3,5}
{2,3}
{2,3,5}
1
{1,2,3}
φ
{2,3,4}
{2,3,4}
{2,3,4}
{2,3,4,Y}
{2,3,4,}
0
1 0
0 2 3
0 0 1 1 0
0 1
1
4 5
6
0
1
1 1
最小化：
0
1
2
0
0 0 1 0
0 1
1
3 4
5
0
1
1 1
P64–8
<1>
<2>
<3>
P64–12
a
a,b
a
0
确定化：
{0}
{0,1}
{1}
φ
给状态编号：
0
1
a
1
1
3 / 21
b
2
2
1
a
{0,1}
{0,1}
{0}
φ
b
{1}
{1}
φ
φ
.
2
3
0
3
3
3
a
a
a b b b
0 1
b
2 3
a
最小化：
a a
b b
1 2
a
0
b
b b a
2 3
0
a b
a
a b
b a
4 5
1
a a
已经确定化了,进行最小化
最小化：
b b a
1 2
0
a b
a
P64–14
<1> 0
1
0
0
<2>:
1
(010|)
*
X
Y
0
2
1
1
X
0
确定化：
{X,1,Y}
{1,Y}
{2}
φ
0
{1,Y}
{1,Y}
{1,Y}
φ
4 / 21
Y
1
{2}
{2}
φ
φ
.
给状态编号：
0
1
2
3
0
1
1
1
3
1
2
2
3
3
0
0 1
0
1 0
1 1
1
2 3
0
最小化：
0
1 1 1
0
1
3
0
0
第四章
P81–1
<1> 按照T,S的顺序消除左递归
递归子程序：
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
5 / 21
.
advance;
S;
T
end
end;
其中:
sym:是输入串指针IP所指的符号
advance:是把IP调至下一个输入符号
error:是出错诊察程序
<2>
FIRST={a,^,<}
FIRST
FIRST<
T
>={,,
}
FOLLOW={>,,,#}
FOLLOW
FOLLOW<
T
>={>}
预测分析表
S
T
a ^ < >
,
#
S(T)
TST
TST
TST
Sa
S^
T
是LL<1>文法
T
T
,ST
P81–2
文法：
<1>
FIRST
FIRST
FIRST
FIRST
FIRST
FIRST
FIRST
={<,a,b,^}
FOLLOW
FOLLOW
FOLLOW
FOLLOW
FOLLOW
FOLLOW
FOLLOW
={*,<,a,b,^,+,>,#}
<2>
考虑下列产生式:
FIRST<+E>∩FIRST<ε>={+}∩{ε}=φ
FIRST<+E>∩FOLLOW
FIRST
6 / 21
.
FIRST
FIRST<*F'>∩FIRST<ε>={*}∩{ε}=φ
FIRST<*F'>∩FOLLOW
FIRST<
所以,该文法式LL<1>文法.
<3>
E
E'
T
T'
F
F'
P
+
*
<
ETE'
>
a b ^
ETE'
ETE'
ETE'
#
E
E
E
E
TFT
FPF
TFT
TFT
TFT
FPF
FPF
FPF
T
T
T
T
T
T
T
T
T
T
T
F
F
*F
F
F
F
F
F
F
P(E)
Pa
Pb
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
7 / 21
.
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) 不是,A、B均不满足条件3。
(4) 是,满足三个条件。
***************/
第五章
P133–1
短语: E+T*F, T*F,
直接短语: T*F
句柄: T*F
P133–2
文法：
<1>
最左推导:
最右推导:
<2>
<<
<<
<<
<<
8 / 21
.
<<
<
<
<
<
<
<
<
<
S
"移进-归约"过程：
步骤栈输入串动作
0 # <<
1 #< <
2 #<<
3 #<<< a,a>,^,>,a># 进
5 #<<,^,>,a># 归
6 #<<
7 #<<
8 #<<
9 #<<
10 #<<
11 #<<
12 #<>,a># 归
13 #<
14 #<
15 #<
16 #<
17 #<
18 #<
19 #<
20 #<
21 #<
22 #<
23 #<
24 #<
25 #<
26 #<
27 ## 归
28 #
9 / 21
.
29 #
30 #
31 #
32 #
33 #
34 #S # 归
P133–3
<1>
FIRSTVT={a,^,<}
FIRSTVT
LASTVT={a,^,>}
LASTVT
<2>
a ^ < > ,
a > >
^ > >
< < < < = <
> > >
, < < < > >
G
6
是算符文法,并且是算符优先文法
<3>优先函数
a ^ < > ,
f 4 4 2 4 4
g 5 5 5 2 3
〔4
栈 输入字符串
# 〔a,
#< a,
#>#
#
#〔t,
#〔t,〔 a,a#
#〔t,〔a ,a#
#〔t,〔t ,a#
#〔t,〔t, a#
#〔t,〔t,a #
#〔t,〔t,s #
#〔t,〔t #
#〔t,〔t #
#〔t,s #
#〔t #
#〔t #
10 / 21
动作
预备
进
进
归
进
进
进
归
进
进
归
归
进
归
归
进
.
# s
success
# 归
P134–5
<1>
0.
S
S
1.
S
S
2.
SAS
3.
SAS
4.
SAS
5.
Sb
6.
Sb
7.
ASA
8.
ASA
9.
ASA
10.
Aa
11.
Aa
<2>
1
S A
8
7
9
S
a
10
11
0
A S
3
2
d
确定化：
5
6
{0,2,5,7,10}
{1,2,5,7,8,10
}
{2,3,5,7,10}
{2,5,7,8,10}
{2,3,5,7,9,10
}
{2,4,5,7,8,10
}
{11}
{6}
S
{1,2,5,7,8,10
}
{2,5,7,8,10}
{2,4,5,7,8,10
}
{2,5,7,8,10}
{2,4,5,7,8,10
}
{2,5,7,8,10}
φ
φ
A
{2,3,5,7,10}
{2,3,5,7,9,10
}
{2,3,5,7,10}
{2,3,5,7,9,10
}
{2,3,5,7,10}
{2,3,5,7,9,10
}
φ
φ
a
{11}
{11}
{11}
{11}
{11}
{11}
φ
φ
4
b
{6}
{6}
{6}
{6}
{6}
{6}
φ
φ
A S
5:
ASA
6:
ASA
S A a
3:
S
S
SAS
SAS
b
ASA
SAS
Sb
S a A S b S A b
ASA
ASA
Sb
a A
Aa
Aa
ASA
4:
SAS
7:
S
0:
S
SAS
S
Aa
AS
A S
AS
SAS
ASA
S
S
b
b
SAS
Sb
Sb
a a b b a
ASA
ASA
Sb
2:
Sb
ASA
Aa
1:
Aa
Aa
DFA
Aa
11 / 21
.
构造LR<0>项目集规范族也可以用GO函数来计算得到。所得到的项目集规范族与上图中的
项目集一样:
I
0
={
S
S
,
SAS
,
Sb
,
ASA
,
Aa
}
GO<
I
0
,a>={
Aa
}=
I
1
GO<
I
0
,b>={
Sb
}=
I
2
GO<
I
0
,S>={
S
S
,
ASA
,
ASA
,
Aa
,
SAS
,
Sb
}=
I
3
GO<
I
0
,A>={
SAS
,
SAS
,
Sb
,
ASA
,
Aa
}=
I
4
GO<
I
3
,a>={
Aa
}=
I
1
GO<
I
3
,b>={
Sb
}=
I
2
GO<
I
3
,S>={
ASA
,
SAS
,
Sb
,
ASA
,
Aa
}=
I
5
GO<
I
3
,A>={
ASA
,
SAS
,
SAS
,
Sb
,
ASA
,
Aa
}=
I
6
GO<
I
4
,a>={
Aa
}=
I
1
GO<
I
4
,b>={
Sb
}=
I
2
GO<
I
4
,S>={
SAS
,
ASA
,
SAS
,
Sb
,
ASA
,
Aa
}=
I
7
GO<
I
4
,A>={
SAS
,
SAS
,
Sb
,
ASA
,
Aa
}=
I
4
GO<
I
5
,a>={
Aa
}=
I
1
GO<
I
5
,b>={
Sb
}=
I
2
GO<
I
5
,S>={
ASA
,
SAS
,
Sb
,
ASA
,
Aa
}=
I
5
GO<
I
5
,A>={
ASA
,
SAS
,
SAS
,
Sb
,
ASA
,
Aa
}=
I
6
GO<
I
6
,a>={
Aa
}=
I
1
GO<
I
6
,b>={
Sb
}=
I
2
GO<
I
6
,S>={
SAS
,
ASA
,
SAS
,
Sb
,
ASA
,
Aa
}=
I
7
GO<
I
6
,A>={
SAS
,
SAS
,
Sb
,
ASA
,
Aa
}=
I
4
GO<
I
7
,a>={
Aa
}=
I
1
GO<
I
7
,b>={
Sb
}=
I
2
GO<
I
7
,S>={
ASA
,
SAS
,
Sb
,
ASA
,
Aa
}=
I
5
GO<
I
7
,A>={
ASA
,
SAS
,
SAS
,
Sb
,
ASA
,
Aa
}=
I
6
项目集规范族为C={
I
1
,
I
2
,
I
3
,
I
4
,
I
5
,
I
6
,
I
7
}
<3>不是SLR文法
状态3,6,7有移进归约冲突
状态3：FOLLOW
状态6：FOLLOW={#,a,b}包含a,b,；移进归约冲突无法消解
状态7：FOLLOW={a,b}包含a,b；移进归约冲突消解
所以不是SLR文法。
<4>构造例如LR<1>项目集规范族
见下图：
对于状态5,因为包含项目[
AAS a/b
],所以遇到搜索符号a或b时,应该用
AAS
归约。又因为状态5包含项目[
Aa a/b
],所以遇到搜索符号a时,应该移进。因此存
在"移进-归约"矛盾,所以这个文法不是LR<1>文法。
b b b
1：
5： 8：
S
S #
ASA a/b
SAS a/b
A
A A
ASA a/b
SAS a/b
SAS a/b
ASA a/b
Aa a/b
SAS a/b
Sb a/b
SAS a/b
12 21
S
/
b a/b
ASA a/b
Aa a/b
Sb a/b
ASA a/b
Aa a/b
.
S
a
a
S
S a S
3：
0： 3：
a a A a
Aa a/b
A
S
S #
SAS #/a/b
9：
6：
S
Sb #/a/b
SAS a/b
ASA a/b
b
4：
ASA a/b
ASA a/b
ASA a/b
S
Sb #/a/b
Aa a/b
ASA a/b
A b
Aa a/b
Aa a/b
a a S b b
SAS a/b
SAS a/b
2： 7：
Sb a/b
Sb a/b
SAS #/a/b
SAS #/a/b
10：
S b
ASA a/b
SAS #/a/b
Sb a/b
A
Sb #/a/b
A
ASA a/b
Aa a/b
/********************第六章会有点难
ASA a/b
Aa a/b
SAS a/b
第六章
Sb a/b
5：
P164–5
<1>
E
E1＋T {if < = int> and < = int >
then := int
else := real}
E
T { := }
T
{ := real}
T
num { := int}
<2>
P164–7
S
L1|L2
S
L
L
L1B
L
B
B
0
{:=+
>}
{:=}
{:=2* + ;
:=+1}
{:=B.c;
:=1}
{B.c:=0}
13 / 21
.
B
1 {B.c:=1}
***********************/
第七章
P217–1
a*<-b+c> ab@c+*
a+b*
-a+b*<-c+d> a@bc@d+*+
if
或 xy+z*0= P1 jez ab+c↑ P2 jump abc↑↑
P1 P2
P217–3
-
三元式序列:
(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,
T
1
(2) @,
T
1
, -,
T
2
(3) +, c, d,
T
3
(4) *,
T
2
,
T
3
,
T
4
14 / 21
xy+z*0= ab+c↑abc↑↑￥
.
(5) +, a, b,
T
5
(6) +,
T
5
, c,
T
6
(7) -,
T
4
,
T
6
,
T
7
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> +D> i:=E*<-i A-B---C
<11>
<12>
<13>
<14>
<15>
<16>
<17>
<18>
<19>
+D>
+D>
D>
>
i:=E*<-E
i:=E* i:=E* A-B---C A-B-- T A-B-- T - 1 1 1 <@,C,-, T > 1 i:=E* T -D i:=E* T -D <+, T ,D, T > i:=E i:=E* i:=E+E i:=E A-B-- T A-B-- T - A-B- T A- T 3 (20) A 2 2 112 > > 2 <*,B, T , T > <:=, T ,-,A> 3 23 产生的四元式： <@,C,-, T > <+, T ,D, T > 12 <*,B, T , T > <:=, T ,-,A> 3 23 1 P218–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 15 / 21 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 ******************/ P218–6 100. 101. 102. 103. 104. 105. 106. 107. 假链：{106,104,103} 真链：{107,100} P218–7 100. 101. 102. 103. 104. 105. 106. <+, C, ‘1’, T1> 107. <:=, T1, -, C> 108. 109. 110. 111. <+, A, ‘2’, T2> 112. <:=, T2, -, A> . / 21 16 . 113. 114. P219–12 /******************** <1> MAXINT – 5 MAXINT – 4 MAXINT – 3 MAXINT – 2 MAXINT – 1 MAXINT <2>翻译模式 方法1： for E1 := E2 to E3 do S SF do MS 1 {backpatch backpatch emit< ‘:=’ ‘+’1>; emit<‘j ,’ ‘,’ ‘,’>; st := ist; } {ist:= makelist FFor I:E 1 to E 2 Iid ****************/ 方法2： S→ for id:=E1 to E2 do S1 S→ F S1 F→ for id:=E1 to E2 do M emit<‘j>,’ ‘,’ ‘,0’>; emit< ‘:=’>; st := makelist emit<‘j,-,-,-’>; := ; := ; } {p:=lookup<>; if p <> nil then := p else error} { := nextquad} Fforid:E1toE2 do { 17 / 21 . INITIAL=NEWTEMP; emit<‘:=,’’, -,’ INITIAL>; FINAL=NEWTEMP; emit<‘:=,’’, -,’ FINAL>; p:= nextquad+2; emit<‘j,’ INITIAL ‘,’ FINAL ’,’ p>; st:=makelist emit<‘j,－,－,－’>; :=lookup<>; if il then emit< ‘:=’ INITIAL> :=nextquad; :=FINAL; } { backpatch p:=nextquad+2; emit<‘j,’ ‘,’ ’,’ p >; st := merge emit<‘j,－,－,－’>; emit<‘succ,’ ’, -,’ >; emit<‘j,－,－,’ >; } 第九章 P270–9 <1> 传名 即当过程调用时,其作用相当于把被调用段的过程体抄到调用出现处,但必须将其中出现的 任一形式参数都代之以相应的实在参数。 A:=2; B:=3; A:=A+1; A:=A+ 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 18 / 21 . 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的值 P306-1 P306-2 read A,B F:=1 C:=A*A B 1 D:=B*B if C L 1 --------------------------- E:=A*A 19 / 21 BB B F:=F+1 E:=E+F B 2 write E halt --------------------------- L 1 : E:=B*B F:=F+2 E:=E+F B 3 write E if E>100 goto L 2 --------------------------- halt B 4 --------------------------- L 2 : F:=F-1 goto L 1 B 5 --------------------------- 基本块为 B 1 、 B 2 、 B 3 、 B 4 、 B 5 P307-4 . BB 20 / 21 . 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 A halt B2有回路,所以{B2}是循环,B2既是入口节点,又是出口节点 （1） 代码外提：不存在不变运算,故无代码外提 （2） 强度削弱：A:=K*I B:=J*I *→+ （3） 删除基本归纳变量：I<100 可以用A<100*K或B<100*J代替 P307-5 A:=0 I:=1 {B2,B3}是循环,B2是入口节点,也是出口节点 （1） 代码外提：B:=J+1 （2） 删除归纳变量 B:=J+1 C:=B+I T:=B+100 L1’: A:=C+A if C=T goto L2 C:=C+1 goto L1’ 21 / 21 L2’:
版权声明：本文标题：编译原理第三版课后习题答案解析 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.roclinux.cn/p/1735805452a1689886.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论