编译原理期末试题(2003年---2004年第二学期) (A卷)

一、选择题（本大题共20小题，每小题1分，共20分）

1、汇编程序是将______翻译成______；编译程序是将_______翻译成__________。 a、汇编语言程序 b、机器语言程序 c、高级语言程序 d汇编语言或机器语言程序

2、描述一个语言的文法是___________。

a、唯一的 b、不唯一的 c、个数有限的

3、生成非0开头的正偶数集的文法是______________。 a、Z::=ABC c、Z::=ABC|2|4|6|8 C::=0|2|4|6|8 C::=0|2|4|6|8 B::=BA|B0|ε B::=BA|B0|0 A::=1|2|3|4|5|6|7|8|9 A::=1|2|3|4|5|6|7|8|9 b、Z::=ABC d、Z::=ABC|2|4|6|8 C::=0|2|4|6|8 C::=0|2|4|6|8 B::=BA|B0|0 B::=BA|B0|ε A::=1|2|3|4|5|6|7|8|9 A::=1|2|3|4|5|6|7|8|9 4、设有文法G[I]： I→I0|I1|I a|Ic|a|b|c

下列符号串中是该文法的句子的有___________________。 ①ab0 ②a0c01 ③aaa ④bc10 可选项有

a、① b、②③④ c、③④ d、①②③④ 5、现有前缀表示的表达式文法G1：

E::=-EE E::=-E E::=a|b|c

则文法的句子—a-bc的所有可能语法树有______棵。

a、1 b、2 c、3 d、4 6、一个上下文无关文法G包括四个组成部分依次为：一组_____、一个_____、一组_____、一组______。

a、字符串 b、字母数字串 c、产生式 d、结束符号 e、开始符号 f、文法 g、非终结符号 h、终结符号

7、语法分析的常用方法是_________：

①自顶向下 ②自底向上 ③自左向右 ④自右向左 可选项有：

a、①②③④ b、①② c、③④ d、①②③ 8、下列文法__________二义文法

E::=EiT|T T::=T+F|iF|F F::=E*|(

可选项有： a、是 b、不是 c、无法判断。 9、素短语是指_______的短语。 ①至少包含一个符号 ②至少包含一个非终结符号 ③至少包含一个终结符号

④除自身外不再包含其它终结符号 ⑤除自身外不再包含其它非终结符号 ⑥除自身外不再包含其它短语

⑦除自身外不再包含其它素短语

可选项有：

a、①④ b、①⑤ c、①⑥ d、②④ e、③⑤ f、③⑦g、②⑦ 10、LR（K）文法是_________。

a、从左到右分析，共经过K步的一种编译方法。

b、从左到右分析，每次向前预测K步的一种编译方法。

c、从左到右分析，每次向貌似句柄的符号串后看K个输入符号的一种编译方法。 d、从左到右分析，每次走K步的一种编译方法。 11、在编译中产生语法树是为了____________。

a、语法分析 b、语义分析 c、词法分析 d、产生目标代码 12、文法的二义性和语言的二义性是两个____________概念。 a、不同 b、相同 c、无法判断

13、下述正规表达式中________与(a*+b)*(c+d)等价。 ① a*（c+d）+b（c+d） ② a*（c+d）*+b（c+d）* ③ a*（c+d）+b*（c+d）

④ （a+b）*c+（a+b）*d ⑤ （a*+b）*c+（a*+b）*d

可选项有:a、① b、② c、③ d、④ e、⑤ f、④⑤ g、③④⑤

14、_______这样的语言，他们能被确定的有限自动机识别，但不能用正规表达式表示： a、存在 b、不存在 c、无法判定是否存在

15、LL（K）文法________二义性的。

a、都是 b、都不是 c、不一定都是

16、下面的文法是__________。S::=aAa|aBb|bAb|bBa A::=x B::=x

可选项有：a、LR（1）文法 b、LALR（1）文法 c、都不是 d、a和b 17、编译过程中，比较常见的中间语言有___________。 ①波兰表示 ②逆波兰表示 ③三元式 ④四元式

⑤树形表示

可选项有：a、①③④ b、②③④ c、③④①⑤ d、②③④⑤ 18、-a-（b*c/（c-d）+（-b）*a）的逆波兰表示是___________。 a、abc*cd-b-a*+/-- b、a-bc*cd-b-a*+/-

c、a-bc*cd-/b-a*+- d、a-bc*/cd-b-a*+-

19、在编译程序中安排中间代码生成的目的是_______________。 ①便于进行存储空间的组织 ②利于目标代码优化 ③利于编译程序的移植 ④利于目标代码的移植

⑤利于提高目标代码的质量

可选项有：

a、②④ b、①②③ c、③④① d、②③④⑤ 20、代码优化的主要目标是_____________。

①如何提高目标程序的运行速度 ②如何减少目标程序运行所需的空间。 ③如何协调①和②

④如何使生成的目标代码尽可能简短 可选项有：

a、②④ b、①②③ c、③④① d、②③④ 二、简答题：（每小题5分，共35分）

1、 证明下面文法是二义性的。S::=ibtSeS|ibtS|a

2、 现有文法S::=SaA|A A::=AbB|B B::=cSd|e

请证实是文法的一个句型，并写出该句型的所有短语、素短语以及句柄。 3、 求出下列文法所产生语言对应的正规式。

S::=bS|aA A::=aA|bB B::=aA|bC|b C::=bS|aA

4、 将表达式((a*d+c)/d+e)*f+g分别表示三元式、四元式、逆波兰式序列 5、 消除下列文法的左递归。

S::=SaP|Sf|P P::=QbP|Q Q::=cSd|e 6、 给出与下图的NFA等价的正规文法。

ε S2 S3 ε a S1 b S0

7、 试对基本块应用DAG进行优化，写出优化后的四元式序列。 三、问答题：

1、 已知文法G A::=aABe|a B::=Bb|d

（1） 给出与上述文法等价的LL（1）文法G’。 （2） 构造预测分析表并给出输入串aade#分析过程。（10分）

2、 设已给文法G: E::=E+T E::=T T::=T*F T::=F F::=P↑F F::=P P::=(E) P::=i 构造此文法的算符优先矩阵。（10分） 3、 有正规式b*abb*(abb*)*

（1） 构造该正规式所对应的NFA（画出状态转换图）。 （2） 将所求的NFA确定化。（画出确定化的状态转换图）。

（3） 将所求的NFA最小化。（画出最小化后的状态转换图）。（10分）

4、 若有文法G（S）的产生式如下：S::=L=R S::=R L::=*R L::=i R::=L,构造识别所有项目集规范族的DFA。（15分）

（1） 判断该文法是否是LR（0）文法，说明理由。 （2） 判断该文法是否是SLR（1）文法，说明理由。 （3） 判断该文法是否是LR（1）文法，说明理由。 （4） 判断该文法是否是LALR（1）文法，说明理由。

装 订 线

华中科技大学武昌分校

《编译原理》试卷A

专业班级：_________学号：_________姓名：__________总分

一、单项选择题(共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．把高级语言翻译成机器语言

C．把中间代码变换成依赖具体机器的目标代码 D．把汇编语言翻译成机器语言

二、填空题（本大题共5小题，每小题2分）（题分 10分）

1．编译程序首先要识别出源程序中每个( )，然后再分析每个( )并翻译其意义。

2．编译器常用的语法分析方法有( )和( )两种。 3．通常把编译过程分为分析前端与综合后端两大阶段。词法、语法和语义分析是对源程序的( )，中间代码生成、代码优化与目标代码的生成则是对源程序的( )。 4．程序设计语言的发展带来了日渐多变的运行时存储管理方案，主要分为两大类，即：( )方案和( )方案。

5．对编译程序而言，输入数据是( )，输出结果是( )。

三、名词解释题(共5小题，每小题4分) （题分 20分） 1．词法分析 2．LL(1)文法 3．语法树

4．LR(0)分析器 5．语言和文法

得分 得分 四、简答题(共4小题，每小题5分) （题分 20分）

1．编译程序和高级语言有什么区别? 2．编译程序的工作分为那几个阶段? 3．简述自下而上的分析方法。 4．简述代码优化的目的和意义。

得分

五、综合应用题(共3小题，每小题10分) （题分 30分）

1．证明下述文法G：

S?aSbS|aS|d

是二义性文法。

得分 2．对于文法G[S]：S?AB，A?Aa|bB，B?a|Sb求句型baSb的全部短语、直接短语和句柄？

句型baSb的语法树如图五(2)所示。

A S

B b

B S b

a

图五(2) 句型baSb的的语法树

3．设有非确定的有自限动机NFA M=({A，B，C}，{0，1}，?，{A}，{C})，其中： ? (A，0)={C} ? (A，1)={A，B} ? (B，1)={C} ? (C，1)={C}。请画出状态转换距阵和状态转换图。

参考答案

一、单项选择题(共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．把高级语言翻译成机器语言

C．把中间代码变换成依赖具体机器的目标代码 D．把汇编语言翻译成机器语言

二、填空题（本大题共5小题，每小题2分，共10分）

1．编译程序首先要识别出源程序中每个(单词)，然后再分析每个(句子)并翻译其意义。 2．编译器常用的语法分析方法有(自底向上)和(自顶向下)两种。

3．通常把编译过程分为分析前端与综合后端两大阶段。词法、语法和语义分析是对源程序的(分析)，中间代码生成、代码优化与目标代码的生成则是对源程序的(综合)。

4．程序设计语言的发展带来了日渐多变的运行时存储管理方案，主要分为两大类，即(静态存储分配)方案和(动态存储分配)方案。

5．对编译程序而言，输入数据是(源程序)，输出结果是(目标程序)。

三、名词解释题(共5小题，每小题4分，共20分)

1．词法分析

词法分析的主要任务是从左向右扫描每行源程序的符号，按照词法规则 从构成源程序的字符串中识别出一个个具有独立意义的最小语法单位， 并转换成统一的内部表示(token)，送给语法分析程序。 2．LL(1)文法

若文法的任何两个产生式A ? ? | ?都满足下面两个条件： （1）FIRST(? ) ? FIRST(? ) = ?；

（2）若? ?* ? ，那么FIRST(? ) ? FOLLOW( A ) = ?。

我们把满足这两个条件的文法叫做LL(1)文法，其中的第一个L代表从左 向右扫描输入，第二个L表示产生最左推导，1代表在决定分析器的每步 动作时向前看一个输入符号。除了没有公共左因子外，LL(1)文法还有一 些明显的性质，它不是二义的，也不含左递归。

3．语法树

句子的树结构表示法称为语法树(语法分析树或语法推导树)。

给定文法G=(VN，VT，P，S)，对于G的任何句型都能构造与之关联的 语法树。这棵树具有下列特征： (1)根节点的标记是开始符号S。

(2)每个节点的标记都是V中的一个符号。 (3)若一棵子树的根节点为A，且其所有直接子孙的标记从左向右的排列 次序为A1A2…AR，那么A?A1A2…AR一定是P中的一条产生式。 (4)若一标记为A的节点至少有一个除它以外的子孙，则A?VN。 (5)若树的所有叶节点上的标记从左到右排列为字符串w，则w是文法G 的句型；若w中仅含终结符号，则w为文法G所产生的句子。 4．LR(0)分析器

所谓LR(0)分析，是指从左至右扫描和自底向上的语法分析，且在分析的 每一步，只须根据分析栈当前已移进和归约出的全部文法符号，并至多再 向前查看0个输入符号，就能确定相对于某一产生式左部符号的句柄是否 已在分析栈的顶部形成，从而也就可以确定当前所应采取的分析动作 (是 移进还是按某一产生式进行归约等)。

5．语言和文法

文法就是语言结构的定义和描述，是有穷非空的产生式集合。 文法G定义为四元组的形式：

G=(VN，VT，P，S)

其中：VN 是非空有穷集合，称为非终结符号集合；VT 是非空有穷集合， 称为终结符号集合；P是产生式的集合(非空)；S是开始符号(或识别符号)。 这里，VN∩VT=?，S?VN。V=VN∪VT，称为文法G的字母表，它是出现 文法产生式中的一切符号的集合。

文法G所描述的语言用L(G)表示，它由文法G所产生的全部句子组成，即

L(G)={x| S?*x，其中S为文法开始符号，且x?VT } 简单的说，文法描述的语言是该文法一切句子的集合。

?

四、简答题(共4小题，每小题5分，共20分)

1．编译程序和高级语言有什么区别?

用汇编语言或高级语言编写的程序，必须先送入计算机，经过转换成用机器 语言表示的目标程序（这个过程即编译），才能由计算机执行。执行转换过程 的程序叫编译程序。汇编程序是指没有编译过的汇编语言源文件。编译程序转 换过的叫目标程序，也就是机器语言。

编译程序的工作情况有三种：汇编型、解释型和编译型。汇编型编译程序用来 将汇编语言编写的程序，按照一一对应的关系，转换成用机器语言表示的程序。 解释型编译程序将高级语言程序的一个语句，先解释成为一组机器语言的指令， 然后立即执行，执行完了，取下一组语句解释和执行，如此继续到完成一个程序 止。用解释型编译程序，执行速度很慢，但可以进行人和计算机的\对话\，随时

可以修改高级语言的程序。BASIC语言就是解释型高级语言。编译型编译程序将 级语言编写的程序，一次就会部翻译成机器语言表示的程序，而且过程进行很快， 在过程中，不能进行人机对话修改。FORTRAN语言就是编译型高级语言。 2．编译程序的工作分为那几个阶段?

词法分析、语法分析和语义分析是对源程序进行的分析(称为编译程序的前端)， 而中间代码生成、代码优化和代码生成三个阶段合称为对源程序进行综合(称为 编译程序的后端)，它们从源程序的中间表示建立起和源程序等价的目标程序。 3．简述自下而上的分析方法。

所谓自下而上分析法就是从输入串开始，逐步进行“归约”，直至归约到文法的 开始符号；或者说从语法树的末端开始，步步向上“归约”，直到根节点。 4．简述代码优化的目的和意义。

代码优化是尽量生成“好”的代码的编译阶段。也就是要对程序代码进行 一种等价变换，在保证变换前后代码执行结果相同的前提下，尽量使目 标程序运行时所需要的时间短，同时所占用的存储空间少。

五、综合应用题(共3小题，每小题10分，共30分)

1．证明下述文法G：

S?aSbS|aS|d

是二义性文法。 解：

一个文法，如果存在某个句子有不只一棵语法分析树与之对应，那么称这个 文法是二义性文法。

句子aadbd有两棵语法树。如下图：

由此可知，S?aSbS|aS|d定义的文法是二义性文法。 2．对于文法G[S]：S?AB，A?Aa|bB，B?a|Sb求句型baSb的全部短语、直接短语和句柄？ 句型baSb的语法树如图五(2)所示。

b

A S

B a S d

d a S d

b a

S b S S a S S S d

(1) (2) B S b

a

图五(2) 句型baSb的的语法树

解：

baSb为句型baSb的相对于S的短语，ba为句型baSb的相对于A的短语，Sb为句型baSb的相对于B的短语，且为直接短语，a为句型baSb的相对于B的短语，且为直接短语和句柄。

3．设有非确定的有自限动机NFA M=({A，B，C}，{0，1}，?，{A}，{C})，其中： ? (A，0)={C} ? (A，1)={A，B} ? (B，1)={C} ? (C，1)={C}。请画出状态转换距阵和状态转换图。 解：

状态转换距阵为：

? A B C

状态转换图为：

1 1 AB0 C ? ? 1 A，B C C 1 1 C10 2001年编译原理试题

1．（10分）处于/* 和 */之间的串构成注解，注解中间没有*/。画出接受这种

注解的DFA的状态转换图。 2．（10分）为语言

L ＝ {ambn | 0 ? m ? 2n}（即a的个数不超过b的个数的两倍）

写一个LR（1）文法，不准超过6个产生式。（若超过6个产生式，不给分。若所写文法不是LR（1）文法，最多给5分。） 3．（10分）构造下面文法的LL（1）分析表。 D ? TL

T ? int | real L ? id R

R ? , id R | ? 4．（15分）就下面文法 S ? ( L) | a L ? L ? S | S ? 给出一个语法制导定义，它输出配对括号的个数。 ? 给出一个翻译方案，它输出每个a的嵌套深度。 如句子(a, (a, a) )，第一小题的输出是2，第二小题的输出是1 2 2。 5．（10分）Pascal语言for语句的含义见教材第222页习题7.13。请为该语句设计一种合理的中间代码结构。你可以按第215页图7.17的方式或者第219页图7.19的方式写出你的设计，不需要写产生中间代码的语法制导定义。 6．（5分）一个C语言程序如下：

func(i1,i2,i3) long i1,i2,i3; {

long j1,j2,j3;

printf(\ printf(\}

main() {

long i1,i2,i3; func(i1,i2,i3); }

该程序在某种机器的Linux上的运行结果如下：

Addresses of i1,i2,i3 = 27777775460,27777775464,27777775470 Addresses of j1,j2,j3 = 27777775444,27777775440,27777775434

从上面的结果可以看出，func 函数的3个形式参数的地址依次升高，而3个局部变量的地址依次降低。试说明为什么会有这个区别。

7．（15分）一个C语言程序及其在某种机器linux操作系统上的编译结果如下。根据所生成的汇编程序来解释程序中四个变量的作用域、生存期和置初值方式等方面的区别。

static long aa = 10; short bb = 20;

func() {

static long cc = 30; short dd = 40; }

.file \ .version \gcc2_compiled.: .data

.align 4

.type aa,@object .size aa,4 aa:

.long 10 .globl bb .align 2

.type bb,@object .size bb,2 bb:

.value 20 .align 4

.type cc.2,@object .size cc.2,4 cc.2:

.long 30 .text

.align 4 .globl func

.type func,@function func:

pushl ?p

movl %esp,?p subl $4,%esp

movw $40,-2(?p)

.L1:

leave ret .Lfe1:

.size func,.Lfe1-func .ident \(GNU) egcs-2.91.66 19990314/Linux (egcs-1.1.2 release)\ 8．（10分）C语言是一种类型语言，但它不是强类型语言，因为编译时的类型检查不能保证所接受的程序没有运行时的类型错误。例如，编译时的类型检查一般不能保证运行时没有数组越界。请你再举一个这样的例子说明C语言不是强类型语言。 9．（10分）如果在A机器上我们有C语言编译器CCA，也有它的源码SA（用C语言写成）。如何利用它通过尽量少的工作来得到B机器的C语言编译器CCB。 10．（5分）表达式(?x.(?yz.(x + y) + z) 3) 4 5和(?x.(?yz.(x + y) + z) 3 5) 4有同样的结果。在抽象机FAM上，哪一个表达式对应的目标代码的执行效率高？为什么？

2001年编译原理试题参考答案

1．

others start 1 / 2 * 2 * others 4 *

/ 5

2．LR（1）文法 S ? AB | aABb A ? aaAb | ? B ? Bb | ?

3． int D D?TL T T?int L R

LR（1）文法 S ? AB A ? aaAb | ab | ? B ? Bb | ?

id

二义文法 S ? AASb | ? A ? a | ?

real

D?TL T?real

, $

L?id R

R ?, id R R ? ?

4． S? ? S print(S.num) S ? (L) S.num := L.num +1 S ? a S.num := 0 L ? L1,S L.num := L1.num + S.num L ? S L.num := S.num S? ? {S.depth := 0} S S ? {L.depth := S.depth +1} (L) S ? a {print(S.depth)} L ? {L1.depth := L.depth} L1, {S.depth := L.depth} S L ? { S.depth := L.depth} S

5． t1 := initial t2 := final if t1 > t2 goto L1 v := t1 L2: stmt if v = t2 goto L1 v := v + 1 goto L2 L1:

6．由于实参表达式是反序进入活动记录，而局部变量是顺序在活动记录中分配。

7．aa是静态外部变量，而bb是外部变量，它们都分配在静态数据区（由.data伪指令开始），但是bb由伪指令.globl指明为全局的，用来解决其它文件中对bb的外部引用，而aa只能由本文件引用。cc是静态局部变量，同aa和bb一样，它的生存期是整个程序并分配在静态数据区。由于cc在源程序中的作用域是函数func的体，而在目标文件中，它的作用域至少已是整个文件了，为避免同源文件中外部变量和其它函数的静态局部变量的名字冲突，所以要对它进行改名，成了cc.2。由于cc不是全局的，因此cc.2前面没有伪指令.globl。dd是自动变量，其作用域是函数func的体，其生存期是该函数激活期间，因此它分配在栈区，并且置初值是用运行时的赋值来实现。

8．例如联合体的类型检查一般也不可能在编译时完成，虽然下面例子是可静态判断类型错误的。 union U { int u1; int *u2;} u; int ?p; u.u1 = 10; p = u.u2; ?p = 0;

9． ? 修改源码SA 的代码生成部分，让它产生B机器的代码，称结果程序为SB。

? 将SB提交给CCA进行编译，得到一个可执行程序。 ? 将SB提交给上述可执行程序进行编译，得到所需的编译器CCB。

10．第一个表达式在执行?yz.(x + y) + z) 3时出现参数个数不足的情况，因此有FUNVAL的值进入栈顶，然后发现参数个数不足，又把它做成FANVAL的情况。而第二个表达式执行的是(?yz.(x + y) + z) 3 5，不会出现参数个数不足的情况。因此第二个表达式的执行效率比第一个表达式的高。

《编译原理》考试试题

（所有答案必须写在答题纸上）

(2006.12.25)

一、(5×6分)回答下列问题：

1．什么是S-属性文法？什么是L-属性文法？它们之间有什么关系？ 2．什么是句柄？什么是素短语？

3．划分程序的基本块时，确定基本块的入口语句的条件是什么？ 4．运行时的DISPLAY表的内容是什么？它的作用是什么？ 5．对下列四元式序列生成目标代码：

A:=B*C D:=E+F G:=A+D H:=G*2

其中，H是基本块出口的活跃变量， R0和R1是可用寄存器

二、(8分)设?={0，1}上的正规集S由倒数第二个字符为1的所有字符串组成，请给出该字集对应的正规式，并构造一个识别该正规集的DFA。 三、(6分)写一个文法使其语言为L(G)={ anbmambn | m,n≥1}。 四、(8分)对于文法G(E):

E?T|E+T T?F|T*F F?(E)|i

1. 写出句型(T*F+i)的最右推导并画出语法树。

2. 写出上述句型的短语，直接短语、句柄和素短语。 五、(12分)设文法G(S)：

S?SiA|AA?A?B|BB?)A*|(

1．构造各非终结符的FIRSTVT和LASTVT集合；

2．构造优先关系表和优先函数。

六、(9分)设某语言的do-while语句的语法形式为 S ? do S(1) While E

其语义解释为：

针对自下而上的语法分析器，按如下要求构造该语句的翻译模式： (1) 写出适合语法制导翻译的产生式； (2) 写出每个产生式对应的语义动作。

七、(8分)将语句 if (A0) then while C>0 do C:=C+D; 翻译成四元式。 八、(10分) 设有基本块如下：

T1:=S+R T2:= 3 T3:= 12/T2 T4:=S/R A:=T1-T4 T5:=S+R B:=T5

T6:=T5*T3 B:=T6

(1)画出DAG图；

(2)设A,B是出基本块后的活跃变量，请给出优化后的四元式序列。 九、(9分) 设已构造出文法G(S)：

(1) S ? BB (2) B ? aB (3) B? b

的LR分析表如下

S(1)的代码 E的代码 真 假

状态 0 1 2 3 4 5 6 a s3 s6 s3 r3 s6 ACTION b s4 s7 s4 r3 s7 GOTO # acc r1 S 1 B 2 5 8 9 7 8 9 r2 r2 r3 r2

假定输入串为abab，请给出LR分析过程(即按照步骤给出状态，符号，输入串的变化过程)。

（END）

《编译原理》考试试题

（所有答案必须写在答题纸上）

(2006.12.25)

一、回答下列问题：(30分)

1．什么是S-属性文法？什么是L-属性文法？它们之间有什么关系？ 解答：

S-属性文法是只含有综合属性的属性文法。 （2分）

L-属性文法要求对于每个产生式A?X1X2…Xn，其每个语义规则中的每个属性或者是综合属性，或者是Xj的一个继承属性，且该属性仅依赖于：

（1） 产生式Xj的左边符号X1,X2…Xj-1的属性；

（2） A的继承属性。 （2分） S-属性文法是L-属性文法的特例。 （2分）

2．什么是句柄？什么是素短语？

一个句型的最左直接短语称为该句型的句柄。（3分）素短语是这样的一个短语，它至少包含一个终结符并且不包含更小的素短语。（3分）

3．划分程序的基本块时，确定基本块的入口语句的条件是什么？ 解答：

（1）程序第一个语句，或

（2）能由条件转移语句或无条件转移语句转移到的语句，或 （3）紧跟在条件转移语句后面的语句。

4．(6分)运行时的DISPLAY表的内容是什么？它的作用是什么？

答：DISPLAY表是嵌套层次显示表。每当进入一个过程后，在建立它的活动记录区的同时建立一张嵌套层次显示表diaplay.假定现在进入的过程层次为i，则它的diaplay表含有i+1个单元，自顶向下每个单元依次存放着现行层、直接外层、…、直至最外层(主程序，0层)等每层过程的最新活动记录的起始地址。通过DISPLAY表可以访问其外层过程的变量。

5．(6分)对下列四元式序列生成目标代码： A:=B*C D:=E+F G:=A+D H:=G*2

其中，H是基本块出口的活跃变量， R0和R1是可用寄存器 答：

LD R0， B

MUL R0， C LD R1， E ADD R1， F ADD R0， R1 MUL R0， 2 ST R0， H

二、设?={0，1}上的正规集S由倒数第二个字符为1的所有字符串组成，请给出该字集对应的正规式，并构造一个识别该正规集的DFA。(8分)

答：

构造相应的正规式：(0|1)*1(0|1) (3分) NFA: (2分)

1 1

? ? ? ? 1 0 1 2 3 4

0 0 确定化：(3分) I I0 I1 {0,1,2} {1,2} {1,2,3} {1,2,4} {1,2,3,4} {1,2} {1,2} {1,2,4} {1,2} {1,2,4} {1,2,3} {1,2,3} {1,2,3,4} {1,2,3} {1,2,3,4}

0

1 0 1 0 0 0 1 2 3 4

0 1 1 1

三、写一个文法使其语言为L(G)={ anbmambn | m,n≥1}。(6分)

答：文法G(S):

S ? aSb | B B ? bBa | ba

四、对于文法G(E): (8分)

E?T|E+T

T?F|T*F F?(E)|i

1. 写出句型(T*F+i)的最右推导并画出语法树。

2. 写出上述句型的短语，直接短语、句柄和素短语。

答： 1. (4分)

E?T?F?(E) ?(E+T) ?(E+F) ?(E+i) ?(T+i) ?(T*F+i)

2. (4分)

短语：(T*F+i), T*F+i, T*F, i 直接短语：T*F, i 句柄：T*F 素短语：T*F, i

五、设文法G(S)：(12分)

S?SiA|AA?A?B|BB?)A*|(E T F ( E ) E + T T F T * F i

3．构造各非终结符的FIRSTVT和LASTVT集合； 4．构造优先关系表和优先函数。(12分) 答：(6分)

FIRSTVT(S)={ i，+，)，( } FIRSTVT(A)={ +，)，( } FIRSTVT(B)={ )，( }

LASTVT(S)={ i，+，*，( } LASTVT(A)={ +，*，( } LASTVT(B)={ *，( }

优先关系表: (3分) i + ( ) i > < < < + > > < < ( > > ) < < < * > > 优先函数: (3分)

* > > > f g i 2 1 + 6 4 ( 6 6 ) 1 6 * 6 1 六、设某语言的do-while语句的语法形式为 (9分) S ? do S(1) While E

其语义解释为：

针对自下而上的语法分析器，按如下要求构造该语句的翻译模式： (1) 写出适合语法制导翻译的产生式； (2) 写出每个产生式对应的语义动作。 答：(1). 适合语法制导翻译的文法(3分) G(S): R? do

U?R S(1) While S?U E (2). (6分) R? do

{ R.QUAD:=NXQ }

U?R S(1) While { U.QUAD:=R.QUAD;

BACKPATCH(S.CHAIN, NXQ) }

S?U E

{ BACKPATCH(E.TC, U.QUAD); S.CHAIN:=E.FC }

答案二：

(1) S ? do M1 S(1) While M2 E

M ?ε (3分)

(2) M ?ε { M.QUAD := NXQ } (6分)

E的代码 假

S(1)的代码 真

S ? do M1 S(1) While M2 E {

BACKPATCH(S(1).CHAIN, M2.QUAD); BACKPATCH(E.TC, M1.QUAD);

S.CHAIN:=E. FC

七、(8分)将语句

if (A0) then while C>0 do C:=C+D 翻译成四元式。(8分) 答：

100 (j<， A， X， 102) 101 (j， -， -， 109) 102 (j>， B， 0， 104) 103 (j， -， -， 109) 104 (j>， C， 0， 106) 105 (j， -， -， 109) 106 (+， C， D， T1) 107 (:=， T1， -， C) 108 (j， -， -， 104) 109

(控制结构3分，其他5分)

八、(10分) 设有基本块如下：

}

T1:=S+R T2:= 3 T3:= 12/T2 T4:=S/R A:=T1-T4 T5:=S+R B:=T5

T6:=T5*T3 B:=T6

(1)画出DAG图；

(2)设A,B是出基本块后的活跃变量，请给出优化后的四元式序列。

答：(1) DAG如右图：(6分) n7 A n8 T6,B

_ *

n3 T1,T5, B n6 T4 + n1 S / n2 R n4 T2 3 n5 4 T3

(2) 四元式序列：(4分) T1:=S+R T4:=S/R A:=T1-T4 B:=T1*4

九、(9分) 设已构造出文法G(S)：

(1) S ? BB (2) B ? aB (3) B? b

的LR分析表如下

状态 0 1 2 3 4 5 6 7 8 9 a s3 s6 s3 r3 s6 r2 ACTION b s4 s7 s4 r3 s7 r2 # acc r1 r3 r2 S 1 GOTO B 2 5 8 9

假定输入串为abab，请给出LR分析过程(即按照步骤给出状态，符号，输入串的变化过程)。 答：

步骤 状态 符号 输入串 0 0 # abab# 1 03 #a bab# 2 034 #ab ab# 3 038 #aB ab# 4 02 #B ab# 5 026 #Ba b# 6 0267 #Bab # 7 0269 #BaB #

8 9

025 01 #BB #S # #

acc

《编译原理》考试试题

（所有答案必须写在答题纸上）

(2006.12.25)

一、(5×6分)回答下列问题：

1．什么是S-属性文法？什么是L-属性文法？它们之间有什么关系？ 2．什么是句柄？什么是素短语？

3．划分程序的基本块时，确定基本块的入口语句的条件是什么？ 4．运行时的DISPLAY表的内容是什么？它的作用是什么？ 5．对下列四元式序列生成目标代码：

A:=B*C D:=E+F G:=A+D H:=G*2

其中，H是基本块出口的活跃变量， R0和R1是可用寄存器

二、(8分)设?={0，1}上的正规集S由倒数第二个字符为1的所有字符串组成，请给出该字集对应的正规式，并构造一个识别该正规集的DFA。 三、(6分)写一个文法使其语言为L(G)={ anbmambn | m,n≥1}。 四、(8分)对于文法G(E):

E?T|E+T T?F|T*F F?(E)|i

1. 写出句型(T*F+i)的最右推导并画出语法树。

2. 写出上述句型的短语，直接短语、句柄和素短语。 五、(12分)设文法G(S)：

S?SiA|AA?A?B|BB?)A*|(

5．构造各非终结符的FIRSTVT和LASTVT集合； 6．构造优先关系表和优先函数。

六、(9分)设某语言的do-while语句的语法形式为 S ? do S(1) While E

其语义解释为：

针对自下而上的语法分析器，按如下要求构造该语句的翻译模式： (1) 写出适合语法制导翻译的产生式； (2) 写出每个产生式对应的语义动作。

七、(8分)将语句 if (A0) then while C>0 do C:=C+D; 翻译成四元式。 八、(10分) 设有基本块如下：

T1:=S+R T2:= 3 T3:= 12/T2 T4:=S/R A:=T1-T4 T5:=S+R B:=T5

T6:=T5*T3 B:=T6

(1)画出DAG图；

(2)设A,B是出基本块后的活跃变量，请给出优化后的四元式序列。 九、(9分) 设已构造出文法G(S)：

(1) S ? BB (2) B ? aB (3) B? b

的LR分析表如下

S(1)的代码 E的代码 真 假

状态 0 1 2 3 4 5 6 7 8 9

a s3 s6 s3 r3 s6 r2 ACTION b s4 s7 s4 r3 s7 r2 GOTO # acc r1 r3 r2 S 1 B 2 5 8 9 假定输入串为abab，请给出LR分析过程(即按照步骤给出状态，符号，输入串的变化过程)。

（END）

《编译原理》考试试题

（所有答案必须写在答题纸上）

(2006.12.25)

二、回答下列问题：(30分)

1．什么是S-属性文法？什么是L-属性文法？它们之间有什么关系？ 解答：

S-属性文法是只含有综合属性的属性文法。 （2分）

L-属性文法要求对于每个产生式A?X1X2…Xn，其每个语义规则中的每个属性或者是综合属性，或者是Xj的一个继承属性，且该属性仅依赖于：

（3） 产生式Xj的左边符号X1,X2…Xj-1的属性；

（4） A的继承属性。 （2分） S-属性文法是L-属性文法的特例。 （2分）

2．什么是句柄？什么是素短语？

一个句型的最左直接短语称为该句型的句柄。（3分）素短语是这样的一个短语，它至少包含一个终结符并且不包含更小的素短语。（3分）

3．划分程序的基本块时，确定基本块的入口语句的条件是什么？ 解答：

（1）程序第一个语句，或

（2）能由条件转移语句或无条件转移语句转移到的语句，或 （3）紧跟在条件转移语句后面的语句。

4．(6分)运行时的DISPLAY表的内容是什么？它的作用是什么？

答：DISPLAY表是嵌套层次显示表。每当进入一个过程后，在建立它的活动记录区的同时建立一张嵌套层次显示表diaplay.假定现在进入的过程层次为i，则它的diaplay表含有i+1个单元，自顶向下每个单元依次存放着现行层、直接外层、…、直至最外层(主程序，0层)等每层过程的最新活动记录的起始地址。通过DISPLAY表可以访问其外层过程的变量。

5．(6分)对下列四元式序列生成目标代码： A:=B*C D:=E+F G:=A+D H:=G*2

其中，H是基本块出口的活跃变量， R0和R1是可用寄存器 答：

LD R0， B

MUL R0， C LD R1， E ADD R1， F ADD R0， R1 MUL R0， 2 ST R0， H

二、设?={0，1}上的正规集S由倒数第二个字符为1的所有字符串组成，请给出该字集对应的正规式，并构造一个识别该正规集的DFA。(8分)

答：

构造相应的正规式：(0|1)*1(0|1) (3分) NFA: (2分)

1 1

? ? ? ? 1 0 1 2 3 4

0 0 确定化：(3分) I I0 I1 {0,1,2} {1,2} {1,2,3} {1,2,4} {1,2,3,4} {1,2} {1,2} {1,2,4} {1,2} {1,2,4} {1,2,3} {1,2,3} {1,2,3,4} {1,2,3} {1,2,3,4}

0

1 0 1 0 0 0 1 2 3 4

0 1 1 1

三、写一个文法使其语言为L(G)={ anbmambn | m,n≥1}。(6分)

答：文法G(S):

S ? aSb | B B ? bBa | ba

四、对于文法G(E): (8分)

E?T|E+T

T?F|T*F F?(E)|i

1. 写出句型(T*F+i)的最右推导并画出语法树。

2. 写出上述句型的短语，直接短语、句柄和素短语。

答： 1. (4分)

E?T?F?(E) ?(E+T) ?(E+F) ?(E+i) ?(T+i) ?(T*F+i)

2. (4分)

短语：(T*F+i), T*F+i, T*F, i 直接短语：T*F, i 句柄：T*F 素短语：T*F, i

五、设文法G(S)：(12分)

S?SiA|AA?A?B|BB?)A*|(E T F ( E ) E + T T F T * F i

7．构造各非终结符的FIRSTVT和LASTVT集合； 8．构造优先关系表和优先函数。(12分) 答：(6分)

FIRSTVT(S)={ i，+，)，( } FIRSTVT(A)={ +，)，( } FIRSTVT(B)={ )，( }

LASTVT(S)={ i，+，*，( } LASTVT(A)={ +，*，( } LASTVT(B)={ *，( }

优先关系表: (3分) i + ( ) i > < < < + > > < < ( > > ) < < < * > > 优先函数: (3分)

* > > > f g i 2 1 + 6 4 ( 6 6 ) 1 6 * 6 1 六、设某语言的do-while语句的语法形式为 (9分) S ? do S(1) While E

其语义解释为：

针对自下而上的语法分析器，按如下要求构造该语句的翻译模式： (1) 写出适合语法制导翻译的产生式； (2) 写出每个产生式对应的语义动作。 答：(1). 适合语法制导翻译的文法(3分) G(S): R? do

U?R S(1) While S?U E (2). (6分) R? do

{ R.QUAD:=NXQ }

U?R S(1) While { U.QUAD:=R.QUAD;

BACKPATCH(S.CHAIN, NXQ) }

S?U E

{ BACKPATCH(E.TC, U.QUAD); S.CHAIN:=E.FC }

答案二：

(1) S ? do M1 S(1) While M2 E

M ?ε (3分)

(2) M ?ε { M.QUAD := NXQ } (6分)

E的代码 假

S(1)的代码 真

S ? do M1 S(1) While M2 E {

BACKPATCH(S(1).CHAIN, M2.QUAD); BACKPATCH(E.TC, M1.QUAD);

S.CHAIN:=E. FC

七、(8分)将语句

if (A0) then while C>0 do C:=C+D 翻译成四元式。(8分) 答：

100 (j<， A， X， 102) 101 (j， -， -， 109) 102 (j>， B， 0， 104) 103 (j， -， -， 109) 104 (j>， C， 0， 106) 105 (j， -， -， 109) 106 (+， C， D， T1) 107 (:=， T1， -， C) 108 (j， -， -， 104) 109

(控制结构3分，其他5分)

八、(10分) 设有基本块如下：

}

T1:=S+R T2:= 3 T3:= 12/T2 T4:=S/R A:=T1-T4 T5:=S+R B:=T5

T6:=T5*T3 B:=T6

(1)画出DAG图；

(2)设A,B是出基本块后的活跃变量，请给出优化后的四元式序列。

答：(1) DAG如右图：(6分) n7 A n8 T6,B

_ *

n3 T1,T5, B n6 T4 + n1 S / n2 R n4 T2 3 n5 4 T3

(2) 四元式序列：(4分) T1:=S+R T4:=S/R A:=T1-T4 B:=T1*4

九、(9分) 设已构造出文法G(S)：

(4) S ? BB (5) B ? aB (6) B? b

的LR分析表如下

状态 0 1 2 3 4 5 6 7 8 9 a s3 s6 s3 r3 s6 r2 ACTION b s4 s7 s4 r3 s7 r2 # acc r1 r3 r2 S 1 GOTO B 2 5 8 9

假定输入串为abab，请给出LR分析过程(即按照步骤给出状态，符号，输入串的变化过程)。 答：

步骤 状态 符号 输入串 0 0 # abab# 1 03 #a bab# 2 034 #ab ab# 3 038 #aB ab# 4 02 #B ab# 5 026 #Ba b# 6 0267 #Bab # 7 0269 #BaB #

8 9

025 01 #BB #S # #

acc