编译原理复习题.docx

编译原理复习题.docx

《编译原理复习题.docx》由会员分享，可在线阅读，更多相关《编译原理复习题.docx（45页珍藏版）》请在冰点文库上搜索。

编译原理复习题

一、填空题：

（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≥0B、b2i|i≥0C、b2i+1|i≥0D、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|bA→aAb|bB、A→aAbA→b

C、Z→AbBA→aA|aB→bB|bD、Z→aAbA→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→AAA→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|BaB→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|TT→T*F|T/F|FF→（E）|i

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

2、（5分）对下面的文法G[S]构造状态转换图,并说明符号串aaba是否是该文法接受的句子：

S→aAS→BA→abSA→bBB→bB→cCC→DD→dD→bB

3、（10分）将下面具有的NFA确定化

4、（5分）求出下列文法所产生语言对应的正规式。

S→aAA→bA|aB|bB→aA。

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

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

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

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

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

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

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

a、Z:

:

=ABCc、Z:

:

=ABC|2|4|6|8

C:

:

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

:

=0|2|4|6|8

B:

:

=BA|B0|εB:

:

=BA|B0|0

A:

:

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

:

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

b、Z:

:

=ABCd、Z:

:

=ABC|2|4|6|8

C:

:

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

:

=0|2|4|6|8

B:

:

=BA|B0|0B:

:

=BA|B0|ε

A:

:

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

:

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

4、设有文法G[I]：

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

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

①ab0②a0c01③aaa④bc10

可选项有

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

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

E:

:

=-EEE:

:

=-EE:

:

=a|b|c

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

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

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

一组_____、一个_____、一组_____、一组______。

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

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

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

可选项有：

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

8、下列文法__________二义文法

E:

:

=EiT|TT:

:

=T+F|iF|FF:

:

=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）等价。

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

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

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

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

5（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|bBaA:

:

=xB:

:

=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分，共35分）

1、证明下面文法是二义性的。

S:

:

=ibtSeS|ibtS|a

2、现有文法S:

:

=SaA|AA:

:

=AbB|BB:

:

=cSd|e

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

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

S:

:

=bS|aAA:

:

=aA|bBB:

:

=aA|bC|bC:

:

=bS|aA

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

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

S:

:

=SaP|Sf|PP:

:

=QbP|QQ:

:

=cSd|e

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

a

b

ε

ε

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在基本块出口之后活跃，写出优化后的四元式序列。

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:

:

=ABCB、Z:

:

=ABC|2|4|6|8

C:

:

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

:

=0|2|4|6|8

B:

:

=BA|B0|εB:

:

=BA|B0|0

A:

:

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

:

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

C、Z:

:

=ABCD、Z:

:

=ABC|2|4|6|8

C:

:

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

:

=0|2|4|6|8

B:

:

=BA|B0|0B:

:

=BA|B0|ε

A:

:

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

:

=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→aSS→WS→UU→aV→bVV→acW→aW

其中的全部无用符号是

A、W，V，UB、V，bC、W，V，a,b,cD、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、（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→ABA→bB|AaB→Sb|a

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

1、（10分）将下面具有的NFA确定化和最小化

2、（10分）

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

Z→aBA→aBB→bBB→aAB→b

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

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

3、（10分）设有以下文法G[S]：

S→aAbDe|dA→BSD|eB→SAc|cD|D→Se|

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

（2）该文法是LL

（1）文法吗？

构造LL

（1）分析表

一、选择题（本大题共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→aSS→WS→UU→aV→bVV→acW→aW

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

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

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

a、abbbb、abababc、abbaabd、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}）,该文法描述的语言是（）。

a、{b2i+1|i≥1}b、{b2i+1|i≥0}c、{bi|i≥0}d、{b2i|i≥0}

二、简答题：

（每小题5分，共30分）

1、证明下面文法是二义性的。

P→PaP|PbP|cP|Pe|f

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

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

S→bS|aAA→aA|bBB→aA|bC|bC→bS|aA

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

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

G[S]：

S→ABA→bB|AaB→Sb|a

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

Z→aBA→aBB→bBB→aAB→b

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

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

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

______。

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

可选项有①②③④⑤⑥⑦

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

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

”这种说法___________。

a、不正确b、正确

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

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

4、下列文法__________二义文法

E:

:

=EiT|TT:

:

=T+F|iF|FF:

:

=ET|（

可选项有：

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

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

可选项有：

a、表达式b、产生式c、单词d、语句

6、文法G[Z]：

Z→BeA→Ae|eB→AfD→f中，________是多余产生式

a、Z→Beb、A→Ae|ec、B→Afd、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≥