《编译原理》训练题.docx

《编译原理》训练题.docx

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

《编译原理》训练题

《编译原理》训练题

第一章

一．填空题

1．一个编译程序是一个①，编译程序完成从②语言

所写的源程序到③语言所写的目标程序的翻译工作。

2．编译程序的整个工作划分成阶段进行的,典型的划分方法，将编译过程分成六

个阶段：

①，②，③，

④，⑤，⑥。

3．对编译程序而言，输入数据是①，输出结果是②。

4．编译方式与解释方式的根本区别在于。

二判断题

（）1．汇编程序是一个编译程序，它把汇编语言程序翻译成机器语言执行。

（）2．编译程序是一个语言翻译程序，它把汇编语言程序翻译成机器语言执

行。

三．选择题

1．汇编程序是将

（1）翻译成

（2）；编译程序是将（3）翻译成（4）。

可选项有：

a.汇编语言程序b.机器语言程序

c.高级语言程序d.汇编语言程序或机器语言程序

e.汇编语言程序或高级语言程序f.机器语言程序或高级语言程序

2．用高级语言编写的程序经编译后产生的程序叫

（1）。

用不同语言编写的程序产生

（1）后，可用

（2）连接在一起生成机器可执行的程序。

在机器中真正执行的是（3）。

可选项有：

a.源程序b.目标程序c.函数

d.过程e.机器指令代码f.模块

g.连接程序h..程序库

3．编译程序与具体的机器

（1），与具体的语言

（2）。

可选项有：

a.有关b.无关

4．编译程序是一种常用的软件。

可选项有：

a.应用b.系统

5．编译程序生成的目标程序是机器语言的程序。

可选项有：

a.一定b.不一定

四、思考题

1．给出一个典型的编译程序的结构框图。

2．什么是前端和后端？

设想相同的前端不同的后端，相同的后端不同的前端生成的编译程序分别有何特征？

第二章

一．填空题

1.INTOA在每个过程目标程序的入口都有这样一条指令，用以完成①的工作，A域的值为②。

2.OPROO在每个过程目标程序的①都有这样一条指令，用以完成②

的工作。

3．PL/0编译程序运行时的存储分配策略采用栈式动态分配，用①链和②链的方式解决递归调用和非局部变量的引用问题。

4.是构成语言文法的单词，是语法成分的最小单位。

二、思考题

1．若PL/0编译程序运行时的存储分配策略采用栈式动态分配，并用动态链和静态链的方式分别解决递归调用和非局部变量的引用问题，试写出下列程序执行到赋值语句b:

=10时运行栈的布局示意图。

varx,y

procedurep;

vara;

procedureq;

varb;

begin（q）

b:

=10;

end（q）;

procedures;

varc,d;

procedurer;

vare,f;

begin（r）

callq;

end（r）;

begin（s）

callr;

end（s）;

begin（p）

calls;

end（p）;

begin（main）

callp;

end（main）.

2．PL/0编译程序所产生的目标代码是一种假想栈式计算机的汇编语言，请说明该汇编语言中下列指令各自的功能和所完成的操作。

INToA

OPRoo

CALoA

第三章

一．填空题

1．设A是符号串，且A=CD，则X3=。

2、产生式是用于定义的一种书写规则。

3、一个上下文无关文法所含四个组成部分是一组①、一组②、

一组③、一组④、。

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

5．文法G产生的的全体是该文法描述的语言。

6．文法G[S]：

S→Ac|aBA→abB→bc描述的语言L（G[S]）={}。

7．已知文法G[E]：

E：

：

=T|E+T|E-T

T：

：

=F|T*F|T/F

F：

：

=（E）|i

该文法的开始符号（识别符号）是①终结符号集合VT是{②}，非终结符号集合VN是{③}，句型T+T*F+i的简单短语有④.，句柄为⑤。

8．实际使用中，我们将限制文法中不能含有①和②规则。

9．G[E]为:

E->E+T|E-T

T->T*F|T/F|F

F->（E）|i

因为存在推导序列:

E=>E+T=>E+T*F所以句型E+T*F

的短语有:

①

直接短语有:

②句柄为:

③

10．三型文法为：

S->aS|a

所描述的语言是{an|n>=}

11.文法

S->a|^|（T）

T->T,S|S

（1）下面对（a,（a,a）的推导为推导：

S=>（T）=>（T,S）=>（S,S）=>（a,S）=>（a,（T））=>（a,（T,S））

=>（a,（S,S））=>（a,（a,S））=>（a,（a,a））

二判断题

（）1．设G=（VN，VT，P，S），若P中的每一个产生式α→β满足|β|≥|α|,仅

仅S→ε除外，则文法G是上下文无关的或2型文法。

（）2．设G=（{S，A，B}，{a,b}，P，S），其中P由下列产生式组成：

S→aB∣bA

A→a∣aS∣bAA

B→b∣bS∣aBB

文法G是上下文无关的或2型文法。

（）3．设G=（VN，VT，P，S），若P中的每一个产生式α→β满足α是一非

终结符,则文法G是上下文有关的或2型文法。

（）4．若一文法G=（VN，VT，P，S）是上下文无关文法，则该文法G一定是上下文有关文法。

（）5．若一文法G=（VN，VT，P，S）是3型文法，则该文法G一定是上下文有关文法。

（）6．如果一个文法存在某个句子对应两棵不同的语法树，则这个文法一定是二义的。

（）7．∑*具有可数的无穷数量的元素，ε∈∑*。

（）8．文法G描述的语言是由文法的识别符号推出的所有符号串的集合

（）9．一个句型中的最右直接推导称为该句型的句柄。

（）10．已知语言L={anbn|n>=1}，则文法A:

:

=aAb|ε，可以产生语言L。

（）11．文法G[E]为:

E->E+T|E-T

T->T*F|T/F|F

F->（E）|i不是二义的.

三．选择题

1．在编译中产生语法树是为了（）

可选项有：

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

2．文法G描述的语言是的集合。

可选项有：

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

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

c由文法的识别符号推出的所有符号串

d由文法的识别符号推出的所有终结符号串

3．一个语言的文法是。

可选项有：

a唯一的

b不唯一的

c个数有限的

4．已知语言L={anbbn|n>=1},则下述文法中，可以产生语言L。

可选项有：

aZ:

:

=aZb|aAb|bA:

:

=aAb|b

bZ:

:

=aAbA:

:

=aAb|b

cZ:

:

=AbBA:

:

=Aa|aB:

:

=Bb|b

dA:

:

=aAbA:

:

=b

5．设有文法G[I]：

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

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

1．Ab02.a0c013.aaa4.cb10

可选项有：

a.1b.23c.34d.1234

6．给定文法A→Bc|cc，B→c|b下面的符号串中，为该文法句子的是。

1．cc2.bcbc3.bcbcc4.bc

可选项有：

a.1b.12c.14d.124

7．一个句型中的最左称为该句型的句柄。

可选项有：

a.短语b.简单短语c.素短语d.终结符号

8．乔姆斯基把文法分成四种类型，即0型、1型、2型和3型。

3型文法也称为

（1），2型文法是

（2）。

可选项有：

a.上下文无关文法b.上下文有关文法.

c正则文法d.短语文法

9．乔姆斯基的3型语言是这样一种语言，其产生式限制为。

可选项有：

a.A→ab.A→aA→aBc.a→d.

10．.一个文法G包括四个组成部分依次为：

一组

（1），一组

（2），一个（3），以及一个（4）

可选项有：

a.字符串b.字母数字串c.产生式d.结束符号

e.开始符号f.文法g.非终结符号h.终结符号

11．设有文法G[S]：

S：

：

=S*S|S+S|（S）|a

该文法二义性文法。

可选项有：

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

12．正则式的“|”读作，“．”读作，“*”读作。

可选项有：

a．并且b．或者c．连接d．闭包

13．G[E]为:

E->E+T|E-T

T->T*F|T/F|F

F->（E）|i

存在推导序列:

E=>E+T=>E+T*F

则E+T*F是一个

a．句型b．句子

14．已知文法G[E]：

E→T|E+T|E-TT→F|T*F|T/FF→（E）|i

该文法的句型T+T*F+i的直接短语为（①），该文法的句型T+T*F+I句柄为（②）。

（1）句型中第一个T

（2）句型中第二个T（3）T+T（4）T*F

（5）F（6）i（7）T+T*F（8）T*F+i（9）T+T*F+i

可选项有：

①a．

（1）b．

（1）

（2）c．

（1）（4）（6）d．

（1）（4）（6）（9）

②a．（4）b．

（2）c．

（1）d．（6）

四、思考题

1．文法G=（{A,B,C},{a,b,c},P,S）

其中P：

S→Ac|aB

A→ab

B→bc

写出L（G[S]）的全部元素。

2．为只包含数字、加号和减号的表达式，例如9-2+5，3-1，7等构造一个文法。

3．已知文法G[Z]:

（1）Z:

:

=aZb

（2）Z:

:

=ab

写出L（G[Z]）的全部元素。

4．写一文法，使其语言是偶正整数的集合。

要求：

（1）允许0打头

（2） 不允许0打头

5．已知文法G:

〈表达式〉∷=〈项〉|〈表达式〉+〈项〉|〈表达式〉-〈项〉

〈项〉∷=〈因子〉|〈项〉*〈因子〉|〈项〉/〈因子〉

〈因子〉∷=（〈表达式〉）|i

试给出下述表达式的推导及语法树。

（1）i*i

（2）i+（i+i）

6．证明下述文法［〈表达式〉］是二义的。

〈表达式〉∷=a|（〈表达式〉）|〈表达式〉〈运算符〉〈表达式〉

〈运算符〉∷=+|-|*|/

7．令文法G［E］为：

E→T|E+T|E-T

T→F|T*F|T/F

F→（E）|i

证明E+T*F是它的一个句型，指出这个句型的所有短语、直接短语和句柄。

8．一个上下文无关文法生成句子abbaa的推导树如下：

（1）给出该句子相应的最左推导，最右推导。

（2）该文法的产生式集合P可能有哪些元素？

（3）找出该句子的所有短语，简单短语，句柄。

9．给出生成下述语言的上下文无关文法：

（1）{anbnambm|n，m>=0}

（2）{1n0m1m0n|n，m>=0}

10．给出生成下述语言的三型文法：

（1）{an|n=0}

（2）{anbm|n,m>=1}

（3）{anbmck|n,m,k>=0}

第四章

一．填空题

1.引入有穷自动机，为词法分析程序的自动构造寻找特殊的方法和工具，有穷

自动机分两类：

①和②。

2．确定的有穷自动机是一个组。

3.确定有穷自动机的化简，是指①，并且它的状态中

没有两个是②。

4.编译过程的第一个阶段是。

5.扫描器的任务是从①中识别出一个个②。

6．如下有穷自动机：

0,1

1101

Y

该有穷自动机为一个：

①（DFA/NFA），从图中可看出初态集为{②}，终态集为：

{③}，有④个状态。

10011101⑤（能/不能）被该有穷自动机M所识别。

f（A,1）=⑥。

二判断题

（）1．一个确定的有穷自动机（DFA）M是一个五元组：

M=（K，∑，f,S,Z）

其中之一K是有穷集，每个元素称为一个状态，∑为字母表，S∈K是唯

一的一个初态，f是转换函数为一个单值函数，若字母表∑含有n个

输入符，任何一个状态最多有n条弧射出，而且每条弧以一个不同的

输入字符标记。

（）2．一个确定的有穷自动机（DFA）M是一个五元组：

M=（K，∑，f,S,Z）

其中之一K是有穷集，每个元素称为一个状态，∑为字母表，S∈K是唯

一的一个初态，f是转换函数可为一个多值函数，若字母表∑含有n个

输入符，任何一个状态可有n条以上的弧射出，而且每条弧以一个不同

的输入字符标记。

（）3．DFA是NFA的特例，对于每个NFAM,存在一个DFAM’,使得L（M）=L（M’））

（）4．如下有穷自动机是一个DFA.

三．选择题

1．无符号常数的识别和拼数工作通常都在（）阶段完成。

可选项有：

a.词法分析b.语法分析c.语义分析d.代码生成

e.代码优化f.表格管理g.出错管理

2．通常高级语言的词法规则可用正则式描述，词法分析器可用（）来实现。

可选项有：

a.语法树b.有穷自动机c.栈d.堆

3.xyxxy是自动机接受的。

a.可以.b.不可以

4.yyxy是自动机接受的。

a.可以b.不可以

5.指出正规式（ab|b）*c与后面的串不匹配

a.ababbcb.ababc.babcd.c

6.指出正规式（a|b）a+（ba）*与后面的串不匹配

a.bab.baac.aad.bba

四．思考题

1．构造正规式1（0|1）*101相应的DFA.

2．将书中P66图4.16确定化：

3．把下图最小化（书中P66图4.17）：

4．构造一个DFA，它接收Σ={0,1}上所有满足如下条件的字符串：

每个1都有0直接跟在右边。

并给出该语言的正规式。

第五章

一．填空题

1．①是编译程序的核心部分。

目前常用的方法有②

和③分析法。

2.若有文法G[S]:

S→pAS→qBA→cAdA→a

则FIRST{S}={①}FOLLOW{A}={②}

3．LL

（1）文法的含义：

第一个L表明①第二个L表

明②，1表明③。

4．当文法不满足LL

（1）时不能用①自顶向下分析分析，但可用②

自顶向下分析。

5．文法G[S]：

S→Ac|aBA→abB→bc描述的语言L（G[S]）={}。

6．已知文法G[E]：

E：

：

=T|E+T

T：

：

=F|T*F

F：

：

=（E）|i

改写该文法以消除直接左递归，改写后的文法为：

E→①E’，E’→②E’|ε。

二、判断题

（）1.由LL

（1）文法的定义可知若文法中含有间接左递归，该文法肯定是LL

（1）文法。

（）2.若文法是LL

（1）文法，该文法肯定能采用确定的自上向下的语法分析。

三．选择题

1．已知文法G（S）：

S→AB|bCA→b|ε

B→aB|εC→ABa|b

FIRST（S）=

（1）,FIRST（A）=

（2）,FIRST（B）=（3）,FIRST（C）=（4）.

可选项有:

a.{b,ε}b.{a,ε}c.{a,b,ε}d.{a,b,#}e.{a,b}f.{#}

FOLLOW（S）＝（5）,FOLLOW（A）＝（6）,FOLLOW（B）＝（7）,FOLLOW（C）＝（8）．

可选项有：

a．｛b｝　b．｛a，#｝　c．｛a，b，#｝　d．｛#｝

SELECT（S→AB）＝（9）,SELECT（S→bC）＝（10）,

a．｛b｝　b．｛a，#｝　c．｛a，b，#｝　d．｛a,b｝

2．已知文法Ｇ［Ｅ］：

E→TE＇E＇→＋TE＇|εT→FT＇T＇→*FT＇|εF→（E）｜i

可推出ε的非终结符有：

（1）

a．ETFb．E＇T＇　c．EE＇　d．EE＇T＇

FIRST（E）＝｛

（2）｝，FIRST（E＇）={（3）}FIRST（T＇）＝｛（4）｝．

FOLLOW（E）＝｛（5）｝，FOLLOW（T）＝｛（6）｝．FOLLOW（F）＝｛（7）｝

SELECT（F→（E））={（8）}SELECT（F→i）={（9）}

可选项有：

a．ε，＋b．*,εc．），＃d．（，i

e．＃，+,）f．*，+，#，）g．（h．i

3．对于文法Ｇ［Ａ］：

Ａ：

：

＝aABe|Ba

B:

:

=Db|e

有人说：

因为ＦＩＲＳＴ（aABe）∩FOLLOW（A）≠Ф,并且ＦＩＲＳＴ（ＢＡ）∩ＦＯＬＬＯＷ（Ａ）≠Ф，所以文法Ｇ［Ａ］不是ＬＬ（１）文法．

这种说法（）．

可选项有：

a．正确b．不正确

4．下列文法：

Ｓ→ＡＡ　　　Ａ→Ａa|a

不是ＬＬ（１）文法的理由是

（1）

可选项有：

a.FIRST（S）∩FIRST（A）≠Ф

b.FIRST（A）∩FOLLOW（A）≠Ф

c.FIRST（Aa）∩FIRST（a）≠Ф

d.都不是

5．已知文法G（S）：

S→Et|RtT→DR|E

R→Dr|eD→a|bd

（1）FIRST（S）=

（1）,FIRST（T）=

（2）,FIRST®=（3）,FIRST（D）=（4）.

可选项有:

A.{d,e}b.{a,b,d,e,e}c.{a,b}d.{a,b,#}e.{a,b,e}f.{#}

答案：

（１）Ｂ　　（２）Ｅ　（３）Ａ　　（４）Ｃ

（２）ＦＯＬＬＯＷ（Ｓ）＝（１），ＦＯＬＬＯＷ（Ｔ）＝（２），ＦＯＬＬＯＷ（Ｒ）＝（３），ＦＯＬＬＯＷ（Ｄ）＝（４）．

可选项有：

Ａ．｛Ｄ｝　Ｂ．｛Ａ，Ｂ｝　Ｃ．｛Ａ，Ｂ，＃｝　Ｄ｛＃｝　Ｅ．｛Ｄ，＃｝

（３）该文法的ＬＬ（１）分析表为（5）．

可选项有：

Ａ．

Ａ

Ｂ

Ｄ

Ｅ

＃

Ｓ

ＲＴ

ＥＴ

Ｔ

ＤＲ

ＤＲ

Ｅ

Ｒ

ＤＲ

Ｅ

Ｄ

Ａ

ＢＤ

Ｂ．

Ａ

Ｂ

Ｄ

Ｅ

＃

Ｓ

ＲＴ

ＲＴ

ＲＴ

ＥＴ

Ｔ

ＤＲ

ＤＲ

Ｅ

Ｒ

ＤＲ

Ｄ

Ａ

ＢＤ

Ｃ．

Ａ

Ｂ

Ｄ

Ｅ

＃

Ｓ

ＲＴ

ＥＴ

Ｔ

ＤＲ

ＤＲ

Ｅ

Ｒ

Ｅ

Ｅ

ＤＲ

Ｅ

Ｄ

Ａ

ＢＤ

Ｄ．

Ａ

Ｂ

Ｄ

Ｅ

＃

Ｓ

ＲＴ

ＲＴ

ＲＴ

ＥＴ

ＲＴ

Ｔ

ＤＲ

ＤＲ

Ｅ

Ｒ

Ｅ

Ｅ

ＤＲ

Ｄ

Ａ

ＢＤ

6．已知文法Ｇ［Ｅ］：

Ｅ→ＴＥ＇　　　Ｅ＇→＋ＴＥ＇｜Ｅ　　　Ｔ→ＦＴ＇　　Ｆ→（Ｅ）｜ＩＤ　　　ＦＯＬＬＯＷ（Ｆ）＝（１），ＦＩＲＳＴ（Ｔ＇）＝（２）．

可选项有：

Ａ．｛＊，＋｝　　Ｂ．｛＊．Ｅ｝　　Ｃ．｛＋，＃，｝｝　Ｄ．｛＊，＋，＃，｝｝

Ｅ，｛＃，｝｝　　Ｆ．｛＊，＋，＃，｝，ＩＤ｝

四、思考题

1．对下面的文法G:

E→TE’

E’→+E|ε

T→FT’

T’→T|ε

F→PF’

F’→*F’|ε

P→（E）|a|b|∧

（1）计算这个文法的每个非终结符的FIRST集和FOLLOW集。

（2）证明这个文法是LL

（1）的。

（3）构造它的预测分析表。

2．已知文法G[S]如下：

3．S→MH∣a

4．H→LSo∣ε

5．K→dML∣ε

6．L→eHf

7．M→K∣bLM

8．判断该文法是否是LL

（1）文法。

如果是构造LL

（1）分析表。

3.证明下述文法不是LL

（1）的。

S→C$

C→bA|aB

A→a|aC|bAA

B→b|bC|aBB

你能否构造一等价的文法，使其是LL

（1）的？

并给出判断过程。

4．证明表达式文法：

E→E+T∣T

T→T*F∣F

F→（E）∣i

为LL

（1）文法。

第七章

一．填空题

1．自底向上分析方法是一种①的过程，当分析的栈顶符号串形成句柄

时采取②动作。

2．编译程序使用的中间代码有多种形式，常见的有①，②，③，

和树形结构。

3．LR

（1）文法的含义：

L表明自①R表明自上向下的②

，1表明需③。

4．自底向上分析的关键问题是在分析过程中如何确定①，自底向上分析的

移进归约过程是自上向下分析②推导的逆过程。

5．文法LR（0）的分析表中Si中的S表示①i表示②。

6.文法LR（0）的分析表中rj中的r表示。

7．LR分析器的关键部分是的构造。

二判断题

（）20.拓广文法的开始符号S′只会在产生式的左部出现。

（）21.LR（0）项目集规范族的项目类型分为四种：

其中移进项目是形如A->α·aβ,a∈V

（）22.LR项目集规范族的项目类型中归约项目是形如A->β·,β∈V*

（）23.LR项目集规范族的项目类型中待约项目是形如A->α·Bβ,B∈V

三．选择题

1．下列文法：

Ｓ→ＡＡ　　　Ａ→Ａa|a

不是ＬＲ（１）文法，理由是（　　　）

可选项有：

a.FIRST（S）∩FIRST（A）≠Ф

b.FIRST（A）∩FOLLOW（A）≠Ф

c.FIRST（Aa）∩FIRST（a）≠Ф

d.都不是

2．设有文法（0）S`→S

（1）S→rD

（2）D→D,i（3）D→i

如果构造ＬＲ（０）项目集规范族，第一个项目集Ｉ0中应有（１）；第Ｉi项目集中若有一个S→r．D项目，则该项目集中一定还含有

（2）

（1）S`→．S

（2）S`→S．（3）S→．rD

（4）S→r．D（5）S→rD．（6）D→．D,i

（7）D→D．,i（8）D→D,．i（9）D→D,i．

（10）D→．i（11）D→i．

可选项有：

a（１）　（３）

b（１）　　（３）　（4）

c（6）　　（１0）

d（6）　（7）　（9）

3．设有文法G:

（0）S`→S

（1）S→aAd

（2）S→bAc

（3）S→bed（4）A→e

如果构造ＬＲ

（1）项目集规范族，第一个项目集Ｉ0中应有（１）；第Ｉi项目集中若有一个S→a．Ad,#项目，则该项目集中一定还含有

（2）

（1）S`→．S,#

（2）S`→S．,#（3）S→．aAd,#

（4）S→a．Ad,#（5）S→aA．D,#（6）S→aAd．,#

（7）S→．bAc,#（8）S→b．Ac,#（9）S→bA．C,#

（10）S→bAc．,#（11）S→．bed,#（12）．S→b．ed,#

（13）S→be．D,#（14）S→bed.#（15）A→．e,d

（