编译原理练习题参考答案[]

一、填空题:

1-01.编译程序的工作过程一般可以划分为词法分析,语法分析,语义分析，之间代码生成,代码优化等几个基本阶段,同时还会伴有表格处理和出错处理 .

1-02.若源程序是用高级语言编写的,目标程序是机器语言程序或汇编程序 ,则其翻译程序称为编译程序.

1-03.编译方式与解释方式的根本区别在于是否生成目标代码 .

1-04.翻译程序是这样一种程序,它能够将用甲语言书写的程序转换成与其等价的用乙语言书写的程

序 .

1-05.对编译程序而言,输入数据是源程序 ,输出结果是目标程序 .

1-06.如果编译程序生成的目标程序是机器代码程序,则源程序的执行分为两大阶段: 编译阶段和运

行阶段 .如果编译程序生成的目标程序是汇编语言程序,则源程序的执行分为三个阶段: 编译阶段 ,

汇编阶段和运行阶段 .

1-07.若源程序是用高级语言编写的，目标程序是机器语言程序或汇编程序，则其翻译程序称为编译程序。

1-08.一个典型的编译程序中，不仅包括词法分析、语法分析、中间代码生成、代码优化、目标代码生成等五个部分，还应包括表格处理和出错处理。其中，词法分析器用于识别单词。

1-09.编译方式与解释方式的根本区别为是否生成目标代码。

2-01.所谓最右推导是指：任何一步α β都是对α中最右非终结符进行替换的。

2-02.一个上下文无关文法所含四个组成部分是一组终结符号、一组非终结符号、一个开始符号、一组产生式。

2-03.产生式是用于定义语法成分的一种书写规则。

2-04.设G[S]是给定文法，则由文法G所定义的语言L(G)可描述为： L(G)＝{x│S x,x∈V T*} 。

2-05.设G是一个给定的文法，S是文法的开始符号，如果S x（其中x∈V*），则称x是文法的一个句型。2-06.设G是一个给定的文法，S是文法的开始符号，如果S x(其中x∈V T*),则称x是文法的一个句子。3-01.扫描器的任务是从源程序中识别出一个个单词符号。

4-01.语法分析最常用的两类方法是自上而下和自下而上分析法。

4-02.语法分析的任务是识别给定的终极符串是否为给定文法的句子。

4-03.递归下降法不允许任一非终极符是直接左递归的。

4-04.自顶向下的语法分析方法的关键是如何选择候选式的问题。

4-05.递归下降分析法是自顶向上分析方法。

4-06.自顶向下的语法分析方法的基本思想是：从文法的开始符号开始，根据给定的输入串并按照文法的产生式一步一步的向下进行直接推导，试图推导出文法的句子，使之与给定的输入串匹配。

5-01.自底向上的语法分析方法的基本思想是：从给定的终极符串开始，根据文法的规则一步一步的向上进行直接归约，试图归约到文法的开始符号。

5-02.自底向上的语法分析方法的基本思想是：从输入串入手，利用文法的产生式一步一步地向上进行直接归约，力求归约到文法的开始符号。

5-03.简单优先方法每次归约当前句型的句柄，算符优先方法每次归约当前句型的最左素短语，二者都是不断移进输入符号，直到符号栈顶出现可归约串的尾，再向前找到可归约串的头，然后归约。

5-04.在LR（0）分析法的名称中，L的含义是自左向右的扫描输入串，R的含义是最左归约，0 的含义是向貌似句柄的符号串后查看0个输入符号。

5-05.在SLR（1）分析法的名称中，S的含义是简单的。

6-01.所谓属性文法是一个属性文法是一个三元组：A＝（G，V，F），一个上下文无关文法G；一个属性的有穷集V和关于属性的断言或谓词的有穷集F。每个断言与文法的某产生式相联。

6-02.综合属性是用于“自下而上”传递信息。

6-03.继承属性是用于“自上而下”传递信息。

6-04.终结符只有综合属性，它们由词法分析器提供。

7-01.在使用高级语言编程时,首先可通过编译程序发现源程序的全部 A 错误和 B 部分错误.

a.语法

b.语义

c.语用

d.运行

8-01.符号表中的信息栏中登记了每个名字的属性和特征等有关信息，如类型、种属、所占单元大小、地址等等。

8-02.一个过程相应的DISPLAY表的内容为现行活动记录地址和所有外层最新活动记录的地址。

9-01.一个过程相应的DISPLAY表的内容为现行活动记录地址和所有外层最新活动记录的地址。

9-02.常用的两种动态存贮分配办法是栈式动态分配和堆式动态分配。

9-03.常用的参数传递方式有传地址，传值和传名。

10-01.局部优化是局限于一个基本块范围内的一种优化。

10-02.代码优化的主要目标是如何提高目标程序的运行速度和如何减少目标程序运行时所需的空间。

二、单选题:

1-10.一个编译程序中，不仅包含词法分析，语法分析，中间代码生成，代码优化，目标代码生

成等五个部分，还应包括 (1)c .其中, (2)b 和代码优化部分不是每个编译程序都必需的.

词法分析器用于识别 (3)c ,语法分析器则可以发现源程序中的 (4)d .

(1) a.模拟执行器 b.解释器 c.表格处理和出错处理 d.符号执行器

(2) a.语法分析 b.中间代码生成 c.词法分析 d.目标代码生成

(3) a.字符串 b.语句 c.单词 d.标识符

(4) a.语义错误 b.语法和语义错误 c.错误并校正 d.语法错误

1-11.程序语言的语言处理程序是一种 (1)a . (2)b 是两类程序语言处理程序,他们的主要区别在于(3)d .

(1) a.系统软件 b.应用软件 c.实时系统 d.分布式系统

(2) a.高级语言程序和低级语言程序 b.解释程序和编译程序

c.编译程序和操作系统

d.系统程序和应用程序

(3) a.单用户与多用户的差别 b.对用户程序的查错能力

c.机器执行效率

d.是否生成目标代码

1-12.汇编程序是将 a 翻译成 b ,编译程序是将 c 翻译成 d .

a.汇编语言程序

b.机器语言程序

c.高级语言程序

d. a 或者 b

e. a 或者 c

f. b 或者 c

1-13.下面关于解释程序的描述正确的是 b .

(1) 解释程序的特点是处理程序时不产生目标代码

(2) 解释程序适用于COBOL 和 FORTRAN 语言

(3) 解释程序是为打开编译程序技术的僵局而开发的

a. (1)(2)

b. (1)

c. (1)(2)(3)

d.(2)(3)

1-14.高级语言的语言处理程序分为解释程序和编译程序两种.编译程序有五个阶段，而解释程序通常缺少(1)e 和 (1)b .其中， (1)e 的目的是使最后阶段产生的目标代码更为高效.

与编译系统相比，解释系统 (2)d .解释程序处理语言时,大多数采用的是 (3)b 方法. (4)a 就是一种典型的解释型语言.

(1): a. 中间代码生成 b.目标代码生成 c.词法分析 d.语法分析 e.代码优化

(2): a.比较简单,可移植性好,执行速度快

b.比较复杂,可移植性好,执行速度快

c.比较简单,可移植性差,执行速度慢

d.比较简单,可移植性好,执行速度慢

(3): a.源程序命令被逐个直接解释执行 b.先将源程序转化为之间代码,再解释执行

c.先将源程序解释转化为目标程序,在执行

d.以上方法都可以

(4) : a. BASIC b. C c. FORTRAN d. PASCAL

1-15.用高级语言编写的程序经编译后产生的程序叫 b .用不同语言编写的程序产生 b 后,可用 g 连接在一起生成机器可执行的程序.在机器中真正执行的是 e .

a. 源程序

b. 目标程序

c. 函数

d. 过程

e. 机器指令代码

f. 模块

g. 连接程序

h.程序库

1-16.要在某一台机器上为某种语言构造一个编译程序,必须掌握下述三方面的内容: c , d , f .

a. 汇编语言

b. 高级语言

c. 源语言

d. 目标语言

e. 程序设计方法

f. 编译方法

g. 测试方法

h. 机器语言

1-17.由于受到具体机器主存容量的限制,编译程序几个不同阶段的工作往往被组合成 (1)d ,

诸阶段的工作往往是 (2)d 进行的.

(1) a. 过程 b. 程序 c. 批量 d.遍

(2) a. 顺序 b. 并行 c. 成批 d.穿插

1-18.编译程序与具体的机器 a , 与具体的语言 a .

a. 有关

b.无关

1-19.使用解释程序时,在程序未执行完的情况下， a 重新执行已执行过的部分.

a. 也能

b.不可能

1-20.编译过程中,语法分析器的任务就是 b .

(1) 分析单词是怎样构成的 (2) 分析单词串是如何构成语句和说明的

(3) 分析语句和说明是如何构成程序的 (4) 分析程序的结构

a. (2)(3)

b. (2)(3)(4)

c. (1)(2)(3)

d.(1)(2)(3)(4)

1-21.编译程序是一种常用的 b 软件.

a. 应用

b. 系统

1-22.编写一个计算机高级语言的源程序后,到正式上机运行之前，一般要经过 b 这几步.

(1) 编辑 (2) 编译 (3) 连接 (4) 运行

a. (1)(2)(3)(4)

b. (1)(2)(3)

c. (1)(3)

d.(1)(4)

1-23.编译程序必须完成的工作有 a .

(1) 词法分析 (2) 语法分析 (3) 语义分析

(4) 代码生成 (5) 之间代码生成 (6) 代码优化

a. (1)(2)(3)(4)

b. (1)(2)(3)(4)(5)

c. (1)(2)(3)(4)(5)(6)

d. (1)(2)(3)(4)(6)

e. (1)(2)(3)(5)(6)

1-24.“用高级语言书写的源程序都必须通过编译,产生目标代码后才能投入运行”这种说法 a .

a. 不正确

b.正确

1-25.把汇编语言程序翻译成机器可执行的目标程序的工作是由 b 完成的.

a. 编译器

b. 汇编器

c. 解释器

d. 预处理器

1-26.编译程序生成的目标程序 b 是机器语言的程序.

a. 一定

b. 不一定

1-27.编译程序生成的目标程序 b 是可执行的程序.

a. 一定

b. 不一定

1-28．编译程序是一种 B 。

A. 汇编程序

B. 翻译程序

C. 解释程序

D. 目标程序

1-29．按逻辑上划分，编译程序第二步工作是 C 。

A. 语义分析

B. 词法分析

C. 语法分析

D. 代码优化

1-30．通常一个编译程序中，不仅包含词法分析，语法分析，中间代码生成，代码优化，目标代码生成等五个部分，还应包括 C 。

A.模拟执行器

B.解释器

C.表格处理和出错处理

D.符号执行器

2-07．文法G所描述的语言是 C 的集合。

A.文法G的字母表V中所有符号组成的符号串

B.文法G的字母表V的闭包V*中的所有符号串

C.由文法的开始符号推出的所有终极符串

D.由文法的开始符号推出的所有符号串

2-08．乔姆斯基（Chomsky）把文法分为四种类型，即0型、1型、2型、3型。其中3型文法是 B 。

A.短语文法

B.正则文法

C.上下文有关文法

D.上下文无关文法

2-09.文法G[N]=（{b}，{N，B}，N，{N→b│bB，B→bN}），该文法所描述的语言是

C 。

A. L(G[N])={b i│i≥0}

B. L(G[N])={b2i│i≥0}

C. L(G[N])={b2i+1│i≥0}

D. L(G[N])={b2i+1│i≥1}

2-10．一个句型中的最左 B 称为该句型的句柄。

可选项有：

A. 短语

B. 简单短语

C. 素短语

D. 终结符号

2-11．设G是一个给定的文法，S是文法的开始符号，如果S x(其中x∈V*),则称x是文法G的一个 B 。

A. 候选式

B. 句型

C. 单词

D. 产生式

2-12．一个上下文无关文法G包括四个组成部分，它们是：一组非终结符号，一组终结符号，一个开始符号，以及一组 D 。

A. 句子

B. 句型

C. 单词

D. 产生式

2-13.文法G[E]：

E→T∣E＋T

T→F∣T﹡F

F→a∣（E）

该文法句型E＋F﹡(E＋T)的简单短语是下列符号串中的 B 。

①（E＋T）②E＋T ③F ④ F﹡(E＋T)

可选项有：

A) ①和③ B) ②和③ C) ③和④ D) ③

2-14．若一个文法是递归的，则它所产生的语言的句子 A 。

A.是无穷多个

B.是有穷多个

C.是可枚举的

D.个数是常量

3-02．词法分析器用于识别 C 。

A. 句子

B. 句型

C. 单词

D. 产生式

4-07.在语法分析处理中，FIRST集合、FOLLOW集合、SELECT集合均是 B 。

A. 非终极符集

B.终极符集

C. 字母表

D. 状态集

4-08.编译程序中语法分析器接收以 A 为单位的输入。

A. 单词

B. 表达式

C. 产生式

D. 句子

5-06．在自底向上的语法分析方法中，分析的关键是 D 。

A. 寻找句柄

B. 寻找句型

C. 消除递归

D. 选择候选式

5-07. 在LR分析法中，分析栈中存放的状态是识别规范句型 C 的DFA状态。

A.句柄

B. 前缀

C. 活前缀

D. LR(0)项目

三、是非题(下列各题，你认为正确的，请在题干的括号内打“ √”，错的打“×”。)

1-31.计算机高级语言翻译成低级语言只有解释一种方式。（×）

1-32.在编译中进行语法检查的目的是为了发现程序中所有错误。（×）

1-34.甲机上的某编译程序在乙机上能直接使用的必要条件是甲机和乙机的操作系统功能完全相同。（×）2-15.正则文法其产生式为A→a，A→Bb, A,B∈V N，a、b∈V T。（√）

4-09.每个文法都能改写为LL(1)文法。（×）

4-10.递归下降法允许任一非终极符是直接左递归的。（√）

5-08.算符优先关系表不一定存在对应的优先函数。（√）

5-09.自底而上语法分析方法的主要问题是候选式的选择。（×）

5-10.LR法是自顶向下语法分析方法。（×）

5-11.简单优先文法允许任意两个产生式具有相同右部。（×）

5-12.若一个句型中出现了某产生式的右部，则此右部一定是该句型的句柄。（×）

5-13.一个句型的句柄一定是文法某产生式的右部。（√）

7-02.数组元素的地址计算与数组的存储方式有关。（√）

8-03.在程序中标识符的出现仅为使用性的。（×）

9-04.对于数据空间的存贮分配，FORTRAN采用动态贮存分配策略。（×）

9-05.在程序中标识符的出现仅为使用性的。（×）

四、名词解释

1-35. 扫描遍____指编译程序对源程序或中间代码程序从头到尾扫描一次。

R

2-16.短语——设G[Z]是给定文法, w=xuy ∈V +，为该文法的句型,如果满足下面两个条件:

① Z xUy ； ② U

u ；

则称句型xuy 中的子串u 是句型xuy 的短语。

2-17.简单短语——设G[Z]是给定文法, w=xuy ∈V +，为该文法的句型,如果满足下面两个条件:

① Z

xUy ；

② U u ；

则称句型xuy 中的子串u 是句型xuy 的简单短语（或直接短语）。 2-18.句柄——一个句型中的最左简单短语称为该句型的句柄。

4-11.语法分析－－按文法的产生式识别输入的符号串是否为一个句子的分析过程。 4-12.选择符集合SELECT －－给定上下文无关文法的产生式A→α, A ∈V N ,α∈V *

, 若

α

ε,则

SELECT(A→α)=FIRST(α),其中如果

α

ε，则SELECT(A→α)=FIRST(α\ε)∪

FOLLOW(A),FIRST(α\ε)表示FIRST(α)的非{ε}元素。

5-14.活前缀——若S′ αA ω αβω是文法G′中的一个规范推导，G′是G 的拓广文法，符号串γ是αβ的前缀，则称γ是G 的，也是G′的一个活前缀。其中 S'为文法开始符号。或：可归前缀

的任意首部。

5-15.可归前缀——是指规范句型的一个前缀，这种前缀不含句柄之后的任何符号。

5-16.LR(0)项目——把产生式右部某位置上标有圆点的产生式称为相应文法的一个LR(0)项目。 5-17.最左素短语——设有文法G[S],其句型的素短语是一个短语,它至少包含一个终结符，并除自身外不

包含其它素短语，最左边的素短语称最左素短语。

6-05.语义规则——对于文法的每个产生式都配备了一组属性的计算规则，称为语义规则。

6-06.翻译方案——将属性文法中的语义规则用花括号{ }括起来，插在产生式右部的合适地方，指明语义规则的计算次序，陈述一些细节，得到一种语义动作与语法分析交错的表示方法，以表述语义动作在语法分析过程中的执行时刻，称之为翻译方案。

7-03.后缀式—— 一种把运算量（操作数）写在前面把算符写在后面（后缀）的表示法。即

一个表达式E 的后缀形式可以如下定义：

(1) 如果E 是一个变量或常量，则E 的后缀式是E 自身。

(2) 如果E 是E 1 op E 2形式的表达式，这里op 是任何二元操作符，则E 的后缀式为E 1’ E 2’op，这

里E 1’和E 2’分别为E 1和E 2的后缀式。

(3) 如果E 是（E 1）形式的表达式，则E 1的后缀式就是E 的后缀式。

答：一个过程的活动指的是该过程的一次执行。就是说，每次执行一个过程体，产生该过程体的一个活动。 9-07.活动记录

答：为了管理过程在一次执行中所需要的信息，使用一个连续的存储块，这样一个连续的存储块称为活动记录。

9-08.活动的生存期

答：指的是从执行某过程体第一步操作到最后一步操作之间的操作序，包括执行过程时调用其它过程花费

的时间。

10-06. 基本块的DAG 。

R

答：一个基本块的DAG是一种其结点带有下述标记或附加信息的DAG。

(1)图的叶结点（没有后继的结点）以一标识符（变量名）或常数作为标记，表示该结点代表该变量或常数的值。如果叶结点用来代表某变量A的地址，则用addr（A）作为该结点的标记。通常把叶结点上作为标记的标识符加上下标0，以表示它是该变量的初值。

(2)图的内部结点（有后继的结点）以一运算符作为标记，表示该结点代表应用该运算符对其后继结点所代表的值进行运算的结果。

(3)图中各个结点上可能附加一个或多个标识符，表示这些变量具有该结点所代表的值。

五、简答题：

2-19什么是句子？什么是语言?

答：设G是一个给定的文法，S是文法的开始符号，如果S x(其中x∈V T*),则称x是文法的一个句子。

设G[S]是给定文法，则由文法G所定义的语言L(G)可描述为： L(G)＝{x│S x,x∈V T*} 。

2-20.已知文法G[E]为：

E→T|E+T|E-T

T→F|T*F|T/F

F→（E）|i

①该文法的开始符号（识别符号）是什么？

②请给出该文法的终结符号集合V T和非终结符号集合V N。

③找出句型T+T*F+i的所有短语、简单短语和句柄。

解：①该文法的开始符号（识别符号）是E。

②该文法的终结符号集合V T={+、-、*、/、（、）、i}。

非终结符号集合V N={E、T、F}。

③句型T+T*F+I的短语为i、T*F、第一个T、T+T*F+i;

简单短语为i、T*F、第一个T;句柄为第一个T。

2-21.已知文法G[S]为：

S→dAB

A→aA|a

B→Bb|ε

① G[S]产生的语言是什么？

② G[S]能否改写为等价的正规文法？

解：① G[S]产生的语言是L(G[S])={da n b m│n≥1,m≥0}。

② G[S]能改写为等价的正规文法,其改写后的等价的正规文法G[Sˊ]为：

Sˊ→dA

A →aA|aB|a

B →bB|b

2-22.设有语言L(G)={ada R | a∈(a,b)*,a R 为a之逆}，试构造产生此语言的上下文无关文法G。

解：根据题义，可知a R 为a之逆的含义就是句子中的符号a、b以d为中心呈左右对称出现；由于a∈(a,b)*，所以a、b的个数可以为零。所以可构造产生此语言的上下文无关文法G[S]为：S→aSa|bSb|d

3-03．简述DFA与NFA有何区别 ?

答：DFA 与NFA 的区别表现为两个方面:一是NFA 可以若干个开始状态，而DFA 仅只一个开始状态。另一方

面，DFA 的映象M 是从K ×∑到K ，而NFA 的映象M 是从K ×∑到K 的子集，即映象M 将产生一个状态集合（可能为空集），而不是单个状态。 3-04.试给出非确定自动机的定义。

答：一个非确定的有穷自动机（NFA ）M 是一个五元组：M=（K ，Σ，f ，S ，Z ）。

其中:

1. K 是一个有穷集，它的每个元素称为一个状态；

2. Σ是一个有穷字母表，它的每个元素称为一个输入符号，所以也称Σ为输入符号表；

3. f 是状态转换函数，是在K ×Σ*→K 的子集的映射，即，f: K ×Σ*→2K ；表明在某状态下对于某

输入符号可能有多个后继状态； 4. S ﹙K 是一个非空初态集； 5. Z ﹙K 是一个终态集（可空）。

3-05. 为正规式（a|b ）*

a(a|b) 构造一个等价的确定的有限自动机。

解答：

3-06. 给定下列自动机，将其转换为确定的自动机。

解答：(1)消除ε边，得到NFA ：

(2)确定化，得到DFA ：

带―号的结点为终止状态

―

― 带―号的结点为终止状态

其中：开始状态：0 终止状态：2

b

3-07. 给定下列自动机：

(1)把此自动机转换为确定自动机DFA 。 (2)给出此DFA 的正则表达式。 解答：（1）： 有状态矩阵如图：

从而可得DFA 如图：

―

＋ 注：带＋号的结点为初始状态； 带―号的结点为终止状态

a b ?0 01 2 01 01 2 －2 1 2 1 2

a b

?0 0,1 2 1 2 －2 1 2

?

a

极小化后：

a

1． Z →C S

2． C →if E then

3． S →A ＝E

其中：Z 、C 、S 、A 、E ∈V N ； if 、then 、＝、∨、i ∈V T （2）此DFA 的正则表达式为： (aa *

b ∣b)(b ∣ab)*

或 a *

b （b ∣ab ）*

。 4-13.消除下列文法G[E]的左递归。

E →E-T ∣T T →T/

F ∣F F →( E )∣i 解答：

消除文法G[E]的左递归后得到： E →TE ’ E’→ -T E’∣ε T →FT’ T’→/FT’∣ε F →( E )∣i

4-14.在LL(1)分析法中,LL 分别代表什么含义?

答:第一个L 代表从左到右的扫描，第二个L 代表每次进行最左推导。 4-15.自顶向下分析思想是什么？

答：从开始符出发导出句型并一个符号一个符号地与给定终结符串进行匹配。如果全部匹配成功，则表示

开始符号可推导出给定的终结符串。因此判定给定终结符号串是正确句子。 4-16.自顶向下的缺点是什么？

答：在推导过程中，如果对文法不做限制。那么产生式的选择成为无根据的，只好一一去试所有可能的产

生式，直至成功为止。这种方法的致命弱点是不断地回溯，大大影响速度。 4-17.LL （1）文法的定义是什么？

答：一个上下文无关文法是LL(1)文法的充分必要条件是每个非终结符A 的两个不同产生式，A →α,A →β；

满足SELECT(A →α)∩SELECT(A →β)=Ф。其中，α、β不能同时ε。

4-18.什么是文法的左递归？

答：一个文法含有下列形式的产生式之一时：

1)A →A β，A ∈VN ，β∈V*

2)A →B β，B →A α，A 、B ∈VN ，α、β∈V* 则称该文法是左递归的。 4-19.递归下降法的主要思想是什么？

答：对每个非终结符按其产生式结构写出相应语法分析子程序。因为文法递归相应子程序也递归，子程序

的结构与产生式结构几乎一致。所以称此种方法称为递归子程序法或递归下降法。 5-19.自底向上分析法的原理是什么？

答：在采用自左向右扫描，自底向上分析的前提下，该类分析方法是从输入符号串入手，通过反复查找当

前句型的句柄（最左简单短语），并使用文法的产生式把句柄归约成相应的非终极符来一步步地进行分析的。最终把输入串归约成文法的开始符号，表明分析成功。 5-23. 给定文法G[Z]：

a) 构造此文法的LR(0)项目集规范族，并给出识别活前缀的DFA 。 b) 构造其SLR （1）分析表。

解答：1.首先拓广文法：在G 中加入产生式0．Z ′→Z ，然后得到新的文法G ′，再求G ′的识别全部活前

缀的DFA ：

2． Follow(Z)＝{#}

Follow(C)＝{i} Follow(S)＝{#}

Follow(E)＝{#,∨,then} Follow(A)＝{＝,# ,∨,then }

I 0：Z ′→.Z

Z →.C S

C →.if E then I 1：Z ′→Z . I 2：Z →C .S

S →.A ＝E A →.i

I 3：C →if .E then

E →.E ∨A E →.A A →.i I 4：Z →C S . I 5：S →A .＝E I 6：A →i .

I 7：C →if E .then

E →E .∨A I 9：S →A ＝.E

E →.E ∨A E →.A A →.i

I 10：C →if E then . I 11：E →E ∨.A

A →.i

I 12：S →A ＝E .

E →E .∨A I 13：E →E ∨A .

S →a A A →Ab A →b

0.S ′→S 1.S →aA 2.A →Ab 3.A →b

5-24. 设有文法G[S]：

求识别该文法所有活前缀的DFA 。 解答：

(1).首先拓广文法：

在G 中加入产生式0.S ′→S ，然后得到新的文法G ′:

(2).再求G ′的识别全部活前缀的DFA ： 6-07.语法制导翻译方法的基本思想是什么?

答：在语法分析过程中，每当使用一条产生式进行推导或归约时，就执行该产生式所对应的语义动作进行

属性计算，完成对输入符号串的翻译。 6-08.何谓“语法制导翻译”?

答：在语法分析过程中，随着分析的步步进展，根据每个产生式所对应的语义子程序（或语义规则描述的

语义动作）进行翻译的办法称作语法制导翻译。

6-09.在一个属性文法中，对应于每个产生式A →a 都有一套与之相关联的语义规则，每条规则的形式为

b ：＝f （c1,c2…，ck ），其中对于b 的要求是什么？ 答：语义规则中的左部属性变量b 被规定为只能是下述两种变量：

① 对应产生式左部符号的综合属性变量； ② 对应产生式右部符号的继承属性变量。

7-05.常用的中间语言种类有哪几种？

答：有逆波兰式、三地址代码、抽象语法树和DAG 。

8-06.符号表的作用有哪些？

答：在编译程序中符号表用来存放语言程序中出现的有关标识符的属性信息，这些信息集中反映了标识符

的语义特征属性。起主要作用是：

① 收集符号属性；

② 上下文语义的合法性检查的依据；

③ 作为目标代码生成阶段地址分配的依据。

9-09．运行时存储器的划分是怎样的？ 答：运行时存储器的划分如下图所示。

10-07. 简述优化的原则是什么？

答：编译程序提供的对代码优化必须遵循的原则是： （1） 等价原则。经过优化后不应改变程序运行的结果。

（2） 有效原则。使优化后所产生的目标代码运行时间较短，占用的存储空间较小。 （3） 合算原则。应尽可能以较低的代价取得较好的优化效果。 10-08．简述常用的优化技术有哪些？ 答：编译程序中常用的优化技术有： （1） 删除公共子表示式； （2） 复写传播； （3） 删除无用代码； （4） 代码外提； （5） 强度削弱； （6） 删除归纳变量； （7） 合并常量。 10-09. 设有基本块： (1) a:=b-c (2) d:=a+4 (3) e:=a-b (4) f:=a+4 (5) b:=b+c (6) c:=b-f (7) b:=b-c (8) f:=b+f (9) a:=a-f (1) 画出DAG 图；

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

(1)给出DAG 如右：

(2)重写三地址代码如下：

+

b 10 f

a:=b-c

d:=a+4

f:=d

e:=a-b

b:=b+c

c:=c+d

b:=b-c

f:=b-d

a:=a+d

10-10.何谓优化？按所涉及的程序范围可分为哪几级优化？

答：优化：对程序进行各种等价变换，使得从变换后的程序出发，能产生更有效的目标代码。

三种级别：局部优化、循环优化、全局优化。

10-11.设有基本块

T1：＝2

T2：＝10/T1

T3：＝S－R

T4：＝S＋R

A：＝T2 * T4

B：＝A

T5：＝S＋R

T6：＝T3 * T5

B：＝T6

(1) 画出DAG图；

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

解：(1)DAG：见右图

(2) 优化后的四元式

T3：＝S－R

T4：＝S＋R

A：＝5*T4

B：＝T3＋T4

编译原理课后习题答案(第三版)

精品文档 第二章 P36-6 (1) L G ()1是0~9组成的数字串 (2) 最左推导: N ND NDD NDDD DDDD DDD DD D N ND DD D N ND NDD DDD DD D ??????????????????0010120127334 556568 最右推导: N ND N ND N ND N D N ND N D N ND N ND N D ??????????????????77272712712701274434 886868568 P36-7 G(S) O N O D N S O AO A AD N →→→→→1357924680||||||||||| P36-8 文法： E T E T E T T F T F T F F E i →+-→→|||*|/()| 最左推导: E E T T T F T i T i T F i F F i i F i i i E T T F F F i F i E i E T i T T i F T i i T i i F 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 E T F T F F F E F E T F E F F E i F T i F F i F i i i i i ?+?+?+?+?+?+?+?+?????+?+?+?+?+?+?+**********()*()*()*()*()*()*()*() 语法树：/********************************

王汝传编译原理习题答案

《编译原理》习题答案： 第一次： P14 2、何谓源程序、目标程序、翻译程序、汇编程序、编译程序和解释程序？它们之间可能有何种关系？ 答：被翻译的程序称为源程序； 翻译出来的程序称为目标程序或目标代码； 将汇编语言和高级语言编写的程序翻译成等价的机器语言，实现此功能的程序称为翻译程序； 把汇编语言写的源程序翻译成机器语言的目标程序称为汇编程序； 解释程序不是直接将高级语言的源程序翻译成目标程序后再执行，而是一个个语句读入源程序，即边解释边执行； 编译程序是将高级语言写的源程序翻译成目标语言的程序。 关系：汇编程序、解释程序和编译程序都是翻译程序，具体见P4 图 1.3。 P14 3、编译程序是由哪些部分组成？试述各部分的功能？ 答：编译程序主要由8个部分组成：（1）词法分析程序；（2）语法分析程序；（3）语义分析程序；（4）中间代码生成；（5）代码优化程序；（6）目标代码生成程序；（7）错误检查和处理程序；（8）信息表管理程序。具体功能见P7-9。 P14 4、语法分析和语义分析有什么不同？试举例说明。 答：语法分析是将单词流分析如何组成句子而句子又如何组成程序，看句子乃至程序是否符合语法规则，例如：对变量x：= y 符合语法规则就通过。语义分析是对语句意义进行检查，如赋值语句中x与y类型要一致，否则语法分析正确，语义分析则错误。 P15 5、编译程序分遍由哪些因素决定？ 答：计算机存储容量大小；编译程序功能强弱；源语言繁简；目标程序优化程度；设计和实现编译程序时使用工具的先进程度以及参加人员多少和素质等等。 补充： 1、为什么要对单词进行内部编码？其原则是什么？对标识符是如何进行内部编码的？ 答：内部编码从“源字符串”中识别单词并确定单词的类型和值；原则：长度统一，即刻画了单词本身，也刻画了它所具有的属性，以供其它部分分析使用。对于标识符编码，先判断出该单词是标识符，然后在类别编码中写入相关信息，以表示为标识符，再根据具体标识符的含义编码该单词的值。 补充： 2、赋值语句：A：= 5 * C的语法和语义指的是什么？ 答：语法分析将检查该语句是否符合赋值语句规则，语义是指将 5 * C 的结果赋值为 A 。第二次作业： P38 1、设T1＝{11，010}，T2＝{0，01，1001}，计算：T2T1，T1*，T2+。 T2T1＝{011，0010，0111，01010，100111，1001010} T1*＝{ε，11，010，1111，11010，01011，010010……} T2+＝{0，01，1001，00，001，01001，010，0101……}

(完整版)编译原理课后习题答案

第一章 1．典型的编译程序在逻辑功能上由哪几部分组成？ 答：编译程序主要由以下几个部分组成：词法分析、语法分析、语义分析、中间代码生成、中间代码优化、目标代码生成、错误处理、表格管理。 2. 实现编译程序的主要方法有哪些？ 答：主要有：转换法、移植法、自展法、自动生成法。 3. 将用户使用高级语言编写的程序翻译为可直接执行的机器语言程序有哪几种主要的方式？ 答：编译法、解释法。 4. 编译方式和解释方式的根本区别是什么？ 答：编译方式：是将源程序经编译得到可执行文件后，就可脱离源程序和编译程序单独执行，所以编译方式的效率高，执行速度快； 解释方式：在执行时，必须源程序和解释程序同时参与才能运行，其不产生可执行程序文件，效率低，执行速度慢。

第二章 1.乔姆斯基文法体系中将文法分为哪几类？文法的分类同程序设计语言的设计与实现关 系如何？ 答：1）0型文法、1型文法、2型文法、3型文法。 2） 2. 写一个文法，使其语言是偶整数的集合，每个偶整数不以0为前导。 答： Z→SME | B S→1|2|3|4|5|6|7|8|9 M→ε | D | MD D→0|S B→2|4|6|8 E→0|B 3. 设文法G为： N→ D|ND D→ 0|1|2|3|4|5|6|7|8|9 请给出句子123、301和75431的最右推导和最左推导。 答：N?ND?N3?ND3?N23?D23?123 N?ND?NDD?DDD?1DD?12D?123 N?ND?N1?ND1?N01?D01?301 N?ND?NDD?DDD?3DD?30D?301 N?ND?N1?ND1?N31?ND31?N431?ND431?N5431?D5431?75431 N?ND?NDD?NDDD?NDDDD?DDDDD?7DDDD?75DDD?754DD?7543D?75431 4. 证明文法S→iSeS|iS| i是二义性文法。 答：对于句型iiSeS存在两个不同的最左推导： S?iSeS?iiSes S?iS?iiSeS 所以该文法是二义性文法。 5. 给出描述下面语言的上下文无关文法。 （1）L1={a n b n c i |n>=1,i>=0 } （2）L2={a i b j|j>=i>=1} （3）L3={a n b m c m d n |m,n>=0} 答： （1）S→AB A→aAb | ab B→cB | ε （2）S→ASb |ab

编译原理复习题及答案

编译原理复习题及答案 一、选择题 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)不是编译程序的组成部分。 A.词法分析程序 B.代码生成程序 C.设备管理程序 D.语法分析程序 15．通常一个编译程序中，不仅包含词法分析，语法分析，语义分析，中间代码生成，代码优化，目标代码生成等六个部分，还应包括(C)。 A．模拟执行器B．解释器 C．表格处理和出错处理D．符号执行器16．编译程序绝大多数时间花在(D)上。 A．出错处理B．词法分析C．目标代码生成D．表格管理 17．源程序是句子的集合，(B)可以较好地反映句子的结构。 A. 线性表 B. 树 C. 完全图 D. 堆栈 18．词法分析器的输出结果是(D)。 A、单词自身值 B、单词在符号表中的位置 C、单词的种别编码 D、单词的种别编码和自身值 19．词法分析器不能(D) A. 识别出数值常量 B. 过滤源程序中的注释 C. 扫描源程序并识别记号 D. 发现括号不匹配 20．文法：G：S→xSx | y所识别的语言是(D)。 A、xyx B、(xyx)* C、x*yx* D、x n yx n (n≥0) 21．如果文法G是无二义的，则它的任何句子α(A) A．最左推导和最右推导对应的语法树必定相同 B．最左推导和最右推导对应的语法树可能不同 C．最左推导和最右推导必定相同 D．可能存在两个不同的最左推导，但它们对应的语法树相同 22．正则文法(A)二义性的。 A. 可以是 B. 一定不是 C. 一定是 23．(B)这样一些语言，它们能被确定的有穷自动机识别，但不能用正则表达式表示。 A. 存在 B. 不存在 C. 无法判定是否存在 24．给定文法A→bA | ca，为该文法句子的是(C) A. bba B. cab C. bca D. cba

编译原理习题解答

第二章：习题2-4 Table表 var x,y; procedure p; var a; procedure q; var b; begin b:=10; end; procedure s; var c,d; procedure r; var e,f; begin call q; end; begin call r; end; begin call s; end; begin call p; end 根据：Page289，变量table:array[0..txmax] of record 结构体以及block函数得到下表，而表中各部分的含义，

第三章文法和语言 5. 写一文法，使其语言是偶正整数的集合 要求： (1)允许0打头 (2)不允许0打头 解： (1)G[S]=({S,P,D,N},{0,1,2,…,9},P,S) P: S→PD|D P->NP|N D→0|2|4|6|8 N->0|1|2|3|4|5|6|7|8|9 (2)G[S]=({S,P,R,D,N,Q },{0,1,2,…,9},P,S) P: S→PD|P0|D P->NR|N R->QR|Q D→2|4|6|8 N->1|2|3|4|5|6|7|8|9 Q->0|1|2|3|4|5|6|7|8|9 6. 已知文法G： <表达式>::=<项>|<表达式>+<项>|<表达式>-<项> <项>::=<因子>|<项>*<因子>|<项>/<因子> <因子>::=(<表达式>)|i。 试给出下述表达式的推导及语法树。 (1)i; (2)(i) (3)i*i; (4)i*i+i; (5)i+(i+i); (6)i+i*i。 解： (1)v=<表达式>=><项>=><因子>=>i=w (2)v=<表达式>=><项>=><因子>=>(<表达式>)=>(<项>)=>(<因子>)=>(i)=w (3)v=<表达式>=><项>=><项>*<因子>=><因子>*<因子>=>i*i=w (4)v=<表达式>=><表达式>+<项>=><项>+<项>=><项>*<因子>+<项> =><因子>*<因子>+<因子>=>i*i+i=w (5)v=<表达式>=><表达式>+<项>=><项>+<项>=><因子>+<因子>=>i+(<表达式>) => i+(<表达式>+<项>)=>i+(<项>+<项>)=> i+(<因子>+<因子>)=>i+(i+i)=w (6)v=<表达式>=><表达式>+<项>=><项>+<项>=><因子>+<项>=>i+<项> =>i+<项>*<因子>=> i+<因子>*<因子>=> i+i*i=w 语法树见下图:

编译原理课后答案

第二章 2.3叙述由下列正规式描述的语言 (a) 0(0|1)*0 在字母表{0, 1}上,以0开头和结尾的长度至少是2的01 串 (b) ((ε|0)1*)* 在字母表{0, 1}上,所有的01串,包括空串 (c) (0|1)*0(0|1)(0|1) 在字母表{0, 1}上,倒数第三位是0的01串 (d) 0*10*10*10* 在字母表{0, 1}上,含有3个1的01串 (e) (00|11)*((01|10)(00|11)*(01|10)(00|11)*)* 在字母表{0, 1}上,含有偶数个0和偶数个1的01串 2.4为下列语言写正规定义 C语言的注释，即以 /* 开始和以 */ 结束的任意字符串，但它的任何前缀（本身除外）不以 */ 结尾。 ［解答］ other → a | b | … other指除了*以外C语言中的其它字符 other1 → a | b | … other1指除了*和/以外C语言中的其它字符 comment → /* other* (* ** other1 other*)* ** */ (f) 由偶数个0和偶数个1构成的所有0和1的串。 ［解答］由题目分析可知，一个符号串由0和1组成，则0和1的个数只能有四种情况： x 偶数个0和偶数个1（用状态0表示）； x 偶数个0和奇数个1（用状态1表示）； x 奇数个0和偶数个1（用状态2表示）； x 奇数个0和奇数个1（用状态3表示）；所以， x 状态0（偶数个0和偶数个1）读入1，则0和1的数目变为：偶数个0和奇数个1（状态1） x 状态0（偶数个0和偶数个1）读入0，则0和1的数目变为：奇数个0和偶数个1（状态2） x 状态1（偶数个0和奇数个1）读入1，则0和1的数目变为：偶数个0和偶数个1（状态0） x 状态1（偶数个0和奇数个1）读入0，则0和1的数目变为：奇数个0和奇数个1（状态3） x 状态2（奇数个0和偶数个1）读入1，则0和1的数目变为：奇数个0和奇数个1（状态3） x 状态2（奇数个0和偶数个1）读入0，则0和1的数目变为：偶数个0和偶数个1（状态0） x 状态3（奇数个0和奇数个1）读入1，则0和1的数目变为：奇数个0和偶数个1（状态2） x 状态3（奇数个0和奇数个1）读入0，则0和1的数目变为：偶数个0和奇数个1（状态1） 因为，所求为由偶数个0和偶数个1构成的所有0和1的串，故状态0既为初始状态又为终结状态，其状态转换图： 由此可以写出其正规文法为： S0 → 1S1 | 0S2 | ε S1 → 1S0 | 0S3 | 1 S2 → 1S3 | 0S0 | 0 S3 → 1S2 | 0S1 在不考虑S0 →ε产生式的情况下，可以将文法变形为： S0 = 1S1 + 0S2 S1 = 1S0 + 0S3 + 1 S2 = 1S3 + 0S0 + 0 S3 = 1S2 + 0S1 所以： S0 = (00|11) S0 + (01|10) S3 + 11 + 00 (1) S3 = (00|11) S3 + (01|10) S0 + 01 + 10 (2) 解(2)式得： S3 = (00|11)* ((01|10) S0 + (01|10)) 代入(1)式得： S0 = (00|11) S0 + (01|10) (00|11)*((01|10) S0 + (01|10)) + (00|11) => S0 = ((00|11) + (01|10) (00| 11)*(01|10))S0 + (01|10) (00|11)*(01|10) + (00|11) => S0 = ((00|11)|(01|10) (00|11)*(01|10))*((00|1

编译原理课后习题答案-清华大学-第二版

第1章引论 第1题 解释下列术语： （1）编译程序 （2）源程序 （3）目标程序 （4）编译程序的前端 （5）后端 （6）遍 答案： （1） 编译程序：如果源语言为高级语言，目标语言为某台计算机上的汇编语言或机器语言，则此翻译程序称为编译程序。 （2） 源程序：源语言编写的程序称为源程序。 （3） 目标程序：目标语言书写的程序称为目标程序。 （4） 编译程序的前端：它由这样一些阶段组成：这些阶段的工作主要依赖于源语言而与目标机无关。通常前端包括词法分析、语法分析、语义分析和中间代码生成这些阶 段，某些优化工作也可在前端做，也包括与前端每个阶段相关的出错处理工作和符 号表管理等工作。 （5） 后端：指那些依赖于目标机而一般不依赖源语言，只与中间代码有关的那些阶段，即目标代码生成，以及相关出错处理和符号表操作。 （6） 遍：是对源程序或其等价的中间语言程序从头到尾扫视并完成规定任务的过程。 第2题 一个典型的编译程序通常由哪些部分组成？各部分的主要功能是什么？并画出编译程序的总体结构图。 答案： 一个典型的编译程序通常包含8个组成部分，它们是词法分析程序、语法分析程序、语义分析程序、中间代码生成程序、中间代码优化程序、目标代码生成程序、表格管理程序和错误处理程序。其各部分的主要功能简述如下。 词法分析程序：输人源程序，拼单词、检查单词和分析单词，输出单词的机内表达形式。 语法分析程序：检查源程序中存在的形式语法错误，输出错误处理信息。 语义分析程序：进行语义检查和分析语义信息，并把分析的结果保存到各类语义信息表中。

目标代码生成程序：将优化后的中间代码程序转换成目标代码程序。 表格管理程序：负责建立、填写和查找等一系列表格工作。表格的作用是记录源程序的各类信息和编译各阶段的进展情况，编译的每个阶段所需信息多数都从表格中读取，产生的中间结果都记录在相应的表格中。可以说整个编译过程就是造表、查表的工作过程。需要指出的是，这里的“表格管理程序”并不意味着它就是一个独立的表格管理模块，而是指编译程序具有的表格管理功能。 错误处理程序：处理和校正源程序中存在的词法、语法和语义错误。当编译程序发现源程序中的错误时，错误处理程序负责报告出错的位置和错误性质等信息，同时对发现的错误进行适当的校正（修复），目的是使编译程序能够继续向下进行分析和处理。 注意：如果问编译程序有哪些主要构成成分，只要回答六部分就可以。如果搞不清楚，就回答八部分。 第3题 何谓翻译程序、编译程序和解释程序？它们三者之间有何种关系？ 答案： 翻译程序是指将用某种语言编写的程序转换成另一种语言形式的程序的程序，如编译程序和汇编程序等。 编译程序是把用高级语言编写的源程序转换（加工）成与之等价的另一种用低级语言编写的目标程序的翻译程序。 解释程序是解释、执行高级语言源程序的程序。解释方式一般分为两种：一种方式是，源程序功能的实现完全由解释程序承担和完成，即每读出源程序的一条语句的第一个单词，则依据这个单词把控制转移到实现这条语句功能的程序部分，该部分负责完成这条语句的功

编译原理习题及答案(整理后)

第一章 1、将编译程序分成若干个“遍”就是为了。 a．提高程序得执行效率 b．使程序得结构更加清晰 c．利用有限得机器内存并提高机器得执行效率 d．利用有限得机器内存但降低了机器得执行效率 2、构造编译程序应掌握。 a．源程序b．目标语言 c．编译方法d．以上三项都就是 3、变量应当。 a．持有左值b．持有右值 c．既持有左值又持有右值d．既不持有左值也不持有右值 4、编译程序绝大多数时间花在上。 a．出错处理b．词法分析 c．目标代码生成d．管理表格 5、不可能就是目标代码。 a．汇编指令代码b．可重定位指令代码 c．绝对指令代码d．中间代码 6、使用可以定义一个程序得意义。 a．语义规则b．语法规则 c．产生规则d．词法规则 7、词法分析器得输入就是。 a．单词符号串b．源程序 c．语法单位d．目标程序 8、中间代码生成时所遵循得就是- 。 a．语法规则b．词法规则 c．语义规则d．等价变换规则 9、编译程序就是对。 a．汇编程序得翻译b．高级语言程序得解释执行 c．机器语言得执行d．高级语言得翻译 10、语法分析应遵循。 a．语义规则b．语法规则 c．构词规则d．等价变换规则 二、多项选择题 1、编译程序各阶段得工作都涉及到。 a．语法分析b．表格管理c．出错处理 d．语义分析e．词法分析 2、编译程序工作时，通常有阶段。 a．词法分析b．语法分析c．中间代码生成 d．语义检查e．目标代码生成 三、填空题 1、解释程序与编译程序得区别在于。 2、编译过程通常可分为5个阶段，分别就是、语法分析、代码优化与目标代码生成。 3、编译程序工作过程中，第一段输入就是，最后阶段得输出为程序。

编译原理课后习题答案

第1 章 1、编译过程包括哪几个主要阶段及每个 阶段的功能。 答案：编译过程包括词法分析、语法分析、语义分析和中间代码生成、优化、目标代码生成5 个阶段。词法分析的功能是对输入的高级语言源程序进行词法分析，识别其中的单词符号，确定它们的种类，交给语法分析器，即把字符串形式的源程序分解为单词符号串形式。语法分析的功能是在词法分析结果的基础上，运用语言的语法规则，对程序进行语法分析，识别构成程序的各类语法范畴及它们之间的层次关系，并把这种层次关系表达成语法树的形式。词义分析和中间代码生成的功能是在语法分析的基础上，对程序进行语义分析，“理解”其含义，产生出表达程序语义的内部表达形式（中间代码）。优化的功能是按照等价变换的原则，对语义分析器产生的中间代码序列进行等价变换，删除其中多余的操作，对耗时耗空间的代码进行优化，以期最后得到高效的可执行代码。目标代码生成的功能是把优化后的中间代码变换成机器指令代码，得到可在目标机器上执行的机器语言程序。 第2 章 1、写一上下文无关文法G，它能产生配 对的圆括号串（如：(),(()),()(())等，甚至 包括0 对括号） 文法为：S→(L)|LS|L L→S| ε 2 、已知文法G ：E→E+T|E-T|T T→T*F|T/F|F F→(E) |i （1）给出i+i*i,i*(i-i)的最左推导，最右推导以及语法树。 （2）i-i+i 哪个算符优先。 【解答】 （1）最左推导：E?E+T?T+T? F+T ? i+T ? i+T*F ? i+F*F ?i+i*F ?i+i*i E?T?T*F? F*F ? i*F ? i*(E) ? i*(E-T) ? i*(T-T) ? i*(F-T) ? i*(i-T) ? i*(i-F) ?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 E?T?T*F? T*(E) ? T*(E-T) ? T*(E-F) ? T*(E-i) ? T*(T-i) ? T*(F-i) ?T*(i-i) ? F*(i-i) ?i*(i-i) i+i*i 以及i*(i-i)的语法树如下所示： （2）i-i+i 的语法树如下图所示。 从上图的语法树可知：“-”的位置位 于“+”的下层，也就是前面两个i 先进 行“-”运算，再与后面的i 进行“+” 运算，所以“-”的优先级高于“+”的 优先级。 3 、文法G: E→ET+|T T→TF*|F F→FP↑|P P→E|i （1）试证明符号串TET+*i↑是G 的一 个句型(要求画出语法树). （2）写出该句型的所有短语,直接短语和句柄. 【解答】（1）采用最右推导： E?T?F? FP↑? Fi↑? Pi↑? Ei↑ ? Ti↑? TF*i↑? TP*i↑? TE*i↑? TET+*i↑ 语法树如下图所示。 从文法G 的起始符号出发，能够推导 出符号串TET+*i↑，所以给定符号串是文法G的句型。 (2) 该句型的短语有： ET+,TET+*,i ,TET+*i↑ 直接短语有：ET+, i 句柄是：ET+ 4、已知文法G：S→iSeS|iS|i ，该文法 是二义文法吗？为什么？ 【解答】该文法是二义文法。 因为对于句子iiiei 存在两种不同的最 左推导： 第 1 种推导：S? iSeS? iiSeS? iiieS? iiiei 第2种推导：S?iS?iiSeS?iiieS?iiiei 第3 章 1、用正规式描述下列正规集： （1）C 语言的十六进制整数； （2）以ex 开始或以ex 结束的所有小写字母构成的符号串； （3）十进制的偶数。 【解答】 （1）C 语言十六进制整数以0x 或者0X 开头，所以一般形式应该为（+|-|ε） (0x|0X)AA*，其中前面括号表示符号， 可以有正号、负号，也可以省略（用ε表示）默认是正数，A 表示有资格出现在十六进制整数数位上的数字，AA*表示一位或者多位（一个或者多个数字的

编译原理第三版课后习题与答案

目录 P36-6 (2) P36-7 (2) P36-8 (2) P36-9 (3) P36-10 (3) P36-11 (3) P64–7 (4) P64–8 (5) P64–12 (5) P64–14 (7) P81–1 (8) P81–2 (9) P81–3 (12) P133–1 (12) P133–2 (12) P133–3 (14) P134–5 (15) P164–5 (19) P164–7 (19) P217–1 (19) P217–3 (20) P218–4 (20) P218–5 (21) P218–6 (22) P218–7 (22) P219–12 (22) P270–9 (24)

P36-6 (1) L G ()1是0~9组成的数字串 (2) 最左推导: N ND NDD NDDD DDDD DDD DD D N ND DD D N ND NDD DDD DD D ??????????????????0010120127334 556568 最右推导: N ND N ND N ND N D N ND N D N ND N ND N D ??????????????????77272712712701274434 886868568 P36-7 G(S) O N O D N S O AO A AD N →→→→→1357924680||||||||||| P36-8 文法： E T E T E T T F T F T F F E i →+-→→|||*|/()| 最左推导: E E T T T F T i T i T F i F F i i F i i i E T T F F F i F i E i E T i T T i F T i i T i i F 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 E T F T F F F E F E T F E F F E i F T i F F i F i i i i i ?+?+?+?+?+?+?+?+?????+?+?+?+?+?+?+**********()*()*()*()*()*()*()*() 语法树：/********************************

编译原理习题及答案(整理后)

第一章 1、将编译程序分成若干个“遍”是为了。 b．使程序的结构更加清晰 2、构造编译程序应掌握。 a．源程序b．目标语言 c．编译方法 3、变量应当。 c．既持有左值又持有右值 4、编译程序绝大多数时间花在上。 d．管理表格 5、不可能是目标代码。 d．中间代码 6、使用可以定义一个程序的意义。 a．语义规则 7、词法分析器的输入是。 b．源程序 8、中间代码生成时所遵循的是- 。 c．语义规则 9、编译程序是对。 d．高级语言的翻译 10、语法分析应遵循。 c．构词规则 二、多项选择题 1、编译程序各阶段的工作都涉及到。 b．表格管理c．出错处理 2、编译程序工作时，通常有阶段。 a．词法分析b．语法分析c．中间代码生成e．目标代码生成 三、填空题 1、解释程序和编译程序的区别在于是否生成目标程序。 2、编译过程通常可分为5个阶段，分别是词法分析、语法分析中间代码生成、代码优化和目标代码生成。 3、编译程序工作过程中，第一段输入是源程序，最后阶段的输出为标代码生成程序。 4、编译程序是指将源程序程序翻译成目标语言程序的程序。

一、单项选择题 1、文法G：S→xSx|y所识别的语言是。 a. xyx b. (xyx)* c. x n yx n(n≥0) d. x*yx* 2、文法G描述的语言L(G)是指。 a. L(G)={α|S+?α , α∈V T*} b. L(G)={α|S*?α, α∈V T*} c. L(G)={α|S*?α,α∈(V T∪V N*)} d. L(G)={α|S+?α, α∈(V T∪V N*)} 3、有限状态自动机能识别。 a. 上下文无关文法 b. 上下文有关文法 c.正规文法 d. 短语文法 4、设G为算符优先文法，G的任意终结符对a、b有以下关系成立。 a. 若f(a)>g(b)，则a>b b.若f(a)

编译原理课后习题答案+清华大学出版社第二版

第 1 章引论 第1 题 解释下列术语： （1）编译程序 （2）源程序 （3）目标程序 （4）编译程序的前端 （5）后端 （6）遍 答案： （1）编译程序：如果源语言为高级语言，目标语言为某台计算机上的汇编语言或机器语言，则此翻译程序称为编译程序。 （2）源程序：源语言编写的程序称为源程序。 （3）目标程序：目标语言书写的程序称为目标程序。 （4）编译程序的前端：它由这样一些阶段组成：这些阶段的工作主要依赖于源语言而与目标机无关。通常前端包括词法分析、语法分析、语义分析和中间代码生成这些阶 段，某些优化工作也可在前端做，也包括与前端每个阶段相关的出错处理工作和符 号表管理等工作。 （5）后端：指那些依赖于目标机而一般不依赖源语言，只与中间代码有关的那些阶段，即目标代码生成，以及相关出错处理和符号表操作。 （6）遍：是对源程序或其等价的中间语言程序从头到尾扫视并完成规定任务的过程。 第2 题 一个典型的编译程序通常由哪些部分组成？各部分的主要功能是什么？并画出编译程序的总体结构图。 答案： 一个典型的编译程序通常包含8个组成部分，它们是词法分析程序、语法分析程序、语义分析程序、中间代码生成程序、中间代码优化程序、目标代码生成程序、表格管理程序和错误处理程序。其各部分的主要功能简述如下。 词法分析程序：输人源程序，拼单词、检查单词和分析单词，输出单词的机内表达形式。 语法分析程序：检查源程序中存在的形式语法错误，输出错误处理信息。 语义分析程序：进行语义检查和分析语义信息，并把分析的结果保存到各类语义信息表中。 中间代码生成程序：按照语义规则，将语法分析程序分析出的语法单位转换成一定形式的中间语言代码，如三元式或四元式。 中间代码优化程序：为了产生高质量的目标代码，对中间代码进行等价变换处理。目标代码生成程序：将优化后的中间代码程序转换成目标代码程序。

编译原理复习题及答案

编译原理复习题及答案一、选择题 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)不是编译程序的组成部分。 A.词法分析程序 B.代码生成程序? C.设备管理程序 D.语法分析程序 15．通常一个编译程序中，不仅包含词法分析，语法分析，语义分析，中间代码生成，代码优化，目标代码生成等六个部分，还应包括(C)。 A．模拟执行器B．解释器?C．表格处理和出错处理 ??? D．符号执行器16．编译程序绝大多数时间花在(D)上。 A．出错处理B．词法分析C．目标代码生成D．表格管理 17．源程序是句子的集合，(B)可以较好地反映句子的结构。 A. 线性表 B. 树 C. 完全图 D. 堆栈 18．词法分析器的输出结果是(D)。 A、单词自身值 B、单词在符号表中的位置 C、单词的种别编码 D、单词的种别编码和自身值 19．词法分析器不能(D) A. 识别出数值常量 B. 过滤源程序中的注释 C. 扫描源程序并识别记号 D. 发现括号不匹配 20．文法：G：S→xSx | y所识别的语言是(D)。 A、xyx B、(xyx)* C、x*yx* D、x n yx n(n≥0) 21．如果文法G是无二义的，则它的任何句子α(A) A．最左推导和最右推导对应的语法树必定相同 B．最左推导和最右推导对应的语法树可能不同 C．最左推导和最右推导必定相同 D．可能存在两个不同的最左推导，但它们对应的语法树相同 22．正则文法(A)二义性的。 A. 可以是 B. 一定不是 C. 一定是 23．(B)这样一些语言，它们能被确定的有穷自动机识别，但不能用正则表达式表示。 A. 存在 B. 不存在 C. 无法判定是否存在 24．给定文法A→bA | ca，为该文法句子的是(C)

编译原理(清华大学 第2版)课后习题答案

第三章 N=>D=> {0,1,2,3,4,5,6,7,8,9} N=>ND=>NDD L={a |a(0|1|3..|9)n且 n>=1} (0|1|3..|9)n且 n>=1 {ab,} a n b n n>=1 第6题. (1) <表达式> => <项> => <因子> => i (2) <表达式> => <项> => <因子> => (<表达式>) => (<项>) => (<因子>)=>(i) (3) <表达式> => <项> => <项>*<因子> => <因子>*<因子> =i*i (4) <表达式> => <表达式> + <项> => <项>+<项> => <项>*<因子>+<项> => <因子>*<因子>+<项> => <因子>*<因子>+<因子> = i*i+i (5) <表达式> => <表达式>+<项>=><项>+<项> => <因子>+<项>=i+<项> => i+<因子> => i+(<表达式>) => i+(<表达式>+<项>) => i+(<因子>+<因子>) => i+(i+i) (6) <表达式> => <表达式>+<项> => <项>+<项> => <因子>+<项> => i+<项> => i+<项>*<因子> => i+<因子>*<因子> = i+i*i 第7题

第9题 语法树 s s s* s s+a a a 推导: S=>SS*=>SS+S*=>aa+a* 11. 推导:E=>E+T=>E+T*F 语法树: E +T * 短语: T*F E+T*F 直接短语: T*F 句柄: T*F 12．

短语： 直接短语： 句柄： 13.(1)最左推导：S => ABS => aBS =>aSBBS => aBBS => abBS => abbS => abbAa => abbaa 最右推导：S => ABS => ABAa => ABaa => ASBBaa => ASBbaa => ASbbaa => Abbaa => a1b1b2a2a3 (2) 文法：S → ABS S → Aa S →ε A → a B → b (3) 短语：a1 , b1 , b2, a2 , , bb , aa , abbaa, 直接短语： a1 , b1 , b2, a2 , , 句柄：a1 14 (1) S → AB A → aAb | ε B → aBb | ε (2) S → 1S0 S → A A → 0A1 |ε 第四章 1. 1. 构造下列正规式相应的DFA (1)1(0|1)*101 NFA (2) 1(1010*|1(010)*1)*0 NFA

(完整版)编译原理及实现课后习题答案

编译原理及实现课后习题解答 2.1设字母表A={a}，符号串x=aaa，写出下列符号串及其长度：x0,xx,x5 以及A+和A*. x0=(aaa)0=ε| x0|=0 xx=aaaaaa |xx|=6 x5=aaaaaaaaaaaaaaa | x5|=15 A+ =A1∪A2∪ …. ∪A n∪…={a,aa,aaa,aaaa,aaaaa…} A* = A0 ∪A1 ∪A2 ∪…. ∪A n ∪…={ε,a,aa,aaa,aaaa,aaaaa…} 2.2令∑={a，b，c}，又令x=abc，y=b，z=aab，写出如下符号串及它们的长度：xy，xyz，（xy）3 xy=abcb |xy|=4 xyz=abcbaab |xyz|=7 (xy)3=(abcb)3 =abcbabcbabcb | (xy)3 |=12 2.3设有文法G[S]：S∷=SS*|SS+|a，写出符号串aa+a*规范推导，并构造语 法树。 S => SS* => Sa* => SS+a* => Sa+a* => aa+a*

S S S * S S + a a a 2.4 已知文法G[Z]：Z∷=U0∣V1 、U∷=Z1∣1 、V∷=Z0∣0 ,请写出全部由此文法描述的只含有四个符号的句子。 Z=>U0=>Z10=>U010=>1010 Z=>U0=>Z10=>V110=>0110 Z=>V1=>Z01=>U001=>1001 Z=>V1=>Z01=>V101=>0101 2.5已知文法G[S]：S∷=AB A∷=aA︱εB∷=bBc︱bc , 写出该文法描述的语言。 A∷=aA︱ε描述的语言: {a n|n>=0} B∷=bBc︱bc 描述的语言：{b n c n|n>=1} L(G[S])={a n b m c m|n>=0,m>=1} 2.6已知文法E∷=T∣E+T∣E-T 、T∷=F∣T*F∣T/F 、F∷=(E)∣i，写出该文法的开始符号、终结符号集合V T、非终结符号集合V N。 开始符号：E V t={+, - , * , / ,（, ）, i} V n={E , F , T}

最新编译原理小题答案

《编译原理》常见题型 一、填空题 1.编译程序的工作过程一般可以划分为词法分析，语法分析，中间代码生成，代码优化(可省) ，目标代码生成等几个基本阶段。 2.若源程序是用高级语言编写的，目标程序是机器语言程序或汇编程序，则其翻译程序称为编译程序. 3.编译方式与解释方式的根本区别在于是否生成目标代码. 5.对编译程序而言，输入数据是源程序，输出结果是目标程序. 7.若源程序是用高级语言编写的，目标程序是机器语言程序或汇编程序，则其翻译程序称为编译程序。 8.一个典型的编译程序中，不仅包括词法分析、语法分析、中间代码生成、代码优化、目标代码生成等五个部分，还应包括表格处理和出错处理。其中，词法分析器用于识别单词。 10.一个上下文无关文法所含四个组成部分是一组终结符号、一组非终结符号、一个开始符号、一组产生式。 12.产生式是用于定义语法成分的一种书写规则。 13.设G[S]是给定文法，则由文法G所定义的语言L(G)可描述为：L(G)＝{x│S=>*x,x∈VT*} 。 14.设G是一个给定的文法，S是文法的开始符号，如果S * ?x（其中x∈V*），则称x是 文法的一个句型。 15.设G是一个给定的文法，S是文法的开始符号，如果S * ?x(其中x∈V T*)，则称x是文 法的一个句子。 16.扫描器的任务是从源程序中识别出一个个单词符号。 17.语法分析最常用的两类方法是自上而下和自下而上分析法。 18.语法分析的任务是识别给定的终结符串是否为给定文法的句子。 19.递归下降法不允许任一非终结符是直接左递归的。 20.自顶向下的语法分析方法的关键是如何选择候选式的问题。 21.递归下降分析法是自顶向下分析方法。 22.自顶向下的语法分析方法的基本思想是：从文法的开始符号开始，根据给定的输入串并按照文法的产生式一步一步的向下进行直接推导，试图推导出文法的句子，使之与给定的输入串匹配。 23.自底向上的语法分析方法的基本思想是：从给定的终结符串开始，根据文法的规则一步一步的向上进行直接归约，试图归约到文法的开始符号。 24.自底向上的语法分析方法的基本思想是：从输入串入手，利用文法的产生式一步一步地 向上进行直接归约，力求归约到文法的开始符号。 26.在LR（0）分析法的名称中，L的含义是自左向右的扫描输入串，R的含义是最 左归约，0 的含义是向貌似句柄的符号串后查看0个输入符号。 31.终结符只有综合属性，它们由词法分析器提供。