南航计算机考研复试考题编译.pdfVIP

大学

2010年入学考试试题

考试科目：编译原理

说明：答案一律写在答题纸上

一、判断（15分）

1、编译程序是一种语言翻译程序，它将源语言程序翻译成功能等价的目标

语言程序。

2、所谓规则或产生式是指形如α→β或α::β的(α,β)有序对，其中α

是字母表V的正闭包元素,而β是字母表V的闭包元素。

3、设文法G=（V，V，P，S），若P中的每一个规则都是A→aB或A→a，

NT

其中A和B是非符，而a是符，则称此文法G为正规文法或3型文法。

4、实用文法中不得含有形如U→U的有害规则，也不得含有由不可达或不可

终止的非符所构成的多余规则。

5、对任意给定的一个正规式R，都可以将它转换为与之功能等价的正规文法，

或与之功能等价的有穷自动机。

6、LEX是一个用于构造各种各样语言的词法分析程序；YACC是一个用于构

造各种各样语言的语法分析程序。

7、假设现有五元组表示的有穷自动机M=（K，V，F，S，Z），若M是NFA，

则S表示初态，且S具有唯一性，它是状态集K的一个元素。

8、算符优先分析方法和LR分析方法都是自下而上的分析方法，它们的分析

过程实际上就是规范归约过程。

9、LR(0)项目集规范族中的项目由两部分构成，一部分是心，即原来的LR(1)

项目，另一部分是向前有哪些信誉好的足球投注网站符号集。

10、所谓优化实质上是对代码进行等价变换，使得变换后的代码运行结果与

变换前的代码运行结果相同，但运行速度或占用的空间加大。常用的优化技

术有删除多余运算、代码外提、强度削弱、变换循环控制条件、合并已知变量与

复写等。

11、对一个不包含空规则的算符文法，如果文法中的任意两个符构成的

符号对之间最多只有大于、小于和等于三种优先关系中的一种成立，则称该算符

文法为算符优先文法。

12、目标程序运行时的动态数据区分为堆区和栈区，它用于存放可变数

据以及管理过程活动的控制信息。

13、在语法分析过程中，随着分析的步步进展，根据每个规则所对应的语义

子程序或语义动作进行翻译的办法，称为语法制导翻译，它被现代很多编译程序

所采用。

14、可归前缀本身就是活前缀，它是包含句柄在内的活前缀。

15、符号表用来存放语言程序中出现的有关标识符的属性信息，这些信息集

中反映了标识符的语义特征属性。

二、将表达式A:=B*（C-D）/D：(共9分)

1、翻译成逆波兰式的中间代码形式。(2分)

2、翻译成四元式的中间代码形式。(4分)

3、将译成的四元式用DAG表示。(3分)

三、现有文法G[E]：(共12分)

E→E+T|E-T|T

T→T*F|T/F|F

F→i|(E)

4、证明：F+T*(E)是文法的一个句型。(3分)

5、构造句型F+T*(E)的语法推导树。(3分)

6、该句型所有短语、直接短语和句柄。(6分)

*

四、给定正规式R=d(a|bc)d，要求：(12分)

1、构造对应的NFAM状态图，使得L(M)=L(R)。(4分)

2、将所得NFAM确定化和最小化。