德州学院编译原理题库

德州学院编译原理题库

一、填空题：（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 该文法（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、都不正确

一、选择题（本大题共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、不一定都是

16、下面的文法是__________。S::=aAa|aBb|bAb|bBa A::=x B::=x

可选项有：a、LR（1）文法 b、LALR（1）文法 c、都不是 d、a和b

17、编译过程中，比较常见的中间语言有___________。

①波兰表示

②逆波兰表示

③三元式

④四元式

⑤树形表示

可选项有：a、①③④ b、②③④ c、③④①⑤ d、②③④⑤

18、-a-（b*c/（c-d）+（-b）*a）的逆波兰表示是___________。

a、abc*cd-b-a*+/-- b、a-bc*cd-b-a*+/-

c、a-bc*cd-/b-a*+- d、a-bc*/cd-b-a*+-

德州学院编译原理题库

19、在编译程序中安排中间代码生成的目的是_______________。

①便于进行存储空间的组织

②利于目标代码优化

③利于编译程序的移植

④利于目标代码的移植

⑤利于提高目标代码的质量

可选项有：

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

20、代码优化的主要目标是_____________。

①如何提高目标程序的运行速度

②如何减少目标程序运行所需的空间。

③如何协调①和②

④如何使生成的目标代码尽可能简短

可选项有：

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

一、 单项选择题（20分，每小题1分）

1、 文法G1：P→ aPQR| abR，RQ→ QR，BQ→ bb，bR→ bc，cR→ cc，它是chomsky

哪一型文法？

A、0型 B、1型 C、2型 D、3型

2、编译程序必须完成的工作有

①词法分析 ②语法分析 ③语义分析 ④代码生成 ⑤中间代码生成 ⑥代码优化

①②③④ B、①②③④⑤ C、①②③④⑥ D、①②③④⑤⑥

3、LR（K）文法________二义性的。

A、都是 B、都不是 C、不一定都是

4、语法分析的常用方法是________。

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

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

5、用高级语言书写的源程序都必须经过编译，产生目标代码后才能投入运行，这种说法

A、不正确 B、正确

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

A、Z::=ABC B、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

C、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

7、文法G所描述的语言是 的集合

A、文法G的字汇表V中所有符号组成的符号串

B、文法G的字汇表V的闭包V*中的所有符号串

C、由文法的开始符号推出的所有符号串

D、由文法的开始符号推出的所有终结符号串。

德州学院编译原理题库

8、给定文法G[I]:I→I1|I0|Ia|Ic|a|b|c, 下面符号串中，为该文法句子的是 。

① ab0 ② a0c01 ③aaa ④bc10

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

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

A、存在 B、不存在 C、无法判定是否存在

10、LR（K）文法是_________。

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

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

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

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

11、-a-（b*c/（c-d）+（-b）*a）的逆波兰表示是___________。

A、a-bc*cd-/b-a*+- B、a-bc*/cd-b-a*+-

C、abc*cd-b-a*+/-- D、a-bc*cd-b-a*+/-

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

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

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

①至少包含一个符号

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

③至少包含一个终结符号

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

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

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

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

可选项有：

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

14、算符优先分析属于 分析方法。

A、自顶向下 B、自底向上 C、 自左向右 D、自右向左

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

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

16、文法G[S]：S→aS S→W S→U U→a V→bV V→ac W→aW

其中的全部无用符号是

A、W，V ，U B、V，b C、 W，V，a, b ,c D、W，V，b，c

17、程序基本块是指

A、一个子程序 B、一个仅有一个入口和一个出口的语句

C、一个没有嵌套的程序段

D、一组顺序执行的程序段，仅有一个入口和一个出口

18、设有文法G[Z]：Z→Z*Z|Z+Z|（Z）|a 该文法 二义性文法

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

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

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

20、语法分析的任务是

①分析单词是怎样构成的 ②分析单词串是如何构成语句和说明的

③分析语句和说明是如何构成程序的 ④分析程序的结构

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

德州学院编译原理题库

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

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

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

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

a、最左短语 b、直接短语 c、句柄 d、素短语 e、最左素短语

3、设有文法G[I]：

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

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

①ab0 ②a0c01 ③aaa ④bc10

可选项有

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

4、LR（K）文法________二义性的。

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

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

_____、一组______。

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

g、非终

结符号 h、终结符号

6、文法G所描述的语言是__________的集合

a、文法G的字汇表V中所有符号组成的符号串

b、文法G的字汇表V的闭包V*中的所有符号串

c、由文法的开始符号推出的所有符号串

d、由文法的开始符号推出的所有终结符号串。

7、设有文法G[Z]：Z→Z*Z|Z+Z|（Z）|a 该文法_______二义性文法

a、是 b、不是 c、无法判断

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

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

可选项有：

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

9、LR（K）文法是_________。

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

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

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

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

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

①至少包含一个符号

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

③至少包含一个终结符号

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

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

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

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

可选项有：

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

德州学院编译原理题库

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

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

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

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

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

a、（a*|b*）(c|d) b、（a*|b*）*(c|d) c、(ab)*(d|c) d、（a*b*）(cd)

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

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

16、文法G[S]：S→aS S→W S→U U→a V→bV V→ac W→aW

其中的全部无用符号是（ ）

a、（W，V，U） b、（V，b）c、（W，V，a, b ,c）d、（W，V，b，c）

16、ab3的另一种表示方法是（ ）

a、abbb b、ababab c、abbaab d、aaabbb

17、编译过程中，比较常见的中间语言有___________。

①波兰表示

②逆波兰表示

③三元式

④四元式

⑤树形表示

可选项有：a、①③④ b、②③④ c、③④①⑤ d、②③④⑤

18、-a-（b*c/（c-d）+（-b）*a）的逆波兰表示是___________。

a、abc*cd-b-a*+/-- b、a-bc*cd-b-a*+/-

c、a-bc*cd-/b-a*+- d、a-bc*/cd-b-a*+-

19、在编译程序中安排中间代码生成的目的是_______________。

①便于进行存储空间的组织

②利于目标代码优化

③利于编译程序的移植

④利于目标代码的移植

⑤利于提高目标代码的质量

可选项有：

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

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

2i+12i+1i2ia、{b | i≥1} b、{b | i≥0} c、{b | i≥0} d、{b | i≥0}

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

1、要在某一台机器上为某种语言构造一个编译程序，必须找掌握下述三方面的内容：

______。

①高级语言 ②源语言 ③目标语言 ④程序设计方法 ⑤编译方法 ⑥

测试方法 ⑦机器语言

可选项有 ①②③④⑤⑥⑦

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

2、“用高级语言书写的源程序都必须经过编译，产生目标代码后才能投入运行。”这种

说法___________。

a、不正确 b、正确

3、若一个文法是递归的，则它所产生的句子个数___________。

德州学院编译原理题库

a、必定是无穷的 b、是有限个的 c、根据具体情况而定

4、下列文法__________二义文法

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

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

5、编译程序的语法分析器接受以________为单位的输入，并产生有关信息供以后各阶

段使用。可选项有： a、表达式 b、产生式 c、 单词 d、语句

6、文法G[Z]：Z→Be A→Ae|e B→Af D→f 中，________是多余产生式

a、 Z→Be b、 A→Ae|e c、B→Af d、D→f

7、算符优先文法属于________。

a、自顶向下语法分析法 b、LR分析法 c、SLR分析法 d、自底向上语法分

析法

8、设有文法G[S]=（{a}，{S,B}，S，{S→a|aB, B→aS}）,该文法描述的语言是_____

a、{ai|i≥0} b、{ a2i|i≥0} c、{ a2i+1|i≥0} d、{ a2i+1|i≥1}

9、描述语言L={ambn|n≥m≥1}的文法是__________

a、Z→ABb b、Z→ABb c、Z→Ab d、Z→aAb

A→aA|a A→Aa|a A→aAb|a A→Ab|aAb|ε

B→bB|b B→aBb|b

10、一个句型中的最左_______称为该句型的句柄。

a、短语 b、直接短语 c、素短语 d、终结符号

11、通常高级语言的词法规则可用正规式描述，词法分析器可用_________来实现

a、语法树 b、有限自动机 c、栈 d、堆

12、文法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、都不是

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

①至少包含一个符号

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

③至少包含一个终结符号

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

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

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

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

可选项有：

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

14、给定文法G[S]：S→ACc A→aA|Sb C→Def D→hACDd|eC| E→bDe|

ε 该文法是____________。 （1）右线性文法 （2）前后文无关文法 （3）左递

归文法 （4）LL（1）文法

可选项有：

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

15、算符文法是指____________的文法。

①没有形如U→ VW 的规则 （U、V、W为非终结符）

②终结符号集中任意两个符号对之间至多有一种优先关系成立

德州学院编译原理题库

③没有相同的规则右部

④没有形如U→ε的规则

可选项有

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

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

a、（a*|b*）(c|d) b、（a*|b*）*(c|d) c、(ab)*(d|c) d、（a*b*）(cd)

17、若一个句型中出现了某一产生式的右部，则此右部_______是该句型的句柄

a、一定 b、不一定

18、前后文无关文法和正规文法所产生的语言类相比_______

a、前后文无关文法产生的语言类大 b、正规文法产生的语言类大

c、两者产生的语言类一样大 d、无法比较

19、编译过程中，比较常见的中间语言有___________。

①波兰表示

②逆波兰表示

③三元式

④四元式

⑤树形表示

可选项有：a、①③④ b、②③④ c、③④①⑤ d、②③④⑤

20、LL（1）文法的条件是_______________。

a、对形如U→X1|X2| |Xn的规则，要求FIRST（Xi）)∩FIRST (Xj)= (i≠j)

b、对形如U→X1|X2| |Xn的规则 若Xi * ε 则要求FIRST(Xj) ∩FOLLOW (U)=

c、a和b

d、都不是

一、 填空题（每空1分，共20分）

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

2、文法、 文法。

3、设有文法G[I]：

I→I1|I0|Ia|Ic|a|b|c ,下列符号串中是该文法的句子的有

（1）ab0 (2)a0c01 (3)aaa (4)bc10

4、一个上下文无关文法G包含四个组成部分依次为：一组，一组，一个 ，以及一组 。

5、确定的有穷自动机是一个，通常表示为。

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

是 、 、 、 、 、 、 、。

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

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

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

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

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

3、设有文法G[I]：

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

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

德州学院编译原理题库

①ab0 ②a0c01 ③aaa ④bc10

可选项有

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

4、生成非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

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

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

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

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

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

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

7、下列文法__________二义文法

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

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

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

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

可选项有：

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

9、LR（K）文法是_________。

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

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

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

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

①至少包含一个符号

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

③至少包含一个终结符号

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

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

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

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

可选项有：

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

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

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

德州学院编译原理题库

12、在编译中产生语法树是为了____________。 a、语法分析 b、语义分析 c、词法分析 d、产生目标代码 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、③④⑤ 17、_______这样的语言，他们能被确定的有限自动机识别，但不能用正规表达式表示： a、存在 b、不存在 c、无法判定是否存在 15、LL（K）文法________二义性的。 a、都是 b、都不是 c、不一定都是 16、下面的文法是__________。S::=aAa|aBb|bAb|bBa A::=x B::=x 可选项有：a、LR（1）文法 b、LALR（1）文法 c、都不是 d、a和b 17、编译过程中，比较常见的中间语言有___________。 ①波兰表示 ②逆波兰表示 ③三元式 ④四元式 ⑤树形表示 可选项有：a、①③④ b、②③④ c、③④①⑤ d、②③④⑤ 18、-a-（b*c/（c-d）+（-b）*a）的逆波兰表示是___________。 a、abc*cd-b-a*+/-- b、a-bc*cd-b-a*+/- c、a-bc*cd-/b-a*+- d、a-bc*/cd-b-a*+- 19、在编译程序中安排中间代码生成的目的是_______________。 ①便于进行存储空间的组织 ②利于目标代码优化 ③利于编译程序的移植 ④利于目标代码的移植 ⑤利于提高目标代码的质量 可选项有： a、②④ b、①②③ c、③④① d、②③④⑤ 20、代码优化的主要目标是_____________。 ①如何提高目标程序的运行速度 ②如何减少目标程序运行所需的空间。 ③如何协调①和② ④如何使生成的目标代码尽可能简短 可选项有： a、②④ b、①②③ c、③④① d、②③④ 一、 选择题（本大题共20小题，每小题1分，共20分） 1、素短语是指_______的短语。 ①至少包含一个符号 ②至少包含一个非终结符号

德州学院编译原理题库

③至少包含一个终结符号

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

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

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

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

可选项有：

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

2、表达式ab+cd+*的逆波兰式表达式所表示的中缀形式的表达式是

A、 a+b+c*d B、 (a+b)*(c+d)

C、 (a+b)*c+d D、a+b*c+d

3、Chomsky的3型语言是这样一种语言，其产生式限制为（ 、 、 为字符串）。

A、 A→ B、 A→a A→aB

C、 → D、 A →

4、设有文法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

5、设有文法G[S]：

S→S*S|S+S|（S）|a

该文法 二义性文法

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

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

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

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

① cc ② bcbc ③ bcbcc ④ bccbcc ⑤bbbcc

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

8、递归下降分析语法分析的属于分析方法。

A、自顶向下 B、自底向上 C、 自左向右 D、自右向左

9、已知语言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

10、若一个句型中出现了某一产生式的右部，则此右部________是句柄。

A、一定 B、不一定

11、考虑文法G[A]：A→A∨B|B C→∧D B→BC| D→（A）|i, 该文法文法。

A、是 B、不是

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

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

13、下列文法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、都不是

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

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

15、对于文法G[A]

A→ABe|Ba B→dB|

德州学院编译原理题库

有人说，因为FIRST（aABe）∩FOLLOW（A）≠ 并且FIRST（Ba）∩FOLLOW（A）≠ ，所以文法G[A]不是LL（1）文法。这种说法

A、正确 B、不正确

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

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

17、若一个句型中出现了某一产生式的右部，则此右部_______是该句型的句柄

A、一定 B、不一定

18、前后文无关文法和正规文法所产生的语言类相比_______

A、前后文无关文法产生的语言类大 B、正规文法产生的语言类大

C、两者产生的语言类一样大 D、无法比较

19、编译过程中，比较常见的中间语言有___________。

①波兰表示

②逆波兰表示

③三元式

④四元式

⑤树形表示

可选项有：A、①③④ B、②③④ C、③④①⑤ D、②③④⑤

20、LL（1）文法的条件是_______________。

A、对形如U→X1|X2| |Xn的规则，要求FIRST（Xi）)∩FIRST (Xj)= (i≠j)

B、对形如U→X1|X2| |Xn的规则 若Xi * ε 则要求FIRST(Xj) ∩FOLLOW (U)=

C、a和b

D、都不是

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

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

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

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

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

3、下述正规表达式中________与(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、③④⑤

4、______这样的语言，他们能被确定的有限自动机识别，但不能用正规表达式表示： a、存在 b、不存在 c、无法判定是否存在

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

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

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

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

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

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

7、下列文法__________二义文法

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

德州学院编译原理题库

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

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

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

可选项有：

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

9、LR（K）文法是_________。

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

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

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

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

①至少包含一个符号

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

③至少包含一个终结符号

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

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

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

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

可选项有：

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

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

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

12、汇编程序是将______翻译成______；编译程序是将_______翻译成__________。 a、汇编语言程序 b、机器语言程序 c、高级语言程序 d汇编语言或机器语言程序

13、设有文法G[I]：

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

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

①ab0 ②a0c01 ③aaa ④bc10

可选项有

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

14、生成非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

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

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

16、下面的文法是__________。S::=aAa|aBb|bAb|bBa A::=x B::=x

德州学院编译原理题库

可选项有：a、LR（1）文法 b、LALR（1）文法 c、都不是 d、a和b

17、编译过程中，比较常见的中间语言有___________。

①波兰表示

②逆波兰表示

③三元式

④四元式

⑤树形表示

可选项有：a、①③④ b、②③④ c、③④①⑤ d、②③④⑤

18、-a-（b*c/（c-d）+（-b）*a）的逆波兰表示是___________。

a、abc*cd-b-a*+/-- b、a-bc*cd-b-a*+/-

c、a-bc*cd-/b-a*+- d、a-bc*/cd-b-a*+-

19、在编译程序中安排中间代码生成的目的是_______________。

①便于进行存储空间的组织

②利于目标代码优化

③利于编译程序的移植

④利于目标代码的移植

⑤利于提高目标代码的质量

可选项有：

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

20、代码优化的主要目标是_____________。

①如何提高目标程序的运行速度

②如何减少目标程序运行所需的空间。

③如何协调①和②

④如何使生成的目标代码尽可能简短

可选项有：

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

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

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

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

2、汇编程序是将______翻译成______；编译程序是将_______翻译成__________。 a、汇编语言程序 b、机器语言程序 c、高级语言程序 d汇编语言或机器语言程序

3、设有文法G[I]：

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

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

①ab0 ②a0c01 ③aaa ④bc10

可选项有

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

4、生成非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

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

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

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

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

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

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

7、下列文法__________二义文法

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

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

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

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

可选项有：

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

9、LR（K）文法是_________。

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

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

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

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

①至少包含一个符号

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

③至少包含一个终结符号

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

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

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

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

可选项有：

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

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

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

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

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

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、③④⑤

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

德州学院编译原理题库

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

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

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

16、下面的文法是__________。S::=aAa|aBb|bAb|bBa A::=x B::=x

可选项有：a、LR（1）文法 b、LALR（1）文法 c、都不是 d、a和b

17、编译过程中，比较常见的中间语言有___________。

①波兰表示

②逆波兰表示

③三元式

④四元式

⑤树形表示

可选项有：a、①③④ b、②③④ c、③④①⑤ d、②③④⑤

18、-a-（b*c/（c-d）+（-b）*a）的逆波兰表示是___________。

a、abc*cd-b-a*+/-- b、a-bc*cd-b-a*+/-

c、a-bc*cd-/b-a*+- d、a-bc*/cd-b-a*+-

19、在编译程序中安排中间代码生成的目的是_______________。

①便于进行存储空间的组织

②利于目标代码优化

③利于编译程序的移植

④利于目标代码的移植

⑤利于提高目标代码的质量

可选项有：

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

20、代码优化的主要目标是_____________。

①如何提高目标程序的运行速度

②如何减少目标程序运行所需的空间。

③如何协调①和②

④如何使生成的目标代码尽可能简短

可选项有：

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

二、简答题：（每小题5分，共30分）

1、 证明下面文法是二义性的。P::=PaP|PbP|cP|Pe|f

2、设一文法S→AB S→c A→bA A→a B→aSb B→c 对于句子bbaacb写出其全部短语，直接短语和句柄。

3、求出下列文法所产生语言对应的正规式。

S::=aA A::=bA|aB|b B::=aA

4、表达式（a+b）*c/d-e*f分别表示三元式、四元式、逆波兰式序列

nmmn5、写一个文法使其语言为L(G)={ abab | m,n≥1}。

6、给出与下图的NFA等价的正规式。

德州学院编译原理题库

c

三、问答题：(共计50分)

1、已知文法G S::=aBc|bAB A::=aAb|b B::=b|

构造预测分析表并给出输入串baabbb分析过程。（10分）

2、 正规式（（0*|1）（1*0））*（10分）

（1） 构造该正规式所对应的NFA（画出状态转换图）。

（2） 将所求的NFA确定化。（画出确定化的状态转换图）。

3、 若有文法G（S）的产生式如下：S::=bASB|bA A::=dSa|b B::=cAa|c构造识别所

有项目集规范族的DFA。（15分）

（1） 判断该文法是否是LR（0）文法，说明理由。

（2） 判断该文法是否是SLR（1）文法，说明理由。

（3） 判断该文法是否是LR（1）文法，说明理由。

（4） 判断该文法是否是LALR（1）文法，说明理由。

4、 设已给文法G: E::=E+T E::=T T::=T*F T::=F F::=(E) F::=i

构造此文法的算符优先矩阵。（15分）

三、简答题（共35分）

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

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

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

6、 (5分)对下面的文法G[S]构造状态转换图,并说明符号串aaba是否是该文法接受

的句子： S→aA S→B A→abS A→bB B→b B→cC C→D D→d D→

bB

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

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

*9、 (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文法，说明理由，并构造相应的分析表。

二、简答题：（每小题5分，共35分）

1、 证明下面文法是二义性的。S::=ibtSeS|ibtS|a

2、 现有文法S::=SaA|A A::=AbB|B B::=cSd|e

请证实是文法的一个句型，并写出该句型的所有短语、素短语以及句柄。

3、 求出下列文法所产生语言对应的正规式。

S::=bS|aA A::=aA|bB B::=aA|bC|b C::=bS|aA

4、 将表达式((a*d+c)/d+e)*f+g分别表示三元式、四元式、逆波兰式序列

5、 消除下列文法的左递归。

S::=SaP|Sf|P P::=QbP|Q Q::=cSd|e

6、 给出与下图的NFA等价的正规文法。

7、对基本块P画出DAG图

B:=3

D:=A+C

E::=A*C

F:=E+D

G:=B*F

H:=A+C

I:=A*C

J:=H+I

K:=B*5

L:=K+J

M:=L

假定只有L在基本块出口之后活跃，写出优化后的四元式序列。

三、问答题：（共计45分）

1、 已知文法G A::=aABe|a B::=Bb|d

（1） 给出与上述文法等价的LL（1）文法G’。

（2） 构造预测分析表并给出输入串aade#分析过程。（10分）

2、 设已给文法G: E::=E+T E::=T T::=T*F T::=F F::=P↑F F::=P P::=(E)

P::=i

构造此文法的算符优先矩阵。（10分）

****3、 有正规式babb(abb)

（1） 构造该正规式所对应的NFA（画出状态转换图）。

（2） 将所求的NFA确定化。（画出确定化的状态转换图）。

（3） 将所求的NFA最小化。（画出最小化后的状态转换图）。（10分）

4、 若有文法G（S）的产生式如下：S::=L=R S::=R L::=*R L::=i R::=L,构造

德州学院编译原理题库

识别所有项目集规范族的DFA。（15分）

（1） 判断该文法是否是LR（0）文法，说明理由。

（2） 判断该文法是否是SLR（1）文法，说明理由。

（3） 判断该文法是否是LR（1）文法，说明理由。

判断该文法是否是LALR（1）文法，说明理由

二、（简答题，共计20分）

1、(10分)已知文法G（T)： T→T*F|F F→F↑P|P P→(T)|i

(1)写出句型T *P↑（T*F）推导过程，画出语法树；

(2)写出句型T *P↑（T*F）的短语、直接短语、句柄和素短语。

2、(5分)构造识别下面正规式的NFA

b（aa|bb）*ab

3、（5分）消除文法G[S]的左递归

G[S]：S→AB A→bB|Aa B→Sb|a

三、（综合题，共计30分）

1、

2、(10分)

（1）对下面的文法G[Z]

Z→aB A→aB B→bB B→aA B→b

构造状态转换图,并说明符号串aaaabbb是否是该文法接受的句子

（2） 写出G[Z]文法相应的正规式：

3、（10分）设有以下文法G[S]：S→aAbDe|d A→BSD|e B→SAc|cD| D→Se|

（1）求出文法中每个非终结符的FOLLOW集

（2）该文法是LL（1）文法吗？构造LL（1）分析表

四、（综合题，共计30分）

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

2、（10分）对基本块P画出DAG图

B:=3

D:=A+C

E::=A*C

F:=E+D

G:=B*F

H:=A+C

I:=A*C

J:=H+I

K:=B*5

德州学院编译原理题库

L:=K+J

M:=L

假定只有L在基本块出口之后活跃，写出优化后的四元式序列。

3、（10分）对于文法G[S]：S→aBb | aAa |bAb|bBa A→x B→x

（1）判断该文法是否是LR（1）文法，构造LR（1）分析表

（2）判断该文法是否是LALR（1）文法，说明理由

二、简答题：（每小题5分，共30分）

1、证明下面文法是二义性的。P→PaP|PbP|cP|Pe|f

2、设一文法E→T|E+T|E-T T→F|T*F|T/F F→(E)|i 证明E+T*(E-T)是它的一个句型，并指出该句型的全部短语，直接短语，句柄和素短语。

3、求出下列文法所产生语言对应的正规式。

S→bS|aA A→aA|bB B→aA|bC|b C→bS|aA

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

5、消除文法G[S]的左递归(G[S])

G[S]：S→AB A→bB|Aa B→Sb|a

6、对下面的文法G[Z]

Z→aB A→aB B→bB B→aA B→b

构造状态转换图,并说明符号串aaaabbb是否是该文法接受的句子

三、问答题：(共50分)

1、已知文法G S::=bBc|aAB A::=bAa|a B::=a|

写出所有非终结符号的First集和Follow集，构造预测分析表并给出输入串abbaaa分析过程。（10分）

2、正规式0（0|1）*1

构造该正规式所对应的NFA（画出状态转换图）。

将所求的NFA确定化和最小化。（分别画出确定化和最小化的状态转换图）。（10分）

3、若有文法G（S）的产生式如下：S::=bASB|bA A::=dSa|b B::=cAa|c构造识别所有项目集规范族的DFA。（20分）

判断该文法是否是LR（0）文法，说明理由。

判断该文法是否是SLR（1）文法，说明理由。

判断该文法是否是LR（1）文法，说明理由。

判断该文法是否是LALR（1）文法，说明理由。

4、简述编译的整个过程（10分）。

二、简答题：（每小题5分，共30分）

1、对于下面的文法G[S]

S→Sa|Ab|b|c A→Bc|a B→Sb|b

构造状态转换图,并说明符号串bcbabcba是否是该文法接受的句子

2、设一文法G[T]：T→T*F|F F→F↑P|P P→(T)|i 证明T*P↑(T*F)是它的一个句型，并指出该句型的全部短语，直接短语，句柄和素短语。

3、求出下列文法所产生语言对应的正规式。

Z→aZ|bZ|aA A→aB B→aA|b

4、将表达式（（A+B*D）/E+F）*F+G^E分别表示为三元式、四元式、逆波兰式序列。

5、（5分）消除文法G[S]的左递归

G[S]：S→SA|A A→SB|B|(S)|() B→[S] | [ ]

6、（5分）对下面的文法G[E]

本文来源：https://www.bwwdw.com/article/j7xe.html