当前位置：搜档网 › 编译原理练习题答案[1]1汇总

编译原理练习题答案[1]1汇总

一、填空题:

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. 扫描遍____指编译程序对源程序或中间代码程序从头到尾扫描一次。

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 。

答：一个基本块的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

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

极小化后：

1．Z→C S

2．C→if E then 3．S→A＝E 4．E→E∨A 5．E→A

6．A→i 其中：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)重写三地址代码如下：

11 a

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

《编译原理》模拟期末试题汇总 6套,含答案

《编译原理》模拟试题一一、是非题（请在括号内，正确的划√，错误的划×）（每个2分，共20分） 1．计算机高级语言翻译成低级语言只有解释一种方式。(×) 2．在编译中进行语法检查的目的是为了发现程序中所有错误。(×) 3．甲机上的某编译程序在乙机上能直接使用的必要条件是甲机和乙机的操作系统功能完全相同。 (√ ) 4．正则文法其产生式为 A->a ， A->Bb, A,B∈VN ， a 、b∈VT 。 (×) 5．每个文法都能改写为 LL(1) 文法。 (√) 6．递归下降法允许任一非终极符是直接左递归的。 (√) 7．算符优先关系表不一定存在对应的优先函数。 (×) 8．自底而上语法分析方法的主要问题是候选式的选择。 (×) 9．LR 法是自顶向下语法分析方法。 (×) 10．简单优先文法允许任意两个产生式具有相同右部。 (×) 二、选择题(请在前括号内选择最确切的一项作为答案划一个勾，多划按错论)(每个4分，共40分) 1．一个编译程序中，不仅包含词法分析，_____，中间代码生成，代码优化，目标代码生成等五个部分。 A．( ) 语法分析B．( )文法分析C．( )语言分析D．( )解释分析 2．词法分析器用于识别_____。 A．( ) 字符串B．( )语句 C．( )单词 D．( )标识符 3．语法分析器则可以发现源程序中的_____。 A．( ) 语义错误 B．( ) 语法和语义错误 C．( ) 错误并校正D．( ) 语法错误 4．下面关于解释程序的描述正确的是_____。

(1) 解释程序的特点是处理程序时不产生目标代码 (2) 解释程序适用于 COBOL 和 FORTRAN 语言 (3) 解释程序是为打开编译程序技术的僵局而开发的 A．( ) (1)(2) B．( ) (1)C．( ) (1)(2)(3) D．( ) (2)(3) 5．解释程序处理语言时 , 大多数采用的是_____方法。 A．( ) 源程序命令被逐个直接解释执行 B．( ) 先将源程序转化为中间代码 , 再解释执行 C．( ) 先将源程序解释转化为目标程序 , 再执行 D．( ) 以上方法都可以 6．编译过程中 , 语法分析器的任务就是_____。 (1) 分析单词是怎样构成的 (2) 分析单词串是如何构成语句和说明的 (3) 分析语句和说明是如何构成程序的 (4) 分析程序的结构 A．( ) (2)(3) B．( ) (2)(3)(4) C．( ) (1)(2)(3) D．( ) (1)(2)(3)(4) 7．编译程序是一种_____。 A. ( ) 汇编程序B．( ) 翻译程序 C．( ) 解释程序 D．( ) 目标程序 8．文法 G 所描述的语言是_____的集合。 A. ( ) 文法 G 的字母表 V 中所有符号组成的符号串 B．( ) 文法 G 的字母表 V 的闭包 V* 中的所有符号串 C．( ) 由文法的开始符号推出的所有终极符串 D. ( ) 由文法的开始符号推出的所有符号串 9．文法分为四种类型，即0型、1型、2型、3型。其中3型文法是_____。 A. ( ) 短语文法 B．( ) 正则文法 C．( ) 上下文有关文法 D．( ) 上下文无关文法 10．一个上下文无关文法 G 包括四个组成部分，它们是：一组非终结符号，一组终结符号，一个开始符号，以及一组 _____。 A．( ) 句子B．( ) 句型 C．( ) 单词 D．( ) 产生式三、填空题(每空1分，共10分)

编译原理试题

中间语言与语法制导翻译重点与难点重点：语法制导翻译的基本思想，属性文法，翻译模式，说明语句的翻译方案。三地址码，各种语句的目标代码结构、属性文法与翻译模式。难点：属性的意义，对综合属性，继承属性，固有属性的理解，属性计算，怎么通过属性来表达翻译。布尔表达式的翻译，对各种语句的目标代码结构、属性文法与翻译模式的理解。基本要求掌握语法制导翻译的基本思想，属性文法，综合属性，继承属性，固有属性，属性计算，S_属性文法，L_属性文法，说明语句的翻译方案，翻译模式、属性文法的实现掌握中间语言与语义分析的基本概念；熟练掌握语法（结构）树、三地址代码、赋值与控制语句的翻译、说明语句的翻译；掌握组合数据说明的翻译、过程调用翻译。例题解析例1 给定文法 E --> T { R.i := T.p } R { E.p := R.s } R --> addop T { R1.i := mknode( addop.val, R.i, T.p ) } R { R.s := R1.s } R --> { R.s := R1.s } T --> ( E ) { T.p := E.p } T --> id { T.p := mkleaf( id, id.entry ) } T --> num { T.p := mkleaf( num, num.val ) } (1) 指出文法中的各非终结符具有哪些综合属性和哪些继承属性 ⑵画出按本翻译模式处理表达式 a + 20 + ( b - 10 ) 时所生成的语法树【解】 (1)E的综合属性 p，R的继承属性i，综合属性s；T的综合属性p (2) 处理表达式 a + 20 + ( b - 10 ) 时所生成的语法树如下 + （NUM, 20） - ( ID, b) (NUM, 10) 例2 定义一个计算器的属性文法,完成一个输入表达式值的计算和显示, 【解】计算器的文法 L → E

王汝传编译原理习题答案

《编译原理》习题答案：第一次： 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．一个正规语言只能对应(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

编译原理试题集33493

第一章引论一.单项选择题 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. Lex是语法分析自动生成器 d. 解释程序属于编译程序 7. 目标代码生成阶段所生成的目标代码的形式不可能是____。 a. 绝对指令代码 b. 可充定位的指令代码。 c. 汇编指令代码 d. 三地址代码 8. 语义错误是指源程序中不符合语义规则的错误，不包括：____ a. 非法字符错误 b. 类型不一致错误。 c. 作用域错误 d. 说明错误

编译原理试题(卷)汇总-编译原理期末试题(卷)(8套含答案解析-大题集)

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

精品文档第二章 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．编译程序首先要识别出源程序中每个，然后再分析每个并翻译其意义。单词，句子 2．编译器常用的语法分析方法有和两种。自底向上，自顶向下 2．通常把编译过程分为分析与综合两大阶段。词法、语法和语义分析是对源程序的分析，中间代码生成、代码优化与目标代码的生成则是对源程序的综合。前端，后端 4．程序设计语言的发展带来了日渐多变的

运行时存储管理方案，主要分为两大类，即方案和分配方案。静态存储分配，动态存储 5．对编译程序而言，输入数据是，输出结果是。源程序，目标程序 6．文法G包括四个组成部分：一组终结符号，一组非终结符号，一组，以及一个开始符号。产生式 7．文法按产生式的形式分为四种类型，它们是：0型文法，又称短语文法；1型文法，又称上下文有关文法；2型文法，又称；3型文法，又称。上下文无关文法，正规文法

8．最右推导称为，由规范推导产生的句型称为规范句型。规范推导 9．设G是一个文法，S是它的开始符号，如果S=>*α，则称α是一个。仅由终结符号组成的句型是一个。句型，句子 10 对于一个文法G而言，如果L(G)中存在某个句子对应两棵不同，那么该文法就称为是二义的。语法树 11．通常程序设计语言的单词符号分为五种：基本字、、常数、算符、界限符。

标识符 12．在自底向上分析法中，LR分析法把“可归约串”定义为。句柄 13．编译中常用的中间代码形式有逆波兰式、三元式、和四元式等。树代码 14．对中间代码优化按涉及的范围分为，和全局优化。局部优化，循环优化 15．局部优化主要包括、利用公共子表达式和删除无用赋值等内容。合并已知量 16．为了构造不带回溯的递归下降分析程

编译原理习题解答

第二章：习题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 语法树见下图:

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

第一章 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、编译程序工作过程中，第一段输入就是，最后阶段得输出为程序。

编译原理试题

1997年编译原理试题 1．（10分）某操作系统下合法的文件名为 device:name.extension 其中第一部分（device:）和第三部分（.extension）可缺省，若device, name和extension都是字母串，长度不限，但至少为1，画出识别这种文件名的确定有限自动机。 2．（20分） a. 下面的二义文法描述命题演算公式，为它写一个等价的非二义文法。 S—> S and S | S or S | not S | p | q | (S) b. 下面文法是否为LL(1)文法？说明理由。 S—> A B | P Q x A—> x y B—> b c P—> d P | εQ—> a Q | ε 3．（10分）某些语言允许给出名字表的一个属性表，也允许声明嵌在另一个声明里面，下面文法抽象这个问题。 D —> attrlist namelist | attrlist (D) namelist —> id, namelist | id attrlist —> A attrlist | A A —> decimal | fixed | float | real D —> attrlist namelist的含义是：在namelist中的任何名字有attrlist 中给出的所有属性。D—> attrlist (D) 的含义是：在括号中的声明提到的所有名字有attrlist 中给出的所有属性，而不管声明嵌套多少层。写一个翻译方案，它将每个名字的属性个数填入符号表。为简单起见，若属性重复出现，则重复计数。4．（10分）把表达式 -(a+b)*(c+d)+(a+b+c) 翻译成四元式。 5．（10分）由于文法二义引起的LR（1）分析动作冲突，可以依据消除二义的规则而得到LR（1）分析表，根据此表可以正确识别输入串是否为相应语言的句子。对于非二义非LR（1）文法引起的LR（1）分析动作的冲突，是否也可以依据什么规则来消除LR（1）分析动作的冲突而得到LR（1）分析表，并且根据此表识别相应语言的句子？若可以，你是否可以给出这样的规则？ 6．（5分）UNIX 下的C编译命令cc的选择项g和O的解释如下，其中dbx 的解释是“dbx is an utility for source-level debugging and execution of programs written in C”。试说明为什么用了选择项g后，选择项O便被忽略。 -g Produce additional symbol table information for dbx(1) and dbxtool(1) and pass -lg option to ld(1) (so as to include the g library, that is:

编译原理试题汇总

一、选择题（每个选择题 2 分，共 20 分） 1 ．文法 G 产生的⑴ 的全体是该文法描述的语言。 A ．句型 B. 终结符集 C. 非终结符集 D. 句子 2 ．若文法 G 定义的语言是无限集，则文法必然是⑵ ： A ．递归的 B 前后文无关的 C 二义性的 D 无二义性的 3 ． Chomsky 定义的四种形式语言文法中， 0 型文法又称为⑶ 文法； 1 型文法又称为⑷ 文法； 2 型语言可由⑸ 识别。 A ．短语结构文法 B 前后文无关文法 C 前后文有关文法 D 正规文法 E 图灵机 F 有限自动机 G 下推自动机 4 ．一个文法所描述的语言是⑹ ；描述一个语言的文法是⑺ 。 A ．唯一的 B 不唯一的 C 可能唯一，好可能不唯一 5 ．数组的内情向量中肯定不含有数组的⑻ 的信息 A．维数 B.类型 C.维上下界 D.各维的界差 6 ．在下述的编译方法中，自底向上的方法有⑼ ，自顶向下的分析方法有⑽ 。 ①简单优先分析②算符优先分析③递归下降分析④预测分析技术⑤LR（K）分析 ⑥ SLR（k）分析⑦ LL（k）分析⑧LALR（K）分析 A.③④⑦ B. ③④⑧ C.①②⑧ D.③④⑤⑥⑦ E.①②⑤⑥⑦ F. ①②⑤⑥⑧ 二、简答题（每小题 5 分，共 20 分） 1 ． LL （ 1 ）分析法对文法有哪些要求？ 2 ．常见的存储分配策略有几种？它们都适合于什么性质的语言？ 3 ．常见循环优化都有哪些项目？ 4 ．什么是活动记录？它主要由哪些内容构成？五、（ 12 分）已给文法 G[S] ：S → SaP | Sf | P P → qbP | q 将 G[S] 改造成 LL （ 1 ）文法，并给出 LL （ 1 ）分析表。七、（ 8 分）将下面的条件语句表示成逆波兰式和四元式序列： if a>b then x:=a+b*c else x:=b-a; 八、（ 8 分）给定基本块： A:=3*5 B:=E+F C:=A+12 D:=E+F A:=D+12 C:=C+1 E:=E+F 假定出基本块后，只有 A 、 C 、 E 是活跃的，给出用 DAG 图完成优化后的代码序列。参考答案：一、⑴ D ⑵ A ⑶ A ⑷ C ⑸ G. ⑹ A ⑺ B ⑻ A ⑼ F ⑽ A 二、 1 ．对于 G 中的每个产生式A →γ 1 | γ 2 | … | γ m ，其各候选式均应满足：（1）不同的候选式不能推出以同一终结符号打头的符号串，即 FIRST( γ i ) ∩ FIRST( γ j )= φ（1 ≤ i ，j ≤ m ；i ≠ j ）

编译原理复习题

程序设计语言与编译复习题一、是非题（请在括号内，正确的划√，错误的划×） 1．词法分析作为单独的一遍来处理较好。(× ) 2．规范归约和规范推导是互逆的两个过程。(×) 3．正规文法产生的语言都可以用上下文无关文法来描述。(× ) 4．编译程序与具体的机器有关,与具体的语言无关。(× ) 5．一张转换图只包含有限个状态，其中有一个被认为是初态，最多只有一个终态。(√ ) 6．目标代码生成时，应考虑如何充分利用计算机的寄存器的问题。(× ) 7．逆波兰法表示的表达式亦称前缀式。(√) 8．如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是二义的。(√ ) 9．对于数据空间的存贮分配，FORTRAN采用动态贮存分配策略。(× ) 10．甲机上的某编译程序在乙机上能直接使用的必要条件是甲机和乙机的操作系统功能完全相同。(×) 11．递归下降分析法是自顶向下分析方法。(√ ) 12．产生式是用于定义词法成分的一种书写规则。(× ) 13．符号表中的信息栏中登记了每个名字的属性和特征等有关信息，如类型、种属、所占单元大小、地址等等。(×) 14．程序语言的语言处理程序是一种应用软件。(× ) 15．解释程序适用于COBOL 和FORTRAN 语言。(×) 16．编译程序是对高级语言程序的解释执行。(× )

17．语法分析时必须先消除文法中的左递归。(×) 18．逆波兰表示法表示表达式时无须使用括号。(√ ) 19．仅考虑一个基本块，不能确定一个赋值是否真是无用的。(√) 20．数组元素的地址计算与数组的存储方式有关。(×) 21．静态数组的存储空间可以在编译时确定。(×) 22．进行代码优化时应着重考虑循环的代码优化，这对提高目标代码的效率将起更大作用。(×) 23．两个正规集相等的必要条件是他们对应的正规式等价。(× ) 24．一个语义子程序描述了一个文法所对应的翻译工作。(× ) 25．计算机高级语言翻译成低级语言只有解释一种方式。(×) 26．在编译中进行语法检查的目的是为了发现程序中所有错误。(× ) 27．正则文法其产生式为A->a ，A->Bb, A,B∈V N，a 、b∈V T。(× ) 28．“ 用高级语言书写的源程序都必须通过编译,产生目标代码后才能投入运行”这种说法。(× ) 29．在程序中标识符的出现仅为使用性的。(× ) 二、选择题 1．词法分析器用于识别_____。 A．( ) 字符串B．( )语句 C．( )单词D．( )标识符 2．文法分为四种类型，即0型、1型、2型、3型。其中0型文法是_____。

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

第一章 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．一个正规语言只能对应( 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)

编译原理试题及答案3

编译原理复习题一、填空题： 1、编译方式与解释方式的根本区别在于（是否生成目标代码）。 2、对编译程序而言，输入数据是（源程序），输出结果是（目标程序）。 3、如果编译程序生成的目标程序是机器代码程序，则源程序的执行分为两大阶段：（编译阶段）和（运行阶段）。 4、如果编译程序生成的目标程序是汇编语言程序，则源程序的执行分成三个阶段：（编译阶段）、（汇编阶段）和（运行阶段）。 5、自顶向下语法分析方法会遇到的主要问题有（回溯）和（（左递归带来的）无限循环）。 6、LL(k)分析法中，第一个L的含义是（从左到右进行分析），第二个L的含义是（每次进行最左推导），“k”的含义是（向输入串中查看K个输入符号）。 7、LL(1)分析法中，第一个L的含义是（从左到右进行分析），第二个L的含义是（每次进行最左推导），“1”的含义是（向输入串中查看1个输入符号）。 8、自顶向下语法分析方法的基本思想是：从（识别符号）出发，不断建立（直接推导），试图构造一个推导序列，最终由它推导出与输入符号相同的（符号串）。 9、自底向上语法分析方法的基本思想是：从待输入的符号串开始，利用文法的规则步步向上进行（直接归约），试图（归约）到文法的（识别符号|开始符号）。 10、LR(0)分析法的名字中，“L”的含义是（从左到右进行分析），“R”的含义是（采用最右推导的逆过程---最左归约），“0”的含义是（向貌似句柄的符号串后查看0个输入符号）。 11、LR(1)分析法的名字中，“L”的含义是（从左到右进行分析），“R”的含义是（采用最右推导的逆过程---最左归约），“1”的含义是（向貌似句柄的符号串后查看1个输入符号）。 12、SLR(1)分析法的名字中，“S”的含义是（简单的），“L”的含义是（从左到右进行分析），“R”的含义是（采用最右推导的逆过程---最左归约），“1”的含义是（向貌似句柄的符号串后查看1个输入符号）。 13、在编译过程中，常见的中间语言形式有（逆波兰表示）、（三元式）、（四元式）和（树形表示）。 14、在编译程序中安排中间代码生成的目的是（便于代码优化）和（便于目标程序的移植）。 15、表达式-a+b*(-c+d)的逆波兰表示为（a-bc-d+*+ ）。 16、表达式a+b*(c+d/e)的逆波兰表示为（abcde/+*+ ）。 17、表达式a:=a+b*c↑(d/e)/f的逆波兰表示为（aabcde/↑*f/+:= ）。 18、文法符号的属性有（继承属性）和（综合属性）两种。 19、一个文法符号的继承属性是通过语法树中它的（兄弟结点与父）结点的相应文法符号的属性来计算的。 20、一个文法符号的综合属性是通过语法树中它的（子）结点的属性来计算的。

编译原理练习题答案[1]1汇总

《编译原理》模拟期末试题汇总 6套,含答案

编译原理试题

王汝传编译原理习题答案

最新编译原理试题汇总+编译原理期末试题(8套含答案+大题集)

编译原理复习题及答案

编译原理试题集33493

编译原理试题(卷)汇总-编译原理期末试题(卷)(8套含答案解析-大题集)

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

编译原理试题库

编译原理习题解答

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

编译原理试题

编译原理试题汇总

编译原理复习题

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

编译原理复习题及答案

编译原理试题及答案3

相关文档

最新文档