编译原理复习题及答案

1、123456789101112131415161718192021编译原理复习题及答案选择题一个正规语言只能对应 ( B )B 一个最小有限状态自动机A 一个正规文法文法 GA :AtaBAb Ba 是(A )A 正规文法B 二型文法下面说法正确的是 ( A )A 一个SLR (1)文法一定也是 LALR ( 1)文法B 一个LR (1)文法一定也是 LALR (1)文法一个上下文无关文法消除了左递归，提取了左公共因子后是满足LL (1)文法的(A )A 必要条件B 充分必要条件下面说法正确的是 ( B )A 一个正规式只能对应一个确定的有限状态自动机( A )B 对文法限制少LALR( 1

2、)文法 ( B )B 一个正规语言可能对应多个正规文法 算符优先分析与规范归约相比的优点是A 归约速度快一个 LR( 1 )文法合并同心集后若不是/ 归约冲突/ 归约冲突/ 归约冲突和归约 / 归约冲突A 则可能存在移进B 则可能存在归约C 则可能存在移进下面说法正确的是 ( A )A Lex 是一个词法分析器的生成器 下面说法正确的是 ( A )A 一个正规文法也一定是二型文法B 一个二型文法也一定能有一个等价的正规文法 编译原理是对 (C) 。A、机器语言的执行C、高级语言的翻译(A) 是一种典型的解释型语言。A. BASICB. CC.把汇编语言程序翻译成机器可执行的目标程序的工作是由C

3、. 解释器定是A. 编译器B. 汇编器用高级语言编写的程序经编译后产生的程序叫A.源程序B.目标程序(C) 不是编译程序的组成部分。A. 词法分析程序B. 代码生成程序B Yacc 是一个语法分析器B、D、汇编语言的翻译 高级语言程序的解释执行FORTRAND.(B) 完成的。D.(B)C.连接程序C.设备管理程序PASCAL预处理器D.解释程序D. 语法分析程序通常一个编译程序中，不仅包含词法分析，语法分析，语义分析，中间代码生成，代码优化， 目标代码生成等六个部分，还应包括 (C) 。A. 模拟执行器B.解释器C.表格处理和出错处理D .符号执行器编译程序绝大多数时间花在 (D) 上。A.

4、出错处理B.词法分析C.目标代码生成D.表格管理源程序是句子的集合， (B) 可以较好地反映句子的结构。A. 线性表B. 树C. 完全图D. 堆栈词法分析器的输出结果是 (D) 。A、单词自身值B单词在符号表中的位置C、单词的种别编码D单词的种别编码和自身值词法分析器不能 (D)A. 识别出数值常量B. 过滤源程序中的注释C. 扫描源程序并识别记号D. 发现括号不匹配文法: G: StxSx | y 所识别的语言是 (D)。A、xyxB、(xyx)*C x*yx*D xnyxn (n 0)如果文法G是无二义的，则它的任何句子a (A)A. 最左推导和最右推导对应的语法树必定相同B. 最左推导和

5、最右推导对应的语法树可能不同C. 最左推导和最右推导必定相同D. 可能存在两个不同的最左推导，但它们对应的语法树相同正则文法(A)二义性的。A.可以是B.定不是C.定是(B)这样一些语言，它们能被确定的有穷自动机识别，但不能用正则表达式表示。A.存在B.不存在C.无法判定是否存在给定文法 At bA | ca，为该文法句子的是(C)A. bbaB.cabC.bcaD.cba22.23.24.25.26.27.28.29.30.31 .32.33.34.35.36.37.38.39.40.41 .42.43.设有文法 GS: S S1|S0|Sa|Sc|a|b|cA.ab0B. aOcO1文法G

6、产生的(D)的全体是该文法描述的语言。 A.句型B.终结符集若文法G定义的语言是无限集，则文法必然是 A.递归的B.上下文无关的描述一个语言的文法是(B)A.唯一的B.不唯一的一个文法所描述的语言是(A)A.唯一的B.不唯一的采用自上而下分析，必须(A) oA、消除回溯C、消除右递归编译过程中，语法分析器的任务是 分析单词的构成 分析单词串如何构成语句 分析语句是如何构成程序 分析程序的结构A.B.词法分析器的输入是(A) oA.符号串B.源程序两个有穷自动机等价是指它们的A.状态数相等C.所识别的语言相等(A)(C) O，下列符号串中是该文法的句子有(D)D. bc10C.a0b0aC.非终

7、结符集(A)C.二义性的C.可能唯一C.可能唯一B消除左递归D提取公共左因子C.C.B.D.D.句子D.无二义性的D.语法单位D.目标程序有向弧数相等状态数和有向弧数相等若状态k含有项目“ Aa”，且仅当输入符号 a FOLLOW(A)寸，才用规则“ A a”归 约的语法分析方法是(D) oA. LALR分析法B. LR(0)分析法C. LR(1)分析法 D . SLR(1)分析法若a为终结符，则Aa a 3为(B)项目。A.归约B.移进C.接受D.待约在使用高级语言编程时，首先可通过编译程序发现源程序的全部和部分(A)错误。A.语法B.语义C.语用D.运行乔姆斯基(Chomsky)把文法分为

8、四种类型，即 A.非限制文法B.正则文法一个句型中的(A)称为该句型的句柄。A.最左直接短语B.最右直接短语在自底向上的语法分析方法中，分析的关键是 A.寻找句柄B.寻找句型在自顶向下的语法分析方法中，分析的关键是 A.寻找句柄B.寻找句型0型、1型、2型、3型。其中3型文法是(B)D.上下文无关文法C.上下文有关文法C.终结符D.非终结符(D)C.消除递归D.选择候选式(C)C.消除递归D.选择候选式在LR分析法中，分析栈中存放的状态是识别规范句型(C)的DFA状态。A.句柄B.前缀C.活前缀D. LR(0)项目一个上下文无关文法 G包括四个组成部分，它们是一组非终结符号，一组终结符号，一个

9、开 始符号，以及一组(B)A.句子B.产生式C.单词D.句型词法分析器用于识别(C)A.句子B.产生式C.单词D.句型45.46.47.48.49.50.51 .52.53.54.55.56.57.58.59.60.61 .62.63.64.65.44.A.汇编程序B.翻译程序C.解释程序D.目标程序按逻辑上划分，编译程序第三步工作是(A)A.语义分析B.词法分析C.语法分析D.代码生成在语法分析处理中，FIRST 集合、FOLLOW言合均是(B)A.非终结符集B.终结符集C.字母表D.状态集编译程序中语法分析器接收以 (A)为单位的输入。A.单词B. 表达式C.产生式D.句子编译程序是一种(

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

11、集已知文法 GS:S tA1, A tA1|S0|0。与G等价的正规式是(C)A. 0(0|1)*B. 1*|0*1C. 0(1|10)*1D. 1(10|01)*0与(a|b)*(a|b)等价的正规式是(C)。*| b*B.(ab)*(a|b)C. (a|b)(a|b)*D.(a|b)*(D)文法不是LL(1)的。A.递归B.右递归C. 2型D.含有公共左因子的给定文法 AtbA|cc，则符号串ccbcbcbcbccbccbcc 是(D)A.B.C.bbbcc中，是该文法句子的D.LR(1)文法都是()A.无二义性且无左递归C.无二义性但可能是左递归B.可能有二义性但无左递归D.可以既有二义

12、性又有左递归文法Et E+E|E*E|i的句子i*i+i*i 有(C)棵不同的语法树。A. 1B. 3文法S t aaS|abc定义的语言是(C)。A.a2kbc|k0B.akbc|k0若B为非终结符，则 At .B 为(D)。A.移进项目B.归约项目同心集合并可能会产生新的(D)冲突。A.二义B.移进/移进就文法的描述能力来说，有(C)A. SLR? LR(0)B. LR? LR(0)LR(1)如图所示自动机 M请问下列哪个字符串不是A. bbaaB. abbaC. 5C.a2k-1bc|k0C.接受项目C.移进/归约C. SLR(1) ? IM所能识别的(D)。C.ababD.akakbc

13、|k0D.待约项目D.归约/归约LR(1) D.无二义文法D.aabb有限状态自动机能识别(C)型文法定义的语言A.上下文无关语言B.上下文有关语言C.正规语言已知文法G是无二义的，则对G的任意句型a (A)A. 最左推导和最右推导对应的语法树必定相同B. 最左推导和最右推导对应的语法树可能相同C. 最左推导和最右推导必定相同D. 可能存在两个不同的最左推导，但他们对应的语法树相同66.(B)不是DFA的成分A.有穷字母表B.多个初始状态的集合C.多个终态的集合D.转换函数67.与逆波兰式(后缀表达式)ab+c d+对应的中缀表达式是(B)A. a+b+c*dB. (a+b)* c+dC. (

14、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/D)的后缀式为(B)。A. ABC-CD/*B. ABCCD/*-*C.ABC-*CD/*D.以上都不对70.(D)不是NFA的成分。A.有穷字母表B.初始状态集合C.终止状态集合D.有限状态集合、问答题1 . 将文法GS改写为等价的 G S，使G S不含左递归和左公共因子。GS : St bSAe | bA A Ab | d 答：

15、文法GS改写为等价的不含左递归和左公共因子的GS为：St bBBt SAe|AAt d AA t bA |2. 将文法GS改写为等价的GS，使GS不含左递归和左公共因子。GS : StSAe|Aeat dAbA|dA|d答：文法GS改写为等价的不含左递归和左公共因子的GS为：S t AeSS tAeS| &A t dAA tAB| B t bA | 3. 将文法GS改写为等价的GS，使GS不含左递归和左公共因子。GS : St Aat B|AS Bt aB|a答：文法GS改写为等价的不含左递归和左公共因子的GS为：S t AA t BAAt SA | B t aBBt B| 4. 判断下面文法

16、是否为LL(1)文法，若是，请构造相应的LL(1)分析表。St aHHT aMd|dMT Ab |At aM | e答：首先计算文法的 FIRST集和FOLLOW如下表。文法的FIRST集和FOLLOW非终结符|FIRST集| FOLLOWISa# Ha , d# Ma , e，&d , bAa , eb 由于 predict(HRaMd A predict(HRd) =a A d =predict(MRAb)A predict(MRe) =a , e A d , b =predict(AraM) A predict(Are) = a A e =所以该文法是LL(1)文法，LL(1)分析表如下

17、表。adbe#Sr aH.Hr aMdRd Mr AbR&R&r AbAr aMRe 5. 判断下面文法是否为 LL(1)文法，若是，请构造相应的LL(1)分析表。Sr aDDRSTe| &Tr bH|HHRd| &答：首先计算文法的 FIRST集和FOLLOW如下表。非终结符FIRST 集FOLLOW集Sa#, b, d, eDa , &# , b, d, e Tb , d,&eHd , &e由于 predict(DRSTe)A predict(DR&) =a A # , b , d , e =predict(TrbH)A predict (TrH) =b A e =predict(HRd)

18、A predict(HRs) = d A e =所以该文法是LL(1)文法，LL(1)分析表如下表:aebd#Sr aD.Dr STeR&R&R&R&TRHr bHRH HR&Rd 6. 判断下面文法是否为 LL(1)文法，若是，请构造相应的LL(1)分析表。Sr aDDR STe| &Tr bMMR bHHRM| &答：文法的FIRST集和FOLLOW集非终结符FIRST 集FOLLOV集Sa # , bDa ,&# , b Tb e Mb e Hb ,&e 由于 predict(DRSTe)A predict(DR&) =a A # , b=predict(HRM) A predict(H

19、R&) = b A e =所以该文法是LL(1)文法，LL(1)分析表如下表：aeb#Sr aD.Dr STeR&R&TT bMMT bHHTgTM.7. 某语言的拓广文法 G为：(0) S f(1) S t Db|B(2) D t d| (3) B t Ba| 证明G不是LR(0)文法而是SLR(1)文法，请给出SLR(1)分析表。 答：拓广文法G，增加产生式S tS在项目集I。中：有移进项目D td归约项目D t 和B t存在移进-归约和归约-归约冲突，所以 G不是LR(0)文法。若产生式排序为：(0) S tS(1) S t DbS t BD t dD t B t BaB tG的LR(0

20、)项目集族及识别活前缀的DFA如下图：由产生式知Follow(S)=#Follow(D)= bFollow(B)= a ,#在丨0中:Follow( D) n d= b n d=Follow(B) n d= a ,# n d=Follow(D) n Follow(B)= b n a ,#=在Is中:Follow(S) n a=# n a=所以在丨0,丨3中的移进-归约和归约-归约冲突可以由Follow集解决，所以G是SLR(1)文法, 构造的SLR(1)分析表如下表：状态ACTIONGOTObda#SDB0r4S4r6r61231acc2S53S6r24r35r16r5r58. 给出与正规式

21、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 n1,2.1,2.1,2,311,2,31,2,Y1,2,321,2,Y1,2.1,2,33确定化后如下图:12. 将下图的NFA确定化为 DFA答：用子集法确定化如下表

22、II aI b状态X,0,1,30,1,32,3,YX0,1,3.0,1,32,3,Y12,3,Y.1,3.Y.21,3 .2,Y.32,Y .1,3.Y.4YY确定化后如下图13. 某语言的拓广文法 G为：(0) S、T(1) T taBd| &(2) B tTb| &证明G不是LR(0)文法而是SLR(1)文法，请给出SLR(1)分析表。 答：拓广文法G，增加产生式S tT在项目集I。中：有移进项目T t aBd和归约项目T t 存在移进-归约冲突，所以G不是LR(0)文法。 若产生式排序为：(0) S tt(1) T t aBdT t& B t TbB t&G的LR(0)项目集族及识别活

23、前缀的DFA如下图所示：识别G活前缀的DFA由产生式知：Follow(T)=#,bFollow(B)= d在I。中：Follow(T) n a=#, b n a=在I2中：Follow(B) n a= d n a=Follow(T) n a=# , b n a=Follow(B) n Follow(T) = d n # ,b=所以在Io, I 2，中的移进-归约和归约-归约冲突可以由Follow集解决，所以G是SLR(1)文法。 构造的SLR(1)分析表如下表。SLR分析表n ameACTIONGOTOabd#TB0S2r2r211acc2S2r2r4r2433S54S6 二5r1r16r31

24、4. 某语言的文法 G为：E t aTd| T t Eb|a证明G不是LR(0)文法而是SLR(1)文法，请给出该文法的SLR(1)分析表。答：拓广文法G，增加产生式S te在项目集I。中：有移进项目 E taTd 和归约项目Et.存在移进-归约冲突，所以G不是LR(0)文法。若产生式排序为：(0) S t E(1) E t aTdE t T t EbT t aG的LR(0)项目集族及识别活前缀的DFA如下图：由产生式知：Follow(E)=# , bFollow(T)= d在Io , I 2中:Follow(E) n a=# , b n a=在|5中:Follow(E) n a=# , b

25、n a=Follow(T) n a= d n a=Follow(T) n Follow(E) = d n # ,b=所以在Io , I 2 , I 5中的移进-归约和归约-归约冲突可以由Follow集解决，所以G是SLR(1)文 法。构造的SLR(1)分析表如下表：n ameACTIONGOTOabd#ET0S2r2r211acc2S5r2r2433S64S75S5r2r4r2436r1r17r315.给出文法GS的LR(1)项目集规范族中I。项目集的全体项目。GS为：S tBD|DB t aD|bD tbI 0:答：Io：16. 给出文法GS的LR(1)项目集规范族中I0项目集的全体项目。G

26、S为：S tD;D|DD t DB|BB t a|bI o：答：I 0：17. 给出文法GS的LR(1)项目集规范族中I0项目集的全体项目。GS为：S tS;V|VV t VaA|AA t b(S)|I 0：答：I 0：18. 文法GM及其LR分析表如下，请给出对串dbba#的分析过程。GM: 1) M tVb A2) V Td3) V t4) A Ta5) A tAba6) A tn ameACTIONGOTObda#匚AV0r3S3121acc2S43r24r6S5r665r4r46S7r17S88r5r5答：对串dbba#的分析过程如下表步骤状态栈文法符号栈剩余输入符号动作10#dbba

27、#移进203#dbba#用V Td归约302#Vbba#移进4024#Vbba#用A T归约50246#VbAba#移进602467#VbAba#移进7024678#VbAba#用A TAba归约80246#VbA#用M tVbA归约901#M#接受19. 文法GS及其LR分析表如下，请给出对输入串da;aoa#的分析过程。GS:0) S1) S tdSoS2) S tdS3) S tS;S4) S t an ameACTIONGOTOdaa#S0S2S3S311S4acc2S2S353r4r4r44S2S365S7S4r26r3r3r37S2S388r1S4r1答：输入串da;aoa#的分析

28、过程如下表:步骤状态栈文法符号栈剩余输入符号动作10#da;aoa#移进202#da;aoa#移进3023#da;aoa#用S t a归约4025#dS;aoa#移进50254#dS;aoa#移进602543#dS;aoa #用S t a归约702546#dS;Soa #用S tS;S归约8025#dSoa #移进90257#dSoa #移进1002573#dSoa#用S t a归约1102578#dSoS#用StdSoS归约1201#S#接受20. 文法GM及其LR分析表如下，请给出对串dada#的分析过程。GM: 1) S t VdB2) V Te3) V t4) B t a5) B t

29、Bda6) B t状态ACTIONGOTOdea#SBV0r3S3121acc2S43r24r6S5r665r4r46S7r17S88r5r5答：对串dada#的分析过程如下表步骤状态栈文法符号栈剩余输入符号动作10#dada#用V t归约202#Vdada#移进3024#Vdada#移进40245#Vdada#用B Ta归约50246#VdBda#移进602467#VdBda#移进7024678#VdBda#用B T Bda归约80246#VdB#用S t VdB归约901#S#接受21. 文法 GE为： i E+T|TT*F|FL (E)|i试给出句型(E+F)*i的短语，简单(直接)短语

30、,句柄和最左素短语。答：短语有：(E+F)*i，(E+F) ，E+F，F，i简单(直接)短语有：F , i句柄是：F最左素短语是：E+F22. 文法GS为：St VS T | ViTTt F| T+FFt )V* |(试给出句型ViFi(的短语，简单(直接)短语,句柄和最左素短语。答：短语有:ViFi( , ViF , F ,(简单(直接)短语有:F ,(句柄是：F最左素短语是：ViF23. 文法GS为：St SdT | TTt TG | GG (S) | a试给出句型(SdG)a的短语、简单(直接)短语、句柄和最左素短语。 答：句型(SdG)a的短语：(SdG)0, m0 用正规文法。(2)

31、 L2= a0 n1n bd m | n0 , m0用二型文法。 答：(1) 描述Li语言的正规文法如下：St aS|AA t bA|bBB tc(2) 描述L2语言的二型文法如下：St ABA t aTT t 0T1|01B t bDD t dD|d25. 下列语言或文法确切属于按乔姆斯基(Chomsky)分类的哪种类型，请填在()内。Whilea 0 V bv 0 do(1) L1= a0 n1nbdm | n0 ，m 0 ( )(2) L2= a nbncnbm | n 0,m0 ()(3) L3= a nbmc| n 0,m0 ()(4) GA:A taB| BAb|a ()(5) GE:E tE+E|E*E|(E)|i () 答：(1) L1= a0 n1nbdm | n0 ，m 0 ( 2 型 )(2) L2= a nbncnbm | n0,m0 ( 1型)(3) L3= a nbmc| n 0,m0 ( 3 型)(4) GA:A taB| B tAb|a