编译原理期末试题.doc

《编译原理》期末试题（一）
一、是非题（请在括号内，正确的划√，错误的划×）（每个2分，共20分）
1．编译程序是对高级语言程序的解释执行。(× )
2．一个有限状态自动机中，有且仅有一个唯一的终态。(×)
3．一个算符优先文法可能不存在算符优先函数与之对应。 (√ )
4．语法分析时必须先消除文法中的左递归 。 (×)
5．LR分析法在自左至右扫描输入串时就能发现错误，但不能准确地指出出错地点。 (√)
6．逆波兰表示法表示表达式时无须使用括号。 (√ )
7．静态数组的存储空间可以在编译时确定。 (×)
8．进行代码优化时应着重考虑循环的代码优化，这对提高目标代码的效率将起更大作用。 (×)
9．两个正规集相等的必要条件是他们对应的正规式等价。 (× )
10．一个语义子程序描述了一个文法所对应的翻译工作。 (×)
二、选择题(请在前括号内选择最确切的一项作为答案划一个勾，多划按错论)(每个4分，共40分)
1．词法分析器的输出结果是_____。
　A．( ) 单词的种别编码 　　　　　　B．( ) 单词在符号表中的位置
　C．( ) 单词的种别编码和自身值 　　D．( ) 单词自身值
2． 正规式 M 1 和 M 2 等价是指_____。 
　A．( ) M1和M2的状态数相等   　 　       B．( ) M1和M2的有向边条数相等
　C．( ) M1和M2所识别的语言集相等 　　D．( ) M1和M2状态数和有向边条数相等
3． 文法G：S→xSx|y所识别的语言是_____。
　A．( ) xyx  　 B．( ) (xyx)* C．( ) xnyxn(n≥0)     D．( ) x*yx*
4．如果文法G是无二义的，则它的任何句子α_____。
　A．( )最左推导和最右推导对应的语法树必定相同 　　
　B．( ) 最左推导和最右推导对应的语法树可能不同 　　
　C．( ) 最左推导和最右推导必定相同   　　
　D．( )可能存在两个不同的最左推导，但它们对应的语法树相同
5．构造编译程序应掌握______。
　A．( )源程序   　　　B．( ) 目标语言    
  C．( ) 编译方法      D．( ) 以上三项都是
6．四元式之间的联系是通过_____实现的。
　A．( ) 指示器         　　B．( ) 临时变量
　C．( ) 符号表             D．( ) 程序变量
7．表达式(┐A∨B)∧(C∨D)的逆波兰表示为_____。
　A. ( ) ┐AB∨∧CD∨ 　　　　B．( ) A┐B∨CD∨∧      
  C．( ) AB∨┐CD∨∧         D．( ) A┐B∨∧CD∨
8. 优化可生成_____的目标代码。
　A．( ) 运行时间较短 　 　　              B．( ) 占用存储空间较小
　C．( ) 运行时间短但占用内存空间大 　　　 D．( ) 运行时间短且占用存储空间小
9．下列______优化方法不是针对循环优化进行的。
　A. ( ) 强度削弱    　　　 B．( ) 删除归纳变量    
　C．( ) 删除多余运算　  　 D．( ) 代码外提
10．编译程序使用_____区别标识符的作用域。
　A. ( ) 说明标识符的过程或函数名
　B．( ) 说明标识符的过程或函数的静态层次
　C．( ) 说明标识符的过程或函数的动态层次
　D. ( ) 标识符的行号
三、填空题(每空1分，共101.优化可生成运行时间短且占用存储空间小的目标代码
2.LR分析法解决“移进-规约”冲突时，右结合意味着建立联系实行移进
3.若B为非终结符，则A→a.Bb为待约项目
4.在目标代码生成阶段，符号表用于数据存储分配的依据
5.四元式之间的联系是通过临时变量实现的
1．计算机执行用高级语言编写的程序主要有两种途径：___解释__和__编译___。
2．扫描器是__词法分析器___，它接受输入的__源程序___，对源程序进行___词法分析__并识别出一个个单词符号，其输出结果是单词符号，供语法分析器使用。
3．自上而下分析法采用___移进__、归约、错误处理、___接受__等四种操作。
4．一个LR分析器包括两部分：一个总控程序和___一张分析表__。
5．后缀式abc-/所代表的表达式是___a/(b-c)__。
6．局部优化是在__基本块___范围内进行的一种优化。
三、对于文法G(E): (8分)
E®T|E+T
T®F|T*F
F®(E)|i
1. 写出句型T*F+i1*i2的最右推导并画出语法树。
2. 写出上述句型的短语，直接短语、句柄、素短语和最左素短语
答：1.E => E+T => E+T*F => E+T*i2 => E+F*i2 => E+i1*i2 => T*F +i1*i2
2.短语：T*F+i1*i2, T*F, i1*i2, i1, i2
直接短语：T*F, i1, i2
句柄：T*F
素短语：T*F, i1, i2
最左素短语：T*F

3. 试为表达式 w+(a+b)*(c+d/(e-10)+8) 写出相应的逆波兰表示。
解： w a b + c d e 10 - / + 8 + * +

《编译原理》期末试题（二）
一、是非题：
1.一个上下文无关文法的开始符，可以是终结符或非终结符。 ( )
2.一个句型的直接短语是唯一的。 （ ）
3.已经证明文法的二义性是可判定的。 （ ）
4.每个基本块可用一个DAG表示。 （ ）
5.每个过程的活动记录的体积在编译时可静态确定。 （ ）
6.2型文法一定是3型文法。 （ ）
7.一个句型一定句子。 ( )
8.算符优先分析法每次都是对句柄进行归约。 X ( )
9.采用三元式实现三地址代码时，不利于对中间代码进行优化。 （ ）
10.编译过程中，语法分析器的任务是分析单词是怎样构成的。 ( )
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.× 9.√ 10.× 11.×
12.√ 13.× 14.√ 15.√ 16.√ 17.× 18.√ 19.√ 20.× 21.√ 22.√

二、填空题：
2.编译过程可分为 （ 词法分析） ，（语法分析），（语义分析与中间代码生成 ），（优化）和（目标代码生成 ）五个阶段。
3.如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是（ 二义性的 ）。
5.语法分析器的输入是（ 单词符号 ），其输出是（ 语法单位 ）。
6.扫描器的任务是从（ 源程序中 ）中识别出一个个（ 单词符号 ）。
13.根据优化所涉及的程序范围，可将优化分成为(局部优化），（循环优化），（全局优化）三个级别。
14.语法分析的方法大致可分为两类，一类是（ 自上而下 ）分析法，另一类是（ 自下而上 ）分析法。
15.预测分析程序是使用一张（ 分析表 ）和一个（ 符号栈 ）进行联合控制的。
17.一张转换图只包含有限个状态,其中有一个被认为是（初）态;而且实际上至少要有一个（终 ）态。
19.语法分析是依据语言的（语法 ）规则进行。中间代码产生是依据语言的（语义）规则进行的。
24.最右推导亦称为（规范推导），由此得到的句型称为（规范）句型。
29.局限于基本块范围的优化称（ 局部优化 ）。
31.2型文法又称为（上下文无关）文法；3型文法又称为（正则 ）文法。
33.算符优先分析法每次都是对(最左素短语）进行归约。
16.写出表达式a＋b*(c-d)/e的逆波兰式和三元序列。16.逆波兰式: abcd-*e/+
三元序列: op arg1 arg2
(1) - c d
(2) * b (1)
(3) / (2) e
(4) + a (3)

五、计算题：
四、设文法G(S)：(12分)

1． 构造各非终结符的FIRSTVT和LASTVT集合；
2． 构造优先关系表和优先函数。(12分)
答：(6分)
FIRSTVT(S)={ i，+，)，( }
FIRSTVT(A)={ +，)，( }
FIRSTVT(B)={ )，( }

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

优先关系表: (3分)

i
+
(
)
*
i
>
<
<
<

+
>
>
<
<
>
(
>
>

>
)

<
<
<

*
>
>

>

优先函数: (3分)

i
+
(
)
*
f
2
6
6
1
6
g
1
4
6
6
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还被引用，请写出优化后的四元序列。6.优化后的四元序列
D:=A-C
E:=A*C
F:=D*E
M:=F+20

9.已知文法G(S)
　　 S→aAcBe
　　 A→Ab| b
　　 B→d
　　(1)给出句子abbcde的最左推导及画出语法树；
(2)给出句型aAbcde的短语、素短语。
9.(1) S=>aAcBe=>AAbcBe=>abbcBe=>abbcde
(2) 短语: aAbcde, Ab, d
素短语: Ab, d

10.设文法G(S):
S→(T) | aS | a
T→T,S | S
⑴消除左递归和提公共左因子；
⑵构造相应的FIRST和FOLLOW集合；
⑶构造预测分析表。
10.(1) S →(L) | aS’
S’→S |ε
L→SL’
L’→,SL’ |ε
(2) FIRST(S)={a, (} FIRST(S’)={a, (, ε}
FIRST(L)={a, (} FIRST(L’)={,, ε}
FOLLOW(S)={,, ), #} FOLLOW(S’)={,, ), #}
FOLLOW(L)={ )} FOLLOW(L’)={ )}
(3)

(
)
a
,
#
S
S →(L)

S → aS’

S’
S’→S
S’→ε
S’→S
S’→ε
S’→ε
L
L→SL’

L→SL’
L’→,SL’

L’

L’→ε

12.已知文法G(S)
　 E→E+T | T
　 T→T*F| F
　 F→(E)| i
　 (1) 给出句型 (i+i)*i+i的最左推导及画出语法树；
　 (2) 给出句型 (E+T)*i+F 的短语，素短语和最左素短语。

12.(1) E=>E+T=>T+T=>T*F+T=>F*F+T=>(E)*F+T=>(E+T)*F+T=>(T+T)*F+T
=>(F+T)*F+T=>(i+T)*F+T=>(i+F)*F+T=>(i+i)*F+T=>(i+i)*i+T
=>(i+i)*i+F=>(i+i)*i+i
(2) 短语 i, F, E+T, (E+T), (E+T)*i, (E+T)*i+F
素短语 i, E+T
最左素短语 E+T

第14页共6页
}

《编译原理》期末试题（二）
三、 设有字母表{a，b}上的正规式R=(ab|a)*。
解：（1）
0
1
2
3
b
a
a
ε
ε
-
+

（2）将（1）所得的非确定有限自动机确定化

ε
a
b
-0
1

1
3
12

2

1
+3

a
b
-+013
123

+123
123
13
+13
123

0
1
2
a
a
b
a
-+
+
+

（3）对（2）得到的DFA化简，合并状态0和2 为状态2：
1
2
a
a
b
-+
+

（4）令状态1和2分别对应非终结符B和A

给定文法G[S]： 用子集法将NFA确定化：

将S、A、Q、BZ、DZ、D、B重新命名，分别用0、1、2、3、4、5、6表示。因为3、4中含有z，所以它们为终态。

a
b
0
1
2
1
1
3
2
2
4
3
2
5
4
1
6
5
1
6
6
2
5

《编译原理》期末试题（五）
一、单项选择题(共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．对编译程序而言，输入数据是(源程序)，输出结果是(目标程序)。

五、综合应用题(共3小题，每小题10分，共30分)
1．证明下述文法G：
S®aSbS|aS|d
是二义性文法。
解：
一个文法，如果存在某个句子有不只一棵语法分析树与之对应，那么称这个
文法是二义性文法。
句子aadbd有两棵语法树。如下图：
S
a
S
S
a
b
S
d
d
d
S
S
a
b
S
S
a
d

(1) (2)

由此可知，S®aSbS|aS|d定义的文法是二义性文法。

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

1
0
4
3
2
e e e e 1

0 0
确定化：(3分)
I

{0,1,2}
{1,2}
{1,2,3}
{1,2}
{1,2}
{1,2,3}
{1,2,3}
{1,2,4}
{1,2,3,4}
{1,2,4}
{1,2}
{1,2,3}
{1,2,3,4}
{1,2,4}
{1,2,3,4}

0
1
4
3
2
1
0
0 1 0 0

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
E
T
F
(
E
)
E
+
T
F
i
T
T
*
F
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分)

3． 构造各非终结符的FIRSTVT和LASTVT集合；
4． 构造优先关系表和优先函数。(12分)
答：(6分)
FIRSTVT(S)={ i，+，)，( }
FIRSTVT(A)={ +，)，( }
FIRSTVT(B)={ )，( }

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

优先关系表: (3分)

i
+
(
)
*
i
>
<
<
<

+
>
>
<
<
>
(
>
>

>
)

<
<
<

*
>
>

>

优先函数: (3分)

i
+
(
)
*
f
2
6
6
1
6
g
1
4
6
6
1

七、(8分)将语句
if (A<X) Ù (B>0) 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是出基本块后的活跃变量，请给出优化后的四元式序列。
T1,T5, B
3
T2
4
S
R
+
/
*
_
T3
T4
A
T6,B
n4
n5
n1
n2
n3
n6
n8
n7
答：(1) DAG如右图：(6分)

(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分析表如下

ACTION
GOTO
状态
a
b
#
S
B
0
s3
s4

1
2
1

acc

2
s6
s7

5
3
s3
s4

8
4
r3
r3

5

r1

6
s6
s7

9
7

r3

8
r2
r2

9

r2

假定输入串为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 025 #BB #
9 01 #S # acc