编译原理试题及参考答案.docx
《编译原理试题及参考答案.docx》由会员分享，可在线阅读，更多相关《编译原理试题及参考答案.docx（23页珍藏版）》请在冰点文库上搜索。
编译原理试题及参考答案
课程测试试题（04A卷）
I、命题院（部）：
数学与计算机科学学院
II、课程名称：
编译原理
III、测试学期：
2006－2007学年度第1学期
IV、测试对象：
数计、国交学院计科专业2004级1、2、国交班
V、问卷页数（A4）：
3页
VI、答卷页数（A4）：
4页
VII、考试方式：
闭卷（开卷、闭卷或课程小论文，请填写清楚）
VIII、问卷内容：
（请老师在出题时安排紧凑，填空题象征性的留出一点空格，学生将所有的答案做在答题纸上的规定位置，并写清楚大题、小题的题号）
一、填空题（共30分，30个空，每空1分）
1、典型高级程序设计语言编译系统的工作过程一般分为六个阶段，即词法分析、语法分析、语义分析、中间代码生成、、目标代码生成。
编译阶段的两种组合方式是组合法和按遍组合法，这两种组合方式的主要参考因素都是的特征。
2、Chomsky将文法按其所表示语言的表达能力，由高往低分为四类：
0型，1型，2型，3型文法。
其中，2型文法也称，它的所有规则α→β都满足：
α∈，β∈（（VN∪VT）*且，仅当β=ε时例外。
3、现代编译系统多采用方法，即在语法分析过程中根据各个规则所相联的或所对应的语义子程序进行翻译的办法。
该方法使用为工具来说明程序设计语言的语义。
4、构造与NFAM等价的正规文法G的方法如下：
（1）对转换函数f（A，a）=B或f（A，ε）=B，改成形如或的产生式；
（2）对可识别终态Z，增加一个产生式：
。
5、代码生成要考虑的主要问题：
充分利用的问题、选择的问题、选择的问题。
6、设有穷自动机M=（K，∑，f，S，Z），若当M为时，满足z0∈f（S，α）且z0∈Z，或当M为时，满足f（S，α）=P∈Z，则称符号串α∈∑*可被M所。
7、符号表中每一项对应一个多元组。
符号表项的组织可分为组织、组织、组织等。
8、对于A∈ＶN定义A的后续符号集：
FOLLOW（A）={a|S=*>uAβ，a∈ＶT，且a∈，u∈ＶT*，β∈Ｖ+;若，则#∈FOLLOW（A）。
也可以定义为：
FOLLOW（A）={a|S=*>…Aa…，a∈ＶT}。
若有，则规定#∈FOLLOW（A）。
9、基本块的定义：
一个基本块是指程序中一个执行的语句序列，其中只有一个入口和一个出口。
入口是程序第一个语句或转移语句的目标语句，或转移语句的后继第一个语句。
出口是程序或转移语句。
在基本块范围内的优化称为。
10、预测分析器由预测分析表、先进后出栈（用来存放分析过程的语法符号）和三部分组成。
其中预测分析表是一个二维矩阵，其形式为M[A，a]，其中A∈VN，a∈VT或#。
若有产生式A→α，使得a∈，则将A→α填入M[A，a]中。
（书写时，通常省略规则左部，只填→α）。
对所有的M[A，a]标记为出错。
二、简述题（共20分，4个小题，每小题5分）
1、简述将NFA转换为最小化DFA的步骤。
2、简述静态存储分配、栈式存储分配和堆式存储分配的特点和主要用途。
3、以表达式a:
=b*（-c）+b/（-d）为例，简述常用的三种中间代码表示形式。
4、简述判别文法Ｇ是否为LL
（1）文法的步骤和将一个非LL
（1）文法转换为LL
（1）文法的方法。
三、应用题（共50分）
1、有文法G[S]：
（12分）
S→aAS|aA→SbA|SS|ba
（1）证明aabbaa是文法的一个句子。
（3分）
（2）构造句子aabbaa的语法树。
（3分）
（3）指出该句子的所有短语、直接短语和句柄。
（6分）
2、对文法G[E']：
（15分）
E'→#E#E→E+T|TT→T*F|FF→P^F|PP→（E）|i
（1）计算G[E']的FIRSTVT和LASTVT。
（5分）
（2）构造G[E']的算符优先关系表,并说明G[E']是否为算符优先文法。
（5分）
（3）给出输入串w=i+i#的算符优先分析过程。
（5分）
3、对以下基本块：
（8分）
A：
=5B：
=R+rT0：
=A+BT1：
=2*A
T2：
=B+AT3：
=A+AX1：
=T1+T2X2：
=T0*T3
（1）画出基本块的DAG图。
（3分）
（2）根据DAG结点原来的构造顺序重写四元式。
（2分）
（3）假设基本块出口后只有X1，X2还被引用，试写出优化后的四元式序列。
（3分）
4、对文法G[S’]：
（15分）
0）S’→S1）S→A2）S→B3）A→aAe
4）A→a5）B→bBd6）B→b
（1）试构造G[S’]的LR（0）项目集规范族DFA。
（4分）
（2）试构造G[S’]的SLR
（1）分析表，并判断它是否为SLR
（1）文法。
（4分）
（3）试用SLR
（1）方法分析输入串aae#。
（4分）
（4）G[S’]是否为LR（0）、LR
（1）和LALR
（1）文法？
为什么？
（3分）
课程测试试题（04B卷）
I、命题院（部）：
数学与计算机科学学院
II、课程名称：
编译原理
III、测试学期：
2006－2007学年度第1学期
IV、测试对象：
数计、国交学院计科专业2004级1、2、国交班
V、问卷页数（A4）：
3页
VI、答卷页数（A4）：
4页
VII、考试方式：
闭卷（开卷、闭卷或课程小论文，请填写清楚）
VIII、问卷内容：
（请老师在出题时安排紧凑，填空题象征性的留出一点空格，学生将所有的答案做在答题纸上的规定位置，并写清楚大题、小题的题号）
一、填空题（共30分，30个空，每空1分）
1、典型编译过程一般分为词法分析、语法分析、语义分析、（并非所有的编译程序都包含此阶段）、代码优化、目标代码生成六个阶段，其中词法分析的任务是对构成源程序的字符串进行扫描和分解，识别出（如标识符等）符号；为代码生成阶段收集类型信息，并进行类型审查和违背语言规范的报错处理是的任务。
2、文法是一些规则的有穷集合，它是以有穷规则集来刻划无穷集合的工具。
文法的四元组表示G=（VN，VT，P，S）中，元素VN，VT分别是非空有限的。
且二者交集为φ；P为产生式/规则集，是文法的核心部分；S∈VN，是文法的开始符号（或识别符），它是一个非终结符，至少要在一条规则中作为出现。
3、构造ＬＲ（０）项目集规范族的项目类型分为四种：
形如A→α.aβ的、形如的待约项目、形如A→αBβ.的归约项目、形如S'→α.的。
4、一个优先关系矩阵对应的优先函数；所表示优先关系唯一的矩阵不一定存在优先函数；当两个终结符对之间无优先关系时，可以将相应元素置出错信息，而使用却无法识别这种情况，不能准确指出出错位置。
5、在编译程序中用符号表来存放语言中出现的有关的语义特征属性信息。
程序设计语言中通用的标识符属性主要有如下几种：
符号名、符号的、符号的存储类别、符号的、符号变量的存储分配信息及数组的内情向量等其它属性。
6、如果文法G=（VN，VT，P，S）中不存在形如A→…BC…的产生式，其中B、C为非终结符，则称之为。
在此基础上，如果a,b∈VT,a≡b,a≮b,a≯b至有一个成立，则称之为。
7、分为三类：
的机器语言代码；的机器语言代码；汇编语言（宏汇编）。
8、在程序流中，一个循环必须具有以下性质：
1），即序列中任意两点都可达，若只有一个结点，则有一条返回本身的回边；2），即从序列外某结点，有一条有向边指向它，或它为图中首结点。
9、LR分析步骤：
1）置输入指针ip指向输入串的第一个符号；令S是栈顶状态，a是ip所指向的符号;将#压入符号栈，将开始状态0压入状态栈；2）根据分析表重复执行如下过程：
如果action[S，a]=Sj，则把入符号栈，把入状态栈，并使ip指向下一个输入符号；如果action[S,a]=rj，则从栈顶弹出第j条规则右部串长|β|个符号，把压入符号栈，将压入状态栈，并输出规则A→β；如果action[S,a]=acc，则分析成功，否则报错。
10、过程（函数）是结构化程序设计的主要手段。
调用与被调用过程两者之间的信息主要通过或参数来传递。
参数分为，常用的参数传递方式有传地址、传值、传名等。
二、简述题（共20分，4个小题，每小题5分）
1、简述运行目标程序时所需空间的种类。
2、简述算符优先分析算法的步骤和算符优先分析方法的优、缺点。
3、简述代码优化的概念和分类，并列举出四种以上常用的代码优化技术。
4、简述判别任意给定的一个上下文无关文法G[S]是否为LALR
（1）文法的过程。
三、应用题（共50分）
1、有文法G[E]：
（16分）
E→T+E｜TT→T*F｜FF→（E）｜i
（1）证明T+T*F+i是文法的一个句型。
（3分）
（2）构造型T+T*F+i的语法树。
（3分）
（3）指出该句型的所有短语、直接短语和句柄。
（7分）
（4）指出该句型的所有素短语和最左素短语。
（3分）
2、将下列条件语句翻译成四元式的中间代码形式：
（6分）
ifafthens1elses2
3、有正规文法G[S]：
（12分）
S→aA|bBA→bS|bB→aS|a
（1）构造对应的正规式R，使得L（R）=L（G）。
（3分）
（2）构造对应的NFA状态图，使得L（M）=L（R）。
（3分）
（3）将所得NFA确定化为DFA。
（3分）
（4）将所得DFA最小化。
（3分）
4、对表达式文法G[E]：
（16分）
E→E-T｜TT→T^F｜FF→（E）｜a
（1）判断G[E]是否为LL
（1）文法。
若不是，改造为LL
（1）文法。
（8分）
（2）构造预测分析表，并对输入串w=a-a^a#进行预测分析。
（8分）
课程测试试题（03A卷）
----------------------以下为教师填写--------------------
I、命题院（部）：
数学与计算机科学学院
II、课程名称：
编译原理
III、测试学期：
2005－2006学年度第1学期
IV、测试对象：
数计学院计算机科学技术专业2003级1、2、3班
V、问卷页数（A4）：
4页
VI、答卷页数（A4）：
6页
VII、考试方式：
闭卷（开卷、闭卷或课程小论文，请填写清楚）
VIII、问卷内容：
（请老师在出题时安排紧凑，填空题象征性的留出一点空格，学生将所有的答案做在答题纸上的规定位置，并写清楚大题、小题的题号）
一、填空（30分）
1、将编译过程的各阶段划分为前端或后端和将编译程序分遍的主要参考因素都是（）和（）的特征。
2、（）是一种语法分析程序的自动构造工具，用它可以直接构造各种语言的语法分析器；而（）是一种词法分析程序的自动构造工具，用它可以直接构造各种语言的词法分析器。
3、假设G[S]是一个文法,如有S
x,则称x是该文法G的（）；文法G产生的（）的全体称为该文法所描述的语言。
4、所谓2型文法就是指（）文法，若用G=（VN，VT，P，S）表示它，则它要求G中的所有规则α→β都满足：
α是（），而β属于（VNUVT）*。
5、文法中形如U→U的规则称为（）规则；由不可达的非终结符或不可终止的非终结符作为左部的规则称为（）规则。
在实用文法中一般不允许含有这两类规则。
6、在用五元组表示的确定的有穷自动机DFAM=（K，V，F，S，Z）中，元素V表示字母表；元素S表示唯一的初态，它是状态集K的一个元素；元素F表示（）；元素Z表示终态集，它是状态集K的一个（）。
7、语法分析方法分为自上而下与自下而上两类，自上而下的分析方法方要有递归子程序分析法和（）；而自下而上的分析方法主要有（）和LR分析方法。
8、LR（0）项目集规范族中的项目可分为四类，它们是移进项目、（）、归约项目和接受项目。
其中，接受项目是（）的一种特例。
9、将非LL
（1）文法转换为等价的LL
（1）文法所采用的两种方法是（）和（）。
但这两种方法并不能保证所有的非LL
（1）文法都能转换为等价的LL
（1）文法。
10、通常局部优化是指基本块内的优化，所谓基本块是指程序中一顺序执行的语句序列，其中只有一个（）语句和一个（）语句。
11、算符优先分析时，在句型N1a1N2…ai-1NiaiNi+1ai+1…ajNj+1aj+1Nj+2…中，寻找的最左素短语NiaiNi+1ai+1…ajNj+1中的终结符应满足下优先关系：
（）、（）、（）。
12、在编译程序中符号表用来存放语言程序中出现的有关标识符的属性信息，这些信息集中反映了标识符的语义特征属性。
符号表的功能可以归结为三个主要方面，即（）、作为上下文语义合法性检查的依据和作为（）的依据。
13、根据优先关系矩阵计算优先函数可用迭代法或优先关系图法，但先关系图方法计算出来的优先函数不一定有效，当（）时，所得的优先函数无效，这时也说明该优先关系矩阵不存在优先函数。
14、当一个过程调用其他过程时，调用过程和被调用过程之间的通信经由非局部变量或者经由参数传递，常用的参数传递方式有（）、（）等。
15、现代很多编译程序都采用（）翻译方法，它是指在语法分析过程中，随着分析的步步进展，根据每个规则所对应的语义子程序或语义动作进行翻译的办法。
这种方法使用（）为工具来说明程序设计语言的语义。
二、结合你所熟悉的一门高级语言的编译系统，简述典型编译程序在各个工作阶段的任务。
（共7分）
三、给定正规式R=（01|10）（01|10）*，要求：
（10分）
1、构造对应的正规文法G，使得L（G）=L（R）。
（4分）
2、构造对应的NFAM状态图，使得L（M）=L（R）。
（3分）
3、将所得NFAM确定化为DFA。
（3分）
四、现有文法G[E]：
（共10分）
E→E+T|E-T|T
T→T*F|T/F|F
F→i|（E）
1、证明：
E-F*（i）是文法的一个句型。
（3分）
2、构造句型E-F*（i）的语法推导树。
（2分）
3、指出该句型所有短语、直接短语和句柄。
（5分）
五、任意给定一个文法G[S]：
（10分）
1、给出判断G[S]是否为LL
（1）文法的步骤。
（4分）
2、如果G[S]是LL
（1）文法，怎样构造它的预测分析表？
（3分）
3、怎样根据预测分析表对给定的某个输入串进行预测分析？
（3分）
六、现有文法G[E]：
（共15分）
E→E;D|D
D→D（T）|H
H→a|（E）
T→T*E|E
1、计算G[E]的FIRSTVT和LASTVT；（4分）
2、构造G[E]的算符优先关系表,并说明G[E]是否为算符优先文法；（5分）
3、给出输入串（a*a）#的算符优先分析过程，并据此说明算符优先分析方法的优点和缺点。
（6分）
七、现有文法G[S’]：
（共18分）
0）S'→S
1）S→L=R
2）S→R
3）L→*R
4）L→i
5）R→L
1、构造G[S’]的LR（0）项目集规范族DFA，并据此判断G[S’]是否为LR（0）文法或SLR
（1）文法。
（6分）
2、构造G[S’]的LR
（1）项目集规范族DFA，并据此判断G[S’]是否为LR
（1）文法或LALR
（1）文法。
（6分）
3、给出相应的LALR
（1）分析表。
（3分）
4、简述LR分析算法。
（3分）
课程测试试题（03B卷）
----------------------以下为教师填写--------------------
I、命题院（部）：
数学与计算机科学学院
II、课程名称：
编译原理
III、测试学期：
2005－2006学年度第1学期
IV、测试对象：
数计学院计算机科学技术专业2003级1、2、3班
V、问卷页数（A4）：
4页
VI、答卷页数（A4）：
6页
VII、考试方式：
闭卷（开卷、闭卷或课程小论文，请填写清楚）
VIII、问卷内容：
（请老师在出题时安排紧凑，填空题象征性的留出一点空格，学生将所有的答案做在答题纸上的规定位置，并写清楚大题、小题的题号）
一、判断（15分）
1、编译程序是一种语言翻译程序，它将源语言程序翻译成功能等价的目标语言程序。
2、所谓规则或产生式是指形如α→β或α:
:
=β的（α,β）有序对，其中α是
1、
字母表V的正闭包元素,而β是字母表V的闭包元素。
3、设文法G=（VN，VT，P，S），若P中的每一个规则都是A→aB或A→a，其中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分）
3、翻译成逆波兰式的中间代码形式。
（2分）
4、翻译成四元式的中间代码形式。
（4分）
5、将译成的四元式用DAG表示。
（3分）
三、现有文法G[E]：
（共12分）
E→E+T|E-T|T
T→T*F|T/F|F
F→i|（E）
6、证明：
F+T*（E）是文法的一个句型。
（3分）
7、构造句型F+T*（E）的语法推导树。
（3分）
8、指出该句型所有短语、直接短语和句柄。
（6分）
四、给定正规式R=d（a|bc）*d，要求：
（12分）
4、构造对应的NFAM状态图，使得L（M）=L（R）。
（4分）
5、将所得NFAM确定化和最小化。
（8分）
五、现有文法G[S]：
（共16分）
S→S;D|D
D→D（T）|H
H→m|（S）
T→T*S|S
1、计算G[S]的FIRSTVT和LASTVT；（4分）
2、构造G[S]的算符优先关系表,并说明G[S]是否为算符优先文法；（6分）
3、给出输入串（m*m）#的算符优先分析过程。
（4分）
4、根据分析过程总结算符优先分析方法的优缺点。
（2分）
六、已知G[S]：
（18分）
S→（A）|a|b
A→A,S|S
1、给出（a,（b,b））的最左推导。
（3分）
2、判断该文法是否为LL
（1）文法。
若是，直接给出它的预测分析表；若不是，先将其改写为LL
（1）文法，再给出它的预测分析表；（10分）
3、给出输入串（b,b）#的分析过程，并说明该串是否为G[S]的句子。
（5分）
七、对给定文法G[S’]:
（共18分）
0）S’→S
1）S→A
2）S→B
3）A→aAc
4）A→a
5）B→bBd
6）B→b
5、构造G[S’]的LR（0）项目集规范族DFA，并据此判断G[S’]是否为LR（0）文法。
（6分）
6、进一步判断G[S’]是否为SLR
（1）文法，并给出对应的SLR
（1）分析表。
（6分）
3、给出输入串bbd#的SLR
（1）分析过程。
（4分）
4、判断G[S’]是否为LR
（1）文法和LALR
（1）文法。
（2分）
编译原理课程测试试卷评分标准
（数计学院04计科A卷）
一、填空题参考答案（共30分，30个空，每空1分）
题号
1
2
3
4
参考答案
代码优化、前后端、源语言与目标机器
上下文无关文法、VN、|β|>=|α|
语法制导翻译、语义动作、属性文法
A→aB、A→B、
Z→ε
题号
5
6
7
8
参考答案
寄存器、计算机指令系统、计算次序
NFA、DFA、接受（识别）
线性、排序、散列
FIRST（β）、β=*>ε、S=*>…A
题号
9
10
参考答案
顺序、最后一个语句、局部优化
预测分析程序、SELECT（A→α）、没有值
说明：
各个答案可有不同表达方式，只要意思相同即可。
二、简述题参考答案（共20分，4个小题，每小题5分）
1、第一步：
将NFA确定化。
用造表法将NFA确定化过程如下：
（0）表的第0行和第0列作标识行列的值。
（1）将ε-closure（I）作为表中第1行第1列。
（2）假定∑={a1，a2，...an}，设第i行第一列已确定状态集为I，则置该行第i列为Iai，如Iai未曾在任何行第一列出现过，则将Iai加入下一空行i+1的第一列，并在第0列标记为Ti+1。
（3）反复重复第
（1）步，直至无新状态出现为止。
（4）重新命名新状态。
（3分）
第二步：
将DFA最小化。
DFA最小化具体过程：
用子集分割法将不含多余状态的DFA分成一些不相交的子集，使得任何两个不同的子集中的状态都是可区别的，而相同子集中状态是等价的。
分割时，首先将DFA状态分成终态子集和非终态子集，再根据输出弧所达到状态的性质逐步细分。
（2分）
2、
（1）静态存储分配的特点：
编译时刻确定存储位置；访问效率高。
主要用途：
子程序的目标代码段、全局数据目标（全局变量）。
（2分）
（2）栈（Stack）式存储分配的特点：
嵌套调用次序、先进后出、生存期限于本次调用、自动释放。
用途：
过程的局部环境、活动记录。
（1分）
（3）堆（Heap）式存储分配的特点：
将内存空间分为若干块，根据用户要求分配；无法满足时，调用无用单元收集程序将被释放的块收集起来重新分配。
主要用途：
用于动态数据结构：
存储空间的动态分配和释放。
（2分）
3、
（1）逆波兰式：
abc-*bd-/+:
=。
（1分）
（2）三元式：
①（-,c,_）②（*,b,①）③（-,d,_）
④（/,b,③）⑤（+,②,
升级会员 