编译原理考试题解答.doc

一.名词解释：
1)前缀
答：前缀——是指符号串任意首部。
2)可归前缀
答：可归前缀——是指规范句型的一个前缀，这种前缀包含句柄且不含句柄之后的任何符号。
3)活前缀
答：活前缀——规范句型的一个前缀，这种前缀不含句柄之后的任何符号。
或给定文法规范句型的可归前缀的任意首部。
4)简单短语
答：简单短语——设G[Z]是给定文法,w=xuy∈V+，为该文法的句型,如果满足下面两个条件:
① Z xUy； ② UÞu；
则称句型xuy 中的子串u是句型xuy的简单短语。
5)扫描遍
答：扫描遍——指编译程序对源程序或中间代码程序从头到尾扫描一次。
6)句柄
答：句柄——给定句型中的最左简单短语就是句柄。
7)句型
答：句型——设G是一个给定的文法，S是文法的开始符号，如果Sx(其中x∈V*),则称x是文法的一个句型。
*
Þ
8)句子
答：句子——设G是一个给定的文法，S是文法的开始符号，如果S x（其中x∈VT*），则称x是文法的一个句子。
9)非终结符
答：非终结符——出现在文法产生式的左部且能派生出符号或符号串的那些符号称为非终结符号。
10)终结符
答：终结符——出现在文法产生式的右部且不能派生出符号或符号串的那些符号称为终结符号。
11）属性文法
答：一个属性文法形式的定义为一个三元组AG，AG=（G，V，E）。
其中G为一个上下文无关文法；V为属性的有穷集；E为一组语义规则。
12）语法制导翻译
答：语法制导翻译——语法制导翻译就是在语法分析的过程中，当进行推导或归约时同步完成附加在所使用的产生式上的语义规则描述的动作，从而实现语义处理。
13）后缀式
答：后缀式——一种把运算量（操作数）写在前面，把算符写在后面（后缀）的表示法。

14）短语
答：短语——设G[Z]是给定文法,w=xuy∈V+，为该文法的句型,如果满足下面两个条件:
① Z xUy； ② U u；
则称句型xuy 中的子串u是句型xuy的短语。
或：句型语法树的全部子树的叶从左到右排列起来构成的符号串均是句型的短语。
15）基本块
答：基本块——源程序或者中间代码程序中只有一个入口和一个出口的顺序执行的代码段。
16）语义规则
答：对于文法的每个产生式都配备了一组属性的计算规则，称为语义规则。
17）语法分析
答：语法分析——按文法的产生式识别输入的符号串是否为一个句子的分析过程。
18）四元式
答：四元式——是一个带有四个域的记录结构，这四个域分别称为操作符域、左运算对象域、右运算对象域及运算结果域。

二．简答题：
1) 什么是句子？ 什么是语言?
*
Þ

解答：句子——设G是一个给定的文法，S是文法的开始符号，如果S x（其中x∈VT*），则称x是文法的一个句子。
语言——语言是句子的集合。
或——设G[S]是给定文法，则由文法G所定义的语言L(G)可描述为：L(G)＝{x│Sx,x∈VT*} 。
2) DFA与NFA有何区别 ?
解答:DFA与NFA的区别表现为两个方面:一是NFA可以有若干个开始状态，而DFA仅只有一个开始状态。另一方面，DFA的映象M是从K×∑到K，而NFA的映象M是从K×∑到K的子集，即映象M将产生一个状态集合（可能为空集），而不是单个状态。
3) 自顶向下的语法分析方法的基本思想是什么?
解答:从文法的开始符号开始，根据给定的输入串并按照文法的产生式一步一步的向下进行直接推导，试图推导出文法的句子，使之与给定的输入串匹配。
4) 自底向上的语法分析方法的基本思想是什么?
解答:从给定的输入串（终结符串）开始，根据文法的规则一步一步的向上进行直接归约，试图归约到文法的开始符号。
5) 一个上下文无关文法G包括哪四个组成部分？
解答:一组非终结符号，一组终结符号，一个开始符号，以及一组产生式。
6) 在自底向上的语法分析方法中，分析的关键是什么？
解答:关键是寻找句柄。
7) 在自顶向下的语法分析方法中，分析的关键是什么？
解答:关键是选择候选式。
8) 编译程序中语法分析器接收以什么为单位的输入？
解答: 接收以单词为单位的输入。
9) 若一个文法是递归的，则它所产生的语言的句子是可枚举的吗？
解答: 它所产生的语言的句子不是可枚举的，而是无穷多个。
10) 编译程序生成的目标程序是不是一定是机器语言的程序？
解答:不一定是机器语言的程序。
11) 词法分析器是用于做什么的？
解答:词法分析器是用于识别单词的。
12) “用高级语言书写的源程序都必须通过编译,产生目标代码后才能投入运行”这种说法正确吗？
解答: 不正确。
13) 把汇编语言程序翻译成机器可执行的目标程序的工作是由什么完成的？
程序代码区
静态数据区
栈区

堆区
解答: 由汇编器（汇编程序）完成的。
14)图示运行时存储空间的划分（分为哪几个区）。
解答: 一般分为静态区和动态区：
程序代码区、静态数据区、栈区和堆区

15)词法分析的主要任务是什么？
解答:词法分析器的任务是对构成源程序的字符串从左到右逐个字符逐个字符地进行扫描，依次把它们识别为一个一个具有独立意义的单词，并确定其属性，再转换为长度统一的属性字并输出。
16)常用的中间语言种类有哪几种？
解答: 常用的中间语言种类有逆波兰表示、三元式、四元式和树形表示。
17）文法G所描述的语言是什么的集合？
解答:是由文法的开始符号推出的所有终结符串的集合。或说是句子的集合。
18）乔姆斯基把文法分为四种类型，即0型、1型、2型、3型。其中2型文法叫什么？
解答: 2型文法叫上下文无关文法。
19）编译程序是一种解释程序吗？还是什么程序？
解答:编译程序是一种翻译程序。
20）按逻辑上划分，编译程序第二步工作是什么？
解答: 编译程序第二步工作是语法分析。
21）源程序是用高级语言编写的，目标程序是机器语言程序或汇编语言程序 ，则其翻译程序称为什么？
解答: 其翻译程序称为编译程序。
22）编译方式与解释方式的根本区别为什么？
解答:编译方式与解释方式的根本区别在于是否生成目标代码。
23）常见的动态存贮分配策略有哪两种？
解答:常见的两种动态存贮分配策略是栈式动态分配策略和堆式动态分配策略。
24）常用的参数传递方式有哪三种？
解答:常见的参数传递方式有传地址、传值和传名三种方式。
25）语法分析的任务是什么？
解答:语法分析的任务是识别给定的终结符串是否为给定文法的句子。
26）局部优化是局限于一个什么范围内的一种优化？
解答: 是局限于一个基本块范围内的一种优化。
27）文法等价的定义是什么？
解答: 设G1和G2是给定的文法，如果有L（G1）= L（G2），则称G1与G2等价。
28）在语法分析处理中，FIRST集合、FOLLOW集合、SELECT集合均是什么集合？
解答: 均是终结符集。
29）通常一个编译程序中应包括哪七个部分？
解答: 通常一个编译程序中应包含词法分析，语法分析，语义分析与中间代码生成，代码优化，目标代码生成以及表格处理和出错处理等七个部分。
32）如果编译程序生成的目标程序是汇编语言程序，则源程序的执行分为哪三个阶段？
解答: 源程序的执行分为三个阶段: 编译阶段，汇编阶段和运行阶段。
33）翻译程序是这样一种程序，它能够将用什么转换成与其等价的用乙语言书写的程序？
解答:能够将用甲语言书写的程序转换成与其等价的用乙语言书写的程序。
34）说明下面文法G[S]是二义性文法：S→SaS|SbS|cSd|eS|f

解答:fafbf是文法G[S]的一个句子，并且有两个不同的最右推导。
（1）S => SaS => SaSbS => SaSbf=> Safbf=> fafbf
（2）S => SbS => Sbf=> SaSbf => Safbf=> fafbf
因此说明此文法有二义性。
35）在属性文法中，综合属性与继承属性是如何传递信息的？
解答: 综合属性用于自下而上传递信息，继承属性用于自上而下传递信息。
36）代码优化的主要目标是什么？
解答: 代码优化的主要目标是如何提高目标程序的运行速度和如何减少目标程序运行时所需的空间。
37）写一个文法，使其语言是无符号二进制实数不含指数）。
解答:文法G(N)：
　　　　　 　N→L.L|L
　　　　　 　L→LB|B
　　　　　 　B→0|1
三．应用题
1）消除下列文法G[A]的左递归。
E→E-T∣T
T→T/F∣F
F→( E )∣i
解答：消除文法G[E]的左递归后得到：
E→TE′
E’→-T E′∣ε
T→FT′
T’→/FT′∣ε
F→( E )∣i

2） 消除下列文法G[A]的左递归。
A→AaB∣B
B→BbC∣C
C→eD∣D
D→(A)∣d
解答：消除文法G[A]的左递归后得到：
A →BAˊ
Aˊ→aBAˊ∣ε
B →CBˊ

Bˊ→bcBˊ∣ε
C→eD∣D
D→(A)∣d

3）给定下列自动机：
其中：开始状态：0
终止状态：2
a

a

Þ

a

0

b

b

b

1
2

把此自动机转换为确定自动机DFA。
a b
Þ0 01 2
01 01 2
－2 1 2
1 2
a b
Þ0 0,1 2
1 2
－2 1 2

Þ
解答： 有状态矩阵如图：

-
Þ
0
2
a
a
b
a
1
01
b
b
b
Þ
0
2
b
a
b
b
1
极小化后：
a
从而可得DFA如图：

4）正规式（a|b）*a(a|b) 构造一个等价的有限自动机。
解答：
a,b
a
a
b
Þ
0
1
2

四．设计题
（1）给定文法G[S′] 及相应翻译方案为：
1．S¢→S {print:“a”}
2．S→r D {print:“b”}
3．D→D，i {print:“c”}
4．D→i {print:“d”}

a. 按chomsky分类法，文法G属于哪一型文法？
b. 符号串ri,i,i是不是该文法的一个句型，请证实。
c. 若是句型，写出该句型的所有短语、简单短语，以及句柄。
d. 构造识别该文法的活前缀的DFA。
e. 判断该文法是LR（0）还是SLR（1），并构造其相应的语法分析表。
f. 对于ri,i,i这个输入符号串，经该翻译方案翻译后的输出是什么？

解答：
a．文法G属于2型(上下文无关)文法。
b．符号串r i,i,i是该文法的一个句型。
证：S¢ÞSÞrDÞrD，iÞ rD，i，i Þ r i，i，i，得证。
或证：构造语法树见图4，可知符号串r i,i,i是该文法的一个句型。
c．句型r i,i,i的短语有：①r i,i,i；② i,i,i；③i,i；④ 第一个i
简单短语有：第一个i
句柄有：第一个i
d．求得文法G的识别全部活前缀的DFA见图3：
I1:
S¢→S.
I0:
S′→.S
S→.rD
I2:
S→r.D
D→.D，i
D→.i
r
I4:
S→rD.
D→D.，i
D
，
S
I5:
D→D，.i
I3:
D→i.
i
i
I6:
D→D，i.
图3 识别全部活前缀的DFA

e．∵在项目集I4中存在冲突项目，∴文法G不是LR（0）文法。
FOLLOW(S¢)={#}
FOLLOW(S)={#}
FOLLOW(D)={ ，,#}
而由于{ ，}∩FOLLOW(S)={ ，}∩{#}=Φ，所以文法G是SLR（1）文法。

S¢
r
S
D
D
i
，
i
D
i
，
图4 句子的语法树
求得文法G的SLR（1）分析表见表1：

ACTION
GOTO
r
，
i
#
S
D
0
S2

1

1

acc

2

S3

4
3

R4

R4

4

S5

R2

5

S6

6

R3

R3

表1 SLR（1）分析表

f．可以先求得该句子的语法树（见图4），然后通过剪枝的方式进行归约，
最后归约到文法的开始符号，在归约的过程中同步产生输出符号串dccba。
即对于r i,i,i这个输入符号串，该翻译方案的输出是：dccba

（2）给定文法:
（1）S→bTc
（2）S→a
（3）T→R
（4）R→R/S
（5）R→S
a)符号串ba/ac是不是该文法的一个句子，请证实。
b)若是句子，写出该句子的所有短语、简单短语和句柄。
c)为该文法设计翻译方案，使句型bR/bTc/bSc/ac经该翻译方案翻译后,输出下列串：
S
b
c
R
R
S
/
a
S
T
a
0342031320
解答：
a) 符号串ba/ac是该文法的一个句子。
∵SÞbTcÞbRcÞbR/ScÞbS/ScÞba/ScÞba/ac，
∴得证。
或：给出符号串ba/ac的语法树如右图，则判定
符号串ba/ac是该文法的一个句子。
b)给出句型ba/ac的语法树如右图：
则可求得句型adbb的短语有：ba/ac,a/a,第1个a, 第2个a
简单短语有：第1个a, 第2个a
句柄有：第1个a

c)给出句型bR/bTc/bSc/ac的语法树如右图：
S
b
c
R
R
S
/
S
a
R
R
S
R
S
b
c
T
/
/
T
b
c
T
按照归约过程，则给定文法的相应翻译方案为：
（1）S→bTc {print(“0”)}
（2）S→a {print(“1”)}
（3）T→R {print(“2”)}
（4）R→R/S {print(“3”)}
（5）R→S {print(“4”)}

（3）设有基本块：
t1:=3*A
t2:=2*C
t3:=t1+t2
t4:=t3+5
t5:=2*C
t6:=3*A
t7:=t6+t5
E:=t7-1
F:=t4-E
a)画出DAG图；
b)假设基本块出口时只有E，F还被引用，请写出优化后的三地址代码序列。
5
－
+
*
+
*
－
t4
t1,t6
2
A
3
n11
n2
n3
n5
n6
n8
E
n7
F
1
n4
t2,t5
t3,t7
n9
C
n10
n11
n12
解答：
a)构造DAG：见右图。

b)优化后的三地址代码序列为：
t1:=3*A
t2:=2*C
t3:=t1+t2
t4:=t3+5
E:=t3-1
F:=t4-E

五．转换题：
给定下列中缀式 (运算符优先级按常规理解) ，分别写出等价的逆波兰式和四元式。
1）a≤b∧a＞0∨b＜0
解答：逆波兰式为：ab≤a0＞∧b0＜∨
写出等价的四元式表示
1. (≤,a ,b ,T1)
2. (＞,a ,0 ,T2)
3. (∧T1,T2,T3)
4. (＜,b ,0 ,T4)
5. (∨,T3,T4,T5)

―
2）―a＋b≤0∨a＜0∧(a―b)>2
解答：逆波兰式为：a―b＋0≤a0＜ab―2＞∧∨；
―
四元式为：1.( ,a, ,T1)
2.( ＋,T1,b ,T2)
3.( ≤,T2,0 ,T3)
4.( ＜,a ,0 ,T4)
5.( ―,a ,b ,T5)
6.( ＞,T5,2 ,T6)
7.( ∧,T4,T6,T7)
8.( ∨,T3,T7,T8)
9 / 9