编译原理(第三版)答案

编译原理复习题及答案

一、 选择题

1． 一个正规语言只能对应( B )

A 一个正规文法 B 一个最小有限状态自动机

2． 文法G[A]：A→ε A→aB B→Ab B→a是( A )

A 正规文法 B 二型文法

3． 下面说法正确的是( A )

A 一个SLR（1）文法一定也是LALR（1）文法

B 一个LR（1）文法一定也是LALR（1）文法

4． 一个上下文无关文法消除了左递归，提取了左公共因子后是满足LL（1）文法的( A )

A 必要条件 B 充分必要条件

5． 下面说法正确的是( B )

A 一个正规式只能对应一个确定的有限状态自动机

B 一个正规语言可能对应多个正规文法

6． 算符优先分析与规范归约相比的优点是( A )

A 归约速度快 B 对文法限制少

7． 一个LR（1）文法合并同心集后若不是LALR（1）文法( B )

A 则可能存在移进/归约冲突

B 则可能存在归约/归约冲突

C 则可能存在移进/归约冲突和归约/归约冲突

8． 下面说法正确的是( A )

A Lex是一个词法分析器的生成器 B Yacc是一个语法分析器

9． 下面说法正确的是( A )

A 一个正规文法也一定是二型文法

B 一个二型文法也一定能有一个等价的正规文法

10． 编译原理是对(C)。

A、机器语言的执行 B、汇编语言的翻译

C、高级语言的翻译 D、高级语言程序的解释执行

11． (A)是一种典型的解释型语言。 A．BASIC B．C C．FORTRAN D．PASCAL

12． 把汇编语言程序翻译成机器可执行的目标程序的工作是由(B)完成的。

A. 编译器 B. 汇编器 C. 解释器 D. 预处理器

13． 用高级语言编写的程序经编译后产生的程序叫(B)

A．源程序 B．目标程序 C．连接程序 D．解释程序

14． (C)不是编译程序的组成部分。

第三章 习题解答

6．每个表达式的推导及语法树分别如下：

(1)

=>

=>

=> i

(2)

=>

=>

=>()

=>()

=>()

=>(i)

(3)

=>

=>*

=>*

=>i*

=>i*i

(4)

=> +

=> +

=> *+

=> *+

=> i*+

=> i*i+

=> i*i+

=> i*i+i

(5)

=> +

=> +

=> +

=> i+

=> i+

=>i+

=>i+(+)

=> i+(+) => i+(+)

=> i+(i+)

=> i+(i+)

=>i+(i+i)

(6)

=> +

=> +

=> +

=> i+

=> i+*

=> i+*

=> i+i*

=> i+i*i

i()i*ii图（1）图（2）图（3） ()+*iii+i+ii图（4）图（5）

+i图（6）*ii

11．根据文法G给定的规则，从文法的开始符E出发可推导出E+T*F，推导过程如下：

E => E+T => E+T*F ，所以E+T*F是该文法的一个句型。由右图的语法树也可以看出，E+T*F是该文法的一个句型。

这个句型的所有短语为：E+T*F, T*F

直接短语为：T*F

句柄为：T*F

13． EE + TT * F(1)最左推导：S=>ABS

=>a1BS

=> a1SBBS

=> a1BBS

=> a1b1BS

=> a1b1b2S

=> a1b1b2Aa3

=> a1b1b2a2a3

最右推导：S=>ABS

=> ABAa3

=> ABa2a3

=> ASBBa2a3

=> ASBb2a2a3

=> ASb1b2a2a3

=> Ab1b2a2a3

=> a1b1b2a2a3

(2)该文法产生式集合P可能有如下规则：S→ABS|Aa|ε

第五章 习题

5-1 设有文法G[S]：

S→A/ A→aA∣AS∣/

(1) 找出部分符号序偶间的简单优先关系。

(2) 验证G[S]不是简单优先文法。

5-2 对于算符文法G[S]：

S→E E→E-T∣T T→T*F∣F F→-P∣P P→(E)∣i

(1) 找出部分终结符号序偶间的算符优先关系。

(2) 验证G[S]不是算符优先文法。

5-3 设有文法G′[E]：

E→E1 E1→E1+T1|T1 T1→T T→T*F|F F→(E)|i

其相应的简单优先矩阵如题图5-3所示，试给出对符号串（i+i）进行简单优先分析的过程。

题图5-3 文法G′[E]的简单优先矩阵

5-4 设有文法G[E]：

E→E+T|T

T→T*F|F

F→(E)|i

其相应的算符优先矩阵如题图5-4所示。试给出对符号串（i+i）进行算符优先分析的过程。

( i * + ) #

( ○＜ ○＜ ○＜ ○＜ ○＝

i ○＞ ○＞ ○＞ ○＞ * ○＜ ○＜ ○＞ ○＞ ○＞ ○＞

+ ○＜ ○＜ ○＜ ○＞ ○＞ ○＞

) ○＞ ○＞ ○＞ ○＞

# ○＜ ○＜ ○＜ ○＜

题图5-4 文法G[E]的算符优先矩阵

5-5 对于下列的文法，试分别构造识别其全部可归前缀的DFA和LR(0)分析表，并判断哪些是LR(0)文法。

(1) S→aSb∣aSc∣ab

(2) S→aSSb∣aSSS∣c

(3) S→A A→Ab∣a

5-6 下列文法是否是SLR(1)文法？若是，构造相应的SLR(1)分析表，若不是，则阐明其理由。

(1) S→Sab∣bR R→S∣a

(2) S→aSAB∣BA A→aA∣B B→b

参考答案

一、单项选择题(共10小题，每小题2分，共20分)

1．语言是

A．句子的集合 B．产生式的集合

C．符号串的集合 D．句型的集合

2．编译程序前三个阶段完成的工作是

A．词法分析、语法分析和代码优化

B．代码生成、代码优化和词法分析

C．词法分析、语法分析、语义分析和中间代码生成

D．词法分析、语法分析和代码优化

3．一个句型中称为句柄的是该句型的最左

A．非终结符号 B．短语 C．句子 D．直接短语

4．下推自动机识别的语言是

A．0型语言 B．1型语言

C．2型语言 D．3型语言

5．扫描器所完成的任务是从字符串形式的源程序中识别出一个个具有独立含义的最小语法单位即

A． 字符 B．单词 C．句子 D．句型

6．对应Chomsky四种文法的四种语言之间的关系是

A．L0L1L2L3 B．L3L2L1L0

C．L3=L2L1L0 D．L0L1L2=L3

7．词法分析的任务是

A．识别单词 B．分析句子的含义

C．识别句子 D．生成目标代码

8．常用的中间代码形式不含

A．三元式 B．四元式 C．逆波兰式 D．语法树

9． 代码优化的目的是

A．节省时间 B．节省空间

C．节省时间和空间 D．把编译程序进行等价交换

10．代码生成阶段的主要任务是

A．把高级语言翻译成汇编语言

B．把高级语言翻译成机器语言