《编译原理》考试试题及答案

《编译原理》考试试题及答案（附录）

一、判断题：

1.一个上下文无关文法的开始符，可以是终结符或非终结符。 ( X ) 2.一个句型的直接短语是唯一的。 ( X ) 3.已经证明文法的二义性是可判定的。 （ X ） 4.每个基本块可用一个DAG表示。 （ √ ）

5.每个过程的活动记录的体积在编译时可静态确定。 （ √ ） 型文法一定是3型文法。 （ x ） 7.一个句型一定句子。 ( X )

8.算符优先分析法每次都是对句柄进行归约。 (应是最左素短语) ( X ) 9.采用三元式实现三地址代码时，不利于对中间代码进行优化。 （ √ ） 10.编译过程中，语法分析器的任务是分析单词是怎样构成的。 ( x ) 11.一个优先表一定存在相应的优先函数。 ( x ) 12.目标代码生成时，应考虑如何充分利用计算机的寄存器的问题。 ( ) 13.递归下降分析法是一种自下而上分析法。 ( ) 14.并不是每个文法都能改写成LL(1)文法。 ( ) 15.每个基本块只有一个入口和一个出口。

( )

16.一个LL(1)文法一定是无二义的。 ( ) 17.逆波兰法表示的表达试亦称前缀式。

( )

18.目标代码生成时，应考虑如何充分利用计算机的寄存器的问题。 ( ) 19.正规文法产生的语言都可以用上下文无关文法来描述。 ( ) 20.一个优先表一定存在相应的优先函数。

( )

型文法一定是2型文法。 ( ) 22.如果一个文法存在某个句子对应两棵不同的语法树，则文法是二义性的。 ( ) 二、填空题：

1.( 最右推导 )称为规范推导。

2.编译过程可分为 （ 词法分析 ） ，（语法分析），（语义分析和中间代码生成），（代码优化）和（目标代码生成）五个阶段。

3.如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是（ ）。 4.从功能上说，程序语言的语句大体可分为（ ）语句和（ ）语句两大类。 5.语法分析器的输入是（ ），其输出是（ ）。 6.扫描器的任务是从（ ）中识别出一个个（ ）。

7.符号表中的信息栏中登记了每个名字的有关的性质，如（ ）等等。 8.一个过程相应的DISPLAY表的内容为（ ）。 9.一个句型的最左直接短语称为句型的（ ）。

10.常用的两种动态存贮分配办法是（ ）动态分配和（ ）动态分配。 11.一个名字的属性包括( )和( )。 12.常用的参数传递方式有（ ），（ ）和（ ）。 13.根据优化所涉及的程序范围，可将优化分成为（ ），（ ）和（ ）三个级别。

14.语法分析的方法大致可分为两类，一类是（ ）分析法，另一类是（ ）分析法。 15.预测分析程序是使用一张（ ）和一个（ ）进行联合控制的。 16.常用的参数传递方式有（ ），（ ）和（ ）。

17.一张转换图只包含有限个状态,其中有一个被认为是（ ）态;而且实际上至少要有一个（ ）态。 18.根据优化所涉及的程序范围，可将优化分成为（ ），（ ）和（ ）三个级别。 19.语法分析是依据语言的（ ）规则进行。中间代码产生是依据语言的（ ）规则进行的。 20.一个句型的最左直接短语称为句型的（ ）。

21.一个文法G，若它的预测分析表M不含多重定义，则该文法是（ ）文法。

22.对于数据空间的存贮分配， FORTRAN采用( )策略， PASCAL采用( )策略。 23.如果一个文法存在某个句子对应两棵不同的语法树， 则称这个文法是( )。 24.最右推导亦称为（ ），由此得到的句型称为（ ）句型。

25.语法分析的方法大致可分为两类，一类是（ ）分析法，另一类是（ ）分析法。 26.对于文法G，仅含终结符号的句型称为 ( )。

27.所谓自上而下分析法是指（ ）。 28.语法分析器的输入是（ ），其输出是（ ）。 29.局限于基本块范围的优化称（ ）。

30.预测分析程序是使用一张（ ）和一个（ ）进行联合控制的。 型文法又称为（ ）文法；3型文法又称为（ ）文法。

32.每条指令的执行代价定义为（ ）。 33.算符优先分析法每次都是对（ ）进行归约。 三、名词解释题：

1.局部优化 2.二义性文法 表

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. 考虑下面的程序：

…

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 S→BA S→BA S→BA A A→BS A→BS A→BS A→d B B→aA B→bS B→c

给出句子 adccd 的分析过程。

8.写一个文法G, 使其语言为 L(G)={albmclanbn| l>=0, m>=1, n>=2} 9.已知文法G(S): S→a| (T) T→T,S|S

的优先关系表如下：

关系 a ( ) , a - .> .> ( <. <. =. <. ) - - .> .>