2013编译原理复习题及答案

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

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

3、.语法分析程序通常一个编译程序中，不仅包含词法分析，语法分析，语义分析，中间代码生成，代码优化，目标代码生成等六个部分，还应包括（C）。A.模拟执行器B.解释器C.表格处理和出错处理D.符号执行器14.源程序是句子的集合，（B）可以较好地反映句子的结构。15.16.A.线性表B.树词法分析器的输出结果是（D）。A、单词自身值C、单词的种别编码词法分析器不能（D）A.识别出数值常量C.扫描源程序并识别记号C.完全图D.堆栈B、单词在符号表中的位置D、单词的种别编码和自身值B.过滤源程序中的注释D.发现括号不匹配17.A、xyxB、(xyx)*C、x*yx*D、xnyx n (n > 0)文

4、法：G: S一 xSx | y所识别的语百是（D）。18.如果文法G是无二义的，则它的任何句子a （A）A .最左推导和最右推导对应的语法树必定相同B .最左推导和最右推导对应的语法树可能不同C.最左推导和最右推导必定相同D .可能存在两个不同的最左推导，但它们对应的语法树相同19.正则文法（A）二义性的。A.可以是B. 一定不是C. 一定是20.（B）这样一些语言，它们能被确定的有穷自动机识别，但不能用正则表达式表示。A.存在B.不存在C.无法判定是否存在给定文法A - bA | ca,为该文法句子的是（C）A. bbaB. cabC. bcaD. cba22.设有文法GS : STS1|S

5、0|Sa|Sc|a|b|c下列符号串中是t文法的句子有（D）23.24.A.ab0B. a0c01描述一个语言的文法是（B）A ,唯一的B.不唯一的一个文法所描述的语言是（A）A ,唯一的B.不唯一的C. a0b0aD.bc10C.可能唯一C.可能唯一25 采用自上而下分析，必须(A) 。A 、消除回溯C、消除右递归B 、消除左递归D、提取公共左因子26编译过程中，语法分析器的任务是(A) 分析单词的构成 分析单词串如何构成语句 分析语句是如何构成程序 分析程序的结构A. C. D. 27词法分析器的输入是( A)。A 符号串B 源程序源程序C.语法单位D 目标程序28两个有穷自动机等价是指它

6、们的(C)。A 状态数相等B.有向弧数相等29归约的语法分析方法是3031C.所识别的语言相等D.状态数和有向弧数相等若状态 k 含有项目“A LALR 分析法若 a 为终结符，则A 归约Af a(D)。B LR(0) 分析法,且仅当输入符号 aCFOLLOW(A)Af a,为(B)项目。在使用高级语言编程时,首先可通过编译程序发现源程序的全部和部分A. 语法B. 语义时，才用规则“B 移进C LR(1) 分析法C.接受C. 语用SLR(1)分析法D 待约(A) 错误。D. 运行3233A. 非限制文法一个上下文无关文法B. 正则文法G 包括四个组成部分，它们是一组非终结符号，一组终结符号，一

7、个开C. 上下文有关文法D. 上下文无关文法乔姆斯基(Chomsky)把文法分为四种类型，即 0型、1型、2型、3型。其中3型文法是(B)始符号，以及一组(B)343536A. 句子词法分析器用于识别A. 句子编译程序是一种(B)A. 汇编程序按逻辑上划分，编译程序第三步工作是A. 语义分析(C)B. 翻译程序B. 词法分析(A)C. 单词C. 单词C. 解释程序C. 语法分析D.D.D.D.句型句型目标程序代码生成37A. 非终结符集B. 终结符集C.字母表D. 状态集在语法分析处理中，FIRST 集合、 FOLLOW 集合均是(B)383940414243444546A. 单词编译过程中，

8、语法分析器的任务就是A. 分析单词是怎样构成的C. 分析语句和说明是如何构成程序的若一个文法是递归的，则它所产生的语言的句子A. 是无穷多个B. 表达式B. 是有穷多个识别上下文无关语言的自动机是(C)A. 下推自动机B. NFA编译原理各阶段工作都涉及(B)A. 词法分析B. 表格管理正则表达式R1 和 R2 等价是指(C)A.B.C.D.C.D. 句子R1R1R1R1(B)B.D.分析程序的结构分析单词串是如何构成语句和说明的(A)。C.是可枚举的C. DFAC.语法分析D. 个数是常量D. 图灵机D. 语义分析和 R2 都是定义在一个字母表上的正则表达式和 R2 中使用的运算符相同和 R

9、2 代表同一正则集和 R2 代表不同正则集已知文法 GS:S-A1 ,A-A1|S0|0。与G等价的正规式是A. 0(0|1)*B. 1*|0*1C. 0(1|10)*1(C)D. 1(10|01)*0与(a|b)*(a|b)等价的正规式是(C)。A.a*| b*B.(ab)*(a|b)C. (a|b)(a|b)*D.(a|b)*(D)文法不是LL(1)的。A. 递归B. 右递归C. 2 型D. 含有公共左因子的编译程序中语法分析器接收以(A) 为单位的输入。474849A. B. C. D. LR(1)文法都是()A. 无二义性且无左递归C. 无二义性但可能是左递归B. 可能有二义性但无左递

10、归D. 可以既有二义性又有左递归文法E-E+E|E*E|i的句子i*i+i*i有(C)棵不同的语法树。A. 1B. 3C. 5D.7给定文法 A fbA|cc,则符号串 ccbcbcbcbccbccbccbbbcc中，是该文法句子的是 (D)50. 文法 SfaaS|abc定义的语言是(C)。51 .52.53.54.A.a2kbc|k>0B.akbc|k>0若B为非终结符，则A- .B 为(D)。A.移进项目B.归约项目同心集合并可能会产生新的 (D)冲突。A.二义B.移进/移进就文法的描述能力来说，有 (C)A. SLR(1) ? LR(0) B . LR(1) ? LR(0)

11、如图所示自动机M,请问下列哪个字符串不是A. bbaaB. abbaC.a2k-1bc|k>0C.接受项目C.移进/归约C. SLR(1) ? LR(1)M所能识别的(D)。D.akakbc|k>0D.待约项目D.归约/归约D.无二义文法 ？ LR(1)D.aabbC.abab55.56.57.58.59.60.61. .有限状态自动机能识别(C)A.上下文无关语言B.上下文有关语言C.正规语言已知文法G是无二义的，则对 G的任意句型a (A)A.最左推导和最右推导对应的语法树必定相同B.最左推导和最右推导对应的语法树可能相同C.最左推导和最右推导必定相同D.可能存在两个不同的最左

12、推导，但他们对应的语法树相同(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. -(a+(b-c)+dC. - (a-(b+c)+d表达式 A*(B-C*(C/D)的后缀式为(B)。A . ABC-CD/*B . ABCCD/*-*C. ABC-*CD/*(D)不是NFA的成分。A.有穷字母表B.初始状态集合C.终止状态集合D.0型文法定义的语言D

13、.转换函数D. a+b*c+dD. (a-(-b+c)+dD.以上都不对D.有限状态集合二、 问 答题1. . 将文法GS改写为等价的G' S使G'环含左递归和左公共因子。GS: A bSAe | bAZ Ab | d答：文法 GS 改写为等价的不含左递归和左公共因子的G'S 为：Sf bBBR SAe | AZ d A 'A' - bA' |£2. 将文法GS改写为等价的G'S,使G'S不含左递归和左公共因子。GS: ASAe|AeZ dAbA|dA|d答：文法 GS 改写为等价的不含左递归和左公共因子的G'S

14、 为：S f AeS'S' fAeS'| eA f dA'A' fAB|eB f bA | £3. 将文法GS改写为等价的G'S,使G'S不含左递归和左公共因子。GS: A AZ B|ASB aB|a答：文法 GS 改写为等价的不含左递归和左公共因子的G'S 为：S 一 AA 一 BAA fSA | sB 一 aBB 一 B| e4. 判断下面文法是否为 LL(1)文法，若是，请构造相应的LL(1)分析表。Sf aHHR aMd | dMr> Ab | £2 aM | e答：首先计算文法的 FIRST集和

15、FOLLOW集如下表。文法的FIRST集和FOLLOW集非终结符FIRST 集FOLLOW 集Sa# .Ha , d.# .Ma , e , £ jd , bAa , e.b.由于 predict (HRaMd ) predict ( HRd ) =a Ad =0predict (MH Ab ) predict (MH e) =a , e A d , b =Opredict (ZaM ) predict (Ae ) = a A e 0所以该文法是LL(1)文法，LL(1)分析表如下表。adbe#S一 aH.H一 aMd一d.M一 Ab.££一 AbA一 aM.&g

16、t;e.5. 判断下面文法是否为LL(1)文法，若是，请构造相应的LL(1)分析表。Sf aDASTe| £Tf bH|H答:首先计算文法的FIRST集和FOLLOW集如下表。非终结符FIRST 集FOLLOW 集Sa#, b, d, e.Da, d#, b, d, e Tb , d,eHd, 8e由于 predict (A STe ) A predict (Ae) =a A# , b , d , e =0predict (T- bH ) A predict (T-H ) =b Ae = 0predict (HRd ) predict (HRe) = d A e 0所以该文法是LL(

17、1)文法，LL(1)分析表如下表:aebd#S一 aD.D一 STe££££T一 H .一 bH一 H .H£一d .6. 判断下面文法是否为LL(1)文法，若是，请构造相应的LL(1)分析表。Sf aDASTe| £T一 bMMr> bHHRM| £ 答：文法的 FIRST集和FOLLOW 集非终结符FIRST 集FOLLOW 集Sa.# , bDa , e# , bTb.e.Mb.e.Hb , ee.由于 predict (A STe ) A predict (Ae) =a A # , b=0predict (HR

18、M ) A predict (HHe) = b A e =所以该文法是LL(1)文法，LL(1)分析表如下表:aeb#S一 aD.D一 STe££T一 bMM一 bHH£一 M .7. 某语百的拓广文法 G'为：(0) S f(1) S 一 Db|B(2) D 一 d| £(3) B 一 Ba| s证明G不是LR(0)文法而是SLR(1)文法，请给出SLR(1)分析表。答:拓广文法G',增加产生式 S'-S在项目集Io中：有移进项目D一d归约项目D 一和B 一 存在移进-归约和归约-归约冲突，所以 G不是LR(0)文法。Io：5

19、TS DbS -* B d 1aD 一 B _* * EtaB f -若产生式排序为： (0) S' S 一 DbD 一 d(4) D一 e B一 Ba (6) B 一 eG'的LR(0)项目集族及识别活前缀的DFA如下图:由产生式知Follow(S尸#Follow(D尸bFollow(B尸a ,#在Io中:Follow(D) n d= b碌l二Follow(B) n d= a ,#d=Follow(D) n Follow(B尸b a ,#> 0在I3中：Foiiow(s) n a=# n a=所以在Io, I3中的移进-归约和归约-归约冲突可以由Follow集解决，所以

20、G是SLR(1)文法,构造的SLR(1)分析表如下表：状态ACTIONGOTObda#SDB0r4S4r6r61231acc2S53S6r24r35r16r5r58. 给出与正规式 R= (ab) * (a|b*) ba等价的NFA。答：与正规式R等价的NFA如下图9. 给出与正规式 R= (ab)*|b) * (a|(ba)*) a 等价的 NFA。答:与正规式R等价的NFA如下图10. 给出与正规式*R= (aba)(ba) |b) b 等价的 NFA。答:与正规式R等价的NFA如下图11. 将下图的NFA确定化为DFA。答：用子集法确定化如下表IIaIb状态X,1,21,2.1,2,3X

21、1,2.1,2.1,2,311,2,31,2,Y1,2,321,2,Y1,2.1,2,33确定化后如下图:用子集法确定化如下表12. 将下图的NFA确定化为 DFAIIaIb状态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.4Y0.0.Y确定化后如下图13.某语百的拓广文法 G'为:(1) S 一 T(2) T f aBd| £(3) B 一 Tb| £证明G不是LR(0)文法而是SLR(1)文法，请给出SLR(1)分析表。答：拓广文法 G',增加产生式 S

22、9;-T在项目集Io中：有移进项目T - aBd和归约项目T 一 存在移进-归约冲突，所以 G不是LR(0)文法。若产生式排序为：(0) S' 一 TT 一aBd(2) T 一 & B 一 Tb(4) B 一 eG'的LR(0)项目集族及识另1J活前缀的DFA如下图所示：识另IJ G'活前缀的DFA由产生式知：Follow(T尸#,bFollow(B尸d在Io中:Follow(T) n a=# b n t 0在I2中：Follow(B)n a= d陶a二Follow(T)n a=# b n a/Follow(B) n Follow(T) = d, b#25所以在

23、I。，I2,中的移进-归约和归约-归约冲突可以由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'-EG'的LR(0)项目集族及识别活前缀的DFA如下图:在项目集Io中：有移进项目 E 一 aTd和归约项目E一 存在移进-归

24、约冲突，所以 G不是LR(0)文法。若产生式排序为：(0) S 一 E E 一 aTd(2) E 一 & T一 Eb(4) T一 a由产生式知：Follow(E)=# , bFollow(T尸d在Io , I2中:Follow(E) na=# b n a。在I5中：Follow(E) na=供 b n a纪Follow(T) n a= d©a=Follow(T) n Follow(E) = d, b=#所以在Io , I2 , I5中的移进-归约和归约-归约冲突可以由Follow集解决，所以G'是SLR(1)文法。构造的SLR(1)分析表如下表：nameACTIONG

25、OTOabd#ET0S2r2r211acc2S5r2r2433S64S75S5r2r4r2436r1r17r315 .给出文法GS的LR(1)项目集规范族中Io项目集的全体项目。GS为：S 一 BD|DB 一 aD|bD 一 B10: 5f 7 ,律答:B 一 aD , fl/a/bB bS/a/bD f B16 .给出文法GS的LR(1)项目集规范族中I0项目集的全体项目。GS为：S 一 D;D|DD 一 DB|BB 一 a|bT S ,注S一加口，#B 一 口，若D - * DB、# /; /a/bD 3 , #/; /a/bB -* * a j #八 /a/bB f * b , it /

26、, /a/b17 .文法GM及其LR分析表如下，请给出对串dbba#的分析过程。GM: 1) M VbA2) V 一 d3) V -e4) A 一 a5) A 一Aba6) A 一 enameACTIONGOTObda#MAV0r3S3121acc2S43r24r6S5r665r4r46S7ri7S88r5r5答：对串dbba#的分析过程如下表步骤状态栈文法符号栈剩余输入符号动作10#dbba#移进203#dbba#用V -d归约302#Vbba#移进4024#Vbba#用A - e归约50246#VbAba#移进602467#VbAba#移进7024678#VbAba#用A 一Aba归约80

27、246#VbA#用M 一VbA 归约901#M#接受18 .文法GS及其LR分析表如下，请给出对输入串da;aoa#勺分析过程。GS: 0) S f1) S - dSoS2) S 一 dS3) S 一 S;SnameACTIONGOTOda;a#S0S2S3S311S4acc2S2S353r4r4r44S2S365S7S4r26r3r3r37S2S388r1S4r1答：输入串da;aoa#的分析过程如下表:步骤状态栈文法符号栈剩余输入符号动作10#da;aoa#移进202#da;aoa#移进3023#da;aoa#用S -a归约4025#dS;aoa#移进50254#dS;aoa#移进6025

28、43#dS;aoa #用S -a归约702546#dS;Soa #用S -S;S归约8025#dSoa #移进90257#dSoa #移进1002573#dSoa#用S -a归约1102578#dSoS#用SfdSoS归约1201#S#接受19 .文法GM及其LR分析表如下，请给出对串dada#勺分析过程。GM: 1) S VdB2) V一 e3) 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#用S VdB归约901#S#接受20 按指定类型给出下列语言的文法。(1) Li= anbm c| n 孑Om>0 用正规文法。(2) L2= a0n1n bdm | n>0， m>0 用二型文法。答：(1) 描述 L 1 语言的正规文法如下：A aS|AA f bA|bBB f c(2) 描述L 2语言的二型文法如下：S AB

30、A f aTT f 0T1|01B f bDD f dD|d, 请填在()内。21.下列语言或文法确切属于按乔姆斯基( Chomsky)分类的哪种类型(1) 1)L1= a0n1nbdm | n>0， m >0 ( )(2) L2= anbncnbm| n > 0,m>0 ()(3) L3= anbmc| n > 0,m>0 ()(4) GA:AfaB| e BfAb|a ()(5) GE:E-E+E|E*E|(E)|i ()答：(1) 1)L1= a0 n1nbdm | n>0， m >0 ( 2 型 )(2) L2= a nbncnbm | n > 0,m>0 (型)(3) L3= a nbmc| n > 0,m>0 (型)(4) GA:AfaB| e BfAb|a ( 2 型)(5) GE:E fE+E|E*E|(E)|i ( 2 型)22 按指定类型给出下列语言的文法。(1) Li= candbm| n > 0,