《编译原理实践及应用》习题的参考答案

附录 部分习题参考答案

第1章参考答案：

1，2，3，4，5，6，7解答：略！

第2章参考答案：

1，2，3：解答：略！ 4. 解答：

A：① B：③ C：① D：②

5. 解答： 用E表示<表达式>，T表示<项>，F表示<因子>，上述文法可以写为：

E → T | E+T T → F | T*F

F → (E) | i 最左推导：

E=>E+T=>E+T+T=>T+T+T=>F+T+T=>i+T+T=>i+F+T=>i+i+T =>i+i+F=>i+i+i

E=>E+T=>T+T=>F+T=>i+T=>i+T*F=>i+F*F=>i+i*F=>i+i*i 最右推导：

E=>E+T=>E+F=>E+i=>E+T+i=>E+F+i=>E+i+i=>T+i+i =>F+i+i=>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*i i+i+i和i+i*i的语法树如下图所示。

i+i+i、i+i*i的语法树

6. 解答：

(1) 终结符号为：{or,and,not,(,),true,false}

非终结符号为：{bexpr,bterm,bfactor} 开始符号为：bexpr

(2) 句子not(true or false)的语法树为：

7. 解答：

(1) 把anbnci分成anbn和ci两部分，分别由两个非终结符号生成，因此，生成此文法的产生式为：

S → AB

A → aAb|ab B → cB|?

(2) 令S为开始符号，产生的w中a的个数恰好比b多一个，令E为一个非终结符号，产生含相同个数的a和b的所有串，则产生式如下：

S → aE|Ea|bSS|SbS|SSb E → aEbE|bEaE|?

(3) 设文法开始符号为S，产生的w中满足|a|≤|b|≤2|a|。因此，可想到S有如下的产生式 （其中B产生1到2个b）：

S → aSBS|BSaS B → b|bb

(4) 解法一：

S →〈奇数头〉〈整数〉〈奇数尾〉 |〈奇数头〉〈奇数尾〉 |〈奇数尾〉 〈奇数尾〉→ 1|3|5|7|9

〈奇数头〉→ 2|4|6|8|〈奇数尾〉 〈整数〉→ 〈整数〉〈数字〉|〈数字〉 〈数字〉→ 0|〈奇数头〉

解法二：文法G=({S,A,B,C,D},{0,1,2,3,4,5,6,7,8,9},P,S)

S→AB | B A→AC | D B→1|3|5|7|9 D→2|4|6|8|B

C→0|D

(5) 文法G=({N,S,N,M,D},{0,1,2,3,4,5,6,7,8,9 },S,P)

S→N0 | N5 N→MD|?

M→1|2|3|4|5|6|7|8|9

D→D0 | DM |?

(6) G[S]：S→aSa | bSb | cSc | a | b | c |? 8. 解答：

(1) 句子abab有如下两个不同的最左推导：

S => aSbS => abS =>abaSbS => ababS => abab S => aSbS => abSaSbS => abaSbS => ababS => abab 所以此文法是二义性的。

(2) 句子abab的两个相应的最右推导：

S => aSbS => aSbaSbS => aSbaSb => aSbab => abab S => aSbS => aSb => abSaSb => abSab => abab (3) 句子abab的两棵分析树：

(a)

9，10：解答：略！

(b)

(4) 此文法产生的语言是：在{a，b}上由相同个数的a和b组成的字符串。

第3章习题解答：

1. 解答：

(1) √ (2) √ (3) × (4) × (5) √ (6) √ 2. [分析]

有限自动机分为确定有限自动机和非确定有限自动机。确定有限自动机的确定性表现在映射?：Q×VT -->q是单值函数，也就是说，对任何状态 q∈Q和输入字符串a∈VT，? (q,a)唯一确定下一个状态。显然，本题给出的是一个确定的有限自动机，它的状态转换图是C中的②。

它所接受的语言可以用正则表达式表示为00(0|1)*，表示的含义为由两个0开始的后跟任意个（包含0个）0或1组成的符号串的集合。 2. 解答：A:④ B:③ C:② D:② E: ④ 3，4．解答：略！ 5．解答：

6．解答：

(1) (0|1)01

(2) ((1|2|…|9)(0|1|2|…|9)*| ?)(0|5) (3) (0|1)*(011)(0|1)* (4) 1*|1*0(0|10)*(1|?) (5) abc…z (6) (0|10*1)*1

(7) (00|11)((01|10)(00|11)(01|10)(00|11)) (8) [分析]

设S是符合要求的串，|S|=2k+1 (k≥0）。 则 S→S10|S21，|S1|=2k (k>0），|S2|=2k (k≥0）。 且S1是{0,1}上的串，含有奇数个0和奇数个1。 S2是{0,1}上的串，含有偶数个0和偶数个1。 考虑有一个自动机M1接受S1，那么自动机M1如下：

*

*

**

***

*

*

和L(M1)等价的正规式，即S1为：

((00|11)|(01|10)(00|11)*(01|10))*(01|10)(00|11)*

类似的考虑有一个自动机M2接受S2，那么自动机M2如下：

和L(M2)等价的正规式，即S2为：

((00|11)|(01|10)(00|11)*(01|10))*

因此，S为：

((00|11)|(01|10)(00|11)*(01|10))*(01|10)(00|11)*0| ((00|11)|(01|10)(00|11)*(01|10))*1

7．解答：

(1) 以0开头并且以0结尾的，由0和1组成的符号串。

(2) {?|?∈{0,1}}

(3) 由0和1组成的符号串，且从右边开始数第3位为0。

(4) 含3个1的由0和1组成的符号串。{?|?∈{0,1}+，且?中含有3个1 } (5) 包含偶数个0和1的二进制串，即{?|?∈{0,1}*，且?中有偶数个0和1} 8. 解答：

*

Q0 Q1 Q2 Q3

*0 1 Q2 Q1 Q3 Q0 Q0 Q3 Q1 Q2

9. 解答：

(1) DFA M=({0，1}，{q0，q1，q2}，q0，{q2}，?)

其中?定义如下:

? (q0，0)=q1 ? (q0，1)=q0 ? (q1，0)=q2 ? (q1，1)=q0 ? (q2，0)=q2 ? (q2，1)=q0

状态转换图为：

(2) 正规式: 1010101

DFA M=({0，1}，{q0，q1，q2，q3}，q0，{q3}，?)，其中?定义如下：

? (q0，0)=q1 ? (q0，1)=q0 ? (q1，0)=q2 ? (q1，1)=q1 ? (q2，0)=q3 ? (q2，1)=q2

? (q3，1)=q3 状态转换图为：

****

10. 解答：

(1) DFA M=({0，1}，{q0，q1，q2，q3}，q0，{q3}，?)，其中?定义如下：

? (q0，0)=q1 ? (q0，1)=q2

? (q1，0)=q1 ? (q1，1)=q3 ? (q2，0)=q3 ? (q2，1)=q1

状态转换图为：

I7 = {S→Sab·}

显然，I1和I5存在移进-归约冲突。求S'和R的Follow集：

Follow(S')={# }

Follow(R)=Follow(S)={a,#}

在I5中，出现的移进－归约冲突，且Follow(R)∩{a}={a}，不能用SLR(1)方法解决。因此，此文法不是SLR(1)文法。

15. 解答：

(1) 构造其拓广文法G'的产生式为

0．S' → S 1．S → A

2．A → BA 3．A → ?

4．B → aB 5．B → b

构造其LR(0)项目集规范族和goto函数(识别活前缀的DFA)如下: I0 = { [S'→·S, #], [S→·A, #], [A→·BA, #, [A→·, #], [B→·aB, a/b/#], [B→·b, a/b/#]} I1 = {[S'→S·, #]}

I2 = {[S→A·, #]}

I3 = {[A→B·A, #], [A→·BA, #], [A→·, #], [B→·aB, a/b/#], [B→·b, a/b/#]} I4 = {[B→b·, a/b/#]} I5 = {[B→a·B, a/b/#], [B→·aB, a/b/#], [B→·b, a/b/#]} I6 = {[A→BA·, #]} I7 = {[B→aB·, a/b/#]}

该文法的LR(1)项目集规范族中没有冲突，所以该文法是LR(1)文法。 构造LR(1)分析表如下：

以上分析表无多的定义入口，所以该文法为LR(1)文法。 (3)对于输入串abab，其分析过程如下：

16. 解答：

(1) 对于产生式S→AaAb|BbBa 来说

First(AaAb)∩First(BbBa)={a}∩{b}=? A，B∈VN仅有一条候选式。

因此，这个文法是LL(1)的。

(2) 下面构造这个文法的识别活前缀的DFA。

I0 = {S'→·S, S→·AaAb, S→·BbBa, A→·, 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·}

由于Follow(A)=Follow(B)={a, b},因此项目集I0中存在归约-归约冲突。在I0状态下，当输入符号是a或是b时，不知用A→?还是B→?进行归约。故此文法不是SLR(1)的。但是，此文法时LR(1)的。 17. 解答：

该文法的拓广文法G'为

0．S' → S

1．S → (SR 2．S → a 3．R → ,SR

4．R → )

构造其LR(0)项目集规范族和goto函数(识别活前缀的DFA)如下:

I0 = {S'→·S, S→·(SR, S→·a} I1 = {S'→S·}

I2 = {S→(·SR, S→·(SR, S→·a} I3 = {S→a·}

I4 = {S→(S·R, R→·,SR, R→·)} I5 = {S→(SR·}

I6 = {R→)·}

I7 = {R→,·SR, S→·(SR, S→·a} I8 = {R→,S·R, R→·,SR, R→·)} I9 = {R→,SR·}

每个LR(0)项目集中没有冲突。因此，此文法是LR(0)文法。其分析表如下：

18．解答： 略！

第5章习题解答：

1，2，3 解答： 略！

4. 解答：

(1) 设S，L，B的值的属性用val表示：

S'→S {printf(S.val)}

1212L2.length

S→L.L {S.val:= L.Val+ L.val/2} S→L {S.val:=L.val}

11

L→LB {L.val:=L.val*2+B.val，

L.length = L1.length+1 }

L→B {L.val:=B.val),

L.length:=2 }

B→0 {B.val:=0} B→ 1 {B.val:=1}

(2) 为S，L引入属性h，用来记录配对的括号个数：

S'→S {printf(S.h)} S→a {S.h:=0} S→(L) {S.h:=S.h+1} L→L(1),S {S.h:=L(1).h+S.h}

L→S {L.h:=S.h)}

(3) 为D引入一个综合属性h，用来记录D中含id的个数：

P→D {printf(D.h)}

1212

D→D;D {D.h:=D.h+D.h} D→id:T {D.h:= 1} D→proc id; D;S {D.h:=D.h+1}

5. 解答：

输入串为bcccaadadadb时的语法树为：

1

1

采用修剪语法树的方法，按句柄方式自下而上归约该语法树，在归约时调用相应的语义规则，由此得到最终的翻译结果为：34242421. 6. 解答：

(a+b)+(c+d/(e-3))*8 7. 解答：

(1) ab-c+*

(2) A not C D not or not or (3) abcde/+*+

(4) A B and C not D or or (5) a-bc-d+*+

(6) A B or C D not E and or and 8. 解答：

三元式 ① (+,a,b) ② (-,1,-) ③ (+,c,d) ④ (*,2,3) ⑤ (+,a,b) ⑥ (+,c,5) ⑦ (-,4,6) 9. 解答：

四元式代码为：

1. (jnz，A，_， x) 2. (j，_，_，3) 3. (jnz，B，_，5) 4. (j，_，_，y) 5. (jnz，C，_，y) 6. (j，_，_，7) 7. (jnz，D，_，y)

四元式 1.(+,a,b,T1) 2.(-,T,-, T2) 3.(+,c,d,T3) 4.(*, T2,T 3,T4) 5.(+,a,b,T5) 6.(+, T5,c, T6) 7.(-, T4,, T6 ,T7)

B1: read N /* 置初值 */

i := 2

B2: if i > N goto B4 /* 第一个for语句 */ B3: T1 := i

T2 := addr(A) /* 数组A的基地址 */ T1 := 2 * T1 T2[T1] := true i := i + 1 goto B2 B4: i := 2

T3 := N ** 0.5

T3 := [T3] + 1 /* [T3]是对T3的值取整 */ B5: if i > T3 goto B12 B6: T4 := i T5 := addr(A) T4:= 2 * T4

if T5[T4] goto B8 B7: goto B11 B8: j := 2 * i

B9: if j > N goto B11 /* 第三个for语句 */ B10: T6 := j T7 := addr(A) T6 := 2 * T6 T7[T6] = false j := j + i goto B9 B11: i := i + 1

goto B5 B12:

(2) 根据上述中间代码，可划分成基本块B1，B2，B3，B4，B5，B6，B7，B8，B9，B10，B11。其程序流图如下：

考查上面的程序流图： D(B3) = { B1, B2, B3 }，又有 B3 → B2，因此 B3 → B2 是一条回边。根据它找到的循环 L1 = { B2, B3 }。

D(B10) = { B1, B2, B4, B5, B6, B9, B10 }，又有 B10 → B9，所以 B10 → B9 是一条回边。根据这条回边找到循环 L2 = { B9, B10 }。

D(B11) = { B1, B2, B4, B5, B6, B9, B11 }，又有 B11 → B5，因此 B11 → B5 是一条回边。根据这条回边找到循环 L3 = { B11, B9, B10, B8, B7, B6, B5 } (3) 进行代码外提

把在循环中不随循环变化的操作提到循环外的前置结点中，且在基本块中作复写传播和删除无用赋值。结果程序流图如图1。

(4) 进行强度削弱和删除归纳变量后，其程序流图如图2。

图1 代码外提、复写传播和删除无用赋

值后的流图 10. 解答：略！

图2 强度削弱和删除归纳变量后的流图

第8章习题解答：

1，2. 解答：略！ 3. 解答：

设所有变量均用名字表示地址，寄存器名字用R0、R1和R2表示。目标代码如下：

(1) MOV x，#1 (2) MOV x，y (3) ADD x，#1 (4) MOV R1，b MUL R1，c

(5) MOV R0，b

ADD R0，c MOV R1，a DIV R1，R0 MOV R2，e

ADD R1，a MOV x，R1

4. 解答：

MOV R0，A SUB R0，B MOV R1，C ADD R1，D MOV S， R1 MOV R1，E SUB R1，F DIV R1，R0 MUL R1，S

MOV V， R1

5. 解答：

(1) MOV R0,b

MUL R0,c ADD R0,a

MOV x,R0 (2) MOV R0,a

DIV R0,b SUB R0,c DIV R0,d MOV x,R0

6. 解答： 略！

ADD R2，f MUL R2，d SUB R1，R2 MOV x，R1

(3) MOV R0,#0

SUB R0,b MUL R0,a

MOV R1,d ADD R1,e MOV R2,c SUB R2,R1 ADD R0,R2 MOV x,R0

8. (j，_，_，x)

10. 解答：

11. 解答：

(1) 四元式序列为：

1．（j<,A,C,3） 2.(j,-,-,14) 3.(j<,B,D,5) 4.(j,-,-,14) 5.(j=,A,1,7)

8.(:=,T,-,C) 9.(j,-,-,14) 11.(j,-,-,14) 12.(+,A,2,T2) 13.(:=, T2,-,A)

6.(j,-,-,10) 14. 7.(+,c,1,T1)

(2) 四元式序列为：

1. (j＞0，x，0，3)

2. (j，_，_，8) 3. (j＞，y，0，5) 4. (j，_，_，8) 5. (＋，x，y，T1) 6. (:＝，T1，_，z)

(3) 四元式序列为：

0. (+，A，3，t0) 1. (:=，t0 ， ，t1) 2. (*，C，A，t2) 3. (*，t2，2，t3)

(4) 四元式序列为：

0. (*,b,2,t0)

1. (:=, t0, ,i) 2. (:=,100, , t1 ) 3. (j, , , 6) 4. (+,i,1,t2 ) 5. (:=, t2, , i)

7. (j，_，_，12) 8. (＋，x，2，T2) 9. (:＝，T2，_，x) 10. (＋，y，3，T3) 11. (:＝，T3，_，y) 12.

4. (:=， t3， ，B) 5. (j<，X，0，7) 6. (j， ， ，0) 7.

8. (+, c, d, t4 ) 9. (*,t3, t4, t5) 10. (+, a, b, t6 ) 11. (+, t6 c, t7 ) 12. ( -, t5, t7, t8) 13. ( :=, t8, , x )

6. (j>, i,t1,15) 7. (+, a, b, t3 )

12. 解答：略！

14. (j, , , 4) 15.

第6章习题解答：

1，2，3，4，5 解答：略！ 6. 解答：

本题考查的要点是掌握栈式动态存储分配策略中运行的布局，填充过程活动记录display表的内容。

运行栈的布局遵循“先进后出”原则，即一个过程调用另一个过程时，被调用过程则在调用过程的栈顶构筑自己的数据区，形成自己的活动记录，包括自己的display表。而display表内容的项数与过程的嵌套层次有关，一般比过程的嵌套层数大1。

(1) demo → A

此时的运行栈只有主程序demo和过程A的2个数据区，过程A只引用主程序demo全局

数据和其自身的局部数据，因此其display表内容有2项，即主程序数据区首址和过程A的主程序数据区首址。

(2) demo →A→B 此时的运行栈只有主程序demo、过程A和过程B的3个数据区，过程B嵌套定义在过程A中，要引用主程序demo全局数据、过程A的数据和其自身的局部数据，因此其display

表内容有3项，即主程序数据区首址、过程A的主程序数据区首址和过程B本身的数据区首址。

(3) demo →A→B→B 此时的运行栈包括主程序demo、过程A和2个过程B的实例的4个数据区，过程B要引用的数据区还是3个：主程序demo全局数据、过程A的数据和当前活跃过程B的局部数据（栈顶数据项），因此其display表内容还是有3项，即主程序数据区首址、过程A的主程序数据区首址和当前活跃过程B本身的数据区首址。

(4) demo →A→B→B→A

此时的运行栈包括主程序demo、2个过程A和2个过程B的实例的5个数据区，但过程

A只引用主程序demo全局数据和其自身的局部数据，因此其display表内容只有2项，即主程序数据区首址和过程A的主程序数据区首址。

各个运行时刻运行栈的布局和使用的display表如图。

第7章习题解答：

1. 解答：

A：局部 B：全局 C：代码外提 D：削减运算强度 E：删除归纳变量 2，3. 解答：略！

4. 解答：

程序流图如下：

回边为：B4→B3，循环L={B3,B4} 5.解答：

各结点n的必经结点集D(n)如下：

D(n0) = {n0} D(n1) = {n0, n1} D(n2) = {n0, n1, n2} D(n3) = {n0, n1, n2, n3}

D(n4) = {n0, n1, n2, n4} D(n5) = {n0, n1, n2, n5} D(n6) = {n0, n1, n2, n5, n6} D(n7) = {n0, n1, n2, n5, n6, n7} 回边和循环：

因为 D(n5) = {n0, n1, n2, n5} ，且 n5 → n2，所以 n5 → n2为一条回边。根据它求出的循环 L1 = {n2, n5, n3, n4}。

因为D(n6) = {n0, n1, n2, n5, n6} ，且 n6 → n1，所以n6 → n1为一条回边。根据这条回边，求出的循环 L2 = {n6, n1, n5, n3, n4, n2}。

6. 解答：

(1) 首先划分基本块并画出其程序流图，其中有三个基本块B1，B2，B3，有一条回边B2 → B2，相应的循环是{B2}。

(2) 强度削弱： 在B2中A和B为乘法运算，可以削弱它们的运算强度，变乘法为加法。优化结果如下图。

(3) 删除归纳变量：在循环中，i是循环的基本归纳变量，A，B是同族的归纳变量，且有线性关系，变换循环控制条件，流图如下。

(4) 代码外提：由于删除归纳变量后有R :=K * 100，是循环不变运算，可以提到前置结点B2'中。

7. 解答：

8. 解答：

(1) DAG如下：

(2) 优化后的三地址代码为：

T3:＝S－R T4:＝S＋R A:＝5*T4

B:＝T3＋T4

9. 解答：(本题中假设采用字节地址，两个字节作为一个机器字。)

(1)程序的中间代码如下：

本文来源：https://www.bwwdw.com/article/4rod.html