大学编译原理课程复习试题及答案Word文档格式.docx
《大学编译原理课程复习试题及答案Word文档格式.docx》由会员分享，可在线阅读，更多相关《大学编译原理课程复习试题及答案Word文档格式.docx（41页珍藏版）》请在冰点文库上搜索。
7.
优先函数的优点是（）。
A.形象直观
B.便于进行比较运算
C.语法分析速度快
D.语法分析方法简单
8.
文法符号的属性通常分为（）两类。
A.共用属性和私有属性
B.固有属性和可变属性
C.语法属性和语义属性
D.综合属性和继承属性
9.
在程序流图中，组成循环的结点序列应满足（）
A.它们是强连通的
B.它们中间有唯一的入口结点
C.它们中间有一条回边
D.它们是强连通的且有唯一的入口结点
10.
在利用寄存器R生成T1:
=C/B的目标代码同时,还应记录信息（）。
A.C/B在T1中
B.T1在C/B中
C.R含有T1,T1在R中
D.R含有C/B,C/B在R中
1.D2.B3.C4.B5.B
6.A7.B8.D9.D10.C
编译方式与解释方式的根本区别在于（）
A.是否生成目标代码
B.是否生成中间代码
C.是否生成汇编代码
D.是否生成优化代码
编译程序生成的目标程序（）
A.一定是机器语言的程序
B.不一定是机器语言的程序
C.一定不是机器语言的程序
D.一定是汇编语言的程序
设字母表∑={0,1,x,y},则∑上的正规式ε所对应的正规集为（）
A.ε
B.{ε0,1,x,y}
C.{ε}
D.Φ
*
假设G是一个文法，S是文法的开始符号，如果S===>
x,则称x是（）
A.短语
C.句子
D.句型
一个算符文法的任何产生式的右部都不含有两个相继的（）
D.ε字
设有文法G[A]：
A→Ax|Ay|Aa|Ac|a|b|c，
下列哪些是该文法的句子（）
（1）aby
（2）aycyx（3）aaa（4）bcxy
A.
（1）
（2）（3）
B.
（1）
（2）（4）
C.
（2）（3）（4）
D.全部
ＬＲ分析器的核心部分是（）
A.带先进后出存贮器的DFA
B.一张动作表
C.一张GOTO表
D.一张分析表
A.它们是强连通的且有唯一的入口结点
D.它们是强连通的
表达式a≤b＋c∧a＞d∨a＋b≠e的后缀式式为（）。
A.abc≤ad＋＞∧ab＋e≠∨
B.ab≤c＋∧da＞ab＋e≠∨
C.abc＋≤ad＞∧ab＋e≠∨
D.abc＋≤ad＞ab＋∧e≠∨
程序基本块是指（）
A.一个子程序
B.一个仅有一个入口和一个出口的语句
C.一个没有嵌套的程序段
D.一组顺序执行的程序段，仅有一个入口和一个出口
1.A2.B3.C4.D5.B
6.C7.D8.A9.C10.D
BNF是一种用于（）的工具。
A.描述句型
B.描述句子
C.描述语言
D.描述文法
B.{ε}
C.{ε0,1,x,y}
规范推导也称为（）
A.最右推导
B.最左推导
C.一般推导
D.自左向右推导
在规范归约中,任何可归约串的出现必在（）
A.栈的内部
B.栈顶
C.剩余的输入串中
D.在先进后出栈中
A.一张分析表
D.带先进后出存贮器的DFA
算符优先分析的关键问题是寻找（）。
A.句柄
B.最左素短语
C.短语
D.直接短语
四元式之间的联系是通过（）
A.指示器
B.临时变量
C.四元式的编号
D.中间运算结果
表达式a≤b＋c∧a＞d∨a＋b≠e的逆波兰式为（）。
A.abc＋≤ad＞∧ab＋e≠∨
C.abc≤ad＋＞∧ab＋e≠∨
代码外提时要求该不变运算所在的结点是循环的（）。
A.某个出口的必经结点
B.至少是一个入口的必经结点
C.入口的必经结点
D.所有出口的必经结点
1.D2.B3.A4.B5.B
6.A7.B8.B9.A10.D
填空题
一个状态转换图可用于一定的字符串。
设∑＝｛a,b,c｝，则∑*中最短的符号串为。
若由文法的开始符号可以推导出串α，且，则α为原文法的一个句子。
若文法的某非终结符P满足，称文法含有左递归。
表达式-（a+b）/（c*d）-e的逆波兰式为______________________________。
后序遍历一棵表达式树，可得到它的。
中间代码是一种面向语法，易于翻译成的代码。
四元式序列中各四元式出现的顺序与是一致的。
若每个程序对应一个流图，则流图中的结点对应一个。
若从流图首结点出发,到达nj的任一通路必须经过ni，则
称的必经结点。
1.识别或接受
2.ε
3.αЄVT*
4.Ｐ==＋＞Ｐα
5.ab+@cd*/e-
6.逆波兰式
7.目标代码
8.运算顺序
9.基本块
10.ni为nj
一个非确定的有限自动机可以表示为一个元式。
设∑＝｛1,2,3｝，则∑*中最短的符号串为。
用∑+表示∑上所有的集合。
三地址代码的一般形式为。
递归下降法对每个构造一个相应的子程序。
在算符优先分析中，用作为可归约串。
在形式语言中，最推导被称为规范推导。
语法树中，一个结点的属性由此结点的父结点和/或兄弟结点的属性确定。
如果循环中对变量I只有唯一的形如I=I±
C的赋值，则称I为循环中的变量。
1.
五
Ｐ==＋＞Ｐα
ε
长度不为0的串
x:
=yopz
非终结符
最左素短语
右
继承
基本归纳
终态与非终态的区别在于。
用于词法分析的扫描缓冲区可将两个半区使用。
一个句型的称为该句型的句柄。
算符优先法尤其适用于的分析。
规范归约的关键在于如何确定。
文法符号的属性值可自底向上应用语义规则计算出来。
DAG代表。
终态可接受空串
识别
互补
最左简单短语
表达式
句柄
综合
有向无环图
判断题
若一个文法是递归的，则由它产生的语言的句子个数是有限的。
（）
用于词法分析的扫描缓冲区可将两个半区重叠使用。
一个LR分析器实质上是一个带有后进先出存储器的DFA。
符号表的每一项一般包含入口栏和信息栏两大部分。
DAG是对循环进行优化的有效工具。
代码外提时要求该不变运算所在的结点是循环的某个出口的必经结点。
1.×
无限
2.×
3.√
4.×
名字
5.×
基本块
6.×
所有
描述程序语言所采用的Ⅲ型文法是上下文无关文法。
状态转换图实现的简单方法是使每个状态结点对应一个非终结符
欲构造行之有效的自下而上分析器，则必须清除文法中含有的左递归。
在规范归约中,任何可归约串的出现必在栈的内部。
循环优化中的强度削弱主要是指将循环中的乘法变成加法。
符号表的信息栏中的内容称为关键字。
×
正规文法
一段小程序
自上而下
栈顶
递归加法
设α是某句型的一个子串，若它能被一次直接归约为一个非终结符，则α是该句型的一个直接短语。
语法分析过程可用一棵树表示出来,这棵树叫做语法树。
四元式作为中间语言，用于翻译除表达式外的其他语句代码。
流图中有向边a→b为回边的条件是aDOMb。
×
要求这个非终结符取代α后，原句型还可继续向开始符方向归约。
分析树
各种
bDOMa
简答题
简述正规式与有限自动机的关系。
已知文法G:
S→iSeS|iS|i
该文法是否具有二义性？
请根据句子iiiei构造语法树予以说明。
何谓递归下降分析法？
应用此种分析法的文法应满足什么条件？
4．简述代码优化所依据的原则与优化的级别，并列举三种常用的优化技术。
正规式用来描述正规集，而有限自动机用来识别正规集，在正规集的意义上它们存在等价关系。
即：
对每一个正规式所代表的正规文法G，都存在一个有限自动机M，使得L（M）=L（G），M所能识别的字的全体恰为这个正规文法G的语言集合；
对每一个有限自动机M，都存在一个可以用正规式表示的正规文法G，使得L（G）=L（M），这个正规文法G的语言集合中的任一个字可以由M识别。
对于句子iiiei，该文法具有两棵不同的语法树与之对应，故为二义性文法。
SS
//\\/\
iSeSiS
/\|//\\
iSiiSeS
|||
Iii
当文法满足LL
（1）条件时，可以为它构造一个不带回溯的自上而下分析程序。
它由一组递归过程（函数）组成，每个过程（函数）对应文法的一个非终极符，这样的分析程序称为递归下降分析器。
利用这种分析程序进行语法分析的方法称为递归下降分析法。
代码优化所依据的原则是：
等价原则、有效原则和合算原则。
代码优化所依据的级别是：
局部优化、循环优化与全局优化。
常用的代码优化技术有：
删除公共子表达式、删除无用赋值、合并已知量、代码外提、强度削弱、删除归纳变量等。
什么是编译器的前端和后端，通常两者之间用什么作为接口？
简述NFA和DFA的联系与区别。
语法分析方法如何分类？
它们面对的主要问题是什么？
何谓中间语言？
简述它的作用。
前端主要由与源语言有关但与目标机无关的那些部分组成，通常包括词法分析、语法分析、语义分析与中间代码产生，有的代码优化工作也可包括在前端。
（2分）后端包括编译程序中与目标机有关的那些部分，如与目标机有关的代码优化和目标代码生成等。
（2分）通常，前端和后端以中间语言作为接口（1分）
联系：
NFA和DFA都是有限自动机，都用于接收、识别一定的字符串。
NFA是DFA的推广，DFA是NFA的特例。
（2分）
区别：
NFA多值函数，DFA是单值函数。
NFA可以有多个初态，DFA只有一个初态。
NFA的每条弧允许用∑*上的一个字作标记，DFA的每条弧只允许用∑上的一个字符作标记。
（3分）
按照语法分析树的建立方法，可以把语法分析方法分为两类：
自上而下分析法与自下而上分析法。
自上而下分析法面对的主要问题是：
如何消除文法的左递归，以及在由文法的开始符出发推导句子的过程中如何避免回溯。
自下而上分析法面对的主要问题是：
在由输入串出发向文法的开始符归约的过程中，如何确定可归约子串（句柄或最左素短语）。
（1分）
中间语言是一种面向语法，复杂性介于用高级语言书写的源程序和用机器语言表示的目标程序之间，是一种易于翻译成目标代码的代码形式。
中间语言的作用在于：
利用它作为中间环节，不仅可以较快地实现源程序翻译过程，而且可在此基础上应用优化方法，将源程序翻译成为运行时间短、占用内存少的目标程序。
何谓上下文无关文法?
它是由哪几部分组成的?
上下文无关文法是这样一种文法，它所定义的语法范畴（或语法单位）是完全独立于这种范畴所处的环境的。
上下文无关文法由四部分所组成：
一组终极符号，一组非终极符号，一个开始符号以及一组产生式。
综合题
构造一个DFA，它接受Σ={a，b}上所有包含ab的字符串。
对文法G（S）：
S→（L）|aS|a
L→L,S|S
1
、消除左递归和回朔；
2、构造各非终结符的FIRST和FOLLOW集合；
3、构造预测分析表。
给出文法G（P）
P→bQb
Q→cR
Q→a
R→Qad
该文法是不是算符优先文法，请构造算符优先关系表证实之。
（1）有如下三地址码：
read（n）
i:
=1
fen:
L1:
ifi<
=ngotoL2
GotoL3
L2:
t1:
=fen*i
fen:
=t1
=i+1
gotoL1
L3:
write（fen）
将该代码段划分为基本块；
并构造相应的程序流图。
（2）对下列四元式序列生成目标代码：
A:
=B*C
D:
=E+F
G:
=A+D
H:
=G*2
其中，H在基本块出口之后是活跃变量，R0和R1是可用寄存器。
1．构造一个DFA，它接受Σ={a，b}上所有包含ab的字符串。
2．对文法G（S）：
答：
3．给出文法G（P）
对于文法G，计算它的每个非终结符的FIRSTVT和LASTVT集合：
4．
（1）有如下三地址码：
read（n）
i:
解：
构造一个最简的DFA，它接受Σ={a，b}上所有满足如下条件的字符串：
所有b都有a直接跟在后面。
得分
设有文法G（X），该文法产生式为：
X→b|&
|（Y）
Y→Y；
X|X
其中X为文法开始符号，b&
；
（）为终结符号
（1）消除左递归和回朔
（2）计算每个非终结符号的FIRST集和FOLLOW集
（3）构造它的预测分析表
设文法G（S）：
S→SiA|A
A→A+B|B
B→）A*|（
1、构造各非终结符的FIRSTVT和LASTVT集合；
2、构造优先关系表和优先函数
对以下程序
（1）READB
（2）J:
（3）A:
=I+2
（4）E:
=I*J
（5）D:
=A+E
（6）B:
=D+B
（7）IfJ>
60goto（10）
（8）J:
=J+1
（9）goto（3）
（10）WRITEB
（11）halt
（1）划分基本块，画出流图
（2）对其中循环进行优化，画出优化后流图
1．构造一个最简的DFA，它接受Σ={a，b}上所有满足如下条件的字符串：
（1）由以上正规式构造相应的NFAM'
（4分）
（2）用子集法对M'
进行确定化，得到DFAM（4分）
I
Ia=ε_CLOSURE（J）
Ib=ε_CLOSURE（J）
{x,1,y}
{1,y}
{2}
--
状态
a
b
1
2
（3）把DFAM’进行化简（4分）
①把M状态集分为两组:
终态结点{0，1}；
非终态结点{2}
②考察{0，1}，因为，{0，1}a={1}包含于{0,1}；
{0，1}b={2}包含于{2}；
所以，{
升级会员 