文档来源为:从网络收集整理.word版本可编辑.欢迎下载支持.
《编译原理》考试试题及答案（附录）
一、判断题：
1.一个上下文无关文法的开始符，可以是终结符或非终结符。 ( X ) 2.一个句型的直接短语是唯一的。 ( X ) 3.已经证明文法的二义性是可判定的。 （ X ） 4.每个基本块可用一个DAG表示。 （ √ ） 5.每个过程的活动记录的体积在编译时可静态确定。 （ √ ） 6.2型文法一定是3型文法。 （ x ） 7.一个句型一定句子。 ( X ) 8.算符优先分析法每次都是对句柄进行归约。 (应是最左素短语) ( X ) 9.采用三元式实现三地址代码时，不利于对中间代码进行优化。 （ √ ） 10.编译过程中，语法分析器的任务是分析单词是怎样构成的。 ( x ) 11.一个优先表一定存在相应的优先函数。 ( x ) 12.目标代码生成时，应考虑如何充分利用计算机的寄存器的问题。 ( ) 13.递归下降分析法是一种自下而上分析法。 ( ) 14.并不是每个文法都能改写成LL(1)文法。 ( ) 15.每个基本块只有一个入口和一个出口。 ( ) 16.一个LL(1)文法一定是无二义的。 ( ) 17.逆波兰法表示的表达试亦称前缀式。 ( ) 18.目标代码生成时，应考虑如何充分利用计算机的寄存器的问题。 ( ) 19.正规文法产生的语言都可以用上下文无关文法来描述。 ( ) 20.一个优先表一定存在相应的优先函数。 ( ) 21.3型文法一定是2型文法。 ( ) 22.如果一个文法存在某个句子对应两棵不同的语法树，则文法是二义性的。 ( ) 二、填空题：
1.( 最右推导 )称为规范推导。
2.编译过程可分为 （ 词法分析 ） ，（语法分析），（语义分析和中间代码生成），（代码优化）和（目标代码生成）五个阶段。
3.如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是（ ）。 4.从功能上说，程序语言的语句大体可分为（ ）语句和（ ）语句两大类。 5.语法分析器的输入是（ ），其输出是（ ）。 6.扫描器的任务是从（ ）中识别出一个个（ ）。
7.符号表中的信息栏中登记了每个名字的有关的性质，如（ ）等等。 8.一个过程相应的DISPLAY表的内容为（ ）。 9.一个句型的最左直接短语称为句型的（ ）。
10.常用的两种动态存贮分配办法是（ ）动态分配和（ ）动态分配。 11.一个名字的属性包括( )和( )。 12.常用的参数传递方式有（ ），（ ）和（ ）。 13.根据优化所涉及的程序范围，可将优化分成为（ ），（ ）和（ ）三个级别。 14.语法分析的方法大致可分为两类，一类是（ ）分析法，另一类是（ ）分析法。 15.预测分析程序是使用一张（ ）和一个（ ）进行联合控制的。 16.常用的参数传递方式有（ ），（ ）和（ ）。
17.一张转换图只包含有限个状态,其中有一个被认为是（ ）态;而且实际上至少要有一个（ ）态。 18.根据优化所涉及的程序范围，可将优化分成为（ ），（ ）和（ ）三个级别。 19.语法分析是依据语言的（ ）规则进行。中间代码产生是依据语言的（ ）规则进行的。 20.一个句型的最左直接短语称为句型的（ ）。
1文档收集于互联网，如有不妥请联系删除.
文档来源为:从网络收集整理.word版本可编辑.欢迎下载支持.
21.一个文法G，若它的预测分析表M不含多重定义，则该文法是（ ）文法。
22.对于数据空间的存贮分配， FORTRAN采用( )策略， PASCAL采用( )策略。 23.如果一个文法存在某个句子对应两棵不同的语法树， 则称这个文法是( )。 24.最右推导亦称为（ ），由此得到的句型称为（ ）句型。
25.语法分析的方法大致可分为两类，一类是（ ）分析法，另一类是（ ）分析法。 26.对于文法G，仅含终结符号的句型称为 ( )。
27.所谓自上而下分析法是指（ ）。 28.语法分析器的输入是（ ），其输出是（ ）。 29.局限于基本块范围的优化称（ ）。
30.预测分析程序是使用一张（ ）和一个（ ）进行联合控制的。 31.2型文法又称为（ ）文法；3型文法又称为（ 32.每条指令的执行代价定义为（ 33.算符优先分析法每次都是对（ ）进行归约。 三、名词解释题：
1.局部优化 2.二义性文法 3.DISPLAY表 4.词法分析器 5.最左推导 6.语法 7.文法 8.基本块
9.语法制导翻译 10.短语 11.待用信息 12.规范句型 13.扫描器 14.超前搜索 15.句柄
16.语法制导翻译 17.规范句型 18.素短语 19.语法 20.待用信息 21.语义 四、简答题：
1.写一个文法G, 使其语言为 不以0开头的偶数集。 2.已知文法G(S)及相应翻译方案
S→aAb {print “1”} S→a {print “2”} A→AS {print “3”} A→c {print “4”} 输入acab, 输出是什么？ 3. 已知文法G(S)
S→bAa
A→(B | a B→Aa)
写出句子b(aa)b的规范归约过程。 4. 考虑下面的程序：
2文档收集于互联网，如有不妥请联系删除.
）文法。。 ）文档来源为:从网络收集整理.word版本可编辑.欢迎下载支持.
…
procedure p(x, y, z)； begin y:=x+y; z:=z*z; end begin
A:=2; B:=A*2; P(A, A, B); Print A, B end.
试问，若参数传递的方式分别采用传地址和传值时，程序执行后输出 A, B的值是什么? 5.文法G(S) S→dAB A→aA| a B→Bb| ε
描述的语言是什么？ 6.证明文法G(S) S→SaS| ε 是二义性的。 7.已知文法G(S) S→BA A→BS| d
B→aA| bS | c 的预测分析表如下 a b c d # S A B S→BA A→BS B→aA S→BA A→BS B→bS S→BA A→BS B→c A→d 给出句子 adccd 的分析过程。 lmlnn
8.写一个文法G, 使其语言为 L(G)={abcab| l>=0, m>=1, n>=2} 9.已知文法G(S): S→a| (T) T→T,S|S
的优先关系表如下：
关系 a ( ) , a ( ) <. <. .> =. .> .> <. .> , <. <. .> .> 请计算出该优先关系表所对应的优先函数表。
10.何谓优化？按所涉及的程序范围可分为哪几级优化？
11.目标代码有哪几种形式？生成目标代码时通常应考虑哪几个问题？
12.一字母表Σ={a, b}，试写出Σ上所有以a为首的字组成的正规集相对应的正规式。 13.基本的优化方法有哪几种？
nn
14.写一个文法G, 使其语言为 L(G)={abc| n≥0} 15.考虑下面的程序：
3文档收集于互联网，如有不妥请联系删除.
文档来源为:从网络收集整理.word版本可编辑.欢迎下载支持.
…
procedure p(x, y, z); begin y:=y+z; z:=y*z+x end; begin a:=2; b:=3;
p(a+b, b, a); print a end.
试问，若参数传递的方式分别采用传地址和传值时，程序执行后输出 a的值是什么? 16.写出表达式a＋b*(c-d)/e的逆波兰式和三元序列。 17.证明文法G(A) A→AA | (A)| ε 是二义性的。
**
18.令Σ={a,b}，则正规式ab|ba表示的正规集是什么？ 19.何谓DISPLAY表？其作用是什么？ 20.考虑下面的程序：
…
procedure p(x, y, z)； begin y:=y+2; z:=z+x; end begin
a:=5; b:=2;
p(a+b, a-b, a); print a end.
试问，若参数传递的方式分别采用传地址和传值时，程序执行后输出 a的值是什么?
nnm
21.写一个文法G, 使其语言为 L(G)={abc| n>0为奇数， m>0为偶数} 22.写出表达式a:=(b+c)*e+(b+c)/f的逆波兰式和三元序列。 23.一个文法G别是LL(1)文法的充要条件是什么？ 24.已知文法G[S]
S→S*aF | aF | *aF F→+aF | +a
消除文法左递归和提公共左因子。
25.符号表的作用是什么？符号表查找和整理技术有哪几种？ 五、计算题： 1.设文法G(S):
S→^ | a | (T) T→T,S | S
⑴ 消除左递归；
⑵ 构造相应的FIRST和FOLLOW集合； ⑶ 构造预测分析表 2.语句 if E then S
4文档收集于互联网，如有不妥请联系删除.
文档来源为:从网络收集整理.word版本可编辑.欢迎下载支持.
(1) 改写文法，使之适合语法制导翻译； (2) 写出改写后产生式的语义动作。 3.设文法G（S）： S→(T) | a T→T+S | S
(1）计算FIRSTVT 和LASTVT； （2）构造优先关系表。 4.设某语言的for语句的形式为
(1)(2)
for i:＝E to E do S 其语义解释为
(1)
i:＝E
(2)
LIMIT:＝E
again: if i＜＝LIMIT then
Begin S;
i:＝i＋1 goto again End;
（1）写出适合语法制导翻译的产生式； （2）写出每个产生式对应的语义动作。 5.把语句
while a<10 do
if c>0 then a:=a+1
else a:=a*3-1;
翻译成四元式序列。 6.设有基本块 D:=A-C E:=A*C F:=D*E S:=2 T:=A-C Q:=A*C G:=2*S J:=T*Q
K:=G*5 L:=K+J M:=L
假设基本块出口时只有M还被引用，请写出优化后的四元序列。 7.已知文法G(S) S→a | ^ | (T) T→T,S | S
(1) 给出句子(a,(a,a))的最左推导；
(2) 给出句型((T,S),a)的短语, 直接短语，句柄。 8.对于 C 语言do S while E语句
(1)改写文法，使之适合语法制导翻译； (2)写出改写后产生式的语义动作。 9.已知文法G(S) S→aAcBe A→Ab| b
5文档收集于互联网，如有不妥请联系删除.
相关推荐：
loading