编译原理期末考试题目及答案.doc

(完整word版)编译原理期末考试题目及答案
一、填空题（每空2分，共20分）
1．编译程序首先要识别出源程序中每个单词，然后再分析每个句子并翻译其意义。
2．编译器常用的语法分析方法有自底向上和自顶向下两种。
3．通常把编译过程分为分析前端与综合后端两大阶段。词法、语法和语义分析是对源程序的分析，中间代码生成、代码优化与目标代码的生成则是对源程序的综合。
4．程序设计语言的发展带来了日渐多变的运行时存储管理方案，主要分为两大类，即静态存储分配方案和动态存储分配方案。
5．对编译程序而言，输入数据是源程序，输出结果是目标程序。
1．计算机执行用高级语言编写的程序主要有两种途径：解释和编译。
2．扫描器是词法分析器，它接受输入的源程序，对源程序进行词法分析并识别出一个个单词符号，其输出结果是单词符号，供语法分析器使用。
3．自下而上分析法采用移进、归约、错误处理、接受等四种操作。
4．一个LL（1）分析程序需要用到一张分析表和符号栈。
5．后缀式abc-/所代表的表达式是a/(b-c)。

二、单项选择题（每小题2分，共20分）
1．词法分析器的输出结果是__C。
　A． 单词的种别编码 　　　　　　B． 单词在符号表中的位置
C． 单词的种别编码和自身值 　　D． 单词自身值
2． 正规式 M 1 和 M 2 等价是指__C_。 
　A． M1和M2的状态数相等   　 　      B． M1和M2的有向边条数相等
C． M1和M2所识别的语言集相等 　 D． M1和M2状态数和有向边条数相等
3． 文法G：S→xSx|y所识别的语言是_C____。
　A． xyx  　 B． (xyx)* C． xnyxn(n≥0)     D． x*yx*
4．如果文法G是无二义的，则它的任何句子α_A____。
　A．最左推导和最右推导对应的语法树必定相同 　　B．最左推导和最右推导对应的语法树可能不同 　　
　C．最左推导和最右推导必定相同   　　 　D．可能存在两个不同的最左推导，但它们对应的语法树相同
5．构造编译程序应掌握____D__。
　A．源程序   　　　B．目标语言       C． 编译方法      D．以上三项都是
6．四元式之间的联系是通过__B___实现的。
　A．指示器         　　B．临时变量 　C．符号表              D．程序变量
7．表达式(┐A∨B)∧(C∨D)的逆波兰表示为__B___。
　A． ┐AB∨∧CD∨ 　　　　B． A┐B∨CD∨∧      C． AB∨┐CD∨∧          D． A┐B∨∧CD∨
8. 优化可生成__D___的目标代码。
　A．运行时间较短 　 　　              B．占用存储空间较小
　C．运行时间短但占用内存空间大 D．运行时间短且占用存储空间小
9．下列___C___优化方法不是针对循环优化进行的。
　A. 强度削弱    　　　 B．删除归纳变量     　C．删除多余运算　  　 D．代码外提
10．编译程序使用_B_区别标识符的作用域。
　A. 说明标识符的过程或函数名 　B．说明标识符的过程或函数的静态层次
　C．说明标识符的过程或函数的动态层次 　D. 标识符的行号

三、判断题（对的打√，错的打×，每小题1分，共10分）
2．一个有限状态自动机中，有且仅有一个唯一的终态。x
3．一个算符优先文法的每个非终结符号间都也可能存在优先关系。X
4．语法分析时必须先消除文法中的左递归 。X
6．逆波兰表示法表示表达式时无须使用括号。R
9．两个正规集相等的必要条件是他们对应的正规式等价。 X
1．编译程序是对高级语言程序的编译执行。X
2．一个有限状态自动机中，有且仅有一个唯一的初始态。R
3．一个算符优先文法的每个非终结符号间都不存在优先关系。R
4．LL（1）语法分析时必须先消除文法中的左递归 。 R
5．LR分析法在自左至右扫描输入串时就能发现错误，但不能准确地指出出错地点。 R
6．逆波兰表示法表示表达式时根据表达式会使用括号。 X
7．静态数组的存储空间可以在编译时确定。X
8．进行代码优化时应着重考虑循环的代码优化，这对提高目标代码的效率将起更大作用。X
9．两个正规集相等的必要条件是他们产生的符号串是相同的。 R
10．一个语义子程序描述了一个文法所对应的翻译工作。 X
1．什么是S-属性文法？什么是L-属性文法？它们之间有什么关系？
S-属性文法是只含有综合属性的属性文法。 （2分）
L-属性文法要求对于每个产生式AàX1X2…Xn，其每个语义规则中的每个属性或者是综合属性，或者是Xj的一个继承属性，且该属性仅依赖于：
（1） 产生式Xj的左边符号X1,X2…Xj-1的属性；
（2） A的继承属性。 （2分）
S-属性文法是L-属性文法的特例。 （１分）

２．什么是LＬ（１）分析器

２．什么是LＲ（０）分析器
所谓LR(０)分析，是指从左至右扫描和自底向上的语法分析，且在分析的每一步，只须根据分析栈当前已移进和归约出的全部文法符号，并至多再向前查看0个输入符号，就能确定相对于某一产生式左部符号的句柄是否已在分析栈的顶部形成，从而也就可以确定当前所应采取的分析动作 (是移进还是按某一产生式进行归约等)。
五、综合题（共40分）
1．（10分）对于文法 G[S] ：
　　S → 1A | 0B | ε 　　A → 0S | 1AA 　　B → 1S | 0BB
　　⑴ (3 分 ) 请写出三个关于 G[S] 的句子；
　　⑵ (4 分 ) 符号串 11A0S 是否为 G [S] 的句型？试证明你的结论。
⑶ (3 分 ) 试画出 001B 关于 G [S] 的语法树。

答：
（1） 三个 0 和 1 数量相等的串 （每个1分）
（2） S => 1A => 11AA => 11A 0S
（3）

 2.（10分）设有语言 L={ α | α∈ {0,1} + ，且α不以 0 开头，但以 00 结尾 } 。
⑵ ３分）试写出描述 L 的正规表达式；
⑵（７分）构造识别 L 的 DFA （要求给出详细过程，并画出构造过程中的 NFA 、 DFA 的状态转换图，以及最小DFA的状态转换图 ) 。
答：
（ 1 ）（３分）正规表达式： 1(0|1) * 00
（ 2 ）（７分）第一步（３分）：将正规表达式转换为 NFA

第二步（２分）：将 NFA 确定化为 DFA ：（１分）
状态 输入
I 0
I 1

t
0
1
[S]
—
[A,D,B]

q 0
—
q 1
[A,D,B]
[D,B,C]
[D,B]
重新命名
q 1
q 2
q 3
[D,B,C]
[D,B,C,Z]
[D,B]

q 2
q 4
q 3
[D,B]
[D,B,C]
[D,B]

q 3
q 2
q 3
[D,B,C,Z]
[D,B,C,Z]
[D,B]

q 4
q 4
q 3
DFA 的状态转换图（１分）

第三步（２分）：将DFA 最小化 ：（１分）
将状态划分终态与非终态两个集合：Ａ＝｛ｑ０，ｑ１，ｑ２，ｑ３｝，Ｅ＝｛ｑ４｝
根据Ａ、Ｅ集合的情况，对Ａ集合进行划分
状态 输入
I 0
I 1
ｑ０
—
Ａ
ｑ１
Ａ
Ａ
ｑ２
Ｅ
Ａ
ｑ３
Ａ
Ａ
将状态集Ａ划分为两个集合：Ａ＝｛ｑ０，ｑ１，ｑ３｝，Ｂ＝｛２｝
根据Ａ、Ｂ集合的情况，对Ａ集合进行划分
状态 输入
I 0
I 1
ｑ０
—
Ａ
ｑ１
Ｂ
Ａ
ｑ３
Ｂ
Ａ
将状态集Ａ划分为两个集合：Ａ＝｛ｑ０｝，Ｃ＝｛ｑ１，ｑ３｝
根据Ａ、Ｃ集合的情况，对Ｃ集合进行划分
状态 输入
I 0
I 1
ｑ１
Ｂ
Ａ
ｑ３
Ｂ
Ａ
最小DFA 的状态转换图（１分）

３．（20分）给定文法 G[E] ：
　　E → E+T | T
　　T → T*F | F
　　F → (E) | i
该文法是 LL(1) 文法吗？（要求给出详细过程，如果是LL（1），给出分析表）
答：（1）该文法不是LL（1）文法，因为有左递归，消除左递归可获得一个LL（1）文法 （2分）
（2） 消除左递归，得新文法 (3分)
E → TE’
E’→ +TE’| ε
T → FT’
　　T’ → *FT’ |ε
　　F → (E) | i
(3)求产生式右部的First集 (2.5分)
First(TE’) = First(T)= First(F)={(,i}
First(+TE’) = {+}
First(FT’) = First(F)={(,i}
First(*FT’) = {*}
First((E)) = {(}
First(i) = {i}
（4） 求所有非终结符的Follow集(2.5分)
Follow(E) = {$,)}
Follow(E’) = Follow(E) = {$,)}
Follow(T) = First(E’)∪Follow(E)={+} ∪{$,)}={$,+,)}
Follow(T’) = Follow(T) ={$,*,)}
Follow(F) = First(T’)∪Follow(T) ∪Follow(T’)= {$,*,)}
（5） 求所有产生式的Select集 (2.5分)
Select（E → TE’）=First(TE’)= {(,i}
Select（E’→ +TE’）=First(+TE’)= {+}
Select（E’→ ε）= Follow(E’) = {$,)}
Select（T → FT’）=First(FT’)= {(,i}
Select（T’ → *FT’）=First(*FT’)= {*}
Select（T’→ ε）= Follow(T’) ={$,+,)}
Select（F → (E)）=First((E))= {(}
Select（F → i）=First(i)= {i}
（6）对相同左部的所有Select即求交集(2.5分)
Select（E’→ +TE’）∩Select（E’→ ε）= Φ
Select（T’ → *FT’）∩Select（T’→ ε）=Φ
Select（F → (E)）∩Select（F → i）=Φ
所以，改造后的文法是LL（1）文法，其分析表如下
（7） LL(1) 分析表（ 5 分）
V N
V T
+
*
i
(
)
$
E

E → TE’
E → TE’ 

E’
E’→ +TE’

 E’→ ε
E’→ ε
T

T → FT’
T → FT’

T’
T’→ ε
T’ → *FT’

T’→ ε
T’→ ε
F

F → (E)
F → i

1．（10分）对于文法G：
S®aSbS|aS|d
证明该文法是二义性文法。
答：一个文法，如果存在某个句子有不只一棵语法分析树与之对应，那么称这个文法是二义性文法。（5分）
句子aadbd有两棵语法树（5分，划一棵树给3分）。如下图：（６分）
S
a
S
S
a
b
S
d
d
d
S
S
a
b
S
S
a
d

(1) (2)

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

３．（20分）给定一个简单的算术表达式文法 G[E] ：
　　E → E+T | T
　　T → T*F | F
　　F → (E) | i
　　该文法是 SLR(1) 文法吗？（要求给出详细过程，如果是SLR文法，给出分析表）
答：
(1) 该文法的拓广文法是： (2分)
　　E’ →E （1）
E → E+T （2）
E → T （3）
T → T*F （4）
T → F （5）
F → (E) （6）
F → i （7）

（2） 相应的LR（0）的DFA：（10分）
)
(
F
T
I0:
E’ →.E
E → .E+T
E → . T
T → .T*F
T → .F
F → .(E)
F → .i

I1:
E’ →E.
E →E.+T
I2:
E →T.
T → T.*F
E
F
I3:
T →F.
T
I4:
F → (.E)
E → .E+T
E → . T
T → .T*F
T → .F
F → .(E)
F → .i

（
i
I6:
E →E+.T
T → .T*F
T → .F
F → .(E)
F → .i

+
*
（
i
i
T
I8:
E →E+T.
T → T.*F
*
I7:
T → T*.F
F → .(E)
F → .i

F
（
i
I9:
F → (E.)
E →E.+T
E
I10:
F → (E) .
+
I5:
F →i.
F
I11:
T → T*F.

（3） 冲突与解决 (3分）
① I1状态中有移进—规约冲突
Follow(E’)={ $ } 不含{ + }
可解决移进—规约冲突
② I2状态中有移进—规约冲突
Follow(E)={ +，），$ } 不含{ * }
可解决移进—规约冲突
③ I8状态中有移进—规约冲突
Follow(E)={ +，），$ } 不含{ * }
可解决移进—规约冲突
(4) SLR分析表 (5分)

ACTION
GOTO
+
*
i
（
）
$
E
T
F
0

S5
S4

1
2
3
1
S6

接受

2
r3
S7

r3
r3

3
r5
r5
r5
R5
r5
r5

4

S5
S4

9
2
3
5
r7
r7
r7
r7
r7
r7

6

S5
S4

8
3
7

S5
S4

11
8
r2
S7

r2
r2

9
S6

S10

10
r6
r6
r6
r6
r6
r6

11
r4
r4
r4
r4
r4
r4

二、单项选择题（每小题2分，共20分）
1．语言是____C_
A．终结符与非终结符的符号串的集合 B． 非终结符符号串的集合 C．终结符符号串的集合 D．产生式的集合
2．编译程序分两阶段工作，前阶段完成的工作是__C___
A．词法分析、语法分析和代码优化 B．代码生成、代码优化和词法分析
C．词法分析、语法分析、语义分析和中间代码生成 D．词法分析、语法分析和代码优化
3．一个句型中称为句柄的是该句型的最左C
A．句型 B．短语 C．直接短语 D．最左直接短语
4．自动机识别的语言是 D
A．0型语言 B．1型语言 C．2型语言 D．3型语言
5．自动机所完成的任务是从字符串形式的源程序中识别出一个个具有独立含义的最小语法单位即 B
A． 字符 B．单词 C．句子 D．句型
6．对应Chomsky四种文法的四种语言之间的关系是B
A．L0ÌL1ÌL2ÌL3 B．L3ÌL2ÌL1ÌL0 C．L3=L2ÌL1ÌL0 D．L0ÌL1ÌL2=L3
7．词法分析的任务是A
A．识别单词 B．分析句子的含义 C．识别句子 D．生成目标代码
8．常用的中间代码形式不含D
A．三元式 B．四元式 C．逆波兰式 D．语法树
9． 代码优化的目的是C
A．节省时间 B．节省空间 C．节省时间和空间 D．把编译程序进行等价交换
10．代码生成阶段的主要任务是C
A．把高级语言翻译成汇编语言 B．把高级语言翻译成机器语言
C．把中间代码变换成依赖具体机器的目标代码 D．把汇编语言翻译成机器语言