《编译技术原理及方法》期末测试习题

一、单选题

1. 在编译程序中，语法分析的主要功能是（ ）

A. 识别单词及其属性

B. 生成中间代码

C. 为单词分配存储空间

D. 分析单词串如何构成短语、子句、程序

2. 文法G: S→aSb | ab 描述的语言是（ ）

A. {aⁿbⁿ | n≥0}

B. {aⁿbⁿ | n≥1}

C. {abⁿ | n≥1}

D. {aⁿbᵐ | n,m≥1}

3. 在LR分析表中，如果某个状态遇到输入符号a时既有移进项目又有归约项目，则说明该文法（ ）

A. 是SLR(1)文法

B. 是LALR(1)文法

C. 是LR(0)文法

D. 不是LR(1)文法

4. 下列哪种文法最适合描述程序设计语言的语法（ ）

A. 2型文法

B. 3型文法

C. 0型文法

D. 1型文法

5. 在语法制导翻译中，产生式A→BC通常对应（ ）

A. 语法分析

B. 词法分析

C. 代码优化

D. 语义动作

6. 表达式(a+b)(c-d)的逆波兰表示是（ ）

A. a+b*c-d

B. a+bcd-

C. abcd+-

D. ab+cd-

7. 在符号表管理中，最重要的作用是（ ）

A. 生成目标代码

B. 实现名字的作用域管理

C. 进行错误处理

D. 类型检查

8. 基本块内的优化不包括（ ）

A. 死代码删除

B. 常数传播

C. 代码外提

D. 删除公共子表达式

9. 对于文法G[E]: E→E+E | E*E | (E) | i，该文法是（ ）

A. 算符优先文法

B. 无二义性的

C. 正则文法

D. 有二义性的

10. 在代码生成阶段，寄存器分配的主要目标是（ ）

A. 减少内存访问次数

B. 便于调试

C. 提高代码可读性

D. 减小指令条数

11. 下列哪个不是中间代码的表示形式（ ）

A. 语法树

B. 逆波兰表示

C. 汇编代码

D. 四元式

12. 在递归下降分析法中，每个非终结符对应（ ）

A. 一个递归子程序

B. 一个产生式

C. 一个状态

D. 一个终结符

13. 数据流分析主要用于（ ）

A. 语法分析

B. 代码优化

C. 词法分析

D. 错误处理

14. 在语法制导定义中，继承属性用于（ ）

A. 存储中间结果

B. 自底向上传递信息

C. 自顶向下传递信息

D. 生成目标代码

15. 编译过程中，类型检查通常在哪个阶段进行（ ）

A. 语义分析

B. 词法分析

C. 语法分析

D. 代码优化

二、判断题

16. 在编译过程中，中间代码的引入主要是为了提高目标代码的执行效率。

A. 对

B. 错

17. LL(1)分析法可以采用带回溯的深度优先搜索策略进行语法分析。

A. 对

B. 错

18. 对于任意一个非确定的有限自动机(NFA)，都存在一个等价的确定有限自动机(DFA)。

A. 对

B. 错

19. 在语法制导翻译中，综合属性的计算顺序是自顶向下的。

A. 对

B. 错

20. 代码优化中的"死代码删除"优化可能会改变程序的实际输出结果。

A. 对

B. 错

三、简答题

21.设文法G规则为:

S ::= AB

B ::= a | Sb

A ::= Aa | bB

对下列句型给出推导语法树，并求出其句型短语，简单短语和句柄。

(1)baabaab (2)bBABb

解：（1）句型baabaab的短语a, ba, baa, baab, baabaab，简单短语a，句柄 a

baabaab.drawio-fxlg-whga.svg

（2）句型bBABb的短语bB, AB, ABb，简单短语bB, AB，句柄bB

bBABb.drawio.svg

22.令文法

N::=D | ND

D::=0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

给出句子0127，34，568的最左推导和最右推导。

解：0127的最左推导N=>ND=>NDD=>NDDD=>DDDD=>0DDD=>01DD=>012D=>0127；

0127的最右推导N=>ND=>N7=>ND7=>N27=>ND27=>N127=>D127=>0127；

34的最左推导N=>ND=>DD=>3D=>34；

34的最右推导N=>ND=>N4=>D4=>34；

568的最左推导N=>ND=>NDD=>DDD=>5DD=>56D=>568；

568的最右推导N=>ND=>N8=>ND8=>N68=>D68=>568

23.对下面文法，构造每个非终结符号相应的FIRST集和FOLLOW集。

1）S∷＝aAd

     A∷＝BC

     B∷＝b｜ε

     C∷＝c｜ε

2）A∷＝BCc｜gDB

     B∷＝ε｜bCDE

     C∷＝DaB｜ca

     D∷＝ε｜dD

     E∷＝gAf｜c

解：（1）

byyl1.png

解：（2）

byyl2.png

24.给出下面表达式的后缀式表示：

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

(2) (a∧b)∨(¬c∨d)

将下列后缀式改写为中缀式：

(3) abc-*cd+e/-

(4) aΘbc*＋

解：

（1）abcde/+*+

（2）ab∧c┐d∨∨

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

（4）-a+b*c

25.请将表达式(a+b)*(c+d)-(a+b+c)分别表示成三元式和四元式序列。

解：三元式序列：

(1) (+, a, b)

(2) (+, c, d)

(3) (*, (1), (2))

(4) (+, (1), c)

(5) (-, (3), (4))

四元式序列：

(1) (+, a, b, t1)

(2) (+, c, d, t2)

(3) (*, t1, t2, t3)

(4) (+, t1, c, t4)

(5) (-, t3, t4, t5)

四、计算题

26.构造下列正规表达式相应的DFA，并进行最小化的化简（子集法）。

(1) b(a|b)*bab (2) ((bb*a) | (aa*))*

解：（1） b(a|b)*bab对应的转换系统为

image-bftj.png

下表由子集法将转换系统转换为DFA：

I

Ia

Ib

K

a

b

{S}

 

{1,2,3}

S

 

1

{1,2,3}

{2,3}

{2,3,4}

1

2

3

{2,3}

{2,3}

{2,3,4}

2

2

3

{2,3,4}

{2,3,5}

{2,3,4}

3

4

3

{2,3,5}

{2,3}

{2,3,4,Z}

4

2

Z

{2,3,4,Z}

{2,3,5}

{2,3,4}

Z

4

3

DFA的状态转换图：

image-3xbl.png

化简后的DFA状态转换图如下：

 image-ve6z.png

(2) ((bb*a) | (aa*))*对应的转换系统为

【暂无答案】

27. 对下面文法G[E]：

E∷＝TE′

E′∷＝+E｜ε

T∷＝FT′

T′∷＝T｜ε

F∷＝PF′

F′∷＝*F′｜ε

P∷＝(E)｜a｜b｜∧

（1）计算这个文法的每个非终结符号的FOLLOW集和所有规则右部的FIRST集。

（2）构造它的LL(1)分析表并分析符号串a*b+b。

解：（1）

byyl3.png

解：（2）

byyl4.png

如果您访问或打印此题库，表示您同意只将本题库用于参考、学习而非其他用途！