2013编译原理复习题及答案

1、编译原理复习题及答案、选择题B一个最小有限状态自动机是(A)B一个最小有限状态自动机是(A)B二型文法A一个正规文法文法GA：AAAA正规文法下面说法正确的是(A)A一个SLR(1)文法一定也是LALR(1)文法B一个LR(1)文法一定也是LALR(1)文法一个上下文无关文法消除了左递归，提取了左公共因子后是满足LL(1)文法的(A)A必要条件B充分必要条件下面说法正确的是(B)A一个正规式只能对应一个确定的有限状态自动机B一个正规语言可能对应多个正规文法算符优先分析与规范归约相比的优点是(A)A归约速度快B对文法限制少一个LR(1)文法合并同心集后若不是LALR(1)文法(B)A则可能存在移

2、进/归约冲突B则可能存在归约/归约冲突C则可能存在移进/归约冲突和归约/归约冲突下面说法正确的是(A)ALex是一个词法分析器的生成器BYacc是一个语法分析器下面说法正确的是(A)A一个正规文法也一定是二型文法B一个二型文法也一定能有一个等价的正规文法10.10.编译原理是对(C)。A、机器语言的执行C、高级语言的翻译B、汇编语言的翻译D、高级语言程序的解释执行.用高级语言编写的程序经编译后产生的程序叫(B)A.A.源程序B.目标程序C.连接程序D.解释程序.(C)不是编译程序的组成部分。A.词法分析程序B.代码生成程序C.设备管理程序D.语法分析程序.通常一个编译程序中，不仅包含词法分析，

3、语法分析，语义分析，中间代码生成，代码优化，目标代码生成等六个部分，还应包括(C)。A.模拟执行器B.解释器C.表格处理和出错处理D.符号执行器A.线性表B.树.词法分析器的输出结果是A.线性表B.树.词法分析器的输出结果是(D)。A、单词自身值C、单词的种别编码.词法分析器不能(D)A.识别出数值常量C.扫描源程序并识别记号完全图D.堆栈B、单词在符号表中的位置D、单词的种别编码和自身值B.过滤源程序中的注释发现括号不匹配.文法：G：SfxSxIy所识别的语言是(D)。A、xyxB、(xyx)*C、x*yx*D、xnyxn(nN0).如果文法G是无二义的，则它的任何句子a(A)A.最左推导和

4、最右推导对应的语法树必定相同B.最左推导和最右推导对应的语法树可能不同C.最左推导和最右推导必定相同D.可能存在两个不同的最左推导，但它们对应的语法树相同.正则文法(A)二义性的。A.可以是B.一定不是C.一定是.(B)这样一些语言，它们能被确定的有穷自动机识别，但不能用正则表达式表示A.存在B.不存在C.无法判定是否存在.给定文法A-bAIca,为该文法句子的是(C)C.bcaD.cba下列符号串中是该文法的句子有C.bcaD.cba下列符号串中是该文法的句子有(D)C.a0b0aD.bc10C.可能唯一C.可能唯一.设有文法GS：SaS1|S0|Sa|Sc|a|b|c,A.ab0B.a0c

5、01.描述一个语言的文法是(B)A.唯一的B.不唯一的.一个文法所描述的语言是(A)A.唯一的B.不唯一的.采用自上而下分析，必须.采用自上而下分析，必须(A)。A、消除回溯C、消除右递归.编译过程中，语法分析器的任务是(A)分析单词的构成分析单词串如何构成语句分析语句是如何构成程序分析程序的结构A.B.词法分析器的输入是(A)。A.符号串B.源程序.两个有穷自动机等价是指它们的(C)。A.状态数相等C.所识别的语言相等B、消除左递归D、提取公共左因子C.D.C.语法单位D.目标程序B.有向弧数相等D.状态数和有向弧数相等.若状态k含有项目飞a”，且仅当输入符号aFOLLOW(A)时，才用规则

6、“Aa归约的语法分析方法是(D)。A.LALR分析法B.LR(0)分析法C.LR(1)分析法D.SLR(1)分析法.若a为终结符，则Aa为田)项目。A.归约B.移进C.接受D.待约.在使用高级语言编程时，首先可通过编译程序发现源程序的全部和部分(A)错误。A.语法B.语义C.语用D.运行.乔姆斯基(Chomsky)把文法分为四种类型，即0型、1型、2型、3型。其中3型文法是(B)A.非限制文法B.正则文法C.上下文有关文法D.上下文无关文法.一个上下文无关文法G包括四个组成部分，它们是一组非终结符号，一组终结符号，一个开始符号，以及一组(B)A.句子B.产生式C.单词D.句型34.词法分析器用

7、于识别(C)A.句子B.产生式C.单词D.句型35.编译程序是一种(B)A.汇编程序B.翻译程序C.解释程序D.目标程序36.按逻辑上划分，编译程序第三步工作是(A)A.语义分析B.词法分析C.语法分析D.代码生成.在语法分析处理中，FIRST集合、FOLLOW集合均是(B)A.非终结符集B.终结符集C.字母表D.状态集.编译程序中语法分析器接收以(A)为单位的输入。A.单词B.表达式C.产生式D.句子39.编译过程中，语法分析器的任务就是39.编译过程中，语法分析器的任务就是(B)A.分析单词是怎样构成的C.分析语句和说明是如何构成程序的B.分析单词串是如何构成语句和说明的D.分析程序的结构

8、.若一个文法是递归的，则它所产生的语言的句子(A)。A.是无穷多个A.是无穷多个B.是有穷多个C.是可枚举的D.个数是常量D.图灵机D.语义分析D.图灵机D.语义分析A.下推自动机B.NFAC.DFA.编译原理各阶段工作都涉及(B)A.词法分析B.表格管理C.语法分析.正则表达式R1和R2等价是指(C)R1和R2都是定义在一个字母表上的正则表达式R1和R2中使用的运算符相同R1和R2代表同一正则集R1和R2代表不同正则集.已知文法GS:SfA1,AfA1|S0|0。与G等价的正规式是(C)A.0(0|1)*B.1*|0*1A.0(0|1)*B.1*|0*1C.0(1|10)*1D.1(10|0

9、1)*0与(a|b)*(a|b)等价的正规式是(C)。A.a*|b*与(a|b)*(a|b)等价的正规式是(C)。A.a*|b*B.(ab)*(a|b)C.(a|b)(a|b)*(D)文法不是LL的。A.递归B.右递归C.2型D.(a|b)*D.含有公共左因子的给定文法AfbA|cc,则符号串ccbcbcbcbccbccbccbbbcc中，是该文法句子的是(D)A.B.LR(1)文法都是()无二义性且无左递归无二义性但可能是左递归C.D.B.可能有二义性但无左递归可以既有二义性又有左递归文法EfE+E|E*E|i的句子i*i+i*i有(C)棵不同的语法树。A.1B.A.1B.3C.5D.750

10、.文法SfaaS|abc定义的语言是(C)。C.C.终止状态集合D.有限状态集合51.52.53.54.55.56.57.58.59.60.61.A.a2kbclk0B.akbclk0C.a2k-lbclk0若B为非终结符A.移进项目则A-.B为(D)。B.归约项目C.接受项目同心集合并可能会产生新的(D)冲突。A.二义B.移进/移进C.移进/归约就文法的描述能力来说，有(C)A.SLR(1)uLR(0)B.LR(1)uLR(0)C.SLR(1)uLR(1)如图所示自动机M,请问下列哪个字符串不是M所能识别的(D)。A.bbaaB.abbaD.akakbclk0D.待约项目D.归约/归约D.无

11、二义文法uLR(1)D.aabbC.abab有限状态自动机能识别(C)A.上下文无关语言B.上下文有关语言C.正规语言已知文法G是无二义的，则对G的任意句型&仆)A.最左推导和最右推导对应的语法树必定相同B.最左推导和最右推导对应的语法树可能相同C.最左推导和最右推导必定相同D.可能存在两个不同的最左推导，但他们对应的语法树相同(B)不是DFA的成分A.有穷字母表B.多个初始状态的集合C.多个终态的集合与逆波兰式(后缀表达式)ab+c*d+对应的中缀表达式是(B)A.a+b+c*dB.(a+b)*c+dC.(a+b)*(c+d)后缀式abc+d+可用表达式(B)来表示。A.(a+b)c)+dB

12、.-(a+(bc)+dC.-(a(b+c)+d表达式A*(B-C*(C/D)的后缀式为(B)。A.ABC-CD/*B.ABCCD/*-*C.ABC-*CD/*D.0型文法定义的语言D.转换函数D.a+b*c+dD.(a(b+c)+dD.以上都不对(D)不是NFA的成分。A.有穷字母表B.初始状态集合二、问答题将文法GS改写为等价的GS,使GS不含左递归和左公共因子。GS：SS答：文法GS改写为等价的不含左递归和左公共因子的GS为：SS将文法GS改写为等价的GS,使GS不含左递归和左公共因子。GS：SS答：文法GS改写为等价的不含左递归和左公共因子的GS为：SSSS将文法GS改写为等价的GS,使

13、GS不含左递归和左公共因子。GS：SS答：文法GS改写为等价的不含左递归和左公共因子的GS为：判断下面文法是否为LL(1)文法，若是,请构造相应的LL(1)分析表。答:首先计算文法的FIRST集和FOLLOW集如下表。文法的FIRST集和FOLLOW集非终结符FIRST集FOLLOW集Sa#.Ha，d.#.Ma,e,d，bAa，e.b.由于predict(HaMd)predict(Hd)=ad二0predict(MAb)predict(M)=a,ed,b=0predict(AaM)predict(Ae)=ae=0所以该文法是LL(1)文法，LL(1)分析表如下表。adbe#SaH.HaMdd.

14、MAb.AbAaM.e.判断下面文法是否为LL(1)文法，若是，请构造相应的LL(1)分析表。答:首先计算文法的FIRST集和FOLLOW集如下表。非终结符FIRST集FOLLOW集Sa#,b,d,e.Da，#,b,d,eTb,d,eHd，e由于predict(DSTe)predict(D)=a#,b,d,e=5predict(TbH)predict(TH)=be二0predict(Hd)predict(H)=de二0所以该文法是LL(1)文法，LL(1)分析表如下表:aebd#SaD.DSTeTH.bHH.Hd.6.判断下面文法是否为LL(1)文法，若是，请构造相应的LL(1)分析表。文法的

15、FIRST集和FOLLOW集非终结符FIRST集FOLLOW集Sa.#，bDa，#，bTb.e.Mb.e.Hb，e.由于predict(DSTe)predict(D)=a#,b=0predict(HM)predict(H)=be=0所以该文法是LL(1)文法，LL(1)分析表如下表：aeb#SaD.DSTeTbMMbHHM.7.某语言的拓广文法为:(0(证明G不是LR(0)文法而是SLR(1)文法，请给出SLR(1)分析表。Follow(D)=bFollow(D)=bIo：SfIo：SfS*Db5fBDfdDfBfBaBfG的1区(0)项目集族及识别活前缀的DFA如下图:由产生式知拓广文法G，

16、增加产生式早S在项目集I。中：有移进项目D归约项目D和存在移进-归约和归约-归约冲突，所以G不是LR(O)文法。若产生式排序为：Follow(S)=#Follow(B)=a,#在I。中：Follow(D)d=bd二0Follow(B)d=a,#d二0Follow(D)Follow(B)=ba,#=0在匕中：Follow(S)a=#a二0所以在I0,I3中的移进-归约和归约-归约冲突可以由Follow集解决，所以G是SLR(1)文法,构造的SLR分析表如下表：状态ACTIONGOTObda#SDB0r4S4r6r61231acc2S53S6r24r35r16r5r58.给出与正规式R=(ab)*

17、(alb*)ba等价的NFA。答：与正规式R等价的NFA如下图给出与正规式R=(ab)*lb)*(al(ba)*)a等价的NFA。答：与正规式R等价的NFA如下图给出与正规式R=(aba)*(ba)*lb)b等价的NFA。答：与正规式R等价的NFA如下图11.将下图的NFA确定化为DFA。a答：用子集法确定化如下表IlaIb状态X,1,21,2.1,2,3X1,2.1,2.1,2,311,2,31,2,Y1,2,321,2,Y1,2.1,2,33确定化后如下图：12.将下图的NFA确定化为DFAoba用子集法确定化如下表IIaIb状态X,0,1,30,1,32,3,YX0,1,3.0,1,32

18、,3,Y12,3,Y.1,3.Y.21,3.0.2,Y.32,Y.1,3.Y.4Y0.Y确定化后如下图aa13.某语言的拓广文法G为:证明G不是LR(0)文法而是SLR(1)文法，请给出SLR(1)13.某语言的拓广文法G为:证明G不是LR(0)文法而是SLR(1)文法，请给出SLR(1)分析表。答：拓广文法G，增加产生式S叮在项目集10中:有移进项目T-aBd和归约项目T存在移进-归约冲突，所以G不是LR(0)文法。若产生式排序为：G的1区(0)项目集族及识别活前缀的DFA如下图所示:识别G活前缀的DFA由产生式知：Follow(T)=#,bFollow(B)=d在I。中：Follow(T)

19、a=#,ba=0在匕中：Follow(B)a=da=0Follow(T)a=#,ba二0Follow(B)Follow(T)=db,b=0所以在I0,I2,中的移进-归约和归约-归约冲突可以由Follow集解决，所以G是SLR(1)文法。构造的SLR(1)分析表如下表。SLR(1)分析表nameACTIONGOTOabd#TB0S2r2r211acc2S2r2r4r2433S54S65r1r16r314.某语言的文法G为:证明G不是LR(0)文法而是SLR文法，请给出该文法的SLR分析表。答：拓广文法G,增加产生式SIo：在项目集I。中：Io：有移进项目ETd和归约项目E存在移进-归约冲突，所

20、以G不是LR(0)文法。若产生式排序为：()()()()G的1G的1区(0)项目集族及识别活前缀的DFA如下图:由产生式知：Follow(E)=#，bFollow(T)=d在I0，I2中：Follow(E)=#,b二。在I5中：Follow(E)a=#,ba=0Follow(T)a=da=0Follow(T)Foliow(E)=db,b=0所以在I0,I2,I5中的移进-归约和归约-归约冲突可以由Follow集解决，所以G是SLR(1)文法。构造的SLR(1)分析表如下表：nameACTIONGOTOabd#ET0S2r2r211acc2S5r2r2433S64S75S5r2r4r2436r1

21、r17r315.给出文法66的1区(1)项目集规范族中I0项目集的全体项目。GS为:答：%：%：3/fs,#$-BDfDBfal),#/a/bE一b#/a/bDf-5,/16.给出文法GS的1区(1)项目集规范族中I0项目集的全体项目。GS为:答：%：%：%：Tf，S,D;DSiD,D-*DBD*B,B-*ajBf*b,井A/J#/:/aA井h/aA杵/；力Zb17.文法GM及其LR分析表如下，请给出对串dbba#的分析过程。nameACTIONGOTO答：对串dbba#的分析过程如下表步骤状态栈文法符号栈剩余输入符号动作10#dbba#移进203#dbba#用Vd归约302#Vbba#移进4

22、024#Vbba#用A归约50246#VbAba#移进602467#VbAba#移进7024678#VbAba#用AAba归约80246#VbA#用MVbA归约901#M#接受18.文法GS及其LR分析表如下，请给出对输入串da;aoa#的分析过程。GS:SSSSSSSSSSnameACTIONGOTOda;a#S0S2S3S311S4acc2S2S353r4r4r44S2S365S7S4r26r3r3r37S2S388r1S4r1答：输入串da;aoa#的分析过程如下表:步骤状态栈文法符号栈剩余输入符号动作10#da;aoa#移进202#da;aoa#移进3023#da;aoa#用Sa归约4

23、025#dS;aoa#移进50254#dS;aoa#移进602543#dS;aoa#用Sa归约702546#dS;Soa#用SS;S归约8025#dSoa#移进90257#dSoa#移进1002573#dSoa#用Sa归约1102578#dSoS#用SdSoS归约1201#S#接受19.文法GM及其LR分析表如下，请给出对串dada#的分析过程。GM1S-VdB状态ACTIONGOTOdea#SBV0r3S3121acc2S43r24r6S5r665r4r46S7r17S88r5r5答：对串dada#的分析过程如下表步骤状态栈文法符号栈剩余输入符号动作10#dada#用V归约202#Vdada

24、#移进3024#Vdada#移进40245#Vdada#用Ba归约50246#VdBda#移进602467#VdBda#移进7024678#VdBda#用BBda归约80246#VdB#用SVdB归约901#S#接受.按指定类型给出下列语言的文法。L=anbmcln0,m0)用正规文法。L2=aOnlnbdmIn0,m0用二型文法。答：(1)描述L语言的正规文法如下：aIbibc(2)描述L2语言的二型文法如下：a01101bDDdDId.下列语言或文法确切属于按乔姆斯基(Chomsky)分类的哪种类型,请填在()内。(1)Ll=aOnlnbdmIn0,m0()L2=anbncnbmIn0m0()L3=anbmdn0m0()albla()I1()1()答：Ll=a