《编译原理复习题及答案解析.docx》由会员分享，可在线阅读，更多相关《编译原理复习题及答案解析.docx（10页珍藏版）》请在三一办公上搜索。
1、编译原理复习题及答案一、选择题1. 一个正规语言只能对应(B)A一个正规文法B一个最小有限状态自动机2.文法GA：AfAfaBBfAbBa是（八）A正规文法B二型文法3.下面说法正确的是（八）A一个SLR(1)文法一定也是LALR(1)文法B一个LR(1)文法一定也是LALR(1)文法4.一个上下文无关文法消除了左递归，提取了左公共因子后是满足LL(1)文法的（八）A必要条件B充分必要条件5.下面说法正确的是(B)A一个正规式只能对应一个确定的有限状态自动机B一个正规语言可能对应多个正规文法6.算符优先分析与规范归约相比的优点是（八）A归约速度快B对文法限制少7.一个LR(I)文法合并同心集后
2、若不是LALR(1)文法(B)A则可能存在移进/归约冲突B则可能存在归约/归约冲突C则可能存在移进/归约冲突和归约/归约冲突8.下面说法正确的是（八）ALe某是一个词法分析器的生成器BYacc是一个语法分析器9.下面说法正确的是（八）A一个正规文法也一定是二型文法B一个二型文法也一定能有一个等价的正规文法10.编译原理是对(C)。A、机器语言的执行B、汇编语言的翻译C、高级语言的翻译D、高级语言程序的解释执行C.FORTRAND.PASCAL11 .（八）是一种典型的解释型语言。A.BASICB.C12 .把汇编语言程序翻译成机器可执行的目标程序的工作是由(B)完成的。A.编译器B.汇编器C.
3、解释器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.词法分析器
4、的输出结果是(D)。A、单词自身值C、单词的种别编码19.词法分析器不能(D)A.识别出数值常量D.堆栈B、单词在符号表中的位置D、单词的种别编码和自身值B.过滤源程序中的注释D.发现括号不匹配C.扫描源程序并识别记号20.文法：G：Sf某S某Iy所识别的语言是(D)。A、某y某B、(某y某)某21.如果文法G是无二义的，则它的任何句子（八）.最左推导和最右推导对应的语法树必定相同B.最左推导和最右推导对应的语法树可能不同C.最左推导和最右推导必定相同C、某某y某某D、某ny某n(n0)D.可能存在两个不同的最左推导，但它们对应的语法树相同22.正则文法（八）二义性的。A.可以是B.一定不是C
5、. 一定是23. (B)这样一些语言，它们能被确定的有穷自动机识别，但不能用正则表达式表示。A.存在B.不存在C.无法判定是否存在24.给定文法AfbAba,为该文法句子的是(C)A.bbaB.cabC.bcaD. cba25 .设有文法GS:SSlSOSaScabc,下列符号串中是该文法的句子有(D).abOB.a0c01C.aObOaD.be1026.文法G产生的(D)的全体是该文法描述的语言。.句型B.终结符集C.非终结符集27.若文法G定义的语言是无限集，则文法必然是（八）A.递归的B.上下文无关的C.二义性的28.描述一个语言的文法是(B)A.唯一的B.不唯一的29.一个文法所描述的
6、语言是（八）A.唯一的B.不唯一的30.采用自上而下分析，必须（八）。A、消除回溯C、消除右递归C.可能唯一C.可能唯一B、消除左递归D.句子D.无二义性的D、提取公共左因子31 .编译过程中，语法分析器的任务是（八）分析单词的构成分析单词串如何构成语句分析语句是如何构成程序分析程序的结构A.B.(4)C.D.32.词法分析器的输入是（八）0A.符号串B.源程序C,语法单位D.目标程序33.两个有穷自动机等价是指它们的(C)。A,状态数相等C.所识别的语言相等B.有向弧数相等D.状态数和有向弧数相等34.若状态k含有项目“Afa”，且仅当输入符号aFOLLOW（八）时，才用规则“A-a”归约的
7、语法分析方法是(D)。.LALR分析法BLR(O)分析法C.LR(I)分析法D.SLR(I)分析法35.若a为终结符，则Afaa为(B)项目。A.归约B.移进C.接受D.待约36 .在使用高级语言编程时,首先可通过编译程序发现源程序的全部和部分（八）错误。.语法B.语义C.语用D.运行37 .乔姆斯基(Chomky)把文法分为四种类型，即0型、1型、2型、3型。其中3型文法是(B)A.非限制文法B.正则文法C.上下文有关文法D.上下文无关文法38.一个句型中的（八）称为该句型的句柄。A.最左直接短语B.最右直接短语C.终结符D.非终结符39 .在自底向上的语法分析方法中，分析的关键是(D)A.
8、寻找句柄B.寻找句型C.消除递归40.在自顶向下的语法分析方法中，分析的关键是(C)A.寻找句柄B.寻找句型C.消除递归D.选择候选式I).选择候选式41 .在LR分析法中，分析栈中存放的状态是识别规范句型(C)的DFA状态。A.句柄B.前缀C.活前缀D.LR(0)项目42 .一个上下文无关文法G包括四个组成部分，它们是一组非终结符号，一组终结符号，一个开始符号，以及一组(B)A.句子B.产生式C.单词D.句型43.词法分析器用于识别(C)A.句子B.产生式C.单词D.句型D.目标程序D.代码生成D.状态集D.句子44 .编译程序是一种(B)A.汇编程序B.翻译程序C.解释程序45 .按逻辑上
9、划分，编译程序第三步工作是（八）A.语义分析B.词法分析C.语法分析46.在语法分析处理中，FIRST集合、FOLLoW集合均是(B)A.非终结符集B.终结符集C.字母表47.编译程序中语法分析器接收以（八）为单位的输入。A.单词B.表达式C产生式48.编译过程中，语法分析器的任务就是(B)A.分析单词是怎样构成的C.分析语句和说明是如何构成程序的B.分析单词串是如何构成语句和说明的D.分析程序的结构D.个数是常量D.图灵机D.语义分析49 .若一个文法是递归的，则它所产生的语言的句子（八）。A.是无穷多个B.是有穷多个C.是可枚举的50.识别上下文无关语言的自动机是(C)A.下推自动机B.N
10、FA51.编译原理各阶段工作都涉及(B)A.词法分析B.表格管理C.DFAC.语法分析52.正则表达式Rl和R2等价是指(C)A. Rl和R2都是定义在一个字母表上的正则表达式B. Rl和R2中使用的运算符相同C.Rl和R2代表同一正则集D.Rl和R2代表不同正则集53.已知文法GS:SfALAfAllSoO0与G等价的正规式是(C)A.0(01)某BJ某|0某ICO(IllO)某154.与(ab)某(ab)等价的正规式是(C)。A.a某Ib某B.某b)某(ab)55.(D)文法不是LL(I)的。A.递归B.右递归C. (ab)(ab)某C.2型D. 1(1001)某0D.(ab)某D.含有公
11、共左因子的56 .给定文法AfbAICc,则符号串CCbcbcbcbccbccbccbbbcc中，是该文法句子的是(D)A.B.C.D.57.LR(I)文法都是()A.无二义性且无左递归C.无二义性但可能是左递归57 可能有二义性但无左递归D.可以既有二义性又有左递归D.758.文法E-E+EIE某Eli的句子i某i+i某i有(C)棵不同的语法树。A.IB.3C.559.文法S-aaSabc定义的语言是(C)0A.a2kbck0B.akbck0C.a2kTbckOC.接受项目C.移进/归约D.akakbckOD.待约项目D.归约/归约60.若B为非终结符，则Af.B为(D)。A.移进项目B.归
12、约项目61.同心集合并可能会产生新的(D)冲突。A.二义B.移进/移进62.就文法的描述能力来说，有(C).SLR(I)LR(O)B.LR(I)LR(O)C.SLR(I)LR(I)D.无二义文法LR(1)63.如图所示自动机M,请问下列哪个字符串不是M所能识别的(D)。A.bbaaB.abbaC.ababD.aabb64 .有限状态自动机能识别(C)A.上下文无关语言B.上下文有关语言C.正规语言D.0型文法定义的语言65 .已知文法G是无二义的，则对G的任意句型（八）A.最左推导和最右推导对应的语法树必定相同B.最左推导和最右推导对应的语法树可能相同C.最左推导和最右推导必定相同D.可能存在
13、两个不同的最左推导，但他们对应的语法树相同66.(B)不是DFA的成分A.有穷字母表B.多个初始状态的集合C.多个终态的集合D.转换函数D.a+b某c+dD.(a(b+c)+d67.与逆波兰式(后缀表达式)ab+c某d+对应的中缀表达式是(B)A.a+b+c某dB.(ab)某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+c)+dC.ABC-某CD/某D.以上都不对70.(D)不是NFA的成分。A.有穷字母表
14、B.初始状态集合C.终止状态集合D.有限状态集合二、问答题1 .将文法GS改写为等价的GS,使GS不含左递归和左公共因子。GS:SfbSAeIbAAfAbld答:文法GS改写为等价的不含左递归和左公共因子的GS为：SiBBfSAelAAfdAA, -bAI2 .将文法GS改写为等价的GS,使GS不含左递归和左公共因子。GS：SfSAelAeA-*dAbAdAId答:文法GS改写为等价的不含左递归和左公共因子的G,S为：SfAeSSfAeSIAfdAA,-ABBfbAl3 .将文法GS改写为等价的GS,使GS不含左递归和左公共因子。GS:S-AA-BrASB-aB：a答：文法GS改写为等价的不含
15、左递归和左公共因子的GS为：SAABA,Az-SAIB-aBB, B4.判断下面文法是否为LL(I)文法，若是,请构造相应的LL(I)分析表。SfaHHfaMddM-*AbAfaMIe答:首先计算文法的FIRST集和FoLLOW集如下表。文法的FIRST集和FOLLOW集非终结符FIRST集FOLLOW集Sa#.H#.a,dMa,e,d,bAb.a,e由于PrCdiCt(HfaMd)predict(Hfd)=ad=predict(MfAb)predict(Mf)=a,ed,b=predict(AfaM)predict(Afe)=aGe=所以该文法是LL(I)文法，LL(I)分析表如下表。adb
16、SfaH.HfaMdfd.MfAb.ffAfaM.5.判断下面文法是否为LL(I)文法，若是，请构造相应的LL(I)分析表。SfaDDfSTeTfbHHHfeIl答：首先计算文法的FIRST集和FOLLOW集如下表。非终结符FIRST集FOLLOW集Sa#,b,d,e.Da,#,b,d,ee-*Ab-*e.#在项目集IO中：有移进项目Ef-aTd和归约项目Ef-存在移进-归约冲突，所以G不是LR(O)文法。若产生式排序为：(O)S-E(l)EaTd(2)E(3)TEb(4)TaG的LR(O)项目集族及识别活前缀的DFA如下图：由产生式知：Follow(E)=,bFollow(T)=dS10,1
17、2中:Follow(E)a=ft,ba=在15中:Follow(E)a=ft,ba=Follow(T)a=da=Follow(T)Follow(E)=d#,b二所以在10,12,15中的移进-归约和归约-归约冲突可以由FOIIOW集解决,所以G是SLR(I)文法。构造的SLR(I)分析表如下表:ACTI0NG0T0nameabdftET0S2r2r211acc2S5r2r2433S64S75S5r2r4r24367rlr3rll5.给出文法GS的LR(I)项目集规范族中IO项目集的全体项goGS为：S-BDDBfaDlbDfB10:答：10：16.给出文法GS的LR(I)项目集规范族中IO项目
18、集的全体项目。GS为：SfD;DDDfDBBBfalb10:答：10：17.给出文法GS的LR(I)项目集规范族中IO项目集的全体项目。GS为：SS;VlVVfVaAlAAfb(三)|10:答：10：18.文法GM及其LR分析表如下，请给出对串dbba#的分析过程。GM:DMVbA2)Vd3)V4)Afa5)AfAba6)A-ACTIONGOTOnamebdaftMAOr3S311acc2S43r24r6S5r665r4r46S7r17S88r5r5答：对串Cibba#的分析过程如下表步骤状态栈文法符号栈剩余输入符号动作#处2#移进10#dbba#用Vfd归约203#Vbba#移进302#Vb
19、ba#用Af归约4024#VbAba#50246#VbAba#移进602467#VbAba#移进7024678#VbA#用A-Aba归约80246#M#用M-VbA归约901接受19.文法GS及其LR分析表如下，请给出对输入串da;aoa#的分析过程。GS:O)SZSDS-dSoS2) SfdS3)S-S;SV24)S-aname012345678dS2S2S2S2aS3r4S7r3rlACTI0N;S4r4S4r3S4aS3S3S3S3#accr4r23rlG0T0S1568答：输入串da;aoa#的分析过程如下表：步骤状态栈文法符号栈#10#d202#da3023#dS4025#ClS;5
20、0254#dS;a602543ftdS;S702546#dS8025#dSo90257#dSoa1002573#CISoS1102578#S1201剩余输入符号da;aoa#a;aoa#;aoa#;aoa#aoa#oa#oa#oa#a#动作移进移进用Sfa归约移进移进用Sfa归约用SfS;S归约移进移进用Sfa归约用S-dSoS归约接受20.文法GM及其LR分析表如下，请给出对串CiacIa#的分析过程。GM:I)SfVelB2)Vfe3) Vf4) Bfa5)B-*Bda6)BfACTION状态deattS0r3S311acc2S43r24r6S5r65r4r46S7rl7S88r5r5答：
21、对串dada#的分析过程如下表步骤状态栈文法符号栈剩余输入符号10#CiaeIa#202#VClada#3024#VClada#40245#VClada#50246#VdBda#G0T0B6V2动作用Vf归约移进移进用Bfa归约678902467024678024601#VdBd#VdBda#VdB#Sa#移进移进用B-Bda归约用SVdB归约接受21 .文法GE为：EfE+TITT-T某FFF-(E)Ii试给出句型(E+F)某i的短语，简单(直接)短语,句柄和最左素短语。答：短语有：(E+F)某i,(E+F),E+F,F,i简单(直接)短语有：F,i句柄是：F最左素短语是：E+F22 .文法
22、GS为：SfVV-TViTTfFT+FF-)V某|(试给出句型ViFi(的短语，简单(直接)短语,句柄和最左素短语。答：短语有:ViFi(,ViF,F,(简单(直接)短语有:F,(句柄是:F最左素短语是:ViF23 .文法GS为：SfSdTlTTfT试给出句型(SCIG)句型(SdG)短语：(SCIG)最左素短语：SdG24 .按指定类型给出下列语言的文法。(l)Ll=anbmc|n0,m0用正规文法。(2)L2=an1nbdmn0m0用二型文法。答：(D描述Ll语言的正规文法如下：SfaSlAAfbAIbBBfC(2)描述L2语言的二型文法如下：S-ABA-a11-0TlOIBfbDD-dDId
