编译原理复习题及答案

编译原理复习题及答案

一、选择题

1.一个正规语言只能对应(B)

A一个正规文法B一个最小有限状态自动机2.文法G[A]：

ATEA—aBB->AbB->a是(A)

A正规文法B二型文法3.下面说法正确的是(A)

A一个SLR(1)文法一定也是LALR(1)文法B一个LR(1)文法一定也是

LALR(l)文法

4.一个上下文无关文法消除了左递归，提取了左公共因子后是满足

口(1)文法的公)

A必要条件B充分必要条件5.下面说法正确的是(B)

A一个正规式只能对应一个确定的有限状态自动机B一个正规语言可

能对应多个正规文法

6.算符优先分析与规范归约相比的优点是(A)

A归约速度快B对文法限制少7.一个LR(1)文法合并同心集后若不

是LALR(l)文法(B)

A则可能存在移进/归约冲突B则可能存在归约/归约冲突

C则可能存在移进/归约冲突和归约/归约冲突8.下面说法正确的是

ALe某是一个词法分析器的生成器BYacc是一个语法分析器9.下面

说法正确的是(A)

A一个正规文法也一定是二型文法

B一个二型文法也一定能有一个等价的正规文法10.编译原理是对

。。

A、机器语言的执行B、汇编语言的翻译

C、高级语言的翻译

D、高级语言程序的解释执行C.FORTRAN

D.PASCAL

11.(A)是一种典型的解释型语言。A.BASICB.C

12.把汇编语言程序翻译成机器可执行的目标程序的工作是由(B)完成

的。A.编译器B.汇编器C解释器D.预处理器13.用高级语言编写的程序经编

译后产生的程序叫(B)A,源程序B.目标程序C.连接程序14.(C)不是编译

程序的组成部份。A.词法分析程序B.代码生成程序

D.解释程序D.语法分析程序

C.设备管理程序

15.通常一个编译程序中，不仅包含词法分析，语法分析，语义分析，

中间代码生成，代码优化，目标代码生成等六个部份，还应包括(C)。

A.摹拟执行器B.解释器C.表格处理和出错处理D.符号执行器16.编

译程序绝大多数时间花在(D)上。A.出错处理B.词法分析

C.目标代码生成

D.表格管理

17.源程序是句子的集合，(B)可以较好地反映句子的结构。A.线性

表B.树C.彻底图18.词法分析器的输出结果是(D)。A、单词自身值C、

单词的种别编码19.词法分析器不能(D)A.识别出数值常量D.堆

栈

R、单词在符号表中的位置口、单词的种别编码和自身值R.过滤源程

序中的注释D.发现括号不匹配

C.扫描源程序并识别记号

20.文法：G：S—某S某|y所识别的语言是(D)。

A、某y某B、(某y某)某21.如果文法G是无二义的，则它的任何句

子a(A)A.最左推导和最右推导对应的语法树必然相同

B.最左推导和最右推导对应的语法树可能不同C最左推导和最

右推导必然相同

C、某某y某某

D、某ny某n(山0)

D.可能存在两个不同的最左推导，但它们对应的语法树相同22.正

则文法(A)二义性的。

A.可以是B.一定不是

C.一定是

23.(B)这样一些语言，它们能被确定的有穷自动机识别，但不能用

正则表达式表示。A.存在B.不存在C无法判定是否存在24.给定文法A

->bA|ca,为该文法句子的是(C)A.bbaB.cabC.bca

D.cba

25.设有文法G[S]：SSl|SO|Sa|Sc|a|b|c,下列符号串中是该文法的句

子有(D)A.ab0B.a0c01C.a0b0aD.bcl026.文法G产生的(D)的全体是该文法

描述的语言。A.句型B.终结符集C.非终结符集27.若文法G定义的语言

是无限集，则文法必然是(A)A.递归的B.上下文无关的C.二义性的28.

描述一个语言的文法是(B)A,惟一的B.不惟一的29.一个文法所描述的

语言是(A)A.惟一的B.不惟一的30.采用自上而下分析，必须

(A)oA、消除回溯

C、消除右递归

C.可能惟一C.可能惟一

B、消除左递归

D.句子

D.无二义性的

D、提取公共左因子

31.编译过程中，语法分析器的任务是(A)①分析单词的构成②分析

单词串如何构成语句③分析沿句是如何构成程序④分析程序的结构

A.②©B.④C.①②@④D.②③④32.词法分析器的输入是(A)o

A.符号串B.源程序C.语法单位D.目标程序33.两个有穷自动机

等价是指它们的(C)。A.状态数相等

C.所识别的语言相等

B.有向弧数相等

D.状态数和有向弧数相等

34.若状态k含有项目—且仅当输入符号a£FOLLOW(A)

时，才用规则“A—a”归约的语法分析方法是(D)。A.LALR分析法B.

LR(O)分析法C.LR(1)分析法D.SLR⑴分析法35.若a为终结符，则A

-crap为(BA页目。A.归约B.移进

C.接受

D.待约

36.在使用高级语言编程时，首先可通过编译程序发现源程序的全部

和部份(A)错误。A.语法B.语义C.语用D.运行

37.乔姆斯基(Chomky)把文法分为四种类型，即0型、1型、2型、3型。

其中3型文法是(B)A.非限制文法B.正则文法C.上下文有关文法D.上下文无

关文法38.一个句型中的(A)称为该句型的句柄。A.最左直接短语B.最右

直接短语

C.终结符D.非终结符

39.在自底向卜•的语法分析方法中，分析的关键是(D)

A.寻觅句柄B.寻觅句型C.消除递归40.在自顶向下的语法分析方法

中，分析的关键是(C)A.寻觅句柄B.寻觅句型C.消除递归

D.选择候选式D.选择候选式

41.在LR分析法中，分析栈中存放的状态是识别规范句型(C)的DFA

状态。A.句柄B.前缀C.活前缀D.LR(O)项目

42.一个上下文无关文法G包括四个组成部份，它们是一组非终结符

号，一组终结符号，一个开始符号，以及一组(B)A.句子B.产生式C.单词

D.句型43.词法分析器用于识别(C)A.句子B.产生式

C.单词

D.句型D.目标程序D.代码生成D.状态集D.句子

44.编译程序是一种(B)A.汇编程序B.翻译程序

C.解释程序

45.按逻辑上划分，编译程序第三步工作是(A)A.语义分析B.词法分

析C.语法分析46.在语法分析处理中，FIRST集合、FOLLOW集合均是

(B)A.非终结符集B.终结符集C字母表47.编译程序中语法分析器接收以

(A)为单位的输入。A.单词B.表达式C.产生式48.编译过程中，语法

分析器的任务就是(B)A.分析单词是怎样构成的

C.分析语句和说明是如何构成程序的

B.分析单词串是如何构成语句和说明的D.分析程序的结构

D.个数是常量D.图灵机D.语义分析

49.若一个文法是递归的，则它所产生的语言的句子(A)。A.是无穷

多个B.是有穷多个C.是可枚举的50.识别上下文无关语言的自动机是

(C)A.下推自动机B.NFA51.编译原理各阶段工作都涉及(B)A.词法分析B.

表格管理

C.DFA

C.语法分析

52.正则表达式R1和R2等价是指(C)

A.R1和R2都是定义在一个字母表上的正则表达式

B.R1和R2中使用的运算符相同C.R1和R2代表同一正则集D.R1和R2

代表不同正则集

53.已知文法G[S]:S-A1,A—A1|SO|O。与G等价的正规式是(C)

A.O(O|1)某B.1某|0某1C.O(1|10)某154.与(a|b)某(a|b)等价的正规式是

(C)oAa某|b某B.(ab)某(a|b)55.(D)文法不是LL(1)的。A.递归B.右递归

C.(a|b)(a|b)某C.2型

D.l(lOIOl)某OD.(alb)某

D.含有公共左因子的

56.给定文法A—bA|cc,则符号串

①cc②bcbc③bcbcc④bccbcc⑤bbbcc中，是该文法句子的是

(D)A.①B.③④⑤C.②④D.①@57.LR(1)文法都是0

A.无二义性且无左递归

C.无二义性但可能是左递归

B.可能有二义性但无左递归D.可以既有二义性又有左递归

D.7

58.文法E-E+E|E某Eli的句子i某i+i某i有(。棵不同的语法树。

A.1B.3C.559.文法S->aaS|abc定义的语言是(C)。

A.{a2kbe|k>O}B.{akbc|kX)}C.{a2k-lbc|kX)}C.接受项目C.移进/归约

D.{akakbc|k>O}D彳寺约项目D.归约/归约

60.若B为非终结符，则A—.B为(D)。

A.移进项目B.归约项目61.同心集合并可能会产生新的(D)冲突。A.二

义B.移进/移进

62.就文法的描述能力来说，有(C)

A.SLR(l)LR(0)B.LR(l)LR(0)C.SLR(1)LR(1)D.无二义文法

LR(1)63.如图所示自动机M,请问下列哪个字符串不是M所能识别的(D)。

A.bbaaB.abbaC.ababD.aabb

64.有限状态自动机能识别(C)

A.上下文无关语言B.上下文有关语言

C.正规语言

D0型文法定义的语言

65.已知文法G是无二义的，则对G的任意句型a(A)

A.最左推导和最右推导对应的语法树必然相同

B.最左推导和最右推导对应的语法树可能相同C.最左推导和最右推

导必然相同

D.可能存在两个不同的最左推导，但他们对应的语法树相同66.(B)

不是DFA的成份

A.有穷字母表B.多个初始状态的集合

C.多个终态的集合

D.转换函数

D.a+b某c+d

D.(a(b+c)>4-d

67.与逆波兰式(后缀表达式)ab+c某d+对应的中缀表达式是(B)

A.a+b+c某dB.(a+b)某c+dC.(a+b)某(c+d)68.后缀式abc+d+可用表达式

(B)来表示。A.((a+b)c)+dB.(a+(bc))+d69.表达式A某(B~C某

(C/D))的后缀式为(B)。A.ABC-CD/某某B.ABCCD/某-某

C.(a(b+€))-Kj

C.ABC.某CD/某D.以上都不对

70.(D)不是NFA的成份。A.有穷字母表B.初始状态集合C.终止状态

集合D.有限状态集合

二、问答题

1.将文法G图改写为等价的G[S],使GIS]不含左递归和左公共因

子。G[S]：S-bSAe|bAA—Ab|d答：

文法G[S]改写为等价的不含左递归和左公共因子的G[S]为：S

bBB-SAe|AA—dA'

A'—bAg

2.将文法G[S]改写为等价的G1S],使G[S]不含左递归和左公共因

子。G[S]：S—SAe|Ae

A—dAbA|dA|d答：

文法G[S]改写为等价的不含左递归和左公共因子的GTS]为：S

TAeSSTAeS|£ATlA'A'TAB|£BTbA|£

3.将文法G[S]改写为等价的G[S],使GIS]不含左递归和左公共因

子。G[S]：S-[AA—B]|ASB—aB|a答：

文法G⑶改写为等价的不含左递归和左公共因子的G[S]为：S

->[AA.B]A'A'—SA佃B—aB，

BJB|£

4.判断下面文法是否为LL(1)文法，若是,请构造相应的LL(1)分析

表。S—>aH

H—>aMd|dM-Ab|8A-^aM|e答：

首先计算文法的FIRST集和FOLLOW集如下表。

文法的FIRST集和FOLLOW集非终结符FIRST集FOLLOW集

S{a}........{#}…H{#}…{a,d}.….M{a,e,£}{d,b}A{b}.…{a,

e).....由于predict(H—>aMd)predict(H—>d)={a}Cl{d}=

predict(M-Ab)npredict(M一£)={a,e}A{d,b}=predict(A

—aM)npredictA—e)={a}D{e}二所以该文法是LL⑴文法，LL(1)分析表如

下表。adbS—>aH.H—aMd—dM—Ab.—g->£A—aM.5.判断下面

文法是否为LL(1)文法，若是，请构造相应的LL(1)分析表。

S—aDD—STe|£T->bH|HH->dB答：

首先计算文法的HRST集和FOLLOW集如下表。非终结符HRST

集FOLLOW集S{a}{#,b,d,e}.D{a,e}{#,b,d,e}

e—>Ab-^e.#

在项目集10中：有移进项目E一・aTd和归约项目E1•存在移

进■归约冲突，所以G不是LR(0)文法。

*

若产生式排序为：(0)S，TE(l)E-aTd(2)E—e(3)T-Eb(4)T-aG的

LR(0)项目集族及识别活前缀的DFA如下图：

由产生式知：

Follow(E)={#,b}Follow(T)={d}在10,12中：

Follow(E)n{a}={#,阴口归}=在15中：

Follow(E)A{a}={#,b}Cl{a}=Follow(T)A{a}={d}A{a}=

Follow(T)AFollow(E)={d}A{#,b}=

所以在10,12,15中的移进.归约和归约.归约冲突可以由Follow集解决，所以

G，是SLR(l)文法。构造的SLR⑴分析表如下表：

ACTIONGOTOnameabd#ETOS2r2r211acc2s5r2r2433s64s75s5r2r4r243

67rlr3rll5.给出文法G[S]的LR⑴项目集规范族中10项目集的全体

项目。G[S]为：S-BD|DB—aDgD—B

10:

答：10：

16.给出文法G[S]的LR(1)项目集规范族中10项R集的全体项go

G[S]为：S-D;D|DDTDB|BB—a|b

10:

答：I。

17.给出文法G[S]的LR(1)项目集规范族中10项目集的全体项目。

G[S]为：S^S;V|W->VaA|AA->b(S)18

10:

答：10：

18.文法G[M]及其LR分析表如下，请给出对串dbba#的分析过程。

G[M]:1)M—VbA

2)VX)Vf

4)A—a5)A一Aba

6)A一

8ACTIONGOTOnamebda#MAOr3S311acc2S43r24r6S5r665r4r46S7r17S88r5r5

答：对串dbba#的分析过程如下表步骤状态栈文法符号栈剩余输入符号动

作#dbba#移进10#dbba#用V-d归约203#Vbba#移进302#Vbba#用A一£

归约4024#VbAba#50246#VbAba#移进602467#VbAba#移进7024678#VbA#用

A—Aba归约80246#M#用M—VbA归约901接受

19.文法G[S]及其LR分析表如下，请给出对输入串da;aoa#的分析

过程。

G[S]:0)S'—S

l)S—dSoS

2)S^dS

3)S一S;S

V2

4)S^aname012345678dS2S2S2S2aS3r4S7r3rlACTION;S4r4S4r3S4aS3S

3S3S3#accr4r2r3rlGOTOS1568输入串da;aoa#的分析过程如下表：步

骤状态栈文法符号栈

#10#d202#da3023#dS4025#dS;50254#dS;a602543#dS;S702546#dS8025#dSo

90257#dSoa1002573#dSoS1102578#S1201剩余输入符号

da;aoa#a;aoa#;aoa#;aoa#aoa#oa#oa#oa#a####动作移进移进用S—a归约移进

移进用S—a归约用S-S;S归约移进移进用S->a归约用S-dSoS归约接受

20.文法G[M]及其LR分析表如下，请给出对串dada#的分析过程。

G|M]:1)S—VdB

2)VT

3)Vf