习题参考答案-编译原理及实践教程(第3版)-黄贤英-清华大学出版社_百

附录 部分习题参考答案

第1章习题

1. 解释下列术语。

翻译程序，编译程序，解释程序，源程序，目标程序，遍，前端，后端

解答：略！

2. 高级语言程序有哪两种执行方式?阐述其主要异同点。描述编译方式执行程序的过程。

解答：略！

3. 在你所使用的C语言编译器中，观察程序1.1经过预处理、编译、汇编、链接四个过程

生成的中间结果。

解答：略！

4. 编译程序有哪些主要构成成分？各自的主要功能是什么？

解答：略！

5. 编译程序的构造需要掌握哪些原理和技术？编译程序构造工具的作用是什么？

解答：略！

6. 复习C语言，其字母表中有哪些符号？有哪些关键字、运算符和界符？标识符、整数和

实数的构成规则是怎样的？各种语句和表达式的结构是什么样的？

解答：略！

7. 编译技术可应用在哪些领域？

解答：略！

8. 你能解释在Java编译器中，输入某个符号后会提示一些单词、某些单词会变为不同的颜

色是如何实现的吗？你能解释在Code Blocks中在输入{后，会自动添加}，输入do 会自动

添加while()是为什么吗？

解答：略！

第2章习题

1. 判断题，对下面的陈述，正确的在陈述后的括号内画√，否则画×。

(1) 有穷自动机识别的语言是正规语言。 （ ）

(2) 若r1和r2是Σ上的正则表达式，则r1|r2也是。 （ ）

(3) 设M是一个NFA，并且L(M)＝{x,y,z}，则M的状态数至少为4个。 （ ）

(4) 令Σ＝{a,b}，则所有以b开头的字构成的正规集的正则表达式为b*(a|b)*。（ ）

(5) 对任何一个NFA M，都存在一个DFA M'，使得L(M')=L(M)。 （ ）

1解答：略！

2.从供选择的答案中，选出应填入下面叙述中 ？内的最确切的解答。

有穷自动机可用五元组（Q，V

T

，，q

0

，Q

f

）来描述，设有一有穷自动机M定义如下：

V

T

={0,1}，Q={q

0

,q

1

,q

2

}，Q

f

={q

2

}，的定义为：

 (q

0

，0)=q

1

 (q

1

，0)=q

2

 (q

2

，1)=q

2

 (q

2

，0)=q

2

M是一个 A 有穷状态自动机，它所对应的状态转换图为 B ,它所能接受的语言可以用正

则表达式表示为 C 。其含义为 D 。

供选择的答案：

A: ①歧义的 ②非歧义的 ③确定的 ④非确定的

B:

C： ①(0|1)

*

②00(0|1)

*

③(0|1)

*

00 ④0(0|1)

*

0

D： ①由0和1所组成的符号串的集合

②以0为头符号和尾符号，由0和1所组成的符号串的集合

③以两个0结束的，由0和1所组成的符号串的集合

④以两个0开始的，由0和1所组成的符号串的集合

2. [分析]

有限自动机分为确定有限自动机和非确定有限自动机。确定有限自动机的确定性表现

在映射：Q×V

T

-->q是单值函数，也就是说，对任何状态 q∈Q和输入字符串a∈V

T

， (q,a)

唯一确定下一个状态。显然，本题给出的是一个确定的有限自动机，它的状态转换图是C

中的②。

*

它所接受的语言可以用正则表达式表示为00(0|1)，表示的含义为由两个0开始的

后跟任意个（包含0个）0或1组成的符号串的集合。

2. 解答：A:④ B:③ C:② D:② E: ④

3．查阅自己熟悉的高级语言的规范，如C或Java，确定：字符集是什么（不包含那些只能

出现在字符串或注释中的字符），数字常量的构成形式是什么，标识符的词法规则是什么？

3解答：略！

4．画出下面的状态转换图，并给出相应的识别函数。

(1) C语言中字符常量是由一对单引号括起来的单个字符，或者以开头的两个字符表示

的转义字符；

解答：

(2) C语言中以/开头的单词有多种，如/、/=、//、/*等，其中前两种表示除法运算和除法

赋值运算，它们需要返回单词本身；后两种表示注释：以/*和*/括起来的多行注释、以//标

记的单行注释，后两种识别后不需要返回单词，直接跳过；

其他

=>

0

/

1

/

=

2

4

其他

n

3

*

*

其他

5

*

7

/

5

其他

解答：

0～9

6

*

(3) C语言中的整数有多种形式：十进制、八进制和十六进制；

0

1～9

0

=>

1

0～7

3

其他

2

*

其他

4

*

x/X

5

0～9

0～9、a～f、A～F

|a～f

*

其他

|A～F

7

6

解答：

(4) C语言中不带指数的浮点数；

0～9

其他其他

0～9

=>

0

0

1～9

1

.

.

8

0～9

9

9

解答：

3

其他

5．一个长度为n的字符串，前缀和后缀分别有多少个，如果字符串为abcd，分别是哪些？

解答：前缀和后缀都是n+1个，字符串abcd的前缀分别，，a，ab，abc，abcd，后缀

分别是：，d，cd，bcd，abcd。

6．试写出以下各描述中所表示的正则表达式：

(1) 以01结尾的二进制数串；

解答：(0|1)

*

01

(2) 不以0开头，能被5整除的十进制整数；

解答：((1|2|…|9)(0|1|2|…|9)

*

| )(0|5)

(3) 包含子串011的由0和1组成的符号串的全体；

解答：(0|1)

*

(011)(0|1)

*

(4) 不包含子串011的由0和1组成的符号串的全体；

解答：1

*

(01|0)* | 1

*

0(0|10)

*

(1|)

(5) 按字典序递增排列的所有小写字母串；

解答：a

*

b

*

c

*

…z

*

(6) Σ={0,1}上的含奇数个1的所有串。

解答：(0|10

*

1)

*

1

(7) 包含偶数个0和1的二进制串；

解答：(00|11) | (00|11)

*

((01|10)(00|11)

*

(01|10)(00|11)

*

)

*

(8) 具有偶数个0和奇数个1的由0和1组成的符号串的全体；

解答：[分析]

设S是符合要求的串，|S|=2k+1 (k≥0）。

则 S→S

1

0|S

2

1，|S

1

|=2k (k>0），|S

2

|=2k (k≥0）。

且S

1

是{0,1}上的串，含有奇数个0和奇数个1。

S

2

是{0,1}上的串，含有偶数个0和偶数个1。

考虑有一个自动机M

1

接受S

1

，那么自动机M

1

如下：

和L(M

1

)等价的正规式，即S

1

为：

**

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

*

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

类似的考虑有一个自动机M

2

接受S

2

，那么自动机M

2

如下：

和L(M

2

)等价的正规式，即S

2

为：

**

((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

另一种答案：(参考龙书上，用a，b表示0,1)

(a(aa)b(b(aa)b)(b(aa)ab|a)|(aa)b)((b(aa)b|(ba(aa)b|a)(b(aa)b)(b(aa)ab|a))*

**********

分析过程：

(9)由/* 和 */括起来的注释的串，且串中没有在双引号中的*/；

解答：

*([^*”]”.*”|*+[^/])**

(10)有些语言是大小写敏感的，因此这些语义中的关键字只有一种写法，描述它的正

则表达式比较简单，但SQL语言是大小写不敏感的，如select和SeLect、SELECt等都是一

样的，试描述SQL中的关键字select的大小写不敏感的正则表达式。

解答：select -> [Ss][Ee][Ll][Ee][Cc][Tt]

7．试描述下列正则表达式所描述的语言：

(1) 0(0|1)

*

0

解答：以0开头并且以0结尾的，由0和1组成的符号串。

(2) ((|0)1

*

)

*

解答：{|∈{0,1}

*

}

(3) (0|1)

*

0(0|1)(0|1)

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

(4) 0

*

10

*

10

*

10

*

解答：含3个1的由0和1组成的符号串。{|∈{0,1}

+

，且中含有3个1 }

(5) (00|11)

*

((01|10)(00|11)

*

(01|10)(00|11)

*

)

*

解答：包含偶数个0和1的二进制串，即{|∈{0,1}

*

，且中有偶数个0和1}

8．假定某语言只有三种单词：①关键字if；②关键字while；③标识符，它是除了if和while

以外的所有以字母构成的串。试构造识别该语言的单词的NFA和DFA。

解答：

NFA中有冲突，可是使用最长优先或者先出现优先的方式来解决。

9．给出识别下列在字母表{0,1}上的语言的最小化DFA，并以状态转换图和状态转换表表示。

(1)所有以00结尾的符号串的集合。

解答：(1) DFA M=({0，1}，{q

0

，q

1

，q

2

}，q

0

，{q

2

}，)

其中定义如下:

 (q

0

，0)=q

1

 (q

0

，1)=q

0

 (q

1

，0)=q

2

 (q

1

，1)=q

0

 (q

2

，0)=q

2

 (q

2

，1)=q

0

状态转换图为：

(2)所有具有3个0的符号串的集合。

解答：正规式: 1

*

01

*

01

*

01

*

DFA M=({0，1}，{q

0

，q

1

，q

2

，q

3

}，q

0

，{q

3

}，)，其中定义如下：

 (q

0

，0)=q

1

 (q

0

，1)=q

0

 (q

1

，0)=q

2

 (q

1

，1)=q

1

 (q

2

，0)=q

3

 (q

2

，1)=q

2

 (q

3

，1)=q

3

状态转换图为：

(3)含有偶数个0或偶数个1的字符串。

解答：

Q0

*

Q1

Q2

Q3

0

Q2

Q3

Q0

Q1

1

Q1

Q0

Q3

Q2

10. 构造与下列正则表达式等价的最小状态的DFA。

(1) 10 | (0|11)0

*

1

解答：(1) DFA M=({0，1}，{q

0

，q

1

，q

2

，q

3

}，q

0

，{q

3

}，)，其中定义如下：

 (q

0

，0)=q

1

 (q

0

，1)=q

2

 (q

1

，0)=q

1

 (q

1

，1)=q

3

 (q

2

，0)=q

3

 (q

2

，1)=q

1

状态转换图为：

(2) ((0|1)

*

| (11))

*

解答：DFA M=({0，1}，{q

0

}，q

0

，{q

0

}，)，其中定义如下:

 (q

0

，0)=q

0

 (q

0

，1)=q

0

状态转换图为：

(3) (a|b)

*

a(a|b)

解答：(a|b)

*

a(a|b)

① 求出NFA M:

②确定化，得到DFA M:

③化简: 在第②步中求出的DFA M中没有等价状态，因此它就是最小化的DFA M。

(4) (a|b)

*

a(a|b)(a|b)

解答：(a)b)

*

a(a|b)(a|b)

① 求NFA M：

② 确定化，得到DFA M：

③化简，在第②步中求出的DFA M中没有等价状态，因此它已经是最小化的DFA M了。

11．应用题：

（1）有假定一台自动售货机，接受1元和5角的硬币，出售每瓶1元5角的饮料，顾客每

次向机器中投放1元5角的硬币，就可得到一瓶饮料（注意：每次只给一瓶饮料，且不找

钱），构造该售货机的有穷自动机（可以是NFA或DFA）。

解答：

其中a代表1元硬币，b代表5角硬币

（2）设计一个状态数最少的DFA，其输入字母表是{0，1}，它能接受以00或01结尾的所

有序列。

解答：正规式为：(0|1)

*

(00|01) 化简：(0|1)

*

0(0|1)

不确定的有穷自动机为：

确定化，并最小化得到：

（3）某操作系统下合法的文件名规则为device:ion，其中第一部分（device:）和

第三部分（.extension）可默认，若device、name和extension都是由字母组成，长度不限，

但至少有1位。

① 请写出识别这种文件名的正则表达式

② 画出其对应的NFA；

③ 将上述得到的NFA确定化为等价的DFA。

解答：① 正规式：(dd

*

:| )dd

*

(.dd

*

| )，d代表a~z的字母

② NFA为：

③ DFA为：

d

d

:

2

=>

0

d

d

3

1

d

.

4

d

5

.

（4）一个C语言编译器编译下面的函数gcd()时，报告parse error before ‘else’。这是因为else

的前面少了一个分号。但是如果第一个注释

/* then part */

误写成

/* then part

那么该编译器发现不了遗漏分号的错误。这是为什么？

long gcd(p,q)

long p,q;

{

if (p%q == 0)

/* then part */

return q

else

/* else part */

return gcd(q, p%q);

}

解答：此时编译器认为

/* then part

return q

else

/* else part */

是程序的注释，因此它不可能再发现else 前面的语法错误。

分析 这是注释用配对括号表示时的一个问题。注释是在词法分析时忽略的，而词法分

析器对程序采取非常局部的观点。当进入第一个注释后，词法分析器忽略输入符号，一直到

出现注释的右括号为止，由于第一个注释缺少右括号，所以词法分析器在读到第二个注释的

右括号时，才认为第一个注释处理结束。

为克服这个问题，后来的语言一般都不用配对括号来表示注释。例如Ada语言的注释

始于双连字符（--），随行的结束而终止。如果用Ada语言的注释格式，那么上面函数应写

成

long gcd(p,q)

long p,q;

{

if (p%q == 0)

-- then part

return q

else

-- else part

return gcd(q, p%q);

12．HTML语言不同于传统的程序设计语言，带有很多标记，有些标记还可以带参数，试说

明如何把下面的HTML文档划分成适当的单词，哪些单词应该具有自身的值，各自是怎样

的词法值？

Here is a photo of my garden

See more photos if you like it.

解答：

13．程序算法练习。

(1) 用自己熟悉的语言编写程序，实现词法分析的部分预处理功能：从文件读入源程序，

去掉程序中多余的空格和注释（用/*…*/标识），用空格取代源程序中的tab和换行，结果显

示在屏幕上。

(2) 编写一个将C程序注释之外的所有保留字全部大写的程序。

(3) 用自己熟悉的语言实现下述算法：

① 把正则表达式变成NFA；

② NFA确定化；

③ DFA最小化。

(4) 编程实现识别Sample语言标识符和实数的程序，并完成：

① 写出Sample语言的标识符和实数的正则表达式；

② 画出识别它们的DFA M；

③ 设计出词法分析器的输出形式；

④ 用自己熟悉的某种语言实现识别程序。

(5) 分别编写能实现下述功能的Lex源程序

①该程序复制一个文件，并将每一个非空的空白符序列用一个空格代替。

②将一个PASCAL程序中除注释之外的所有保留字全部小写。

③生成可计算文本文件的字符、单词和行数且能报告这些数字的程序，其中单词是

不带标点或空格的字母和/或数字的序列，标点和空格不计算为单词。

④为一个文本文件添加行号，并将其输出到屏幕上。

⑤将文本中的十进制数替换成十六进制数，并打印被替换的次数。

⑥将输入文件中注释之外的所有大写字母转变成小写字母（即：任何位于分隔符/*和*/

之间的字符不变）。

解答：略

第3章习题

1．语法分析器的功能是什么？其输入/输出各是什么？

解答：略

2．自上而下语法分析和自下而上语法分析的主要差别是什么？

解答：略

3．自上而下语法分析面临的两个主要问题是什么？如何解决？

解答：略

4．解释下列术语：

上下文无关文法、推导、最左推导、最右推导、句型、句子、语言、文法等价、语法树、

二义文法、LL(1)文法、归约、规范归约、句柄、短语、最左素短语、活前缀、项目

解答：略

5. 从供选择的答案中，选出应填入 的正确答案

已知文法G[S]的产生式如下：

S → (L)|a

L → L,S|S

属于L(G[S])的句子是 A ，(a,a)是L(G[S])的句子，这个句子的最左推导是 B ，

最右推导是 C ，语法树是 D。

供选择的答案：

A： ① a ② a,a ③ (L) ④ (L,a)

B,C：① S



(L)



(L,S)



(L,a)



(S,a)



(a,a)

② S



(L)



(L,S)



(S,S)



(S,a)



(a,a)

③ S



(L)



(L,S)



(S,S)



(a,S)



(a,a)

D：

5. 解答：A：① B：③ C：① D：②

6. 已知某算术表达式的文法G为：

(1) → + |

(2) → * |

(3) → i |()

给出i+i+i和i+i*i的最左推导、最右推导和语法树

6. 解答：用E表示< AEXPR >，T表示< TERM >，F表示< FACTOR >，上述文法可以写为：

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的语法树

7. 已知某文法G[bexpr]：

bexpr→bexpr or bterm|bterm

bterm→bterm and bfactor | bfactor

bfactor→not bfactor|(bexpr)|true |false

(1) 请指出此文法的终结符号、非终结符号和开始符号。

(2) 试对句子not(true or false)构造一棵语法树。

7. 解答：

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

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

开始符号为：bexpr

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

8. 试构造生成下列语言的上下文无关文法：

(1) L

1

={a

n

b

n

c

i

| n≥1,i≥0 }。

解答：(1) 把a

n

b

n

c

i

分成a

n

b

n

和c

i

两部分，分别由两个非终结符号生成，因此，生成此文法

的产生式为：

S → AB

A → aAb|ab

B → cB|

(2) L

2

={w | w∈{a,b}

+

，且w中a的个数恰好比b多1 }。

解答：(2) 令S为开始符号，产生的w中a的个数恰好比b多一个，令E为一个非终结

符号，产生含相同个数的a和b的所有串，则产生式如下：

S → aE|Ea|bSS|SbS|SSb

E → aEbE|bEaE|

(3) L

3

={w | w∈{a,b}

+

，且|a|≤|b|≤2|a| }。

解答：(3) 设文法开始符号为S，产生的w中满足|a|≤|b|≤2|a|。因此，可想到S有如下的产

生式 （其中B产生1到2个b）：

S → aSBS|BSaS

B → b|bb

(4) L

4

={w | w是不以0开始的奇数集 }。

解答：(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) L

5

是不允许0开头的能被5整除的无符号数的集合。

解答：(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) 语言L

6

={x|x∈{a,b,c}

*

，x是重复对称排列的（aabcbaa,aabbaa等）}。

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

(7) 用后缀方式表示的算术表达式。

解答： S→SS op|a op →+|-|*|/

(8) 由整数、标识符、四个二目运算（+、-、*、/）构成的表达式。

解答：S→id|num|S op S op →+|-|*|/

9．已知某文法G：

→i|() |

→ + | - | * | /

(1) 试用最左推导证明该文法是二义性的。

(2) 对于句子i+i*i构造两个相应的最右推导。

9. 解答：存在句型i+i*i，有两棵不同的语法树，如下图所示，所以是二义文法。

A

A O A

i

+

A O A

i*i

A

A O A

A O A

*

i+i

i

10. 对下面的陈述，正确的在陈述后的括号内画"√"，否则画"×"

(1) 存在有左递归规则的文法是LL(1)的。 ( )

(2) 任何算符优先文法的句型中不会有两个相邻的非终结符号。 ( )

(3) 算符优先文法中任何两个相邻的终结符号之间至少满足三种关系(ab，ab，ab)

之一。 ( )

(4) 任何LL(1)文法都是无二义性的。 ( )

(5) 每一个SLR(1)文法也都是LR(1)文法。 ( )

(6) 存在一种算法，能判定任何上下文无关文法是否是LL(1)的。 ( )

(7) 任何一个LL(1)文法都是一个LR(1)文法，反之亦然。 ( )

(8) LR(1)分析中括号中的1是指，在选用产生式A→进行分析，看当前读入符号是否在

First()中。

10. 解答：

(1)× (2)√ (3)× (4)√ (5)√ (6)√ (7)× (8)×

11. 选择题，从供选择的答案中，选出应填入____内的正确答案。

(1) 在编译程序中，语法分析分为自顶向下分析和自底向上分析两类。__A__和LL(1)

分析法属于自顶向下分析；__B__和LR分析法属于自底向上分析。自顶向下分析试图为输入

符号串构造一个__C__；自底向上分析试图为输入符号串构造一个__D__。采用自顶向下分析

方法时，要求文法中不含有__E__。

供选择的答案：

A、B： ①深度分析法 ②宽度优先分析法

③算符优先分析法 ④递归子程序分析法

C、D： ①语法树 ②有向无环图

③最左推导 ④最右推导

E： ①右递归 ②左递归

③直接右递归 ④直接左递归

(2) 自底向上语法分析采用___A__分析法，常用的是自底向上语法分析有算符优先分

析法和LR分析法。LR分析是寻找右句型的 ___B__；而算符优先分析是寻找右句型的__C __。

LR分析法中分析能力最强的是___D__；分析能力最弱的是___E__。

供选择的答案：

A： ①递归 ②回溯 ③枚举 ④移进-归约

B、C：①短语 ②素短语 ③最左素短语 ④句柄

D、E：①SLR(1) ②LR(0) ③LR(1) ④LALR(1)

11. 解答：

(1)A：④ B：③ C：③ D：④ E：②

(2)A：④ B：④ C：③ D：③ E：②

12. 试为下述文法构造一个递归下降的分析程序。

(1)假定布尔表达式文法G[bexpr]，其产生式如下：

bexpr→bexpr or bterm | bterm

bterm→bterm and bfactor | bfactor

bfactor→not bfactor|(bexpr) |true |false

解答：①消除给定文法中的左递归，并提取公因子：

bexpr→bterm {or bterm }

bterm→bfactor {and bfactor}

bfactor→not bfactor | (bexpr) | true |false

②用类C语言写出其递归分析程序:

void bexpr();

{

bterm();

WHILE(lookahead =='or') {

match ('or');

bterm();

}

}

void bterm();

{

bfactor();

WHILE(lookahead =='and'){

match ('and');

bfactor();

}

}

void bfactor();

{

if (llokahead=='not') then {

match ('not');

bfactor();

}

else if(lookahead=='(') then {

match (‘(');

bexpr();

match(')');

}

else if(lookahead =='true')

then match ('true)

else if (lookahead=='false')

then match ('false');

else error;

}

(2)假定某语言文法G，其产生式如下：

stmt→if e then stmt stmtTail | while e do stmt | begin list end | s

stmtTail→else stmt | 

list→listTail|stmt

listTail →;list | 

解答：可以将 e 和 s 当做分别代表条件表达式和“其他语句”的终结符号。如果我们

按照下列方法来解决，因为展开可选“else”（非终结符号 stmtTail）而引起的冲突：当我们

从输入中看到一个 else 时，就选择替换这个 else。相当于处理下列输入时的行为：

1. if e then s; if e then s end

2. while e do begin s; if e then e; end

这样就可以写递归下降的分析程序了。

13．已知文法G[S]，其产生式如下：

S→(L)|a

L→ L,S|S

消除左递归，如果是LL(1)文法，构造分析表。说明对输入符号串(a,(a,a))的分

析过程。

13. 解答：

消除所给文法的左递归，得G'：

S →(L)|a

L → SL'

L'→ ,SL' |

实现预测分析器的不含递归调用的一种有效方法是使用一张分析表和一个栈进行联合

控制，下面构造预测分析表：

根据文法G'有：

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

First(L) = { ( , a ) Follow(L) = { ) }

First(L') = { ,} Follow(L') = { ) }

按以上结果，构造预测分析表M如下：

文法G'是LL(1)的，因为它的LL(1)分析表不含多重定义入口。

预测分析器对输入符号串(a,(a,a))做出的分析动作如下：

步骤

1

2

3

4

5

6

栈

#S

#)L(

#)L

#)L'S

#)L'a

#)L'

剩余输入串 输出

(a,(a,a))# #

a,(a,a))# S →(L)

a,(a,a))#

a,(a,a))# L → SL'

a,(a,a))# S →a

,(a,a))#

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

#)L'S,

#)L'S

#)L')L(

#)L')L

#)L')L'S

#)L')L'a

#)L')L'

#)L')L'S,

#)L')L'S

#)L')L'a

#)L')L'

#)L')

#)L'

#)

#

,(a,a))# L'→ ,SL'

(a,a))#

(a,a))# S →(L)

a,a))#

a,a))# L → SL'

a,a))# S →a

,a))#

,a))# L'→ ,SL'

a))#

a))# S →a

))#

))#

L'→



)#

)#

L'→



#

14．求下述文法中各个非终结符的First集、Follow集，各候选式的First集。

(1) S→AB | bC

(2) A→b |

(3) B→aD |

(4) C→AD | b

(5) D→aS | c

14. 解答：

各非终结符的First集：

First(S)={First(A){}}∪{First(B){}}∪{}∪{b}={a,b, }

First(A)={b}∪{}={b,}

First(B)＝{}∪{a}={a,}

First(C)={First(A) {}}∪First(D)∪First(b) ={a,b,c}

First(D)={a}∪{c}={a,c}

各个候选式的First集为：

First(AB)={a,b, } First(bC)={b}

First()＝{} First(b)＝{b}

First(aD)={a} First(AD)={a,b,c}

First(b)={b} First(aS)={a}

First(c)={c}

各非终结符的Follow集的计算：

Follow(S)={#}∪Follow(D) ={#}

Follow(A)=(First(B){})∪Follow(S)∪First(D) ={a,#,c}

Follow(B)=Follow(S) ={#}

Follow(C)=Follow(S) ={#}

Follow(D)=Follow(B)∪Follow(C) ={#}

15. 对下面的文法G：

E→TE'

E'→+E|

T→FT'

T'→T|

F→PF'

F'→*F'|

P→(E)|a|b|∧

(1) 计算这个文法的每个非终结符的First和Follow；

(2) 证明这个文法是LL(1)的；

(3) 构造它的预测分析表。

15．解答：

(1) 求First和Follow集

First(E)=First(T)={(,a,b,∧} ⑦

First(E')={+, } ⑥

First(T)=First(F)={(,a,b, ∧} ④

First(T')=｛(,a,b, ∧, ｝ ⑤

First(F)=First(P)={(,a,b, ∧} ③

First(F')=｛*，｝ ②

First(P)={(,a,b, ∧} ①（计算顺序）

Follow(E)= {#, ) } （1,7）

Follow(E')= Follow(E)={#，)} (1)（使用的产生式）

Follow(T) = First(E')＼{}∪Follow(T') (1,4)

= {+}∪{),#}={+,),#}

Follow(T')= Follow(T)={+,},#} (3)

Follow(F)= First(T')＼{}∪Follow(T) (3,4)

= {(,a,b,∧,+ ,),#}

Follow(F')= Follow(F) (5)

= {(,a,b,∧,+ ,),#}

Follow(P)= First(F')＼{}∪Follow(F) (5,6)

={*,(,a,b,∧,+ ,),#}

(2) 证明:

∵a. 文法不含左递归；

b. 每个非终结符的各个侯选式的First集不相交；

c. First(E')∩Follow(E')={+, }∩{#,),}=

First(T')∩Follow(T')={(,a,b,∧, }∩{+,)}=

First(F')∩Follow(F')={*, }∩{,a,( ∧,+,},#}= 

∴改造后的文法满足LL(1)文法的三个条件，是LL(1)文法。

(3) 预测分析表如下所示。

a b

*

+

E'→+E

T'→

∧

(

) #

E E→TE' E→TE'

E'

E→TE' E→TE'

E'→ E'→

T T→FT' T→FT'

T' T'→T T'→T

T→FT' T→FT'

T'→T T'→T

T'→ T'→

F F→PF' F→PF'

F'

F'→

P P→a

F'→

P→b

F→PF' F→PF'

F'→ F'→

P→∧ P→(E)

F'→*F'

F'→ F'→ F'→

16. 下面文法中哪个是LL(1)的，说明理由。

(1) S→Abc (2) S→Ab

A→a|

B→b|

16.解答：(1)

A→a|B|

B→b|

a. 文法不含左递归；

S→Abc

b. S,A,B各候选式的First集不相交；

A→a│

c. First(A)∩Follow(A)={a,}∩{b}=

B→b│

First(B)∩Follow(B)={b,}∩=

∴该文法为LL(1)文法。

解答：(2)

a. 文法不含左递归；

S→Ab

b. S,A,B各候选式的First集不相交；

A→a│B│

c. First(A)∩Follow(A)={a,b, }∩{b}={b }≠

B→b│

∴ 该文法不是LL(1)文法。

17. 已知文法G[E]：

E→T|E＋T

T→F|T*F

F→(E)|i

(1) 给出句型(T * F＋i)的最右推导，并画出语法树；

(2) 给出句型(T * F＋i)的短语、素短语和最左素短语；

(3) 证明E+T*F是文法的一个句型，指出这个句型的所有短语、直接短语和句柄。

17. 解答：

① 最右推导：

E=>T=>F=>(E)=>(E＋T)=>(E＋F)=>(E＋i)=> (T＋i)=>(T*F＋i)

语法树：

图4.1 句型(T*F＋i)的语法树

② 短语：(T*F＋i)，T*F＋i，T*F，i

素短语：T*F，i

最左素短语：T*F

③ 由于E =>E+T =>E+T*F，故E+T*F为该文法的句型

短语：T*F、E+T*F

直接短语： T*F

句柄： T*F

18. 给定文法G[S]，其产生式如下：

S→(T)|a

T→T,S|S

(1) 给出输入串(a,(a,a))的最左和最右推导过程；

(2) 计算该文法各非终结符的FirstVT和LastVT集；

(3) 构造算符优先表；

(4) 计算上述文法的优先函数；

(5) 给出输入串(a,(a,a))的算符优先分析过程。

18. 解答：

最左推导：

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,(T,a)) => (T,(a,a)) => (S,(a,a)) => (a,(a,a))

文法中S和T的FirstVT和LastVT集为：

FirstVT(S)={a,(} FirstVT(T)={,,a, (}

lastVT(S)={a, ）} lastVT(T)={,,a,)}

文法G[S]的算符优先关系表：

根据优先关系表，对每个终结符或#建立符号f与g，把f

(

和g

)

分成一组。根据G[S]的算

符优先关系表，画出如下的有向图。

优先函数如下：

用算符优先分析法分析句子(a,(a,a))。

给定的输入符号串是文法的一个句子。

19. 给定文法：S→aS | bS | c

(1) 求出该文法对应的全部LR(0)项目；

(2) 构造识别该文法所有活前缀的DFA；

(3) 该文法是否是LR(0)的，若是，构造LR(0)分析表。

(4) 给出输入串ababc的LR分析过程。

19.解答：

（1）.拓广文法

(0)S' S

(1)S aS

(2)S bS

(3)S c

（2）.写出所有的项目

1. S'  · S 2. S'  S·

3. S  · aS 4. S a · S 5. S aS·

6. S  · bS 7. S b · S 8. SbS·

9. S  · c 10. S  c ·

（3）.求项目集规范族

每个项目集中的各个项目不冲突,则是LR(0)文法。

（4）.构造LR(0)分析表

状 ACTION

态

a b

S

0

S

2

S

5

GOTO

c

S

3

S

3

r

3

r

1

S

3

r

2

#

acc

r

3

r

1

r

2

S

1

4

6

S

1

S

2

S

2

S

5

S

3

r

3

S

4

r

1

r

3

r

1

S

5

S

2

S

5

S

6

r

2

r

2

20.下列文法是否为SLR(1)文法？若是，请构造相应的分析表。若不是，请说明理由。

(1) S→Sab|bR

R→S|a

(2) S→aSAB|BA

A→aA|B

B→b

20. 解答：(1) 该文法的拓广文法G

'

为

0．S

'

→ S

1．S → Sab

2．S → bR

3．R → S

4．R → a

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

I

0

= {S'→·S, S→·Sab, S→·bR}

I

1

= {S'→S·, S→S·ab}

I

2

= {S→b·R, R→·S, R→·a, S→·Sab, S→·bR}

I

3

= {S→Sa·b}

I

4

= {S→bR·}

I

5

= {R→S·, S→S·ab}

I

6

= {R→a·}

I

7

= {S→Sab·}

显然，I

1

和I

5

存在移进-归约冲突。求S'和R的Follow集：

Follow(S')={# }

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

在I

5

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

此文法不是SLR(1)文法。

20. 解答：(2) 该文法的拓广文法G'为

0．S

'

→ S

1．S → aSAB

2．S → BA

3．A → aA

4．A → B

5．B → b

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

I

0

= {S'→·S, S→·aSAB, S→·BA, B→·b}

I

1

= {S'→S·}

I

2

= {B→b·}

I

3

= {S→a·SAB, S→·aSAB, S→·BA, B→·b}

I

4

= {S→B·A, A→·aA, A→·B, B→·b}

I

5

= {S→aS·AB, A→·aA, A→·B, B→·b}

I

6

= {S→aSA·B, B→·b}

I

7

= {A→a·A, A→·aA, A→·B, B→·b}

I

8

= {A→B·}

I

9

= {S→BA·}

I

10

= {S→aSAB·}

I

11

= {A→aA·}

显然，上述状态中没有出现冲突。显然，该文法是LR(0)的文法，因此也是SLR(1)的。

求各个非终结符的Follow集，以便构造分析表：

Follow(S

'

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

Follow(A)={a,b,#} Follow(B)={a,b,#}

构造的SLR(1)分析表如下：

21. 设文法G为

S→A

A→BA|

B→aB|b

(1) 证明它是LR(1)文法。

(2) 构造它的LR(1)分析表。

(3) 给出输入符号串abab的分析过程。

21. 解答：

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

0．S' → S

1．S → A

2．A → BA

3．A → 

4．B → aB

5．B → b

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

I

0

= { [S'→·S, #], [S→·A, #], [A→·BA, #, [A→·, #],

[B→·aB, a/b/#], [B→·b, a/b/#]}

I

1

= {[S'→S·, #]}

I

2

= {[S→A·, #]}

I

3

= {[A→B·A, #], [A→·BA, #], [A→·, #],

[B→·aB, a/b/#], [B→·b, a/b/#]}

I

4

= {[B→b·, a/b/#]}

I

5

= {[B→a·B, a/b/#], [B→·aB, a/b/#],

[B→·b, a/b/#]}

I

6

= {[A→BA·, #]}

I

7

= {[B→aB·, a/b/#]}

该文法的LR(1)项目集规范族中没有冲突，所以该文法是LR(1)文法。

构造LR(1)分析表如下：

以上分析表无多的定义入口，所以该文法为LR(1)文法。

(3)对于输入串abab，其分析过程如下：

22．证明下面文法是LL(1)的但不是SLR(1)文法

S→AaAb|BbBa

A→

B→

22. 解答：

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

First(AaAb)∩First(BbBa)={a}∩{b}=

A，B∈V

N

仅有一条候选式。

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

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

I

0

= {S'→·S, S→·AaAb, S→·BbBa, A→·, B→·}

I

1

= {S'→S·}

I

2

= {S→A·aAb}

I

3

= {S→B·bBa}

I

4

= {S→Aa·Ab, A→·}

I

5

= {S→Bb·Ba, B→·}

I

6

= {S→AaA·b}

I

7

= {S→BbB·a}

I

8

= {S→AaAb·}

I

9

= {S→BbBa·}

由于Follow(A)=Follow(B)={a, b},因此项目集I

0

中存在归约-归约冲突。在I

0

状态下，当

输入符号是a或是b时，不知用A→还是B→进行归约。故此文法不是SLR(1)的。但是，

此文法时LR(1)的。

23. 下面文法属于哪类LR文法？试构造其分析表，并给出符号串(a,a)的分析过程。

S→(SR|a

R→,SR|)

23. 解答：

该文法的拓广文法G'为

0．S' → S

1．S → (SR

2．S → a

3．R → ,SR

4．R → )

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

I

0

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

I

1

= {S'→S·}

I

2

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

I

3

= {S→a·}

I

4

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

I

5

= {S→(SR·}

I

6

= {R→)·}

I

7

= {R→,·SR, S→·(SR, S→·a}

I

8

= {R→,S·R, R→·,SR, R→·)}

I

9

= {R→,SR·}

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

24．算法程序题

(1)构造Sample语言算术表达式的递归下降分析程序，或者某一控制语句的递归下降分

析程序，要求：

① 书写出Sample语言语法的形式描述(BNF)；

② 消除左递归，提取左公因子；

③ 用某种高级语言书写出它的递归预测分析器。

(2) 构造Sample算术表达式的LL(1)分析器：

① 书写出Sample语言语法的形式描述(BNF)；

② 消除左递归，提取左公因子；

③ 计算First集和Follow集；

④ 构造其LL(1)分析表和LL(1)驱动程序。

(3) 构造Sample算术表达式的算符优先分析器：

① 书写出Sample语言语法的形式描述(BNF)；

② 计算FirstVT集和LastVT集；

③ 构造其算符优先关系表和算符优先分析程序。

(4) 构造Sample算术表达式的LR(0)分析器：

① 书写出Sample语言语法的形式描述(BNF)；

② 构造识别活前缀的有穷自动机；

③ 构造其LR(0)分析表和LR分析程序。

(5) 使用软件工具Yacc，构造LALR分析器，要求：

① 书写出Sample语言语法的形式描述(BNF)；

② 书写出Yacc的源程序；

③ 用Yacc生成LALR分析器。

④ 完成的分析程序的功能是：输入是算术表达式，输出为相应的后缀表达式；计

算出算术表达式的值。

24．解答： 略！

第4章习题

1．符号表的作用是什么，符号表中一般需要登记哪些内容，对符号表主要进行哪些操作？

如果需要将常量、变量、函数的符号表放在一张表中，请你设计符号表的结构。

解答：略！

2．静态语义检查是编译程序对源程序的最后一次检查，你认为静态语义检查包括哪些内容？

并举例说明，会提示哪些错误？

解答：略！

3. 程序出现了死循环、除数为0等，这种错误是在哪些阶段检查出来的？

解答：略！

4．写出下面程序的符号表，列出变量的作用域，并指出会发现哪些错误。

/* 程序段4.3 */

int x;

main()

{

int a;

while(a){

char x;

if(x>y){

a=a+x;

func1 = a*y;

}

printf(“Hello world!”);

}

char y;

int func1(int a, int b)

{

do{

char x;

int *y;

if(x>y){

if(y){

int z;

printf(“Input numbers”);

y=y-1;

continue;

}

a=a+x;

}

……

printf(“the result is %d”,*var1);

}

解答：略！

5．算法程序练习。

（1）用自己熟悉的语言编写程序：建立符号表，并对符号表进行插入和查找操作；

（2）用自己熟悉的语言编写程序：实现静态语义检查的功能，至少检查变量未声明，表达

式赋值时类型错误，break、continue的使用位置是否合适，函数调用中形参和实参不匹配等。

解答：略！

解答：略！

第5章习题

1. 解释下列术语。

属性、属性文法、继承属性、综合属性、语义子程序、语法制导的翻译、翻译模式。

解答： 略！

2．为什么要生成中间代码？常见的中间代码有哪几种形式？

解答： 略！

3．分别为如下文法配上语义子程序。

(1) 文法G

1

由开始符S产生一个二进制数，综合属性val给出该数的十进制值：

S→L.L| L

L→LB | B

B→0 | 1

试设计求 的属性文法，其中已知B的综合属性，它是由B产生的二进制的值。

对该属性文法，如输入二进制101.101，输出=5.625。

(2) 有文法G

2

：

S→(L) | a

L→L , S | S

为此文法配上语义动作子程序（或者说为此文法写出一个语法制导的定义），使其输出

配对括号的个数，如对于句子(a, (a, a))输出是2。

(3) 文法G

3

的产生式如下。

P→D

D→D;D | id:T | proc id; D;S

试写出各个产生式的语法制导的翻译规则，打印该程序一共声明了多少个id。

3. 解答：

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

S'→S {printf()}

S→L

1

.L

2

{:= L

1

.Val+ L

2

.val/2

}

S→L {:=}

L→L

1

B {:=L

1

.val*2+，

= L

1

.length+1 }

L→B {:=),

:=2 }

B→0 {:=0}

B→ 1 {:=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)}

D→D

1

;D

2

{D.h:=D

1

.h+D

2

.h}

D→id:T {D.h:= 1}

D→proc id; D

1

;S {D.h:=D

1

.h+1}

4．文法G及相应的语法制导的翻译规则为：

P→bQb { print(“1”)}

Q→cR { print(“2”)}

Q→a { print(“3”)}

R→Qad { print(“4”)}

若输入串为bcccaadadadb时，其输出是什么？

4. 解答：

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

采用修剪语法树的方法，按句柄方式自下而上归约该语法树，在归约时调用相应的语义

规则，由此得到最终的翻译结果为：34242421.

5．请把逆波兰表示ab+cde3-/+8*+复原成中缀表达式。

5. 解答：

(a+b)+(c+d/(e-3))*8

6．给出下面表达式的逆波兰表示和抽象语法树：

(1) a*(-b+c)

(2) !A || !(C || !D)

(3) a+b*(c+d/e)

(4) (A && B ) || (!C || D)

(5) -a+b*(-c+d)

(6) (A || B) && (C || ! D && E)

6. 解答：

(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

7．分别给出下述表达式的三元式、四元式序列和DAG。

（1）-(a+b)*(c+d)-(a+b+c)

（2）A || (B && ! (C || D))

7. 解答：（1）

三元式

① (+,a,b)

② (-,1,-)

③ (+,c,d)

④ (*,2,3)

⑤ (+,a,b)

⑥ (+,c,5)

⑦ (-,4,6)

四元式

1.(+,a,b,T

1

)

2.(-,T,-, T

2

)

3.(+,c,d,T

3

)

4.(*, T

2,

T

3

,T

4

)

5.(+,a,b,T

5

)

6.(+, T

5

,c, T

6

)

7.(-, T

4,,

T

6

,T

7

)

7. 解答：（2）

四元式代码为：

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)

8. (j，_，_，x)

8．根据while语句的目标结构写出while语句的属性文法。

8. 解答：

9．利用表5.3定义的语义规则，给出表达式（3+4）*（5+6）的带注释的语法分析树。

9. 解答：略

10．C语言中没有布尔类型，试说明C语言编译器可能使用什么方式将一个if语句翻译为

四元式。

10. 解答：略

11．将下面的语句翻译为四元式序列：

(1) if ((A

if (A==1)

c=c+1;

else if (A<=D)

A=A+2;

}

(3) do {

A=A+3;

B=C*A*2;

}while(X<0);

(5) int count = 0,x=0;

while(x<100) {

y = x%2;

if (x =!0) {

count=count+1;

continue;

}

x=x+1;

}

z＝x＋y;

else {

x＝x＋2;

y＝y＋3;

(4) for (i = b*2;i<=100;i=i+1) {

}

(6) int sum(int,int);

main()

{

int x,y,r;

r=sum(x*y+x,x+y);

}

int sum(int a,int b) {

return a+b;

}

x= (a+b)*(c+d)-(a+b+c);

if (x < 0) break;

11. 解答：

(1) 四元式序列为：

1．（j<,A,C,3） 8.(:=,T,-,C)

2.(j,-,-,14) 9.(j,-,-,14)

3.(j<,B,D,5) 11.(j,-,-,14)

4.(j,-,-,14) 12.(+,A,2,T

2

)

5.(j=,A,1,7) 13.(:=, T

2,

-,A)

6.(j,-,-,10) 14.

7.(+,c,1,T

1

)

(2) 四元式序列为：

1. (j＞0，x，0，3) 7. (j，_，_，12)

2. (j，_，_，8) 8. (＋，x，2，T

2

)

3. (j＞，y，0，5) 9. (:＝，T

2

，_，x)

4. (j，_，_，8) 10. (＋，y，3，T

3

)

5. (＋，x，y，T

1

) 11. (:＝，T

3

，_，y)

6. (:＝，T

1

，_，z) 12.

(3) 四元式序列为：

0. (+，A，3，t0)

1. (:=，t0 ， ，t1)

2. (*，C，A，t2)

3. (*，t2，2，t3)

4. (:=， t3， ，B)

5. (j<，X，0，7)

6. (j， ， ，0)

7.

(4) 四元式序列为：

0. (*,b,2,t0)

1. (:=, t0, ,i)

8. (+, c, d, t4 )

9. (*,t3, t4, t5)

2. (:=,100, , t1 )

3. (j, , , 6)

4. (+,i,1,t2 )

5. (:=, t2, , i)

6. (j>, i,t1,15)

7. (+, a, b, t3 )

10. (+, a, b, t6 )

11. (+, t6 c, t7 )

12. ( -, t5, t7, t8)

13. ( :=, t8, , x )

14. (j, , , 4)

15.

12. 算法程序题

(1) 用自己熟悉的语言编写程序，其功能是将布尔表达式翻译为四元式代码。

(2) 用自己熟悉的语言编写程序，其功能是将简单赋值语句翻译为四元式代码。

(3) 在第3章写的各种控制语句的递归下降分析程序的基础上，实现其递归下降的语法

制导翻译程序，翻译为四元式代码。

(4) 理解函数声明、定义和调用，用自己熟悉的语言编写程序，实现函数的四元式代码

生成。

12. 解答：略！

第6章习题

1．常见的存储分配策略有哪几种？叙述何时使用何种存储分配策略。

2．常用的参数传递方式有哪几种，各种方式有什么区别？

3．什么是名字的作用域，以C语言为例，说明在嵌套层次中名字的作用域的含义。

4．什么是函数、局部变量、活动记录？函数的局部数据区包括哪些内容？

5．为什么需要运行时存储分配？一个源程序是如何与运行时存储分配联系在一起的？

6．掌握C语言的栈帧分配方式，以栈帧中应包含哪些数据，以及存放次序。

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

7．以如下C语言程序为例，结合程序运行时栈帧和其它地址空间的特点，说明如果将静态

变量ss分配在运行栈中，程序的运行结果是什么，如果将ss分配在静态数据区，程序运行

的结果是什么，说明原因。

void fun()

{

static int ss = 0;

printf(“%dn”,ss++);

}

main()

{

fun();

fun();

}

7.解答：略！

8．下面的代码是递归计算Fiabonacci数列的C语言代码，假设f的活动记录按顺序包含下

来元素，（返回值，参数n，局部变量s，局部变量t）。通常在活动记录中还会有其它元素。

假设初始调用为f(5)：

(1)给出完整的活动树;

(2)当第1个f(1)调用即将返回时，画出运行栈和其中的活动记录；

int f(int n) {

int t, s;

if(n<2) return I;

s=f(n-1);

t=f(n-2);

return s+t;

}

8.解答：略！

9. 下面是一个类PASCAL结构(嵌套过程)的程序，该语言的编译器采用栈式动态分配策略

管理目标程序数据空间。

program demo;

procedure A;

procedure B;

begin

…

if d then B else A;

end;

begin

B;

end;

begin

A;

end.

若过程调用为：

(1) demo → A

(2) demo →A→B

(3) demo →A→B→B

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

分别给出这4个时刻运行栈的布局和使用的display表。

9. 解答：

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

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

优化。循环优化属于 B 优化，它对于提高目标代码的运行速度是非常有效的。循环优化

主要采用的三项优化措施是 C 、 D 、 E 。

1. 解答：

A：局部 B：全局 C：代码外提

D：削减运算强度 E：删除归纳变量

2. 解释下列术语：

基本块，流图，DAG，循环，回边，必经结点，局部优化

2. 解答：略！

3. 什么是代码优化？代码优化如何分类？常用的代码优化技术有哪些？

3. 解答：略！

4.将以下中间代码划分为基本块，并画出流图。

(1) x=1

(2) i=0

(3) if i>=10 goto (7)

(4) x=x*i

(5) i=i+1

(6) goto (3)

(7) if x>500 goto (11)

(8) return 500

(9) return

(10) goto (13)

(11) return x

(12) return

(13) return

4. 解答：

5．试构造下面的程序的流图，并找出其中所有回边及循环。

//下列程序中，read和write表示输入和输出

read P

x = 1

c = P * P

if c < 100 goto L1

B = P * P

x = x + 1

B = B + x

write x

L1: B= 10

x = x + 2

B = B + x

write B

if B < 100 goto L2

L2: x = x + 1

goto L1

n

0

n

1

n

2

n

3

n

4

n

5

n

6

n

7

5. 解答：

程序流图如下：

回边为：B

4

→B

3

，循环L={B

3

,B

4

}

6．对图7.18所示的流图，求出各结点n

i

的必经结点集D(n

i

)、回边，并找出图中的循环(n

0

为首结点)。

6.解答：

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

D(n

0

) = {n

0

}

D(n

1

) = {n

0

, n

1

}

D(n

2

) = {n

0

, n

1

, n

2

}

D(n

3

) = {n

0

, n

1

, n

2

, n

3

}

D(n

4

) = {n

0

, n

1

, n

2

, n

4

}

D(n

5

) = {n

0

, n

1

, n

2

, n

5

}

D(n

6

) = {n

0

, n

1

, n

2

, n

5

, n

6

}

D(n

7

) = {n

0

, n

1

, n

2

, n

5

, n

6

, n

7

}

回边和循环：

因为 D(n

5

) = {n

0

, n

1

, n

2

, n

5

} ，且 n

5

→ n

2

，所以 n

5

→ n

2

为一条回边。根据它求出的循环

L

1

= {n

2

, n

5

, n

3

, n

4

}。

因为D(n

6

) = {n

0

, n

1

, n

2

, n

5

, n

6

} ，且 n

6

→ n

1

，所以n

6

→ n

1

为一条回边。根据这条回边，

求出的循环 L

2

= {n

6

, n

1

, n

5

, n

3

, n

4

, n

2

}。

7. 对如下程序段划分基本块，画出流图，进行尽可能多的优化，并指出进行了何种优化，

给出建议说明及优化后的结果形式。

I = 1 （2） 1) i=1

（1）

read J, K

L: A = K * I

B = J * I

C = A * B

write C

I = I + 1

if I < 100 goto L

2)j=1

3)t1=10*i

4)t2=t1+j

5)t3=8*t2

6)t4=t3-88

7)a[t4]=0.0

8)j=j+1

9)if j<=10 goto(3)

10)i=i+1

11)if i<=10 goto (2)

12)i=1

13)t5 = i-1

14)t6=88* t5

15)a[t6]=1.0

16)i=i+1

17)if i<=10 goto (13)

7. 解答：

(1) 首先划分基本块并画出其程序流图，其中有三个基本块B

1

，B

2

，B

3

，有一条回边B

2

→ B

2

，相应的循环是{B

2

}。

(2) 强度削弱： 在B

2

中A和B为乘法运算，可以削弱它们的运算强度，变乘法为加

法。优化结果如下图。

(3) 删除归纳变量：在循环中，i是循环的基本归纳变量，A，B是同族的归纳变量，且

有线性关系，变换循环控制条件，流图如下。

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

结点B

2

'中。

（2）解答：

8. 为下列基本块构造DAG:

d = b*c

e = a+b

b = b*c

a = e-d

8. 解答：

9．设有基本块

T1=2

T2 =10/T

T3 =S-R

T4 =S+R

A=T2 * T4

B= A

T5 =S+R

T6 =T3 * T5

B=T6

(1) 画出DAG图。

(2) 假设基本块出口时只有A和B还被引用，请写出优化后的三地址代码序列。

9. 解答：

(1) DAG如下：

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

T

3

:＝S－R

T

4

:＝S＋R

A:＝5*T

4

B:＝T

3

＋T

4

10. 下面是应用筛法求2到N之间素数的PASCAL程序：

begin

read N;

for i = 2 to N do

A[i] = true;/*置初值*/

for i = 2 to N**0.5 do /*运算符**代表乘幂*/

if A[i] then /*i是一个素数*/

for j = 2 * i to N by i do

A[j] = false; /*j可被i除尽*/

end

(1) 试写出其中间代码，假设数组A静态分配存储单元，且下界为0。

(2) 画出流图并求出其中的循环。

(3) 进行代码外提。

(4) 进行强度削弱和删除归纳变量。

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

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

B

1

: read N /* 置初值 */

i := 2

B

2

: if i > N goto B

4

/* 第一个for语句 */

B

3

: T

1

:= i

T

2

:= addr(A) /* 数组A的基地址 */

T

1

:= 2 * T

1

T

2

[T

1

] := true

i := i + 1

goto B

2

B

4

: i := 2

T

3

:= N ** 0.5

T

3

:= [T

3

] + 1 /* [T

3

]是对T

3

的值取整 */

B

5

: if i > T

3

goto B

12

B

6

: T

4

:= i

T

5

:= addr(A)

T

4

:= 2 * T

4

if T

5

[T

4

] goto B

8

B

7

: goto B

11

B

8

: j := 2 * i

B

9

: if j > N goto B

11

/* 第三个for语句 */

B

10

: T

6

:= j

T

7

:= addr(A)

T

6

:= 2 * T

6

T

7

[T

6

] = false

j := j + i

goto B

9

B

11

: i := i + 1

goto B

5

B

12

:

(2) 根据上述中间代码，可划分成基本块B

1

，B

2

，B

3

，B

4

，B

5

，B

6

，B

7

，B

8

，B

9

，B

10

，

B

11

。

其程序流图如下：

考查上面的程序流图：

D(B

3

) = { B

1

, B

2

, B

3

}，又有 B

3

→ B

2

，因此 B

3

→ B

2

是一条回边。根据它找到的循环 L

1

= { B

2

, B

3

}。

D(B

10

) = { B

1

, B

2

, B

4

, B

5

, B

6

, B

9

, B

10

}，又有 B

10

→ B

9

，所以 B

10

→ B

9

是一条回边。根据

这条回边找到循环 L

2

= { B

9

, B

10

}。

D(B

11

) = { B

1

, B

2

, B

4

, B

5

, B

6

, B

9

, B

11

}，又有 B

11

→ B

5

，因此 B

11

→ B

5

是一条回边。根据

这条回边找到循环 L

3

= { B

11

, B

9

, B

10

, B

8

, B

7

, B

6

, B

5

}

(3) 进行代码外提

把在循环中不随循环变化的操作提到循环外的前置结点中，且在基本块中作复写传播和

删除无用赋值。结果程序流图如图1。

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

图1 代码外提、复写传播和删除无用赋图2 强度削弱和删除归纳变量后的流图

值后的流图

11. 算法程序题

（1）用自己熟悉的语言编写程序，实现基本块的划分算法。

（2）用自己熟悉的语言编写程序，实现求某基本块的DAG图。

（3）用自己熟悉的语言编写程序，实现求给定流图中的必经结点集。

11. 解答：略！

第8章习题

1.一个编译程序的目标代码生成阶段主要需要考虑哪些问题？

2.引用信息和活跃信息的作用是什么，如何实现？

3.寄存器描述和地址描述的作用是什么，如何实现？

1，2，3 解答：略！

4.生成下列Sample语句的目标代码，假定所有变量均为静态分配，并有三个寄存器可用。

(1) x = 1

(2) x = y

(3) x = x+1

(4) x = a+b*c

(5) x = a/(b+c)-d*(e+f)

4. 解答：

设所有变量均用名字表示地址，寄存器名字用R

0

、R

1

和R

2

表示。目标代码如下：

(1) MOV x，#1 (5) MOV R

0

，b

(2) MOV x，y ADD R

0

，c

(3) ADD x，#1 MOV R

1

，a

(4) MOV R

1

，b DIV R

1

，R

0

MUL R

1

，c MOV R

2

，e

ADD R

1

，a ADD R

2

，f

MOV x，R

1

MUL R

2

，d

SUB R

1

，R

2

MOV x，R

1

5. 利用简单代码生成算法，对下列三地址代码生成目标代码：

（-，A，B，T）

（+，C，D，S）

（-，E，F，W）

（/，W，T，U）

（*，U，S，V）

5. 解答：

MOV R

0

，A

SUB R

0

，B

MOV R

1

，C

ADD R

1

，D

MOV S， R

1

MOV R

1

，E

SUB R

1

，F

DIV R

1

，R

0

MUL R

1

，S

MOV V， R

1

6．假定所有变量都存放在内存中，为下列赋值语句生成目标代码。

(1) x=a+b*c

(2) x=(a/b-c)/d

(3) x=(a*-b)+(c-(d+e))

(4) if x

x=0

Goto L2

L1: z=1

L2:

6. 解答：

(1) MOV R

0

,b

MUL R

0

,c

ADD R

0

,a

MOV x,R

0

(2) MOV R

0

,a

DIV R

0

,b

SUB R

0

,c

DIV R

0

,d

MOV x,R

0

(3) MOV R

0

,#0

SUB R

0

,b

MUL R

0

,a

MOV R

1

,d

ADD R

1

,e

MOV R

2

,c

SUB R

2

,R

1

ADD R

0

,R

2

MOV x,R

0

(4)

7．将表达式A*(B+C)-D*(B+C)采用四元式进行表达，并生成相应的80x86汇编代码。假设

变量A、B、C、D分别对应栈帧中的内存单元(SP)+14H、(SP)+16H、(SP)+18H、(SP)+1AH，

每个变量占两字节。可用寄存器为AX、CX、DX，寄存器的初始状态为空。

7. 解答： 略！

8．算法程序题。

(1) 编程实现简单代码生成算法。

(2) 用算法描述寄存器的分配算法，计算活跃信息和引用信息。

(3) 试给出一个算法，直接对DAG计算引用和活跃信息。

8. 解答： 略！