编译原理复习题集.doc

《编译原理》复习题集

1．名词解释
短语
句柄
文法
上下文无关文法
LL（1）文法
LR（1）文法
语法分析
无环路有向图(DAG)
后缀式
语法制导翻译
遍
局部优化
词法分析
语法分析
语义分析
源语言
源程序
目标语言
中间语言（中间表示）

2．简答题
编译程序和高级语言有什么区别?
编译程序的工作分为那几个阶段?
简述自下而上的分析方法。
目标代码有哪几种形式？生成目标代码时通常应考虑哪几个问题？
何谓优化？按所涉及的程序范围可分为哪几级优化？
简述代码优化的目的和意义。

3．叙述下面的正规式描述的语言，并画出接受该语言的最简DFA的状态转换图。
(1|01)*0*

4．Pascal语言无符号数的正规定义如下：
numdigit+(.digit+)?(E(+|-)?digit+)?
其中digit表示数字，用状态转换图表示接受无符号数的确定有限自动机。

5．画出Pascal中实数(不带正负号，可带指数部分)的状态转换图。

6．用状态转换图表示接收(a|b)aa的确定的有限自动机。

7．处于/*和*/之间的串构成注解，注解中间没有*/。画出接受这种注解的DFA的状态转换图。

8．某操作系统下合法的文件名为
device:name.extension
其中第一部分（device:）和第三部分（.extension）可缺省，device,name和extension都是字母串，长度不限，但至少为1，画出识别这种文件名的确定有限自动机。

9．构造一个DFA，它接受0,1上0和1的个数都是偶数的字符串。

10．设有非确定的有自限动机NFAM=({A，B，C}，{0，1}，δ，{A}，{C})，其中：δ(A，0)={C}δ(A，1)={A，B}δ(B，1)={C}δ(C，1)={C}。请画出状态转换距阵和状态转换图。

11．设L{a,b,c}*是满足下述条件的符号串构成的语言：
(1)若出现a，则其后至少紧跟两个c；
(2)若出现b，其后至少紧跟一个c。
试构造识别L的最小化的DFA，并给出描述L的正规表达式。

12．写出字母表∑={a,b}上语言L={w|w的最后两个字母是aa或bb}的正规式，并画出接受该语言的最简DFA。

13．有穷自动机M接受字母表∑＝{0,1}上所有满足下述条件的串：串中至少包含两个连续的0或两个连续的1。请写出与M等价的正规式。

14．有正规式b*abb*(abb*)*，
(1)构造该正规式所对应的NFA(画出状态转换图)。
(2)将所求的NFA确定化(画出确定化的状态转换图)。
(3)将所求的NFA最小化.(画出最小化后的状态转换图)。

15．求出下列文法所产生语言对应的正规式.
SbS|aA
AaA|bB
BaA|bC|b
CbS|aA

16．给出与下图的NFA等价的正规式。
S0
S1
S3
S2

17．把下面的NFA确定化。

1
2
3
4
5

6
1
0
1
1
1
0
1

18．下面两个文法中哪一个不是LR（1）文法？对非LR（1）的那个文法。给出那个有移进－归约冲突的规范的LR（1）项目集。
SaAc SaAc
AbbA|b AbAb|b

0
1
2

3
a
a
b
a
b
b
a,b
19．将下面的DFA化成最简形式。

20．为语言
L＝{w|w(a|b)*并且在w的任何前缀中，a的个数不少于b的个数
写一个LR（1）文法，不准超过6个产生式。

21．写一个文法，使其语言是奇数集，且每个奇数不以0开头。

22．考查文法G(s):
S→(T)|a+S|a
T→T,S|S
消除文法的左递归；
提取公共左因子；
对每个非终结符，写出不带回朔的递归子程序。

23．设文法G(S)：
S→(L)|aS|a
L→L，S|S
(1)消除左递归和回溯；
(2)计算每个非终结符的FIRST和FOLLOW；
(3)构造预测分析表。

24．消除下列文法的左递归.
SSaP|Sf|P
PQbP|Q
QcSd|e

25．已知文法G：
AaABe|a
BBb|d
给出与上述文法等价的LL(1)文法G'。

26．已知文法G[A]：
A→aAB|a
B→Bb|d
（1）构造与G[A]等价的LL(1)文法；
（2）构造G’[A]的预测分析表。

27．程序的文法如下：
PD
DD;D|id:T|procid;D;S
（1）写一个语法制导定义，打印该程序一共声明了多少个id。
（2）写一个翻译方案，打印该程序每个变量id的嵌套深度。

28．构造下面文法的LL（1）分析表。
DTL
Tint|real
LidR
R,idR|