编译原理试题

德州学院期末考试试题

（ 1 至 学年第 学期）

课程名称： 考试对象： 试卷类型： （1） 考试时间： 分钟

一、填空题：（10分，第1小题每2个1分，其余每空1分）

1、编译程序一般含有八部分，分别是 、 、

、 、 、 、 、 。

2、编译程序与解释程序的根本区别是

3、一个上下文无关文法G包括四个组成部分依次为：一组_____、一个_____、一组_____、一组______。

4、设G是一个文法，S是文法的开始符号，如果S* X，则称X是 。

二、选择题（本大题共15小题，每小题1分，共15分）

1、编译程序生成的目标程序 是机器语言程序。

A、 一定 B、 不一定

2、设有文法G[S]=（{b},{S,B},S,{S→b|bB, B→bS}）,该文法描述的语言是 。

A、bi | i≥0 B、b2i | i≥0 C、b2i+1 | i≥0 D、b2i+1 | i≥1

3、设有文法G[S]： S→S*S|S+S|（S）|a

该文法 二义性文法

A、是 B、不是 C、无法判断

4、汇编程序是将______翻译成______；编译程序是将_______翻译成__________。

A、汇编语言程序 B、机器语言程序

C、高级语言程序 D、汇编语言或机器语言程序

5、给定文法A→bA|cc, 下面符号串中，为该文法句子的是 。

① cc ② bcbc ③ bcbcc ④ bccbcc ⑤bbbcc

A、① B、①③④⑤ C、①⑤ D、①④⑤ E、①②③④⑤

6、语法分析的常用方法是 。

①自顶向下 ②自底向上 ③ 自左向右 ④自右向左

A、①②③④ B、①② C、③④ D、①②③

7、已知语言L={anbbn|n≥1}，则下述文法中， 可以产生语言L

A、Z→aZb|aAb|b A→aAb|b B、A→aAb A→b

C、Z→AbB A→aA|a B→bB|b D、Z→aAb A→aAb|b

8、下列正规表达式中________与(a|b)*(c|d)等价。

A、（a*|b*）(c|d) B、（a*|b*）*(c|d) C、(ab)*(d|c) D、（a*b*）(cd)

9、算符优先分析法每次都是对 进行归约。

A、最左短语 B、直接短语 C、句柄 D、素短语 E、最左素短语

10、简单优先分析法每次都是对 进行归约

A、最左短语 B、直接短语 C、句柄 D、素短语 E、最左素短语

11、下列文法G[S] ]：S→AA A→Aa|a不是LR（1）文法，理由是

A.、FIRST(S)∩FIRST（A）≠ B、FIRST（A）∩FOLLOW（A）≠

C、FIRST（Aa）∩FIRST（a）≠ D、都不是

12、设有文法G[E]：E→E*E|E+E|（E）|a 该文法 LR（1）文法

A、是 B、不是 C、无法判断

13、对于文法G[A]： A→aABe|Ba B→dB| 有人说，因为FIRST（aABe）∩FOLLOW（A）≠ 并且FIRST（Ba）∩FOLLOW（A）≠，所以文法G[A]不是LL（1）文法。这种说法

A、正确 B、不正确

14、素短语是指_______的短语。

①至少包含一个符号

②至少包含一个非终结符号

③至少包含一个终结符号

④除自身外不再包含其它终结符号

⑤除自身外不再包含其它非终结符号

⑥除自身外不再包含其它短语

⑦除自身外不再包含其它素短语

可选项有：

A、①④ B、①⑤ C、①⑥ D、②④ E、③⑤ F、③⑦ G、②⑦

15、表达式A*（B-C*（C/D））的逆波兰式为

A、 ABC-CD/** B、 ABCCD/*-*

C、 ABC-*CD/* D、都不正确

三、简答题（共35分）

1、 (10分)现有文法G[E]:

E→E+T|E-T|T T→T*F|T/F|F F→(E)|i

画出句型E+F*（E+i）的语法树,找出它的短语，直接短语，句柄和素短语

2、 (5分)对下面的文法G[S]构造状态转换图,并说明符号串aaba是否是该文法接受的句子： S→aA S→B A→abS A→bB B→b B→cC C→D D→d D→bB

3、 (10分)将下面具有的NFA确定化

4、 (5分)求出下列文法所产生语言对应的正规式。S→aA A→bA|aB|b B→aA。

5、 (5分)构造识别下面正规式的NFA （a|b）*ba。

四、 综合题（共40分）

1、（10分）下面的文法G[S]是否是LL（1）文法，说明理由，构造LL（1）分析表

S→aBc|bAB A→aAb|Bb B→cB|

2、（5分）消除下列文法的左递归，消除左递归后判断是否是LL（1）文法。

S→SaB|bB A→S|a B→Ac

3、（5分）构造下面算符文法的优先矩阵，判断是否是算符优先文法

S→A[] A→[ A→aA A→B] B→a

4、（10分）将表达式A+B*(C-D)-E/F↑G分别表示为三元式、四元式、逆波兰式序列

5、（10分）现有文法如下：

S→aS|bS|a 判断该文法是哪一类LR文法，说明理由，并构造相应的分析表。

S

A B

Z a b

a 

 —

欢迎下载 2 德州学院期末考试试题

（ 2 至 学年第 学期）

课程名称： 考试对象： 试卷类型： （1） 考试时间： 分钟

二、选择题（本大题共20小题，每小题1分，共20分）

1、汇编程序是将______翻译成______；编译程序是将_______翻译成__________。

a、汇编语言程序 b、机器语言程序 c、高级语言程序 d汇编语言或机器语言程序

2、描述一个语言的文法是___________。

a、唯一的 b、不唯一的 c、个数有限的

3、生成非0开头的正偶数集的文法是______________。

a、Z::=ABC c、Z::=ABC|2|4|6|8

C::=0|2|4|6|8 C::=0|2|4|6|8

B::=BA|B0|ε B::=BA|B0|0

A::=1|2|3|4|5|6|7|8|9 A::=1|2|3|4|5|6|7|8|9

b、Z::=ABC d、Z::=ABC|2|4|6|8

C::=0|2|4|6|8 C::=0|2|4|6|8

B::=BA|B0|0 B::=BA|B0|ε

A::=1|2|3|4|5|6|7|8|9 A::=1|2|3|4|5|6|7|8|9

4、设有文法G[I]：

I→I0|I1|I a|Ic|a|b|c

下列符号串中是该文法的句子的有___________________。

①ab0 ②a0c01 ③aaa ④bc10

可选项有

a、① b、②③④ c、③④ d、①②③④

5、现有前缀表示的表达式文法G1：

E::=-EE E::=-E E::=a|b|c

则文法的句子—a-bc的所有可能语法树有______棵。

a、1 b、2 c、3 d、4

6、一个上下文无关文法G包括四个组成部分依次为：一组_____、一个_____、一组_____、一组______。

a、字符串 b、字母数字串 c、产生式 d、结束符号 e、开始符号 f、文法 g、非终结符号 h、终结符号

7、语法分析的常用方法是_________：

①自顶向下 ②自底向上 ③自左向右 ④自右向左

可选项有：

a、①②③④ b、①② c、③④ d、①②③

8、下列文法__________二义文法

E::=EiT|T T::=T+F|iF|F F::=E*|(

可选项有： a、是 b、不是 c、无法判断。

9、素短语是指_______的短语。

①至少包含一个符号

②至少包含一个非终结符号

③至少包含一个终结符号 ④除自身外不再包含其它终结符号

⑤除自身外不再包含其它非终结符号

⑥除自身外不再包含其它短语

⑦除自身外不再包含其它素短语

可选项有：

a、①④ b、①⑤ c、①⑥ d、②④ e、③⑤ f、③⑦g、②⑦

10、LR（K）文法是_________。

a、从左到右分析，共经过K步的一种编译方法。

b、从左到右分析，每次向前预测K步的一种编译方法。

c、从左到右分析，每次向貌似句柄的符号串后看K个输入符号的一种编译方法。

d、从左到右分析，每次走K步的一种编译方法。

11、在编译中产生语法树是为了____________。

a、语法分析 b、语义分析 c、词法分析 d、产生目标代码

12、文法的二义性和语言的二义性是两个____________概念。

a、不同 b、相同 c、无法判断

13、下述正规表达式中________与(a*+b)*(c+d)等价。

① a*（c+d）+b（c+d）

② a*（c+d）*+b（c+d）*

③ a*（c+d）+b*（c+d）

④ （a+b）*c+（a+b）*d

⑤ （a*+b）*c+（a*+b）*d

可选项有:a、① b、② c、③ d、④ e、⑤ f、④⑤ g、③④⑤

14、_______这样的语言，他们能被确定的有限自动机识别，但不能用正规表达式表示：

a、存在 b、不存在 c、无法判定是否存在

15、LL（K）文法________二义性的。

a、都是 b、都不是 c、不一定都是