编译原理复习题及答案

1、编译原理复习题及答案选择题1 .一个正规语言只能对应（B）A一个正规文法B一个最小有限状态自动机2 .文法GA:Af&ZaBBfAb3-&是（A）A正规文法B二型文法3 .下面说法正确的是（A）A一个SLR（1）文法一定也是LALR（1）文法B一个LR（1）文法一定也是LALR（1）文法4 .一个上下文无关文法消除了左递归，提取了左公共因子后是满足LL（1）文法的（AA必要条件B充分必要条件5 .下面说法正确的是（B）A一个正规式只能对应一个确定的有限状态自动机B一个正规语言可能对应多个正规文法6 .算符优先分析与规范归约相比的优点是（A）A归约速度快B对文法限制少7 .一个L

2、R（1）文法合并同心集后若不是LALR（1）文法（B）A则可能存在移进/归约冲突B则可能存在归约/归约冲突C则可能存在移进/归约冲突和归约/归约冲突8 .下面说法正确的是（A）ALex是一个词法分析器的生成器BYacc是一个语法分析器9 .下面说法正确的是（A）A一个正规文法也一定是二型文法B一个二型文法也一定能有一个等价的正规文法10.编译原理是对（C）。A、机器语言的执行C、高级语言的翻译B、汇编语后的翻译D、高级语言程序的解释执行11 .（A）是一种典型的解释型语言。C.FORTRAND.PASCALA.BASICB.C12 .把汇编语言程序翻译成机器可执行的目标程序的工作是由（B）完成

3、的。A.编译器B.汇编器C,解释器D,预处理器13 .用高级语言编写的程序经编译后产生的程序叫（B）A.源程序B.目标程序C.连接程序D.解释程序14 .（C）不是编译程序的组成部分。A.词法分析程序B.代码生成程序C.设备管理程序D.语法分析程序15 .通常一个编译程序中，不仅包含词法分析，语法分析，语义分析，中间代码生成，代码优化,目标代码生成等六个部分，还应包括（C）。A.模拟执行器B.解释器C.表格处理和出错处理D.符号执行器16 .编译程序绝大多数时间花在（D）上。A.出错处理B.词法分析C.目标代码生成D.表格管理17 .源程序是句子的集合，（B）可以较好地反映句子的结构。A.线性

4、表B.树C.完全图D.堆栈18 .词法分析器的输出结果是（D）。A、单词自身值C、单词的种别编码19 .词法分析器不能（D）A.识别出数值常量C.扫描源程序并识别记号20 .文法：G:SfxSx|y所识别的语言是（D）。A、xyxB、（xyx）*B、单词在符号表中的位置D、单词的种别编码和自身值B.过滤源程序中的注释D.发现括号不匹配C、x*yx*D、xnyxn（n>0）21. 如果文法G是无二义的，则它的任何句子«（A）A.最左推导和最右推导对应的语法树必定相同B.最左推导和最右推导对应的语法树可能不同C.最左推导和最右推导必定相同D.可能存在两个不同的最左推导，但它们对应的

5、语法树相同22. 正则文法（A）二义性的。A.可以是B.一定不是C.一定是23. （B）这样一些语言，它们能被确定的有穷自动机识别，但不能用正则表达式表示。A.存在B.不存在C.无法判定是否存在24. 给定文法AfbA|ca,为该文法句子的是（C）A.bbaB.cabC.bcaD.cba25. 设有文法GS:STS1|S0|Sa|Sc|a|b|c下列符号串中是文法的句子有(D)A.ab0B.a0c01C.a0b0aD.bc1026. 文法G产生的（D）的全体是该文法描述的语言。C.非终结符集D.句子A.句型B.终结符集27. 若文法G定义的语言是无限集，则文法必然是（A）A.递归的B.上下文无

6、关的C.二义性的D.无二义性的28 .描述一个语言的文法是（B）A,唯一的B.不唯一的29 .一个文法所描述的语言是（A）A,唯一的B.不唯一的30 .采用自上而下分析，必须（A）。A、消除回溯C、消除右递归31 .编译过程中，语法分析器的任务是（A）分析单词的构成分析单词串如何构成语句分析语句是如何构成程序分析程序的结构C.可能唯一C.可能唯一B、消除左递归D、提取公共左因子A.B.C.D.32.词法分析器的输入是（A）。A.符号串B.源程序C.语法单位D.目标程序33.两个有穷自动机等价是指它们的A.状态数相等C.所识别的语言相等（C）oB.有向弧数相等D.状态数和有向弧数相等34.若状态

7、k含有项目“A-a”，且仅当输入符号aCFOLLOW(A)时，才用规则“A一a”归约的语法分析方法是（D）。35.A.LALR分析法B.LR(0)分析法若a为终结符，则A-”为（B）项目。C. LR(1)分析法D. SLR(1)分析法A.归约B.移进C.接受D.待约36.在使用高级语言编程时，首先可通过编译程序发现源程序的全部和部分（A）错误。A.语法B.语义C.语用D.运行37.乔姆斯基（Chomsky）把文法分为四种类型，即0型、1型、2型、3型。其中3型文法是（B）A.非限制文法B.正则文法C.上下文有关文法D.上下文无关文法38.一个句型中的（A）称为该句型的句柄。A.最左直接短语B.

8、最右直接短语C.终结符D.非终结符39.在自底向上的语法分析方法中，分析的关键是(D)40.4142434445.46.47484950A.寻找句柄B.寻找句型C.消除递归D.选择候选式在自顶向下的语法分析方法中，分析的关键是A.寻找句柄B.寻找句型(C)C.消除递归D.选择候选式在LR分析法中，分析栈中存放的状态是识别规范句型（C）的DFA状态。A.句柄B.前缀C.活前缀D.LR(0)项目一个上下文无关文法始符号，以及一组（B）A.句子词法分析器用于识别A.句子编译程序是一种（B）A.汇编程序G包括四个组成部分，它们是一组非终结符号，一组终结符号，一个开C.单词D.句型(C)C.单词D.句型

9、B.翻译程序C.解释程序D.目标程序按逻辑上划分，编译程序第三步工作是A.语义分析B.词法分析在语法分析处理中,A.非终结符集(A)C.语法分析D.代码生成FIRST集合、FOLLOW集合均是（B）B.终结符集C.字母表D.状态集编译程序中语法分析器接收以（A）为单位的输入。A.单词B.表达式D.句子编译过程中，语法分析器的任务就是A.分析单词是怎样构成的C.分析语句和说明是如何构成程序的(B)B.D.分析单词串是如何构成语句和说明的分析程序的结构若一个文法是递归的，则它所产生的语言的句子A.是无穷多个B.是有穷多个识别上下文无关语言的自动机是（C）A.下推自动机B.NFA编译原理各阶段工作都

10、涉及（B）A.词法分析B.表格管理52.正则表达式R1和R2等价是指（C）(A)。C.是可枚举的D.个数是常量C.DFAD.图灵机C.语法分析D.语义分析A.R1和R2都是定义在一个字母表上的正则表达式B.R1和R2中使用的运算符相同C.R1和R2代表同一正则集D.R1和R2代表不同正则集53.已知文法GS:S-A1,A-A1|S0|0。与G等价的正规式是(C)A.0(0|1)*B.1*|0*1C.0(1|10)*1D.1(10|01)*054. 与(a|b)*(a|b)等价的正规式是(C)。A.a*|b*B.(ab)*(a|b)55. (D)文法不是LL(1)的。A.递归B.右递归C.(a|

11、b)(a|b)*D.(a|b)*C.2型D.含有公共左因子的56. 给定文法A一bA|cc,则符号串ccbcbcbcbccbccbccbbbcc中，是该文法句子的是(D)57.A.B.C.D.LR(1)文法都是()A.无二义性且无左递归B.可能有二义性但无左递归C.无二义性但可能是左递归D.可以既有二义性又有左递归58.文法EfE+E|E*E|i的句子i*i+i*i有(C)棵不同的语法树。A.1B.3C.5D.759 .文法S-aaS|abc定义的语言是(C)。A.a2kbc|k>0B.akbc|k>060 .若B为非终结符，则A-ot.B);(D)。A.移进项目B.归约项目61

12、.同心集合并可能会产生新的(D)冲突。A.二义B.移进/移进C.a2k-1bc|k>0C.接受项目C.移进/归约D.akakbc|k>0D.待约项目D.归约/归约62.就文法的描述能力来说，有(C)A.SLR(1)?LR(0)B.LR(1)?LR(0)C.SLR(1)?LR(1)D.无二义文法？LR(1)63.如图所示自动机M,请问下列哪个字符串不是M所能识别的(D)。A.bbaaB.abbaC.ababD.aabb64. 有限状态自动机能识别(C)D.0型文法定义的语言A.上下文无关语言B.上下文有关语言C.正规语言65. 已知文法G是无二义的，则对G的任意句型a(A)A.最左推

13、导和最右推导对应的语法树必定相同B.最左推导和最右推导对应的语法树可能相同C.最左推导和最右推导必定相同D.可能存在两个不同的最左推导，但他们对应的语法树相同66. (B)不是DFA的成分A.有穷字母表B.多个初始状态的集合C.多个终态的集合D.转换函数67. 与逆波兰式(后缀表达式)ab+c*d+对应的中缀表达式是(B)A.a+b+c*dB.(a+b)*c+dC.(a+b)*(c+d)D.a+b*c+d68. 后缀式abc-+-d+可用表达式(B)来表示。A.(-(a+b)-c)+dB.-(a+(b-c)+dC.-(a-(b+c)+dD.(a-(-b+c)+d69. 表达式A*(B-C*(C

14、/D)的后缀式为(B)oA.ABC-CD/*B.ABCCD/*-*C.ABC-*CD/*D.以上都不对70. (D)不是NFA的成分。A.有穷字母表B.初始状态集合C.终止状态集合D.有限状态集合问答将文法GS改写为等价的G'S使G'环含左递归和左公共因子。GS:SbSAe|bAZAb|d答：文法GS改写为等价的不含左递归和左公共因子的G'S为:SfbBA'-bA'|£2. 将文法GS改写为等价的G'S,使G'S不含左递归和左公共因子。GS:SSAe|AeZdAbA|dA|d答：文法GS改写为等价的不含左递归和左公共因子的G&#

15、39;S为：SfAeS'S'fAeS'|eAfdA'A'fAB|eBfbA|£3. 将文法GS改写为等价的G'S,使G'S不含左递归和左公共因子。GS:川AAB|ASBaB|a答：文法GS改写为等价的不含左递归和左公共因子的G'S为：SfAAfBAA-SA|£BfaBBfB|e4. 判断下面文法是否为LL(1)文法，若是，请构造相应的LL(1)分析表。SfaHHRaMd|dMr>Ab|£2aM|e答：首先计算文法的FIRST集和FOLLOW集如下表。文法的FIRST集和FOLLOW集非终结符FI

16、RST集FOLLOW集Sa#.Ha,d.#.Ma,e,sd,bAa,e.b.由于predict(HRaMd)predict(HRd)=aAd=0predict(MHAb)predict(MHe)=a,eAd,b=0predict(ZaM)predict(Are)=ane阅所以该文法是LL(1)文法，LL(1)分析表如下表。adbe#S一aH.H一aMd一d.M一Ab.££一AbA一aM.>e.5.判断下面文法是否为LL(1)文法，若是，请构造相应的LL(1)分析表。SfaDASTe|£T一bH|HHRd|£答：首先计算文法的FIRST集和FOLLO

17、W集如下表。非终结符FIRST集FOLLOW集Sa#,b,d,e.Da,e#,b,d,eTb,d,eeHd,ee由于predict(ASTe)Apredict(Ae)=aA#,b,d,e=predict(T-bH)Apredict(T-H)=bAe=0predict(HRd)predict(HRe)=dAe切所以该文法是LL(1)文法，LL(1)分析表如下表:aebd#S一aD.D一STe££££T一H.一bH一H.H£一d.6.判断下面文法是否为LL(1)文法，若是，请构造相应的LL(1)分析表。SfaDASTe|£T一bMMr&g

18、t;bHHRM|£答：文法的FIRST集和FOLLOW集非终结符FIRST集FOLLOW集Sa.#,bDa,e#,bTb.e.Mb.e.Hb,ee.由于predict(ASTe)Apredict(Ae)=aA#,b=0predict(HRM)Apredict(HHe)=bAe骨所以该文法是LL(1)文法，LL(1)分析表如下表：aeb#S一aD.D一STe££T一bMM一bHH£一M.7.某语百的拓广文法G'为：(0)Sf(1) S一Db|B(2) D一d|s(3) B一Ba|s证明G不是LR(0)文法而是SLR(1)文法，请给出SLR(1)分析

19、表。Io：MfTSDb£fBDfdD一8-*BaBf-答：拓广文法G',增加产生式S'-S在项目集Io中：有移进项目D一d归约项目D一和B一存在移进-归约和归约-归约冲突，所以G不是LR(0)文法。若产生式排序为：(0)S'fS一DbS一BD一d(4) D一eB一Ba(6)B一eG'的LR(0)项目集族及识别活前缀的DFA如下图:由产生式知Follow(S)=#Follow(D)=bFollow(B)=a,#在I0中:Follow(D)nd=b倏=Follow(B)nd=a,#币d=Follow(D)nFollow(B)=bn疝#=在I3中：Follo

20、w(S)na=#ne二所以在Io,I3中的移进-归约和归约-归约冲突可以由Follow集解决，所以G是SLR(1)文法,构造的SLR(1)分析表如下表：状态ACTIONGOTObda#SDB0r4S4r6r61231acc2S53S6r24r35ri6r5r58.给出与正规式R=(ab)*(a|b*)ba等价的NFA。答:与正规式R等价的NFA如下图R=(ab)*|b)*(a|(ba)*)a等价的NFA。9. 给出与正规式答:与正规式R等价的NFA如下图10. 给出与正规式R=(aba)(ba)|b)b等价的NFA。答：与正规式R等价的NFA如下图11. ,将下图的NFA确定化为DFA。答:用

21、子集法确定化如下表IIaIb状态X,1,2)1,2.1,2,3X1,2.1,2.1,2,311,2,31,2,Y1,2,321,2,Y1,2.1,2,33确定化后如下图:12. 将下图的NFA确定化为DFA。答：用子集法确定化如下表IIaIb状态X,0,1,30,1,32,3,YX0,1,3.0,1,32,3,Y12,3,Y.1,3.Y.21,3.0.2,Y.32,Y.1,3.Y.4Y.0.0.Y确定化后如下图13.某语百的拓广文法G'为：(1) S一T(2) TfaBd|£(3) B一Tb|£证明G不是LR(0)文法而是SLR(1)文法，请给出SLR(1)分析表。

22、答：拓广文法G',增加产生式S'-T在项目集Io中：有移进项目T-aBd和归约项目T一存在移进-归约冲突，所以G不是LR(0)文法。若产生式排序为:(0)S'T(2)TB一aBd.£一Tb(4)B一eG'的LR(0)项目集族及识另1J活前缀的DFA如下图所示:识另IJG'活前缀的DFA由产生式知：Follow(T)=#,bFollow(B)=d在I0中:Follow(T)na=#bna0在I2中：Follow(B)na=dia=Follow(T)na=#bna=_'Follow(B)nFollow(T)=d,b#5所以在I。，I2,中的

23、移进-归约和归约-归约冲突可以由Follow集解决，所以G是SLR(1)文法。构造的SLR(1)分析表如下表。SLR(1)分析表nameACTIONGOTOabd#TB0S2r2r211acc2S2r2r4r2433S54S65riri6r314.某语言的文法G为：E-aTd|£T一Eb|a证明G不是LR(0)文法而是SLR(1)文法，请给出该文法的SLR(1)分析表。答：拓广文法G',增加产生式S'-E在项目集Io中：I匚有移进项目E一aTd,片fE和归约项目E>,Ef*aTd存在移进-归约冲突，所以G不是LR(0)文法。Ef.若产生式排序为：(0)S一EE一

24、aTd(2)E-eT一Eb(4)T一aG'的LR(0)项目集族及识别活前缀的DFA如下图：由产生式知:Follow(E)=#,bFollow(T)=d在I0,I2中：Follow(E)na=#bna0在I5中：Follow(E)na=#bna='Follow(T)na=dPLa=Follow(T)nFollow(E)=d,b=#5所以在I。，I2,I5中的移进-归约和归约-归约冲突可以由Follow集解决，所以G'是SLR(1)文法。构造的SLR(1)分析表如下表:nameACTIONGOTOabd#ET0S2r2r211acc2S5r2r2433S64S75S5r2r

25、4r2436r1r17r315.给出文法GS的LR(1)项目集规范族中I0项目集的全体项目。GS为:S一BD|DB一aD|bD一B|0：1T.|0:3,f7,#Sf-BD/SfD.率B-'aDj#/耳/bB，bS/a/bDf*B*16.给出文法GS的LR(1)项目集规范族中I0项目集的全体项目。GS为：S一D;D|DD一DB|BB一a|bI0：答:5TS,持S,并g一I,ifD-*DB、#/:/a/bD3,#/;/a/bB-*aj*八/a/bBf*b,it/,/a/b17.给出文法GS的LR(1)项目集规范族中I0项目集的全体项目。GS为：S一S;V|VV一VaA|AA一b(S)|sI

26、o:Io:3,f7,外SSI,；/#ST¥，;/tMf'VaA,;/i/aAb(S),;/#/aAf,；/t*/a18.文法GM及其LR分析表如下，请给出对串dbba#的分析过程。GM:1)MVbA2) V一d3) V-e4) A一a5) A一Aba6) A一enameACTIONGOTObda#MAV0r3S3121acc2S43r24r6S5r665r4r46S7r17S88r5r5答：对串dbba#的分析过程如下表步骤状态栈文法符号栈剩余输入符号动作10#dbba#移进203#dbba#用V-d归约302#Vbba#移进4024#Vbba#用A-e归约50246#VbA

27、ba#移进602467#VbAba#移进7024678#VbAba#用A一Aba归约80246#VbA#用M一VbA归约901#M#接受19.文法GS及其LR分析表如下，请给出对输入串da;aoa#勺分析过程。GS:0)Sf1) S-dSoS2) S一dS3) S一S;S4) S一anameACTIONGOTOda；a#S0S2S3S311S4acc2S2S353r4r4r44S2S365S7S4r26r3r3r37S2S388riS4ri答：输入串da;aoa#的分析过程如下表:步骤状态栈文法符号栈剩余输入符号动作10#da;aoa#移进202#da;aoa#移进3023#da;aoa#用S

28、-a归约4025#dS;aoa#移进50254#dS;aoa#移进602543#dS;aoa#用S-a归约702546#dS;Soa#用S-S;S归约8025#dSoa#移进90257#dSoa#移进1002573#dSoa#用S-a归约1102578#dSoS#用SfdSoS归约1201#S#接受20.文法GM及其LR分析表如下，请给出对串dada#勺分析过程。GM:1)SVdB2) V一e4) B一a5) B一Bda6) B一e状态ACTIONGOTOdea#SBV0r3S3121acc2S43r24r6S5r665r4r46S7r17S88r5r5答：对串dada#的分析过程如下表步骤状

29、态栈文法符号栈剩余输入符号动作10#dada#用V-e归约202#Vdada#移进3024#Vdada#移进40245#Vdada#用B-a归约50246#VdBda#移进602467#VdBda#移进7024678#VdBda#用B一Bda归约80246#VdB#用SVdB归约901#S#接受21. 文法GE为：E-E+T|TT-T*F|FF一(E)|i试给出句型（E+F）*i的短语，简单（直接）短语,句柄和最左素短语。答：短语有：（E+F）*i,（E+F）,E+F,F,i简单（直接）短语有：F,i句柄是：F最左素短语是：E+F22. 文法GS为：SfVYfT|ViTT-F|T+FF-）V*

30、|（试给出句型ViFi（的短语，简单（直接）短语,句柄和最左素短语。答：短语有：ViFi（,ViF,F,（简单（直接）短语有：F,（句柄是：F最左素短语是：ViF23. 文法GS为：SfSdT|TTfTG|GG（S）|a试给出句型（SdG）a的短语、简单（直接）短语、句柄和最左素短语。答：句型（SdG）a的短语：（SdG）a、（SdG）、SdG、G、a简单（直接）短语：G、a句柄：G最左素短语：SdG24. 按指定类型给出下列语言的文法。（1）Li=anbmc|n导Om0用正规文法。(2)L2=a0n1nbdm|n>0,m>0用二型文法。答:(1)描述Li语言的正规文法如下：AaS|AAfbA|bBBfc(2)描述L2语言的二型文法如下：SABAfaTTf0T1|01BfbDDfdD|d，请填在（）内。25. 下列语言或文法确切属于按乔姆斯基(Chomsky)分类的哪种类型(1) L1=a0n1nbdm|n>0,m>0()(2) L2=anbncnbm|n>0,m>0()(3) L3=anbmc|n>0,m>0()(4) GA:AfaB|eBfAb|a()(5) GE:E-E+E|E*E|(E)|i()答：(1) L1=a0n1nbdm|n>0,m&g