编译原理复习题及答案

《编译原理复习题及答案》由会员分享，可在线阅读，更多相关《编译原理复习题及答案（16页珍藏版）》请在装配图网上搜索。

1、-编译原理复习题及答案一、 选择题1 一个正规语言只能对应(B)A 一个正规文法B 一个最小有限状态自动机2 文法GA：AAaB BAb Ba是(A)A 正规文法B 二型文法3 下面说确的是(A)A 一个SLR1文法一定也是LALR1文法B 一个LR1文法一定也是LALR1文法4 一个上下文无关文法消除了左递归，提取了左公共因子后是满足LL1文法的(A)A 必要条件B 充分必要条件5 下面说确的是(B)A 一个正规式只能对应一个确定的有限状态自动机B 一个正规语言可能对应多个正规文法6 算符优先分析与规归约相比的优点是(A)A 归约速度快B 对文法限制少7 一个LR1文法合并同心集后假设不是L

2、ALR1文法(B)A 则可能存在移进/归约冲突B 则可能存在归约/归约冲突C 则可能存在移进/归约冲突和归约/归约冲突8 下面说确的是(A)A Le*是一个词法分析器的生成器B Yacc是一个语法分析器9 下面说确的是(A)A 一个正规文法也一定是二型文法B 一个二型文法也一定能有一个等价的正规文法10 编译原理是对(C)。A、机器语言的执行B、汇编语言的翻译C、高级语言的翻译D、高级语言程序的解释执行11 (A)是一种典型的解释型语言。ABASICBCCFORTRANDPASCAL12 把汇编语言程序翻译成机器可执行的目标程序的工作是由(B)完成的。A. 编译器B. 汇编器C. 解释器D.

3、预处理器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. 线性表B. 树C. 完全图D. 堆栈18 词法分析器的输出结果是(D)。

4、A、单词自身值B、单词在符号表中的位置C、单词的种别编码D、单词的种别编码和自身值19 词法分析器不能(D)A. 识别出数值常量B. 过滤源程序中的注释C. 扫描源程序并识别记号D. 发现括号不匹配20 文法：G：S*S* | y所识别的语言是(D)。A、*y*B、(*y*)*C、*y*D、*ny*n (n0)21 如果文法G是无二义的，则它的任何句子(A)A最左推导和最右推导对应的语法树必定一样B最左推导和最右推导对应的语法树可能不同C最左推导和最右推导必定一样D可能存在两个不同的最左推导，但它们对应的语法树一样22 正则文法(A)二义性的。A. 可以是B. 一定不是C. 一定是23 (B)

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

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

7、的语法分析方法是(D)。ALALR分析法BLR(0)分析法CLR(1)分析法 DSLR(1)分析法35 假设a为终结符，则A a为(B)工程。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.最右直接短语C. 终结符D. 非终结符39 在自底向上的语法分析方法中，分析的关键是(D)

8、A. 寻找句柄B. 寻找句型C. 消除递归D. 选择候选式40 在自顶向下的语法分析方法中，分析的关键是(C)A. 寻找句柄B. 寻找句型C. 消除递归D. 选择候选式41 在LR分析法中，分析栈中存放的状态是识别规句型(C)的DFA状态。A.句柄B. 前缀C. 活前缀D. LR(0)工程42 一个上下文无关文法G包括四个组成局部，它们是一组非终结符号，一组终结符号，一个开场符号，以及一组(B)A. 句子B. 产生式C. 单词D. 句型43 词法分析器用于识别(C)A. 句子B. 产生式C. 单词D. 句型44 编译程序是一种(B)A. 汇编程序B. 翻译程序C. 解释程序D. 目标程序45

9、按逻辑上划分，编译程序第三步工作是(A)A. 语义分析B. 词法分析C. 语法分析D. 代码生成46 在语法分析处理中，FIRST集合、FOLLOW集合均是(B)A. 非终结符集B.终结符集C. 字母表D. 状态集47 编译程序中语法分析器接收以(A)为单位的输入。A. 单词B. 表达式C. 产生式D. 句子48 编译过程中，语法分析器的任务就是(B)A. 分析单词是怎样构成的B. 分析单词串是如何构成语句和说明的C. 分析语句和说明是如何构成程序的D. 分析程序的构造49 假设一个文法是递归的，则它所产生的语言的句子(A)。A.是无穷多个B.是有穷多个C.是可枚举的D.个数是常量50 识别上

10、下文无关语言的自动机是(C)A. 下推自动机B. NFAC. DFAD. 图灵机51 编译原理各阶段工作都涉及(B)A.词法分析B.表格管理C.语法分析D.语义分析52 正则表达式R1和R2等价是指(C)A.R1和R2都是定义在一个字母表上的正则表达式B.R1和R2中使用的运算符一样C.R1和R2代表同一正则集D.R1和R2代表不同正则集53 文法GS:SA1， AA1|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)C. (a

11、|b)(a|b)*D.(a|b)*55 (D)文法不是LL(1)的。A. 递归B. 右递归C. 2型D.含有公共左因子的56 给定文法AbA|cc，则符号串cc bcbc bcbcc bccbcc bbbcc中，是该文法句子的是(D)A. B. C. D. 57 LR(1)文法都是()A. 无二义性且无左递归B. 可能有二义性但无左递归C. 无二义性但可能是左递归D. 可以既有二义性又有左递归58 文法EE+E|E*E|i的句子i*i+i*i有(C)棵不同的语法树。A. 1B.3C. 5D.759 文法 SaaS|abc 定义的语言是(C)。A.a2kbc|k0B.akbc|k0C.a2k-1

12、bc|k0D.akakbc|k060 假设B为非终结符，则 Aa.Bb为(D)。A.移进工程B.归约工程C.承受工程D.待约工程61 同心集合并可能会产生新的(D)冲突。A.二义B.移进/移进C.移进/归约D.归约/归约62 就文法的描述能力来说，有(C)ASLR(1) LR(0)BLR(1) LR(0)CSLR(1)LR(1)D无二义文法 LR(1)63 如下列图自动机M，请问以下哪个字符串不是M所能识别的(D)。A. bbaaB. abbaC. ababD. aabb64 有限状态自动机能识别(C)A.上下文无关语言B.上下文有关语言C.正规语言D.0型文法定义的语言65 文法G是无二义的

13、，则对G的任意句型(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. (a+b)* (c+d)D. a+b*c+d68 后缀式abc+d+可用表达式(B)来表示。A( (a+b)c)+d B(a+(bc)+d C (a(b+c)+d D(a(b+c)+d69 表达

14、式A*(B-C*(C/D)的后缀式为(B)。AABC-CD/*BABCCD/*-*CABC-*CD/*D以上都不对70 (D)不是NFA的成分。A. 有穷字母表B. 初始状态集合C. 终止状态集合D. 有限状态集合二、 问答题1 将文法GS 改写为等价的GS，使GS不含左递归和左公共因子。GS： SbSAe | bA AAb | d答：文法GS 改写为等价的不含左递归和左公共因子的GS为：SbB BSAe | AAd A A bA | 2 将文法GS 改写为等价的GS，使GS不含左递归和左公共因子。GS： SSAe|Ae AdAbA|dA|d答：文法GS 改写为等价的不含左递归和左公共因子的G

15、S为： S AeSS AeS| A dA A AB| B bA | 3 将文法GS 改写为等价的GS，使GS不含左递归和左公共因子。GS： SA AB|AS BaB|a答：文法GS 改写为等价的不含左递归和左公共因子的GS为：S AA BAASA|B aBBB|4 判断下面文法是否为LL(1)文法，假设是,请构造相应的LL(1)分析表。SaHHaMd | dMAb | AaM | e答：首先计算文法的 FIRST集和FOLLOW集如下表。文法的 FIRST集和FOLLOW集 非终结符FIRST集FOLLOW集Sa* Ha ，d* Ma ，e ，d ，bAa ，eb由于predictHaMdpr

16、edictHd=ad =predictMAbpredictM=a ，ed ，b =predictAaMpredictAe= a e =所以该文法是LL(1)文法，LL(1)分析表如下表。adbe*SaHHaMddMAbAbAaMe5 判断下面文法是否为LL(1)文法，假设是，请构造相应的LL(1)分析表。SaDDSTe|TbH|HHd|答：首先计算文法的 FIRST集和FOLLOW集如下表。 非终结符FIRST集FOLLOW集Sa*，b，d，eDa，*，b，d，e Tb，d，eHd，e由于predictDSTepredictD=a* ，b ，d ，e =predictTbHpredictTH=

17、be =predictHdpredictH= d e =所以该文法是LL(1)文法，LL(1)分析表如下表：aebd*SaDDSTeTHbHHHd6 判断下面文法是否为LL(1)文法，假设是，请构造相应的LL(1)分析表。SaDDSTe|TbMMbHHM|答：文法的 FIRST集和FOLLOW集非终结符FIRST集FOLLOW集Sa* ，bDa ，* ，bTbeMbeHb ，e由于predictDSTepredictD=a* ，b=predictHMpredictH= b e =所以该文法是LL(1)文法，LL(1)分析表如下表：aeb*SaDDSTeTbMMbHHM7 *语言的拓广文法G为：

18、(0) SS(1) S Db|B(2) D d|(3) B Ba|证明G不是LR(0)文法而是SLR(1)文法，请给出SLR(1)分析表。答：拓广文法G，增加产生式SS在工程集I0中：有移进工程D d 归约工程D 和B 存在移进-归约和归约-归约冲突，所以G不是LR(0)文法。假设产生式排序为：(0) SS(1) S Db(2) S B(3) D d(4) D (5) B Ba(6) B G的LR(0)工程集族及识别活前缀的DFA如以下列图：由产生式知Follow(S)=* Follow(D)= bFollow(B)= a ,*在I0中:Follow(D) d= b d=Follow(B) d

19、= a ,* d=Follow(D) Follow(B)= ba ,* =在I3中:Follow(S) a=*a=所以在I0，I3中的移进-归约和归约-归约冲突可以由Follow集解决,所以G是SLR(1)文法, 构造的SLR(1)分析表如下表：状态ACTIONGOTObda*SDB0r4S4r6r61231acc2S53S6r24r35r16r5r58 给出与正规式Rab*a|b*ba等价的NFA。答：与正规式R等价的NFA如以下列图9 给出与正规式R(ab)*|b*a|(ba)*a 等价的NFA。答：与正规式R等价的NFA如以下列图10 给出与正规式 Raba*(ba)*|bb等价的NFA

20、。答：与正规式R等价的NFA如以下列图11 将以下列图的NFA确定化为DFA。答：用子集法确定化如下表IIaIb状态*,1,21,21,2,31,2,Y1,21,21,2,Y1,21,2,31,2,31,2,31,2,3*123确定化后如以下列图：12 将以下列图的NFA确定化为DFA。答：用子集法确定化如下表IIaIb状态*,0,1,30,1,32,3,Y1,32,YY0,1,30,1,31,31,32,3,Y2,3,YY2,YY*1234Y确定化后如以下列图13 *语言的拓广文法G为：(0) ST (1) T aBd|(2) B Tb| 证明G不是LR(0)文法而是SLR(1)文法，请给出

21、SLR(1)分析表。答：拓广文法G，增加产生式ST 在工程集I0中：有移进工程T aBd和归约工程T 存在移进-归约冲突，所以G不是LR(0)文法。 假设产生式排序为： (0) ST(1) T aBd(2) T (3) B Tb(4) B G的LR(0)工程集族及识别活前缀的DFA如以下列图所示：识别G活前缀的DFA由产生式知：Follow(T)=*,b Follow(B)= d在I0中： Follow(T) a=* ，b a=在I2中：Follow(B) a= d a=Follow(T) a=* ，b a=Follow(B) Follow(T) = d* ，b=所以在I0，I2，中的移进-归

22、约和归约-归约冲突可以由Follow集解决，所以G是SLR(1)文法。 构造的SLR(1)分析表如下表。SLR(1)分析表nameACTIONGOTOabd*TB0S2r2r211acc2S2r2r4r2433S54S65r1r16r314 *语言的文法G为： E aTd|T Eb|a证明G不是LR(0)文法而是SLR(1)文法，请给出该文法的SLR(1)分析表。答：拓广文法G，增加产生式SE在工程集I0中： 有移进工程E aTd和归约工程E 存在移进-归约冲突，所以G不是LR(0)文法。 .假设产生式排序为：(0) SE (1) E aTd (2) E (3) T Eb (4) T aG的L

23、R(0)工程集族及识别活前缀的DFA如以下列图：由产生式知：Follow(E)=* ，b Follow(T)= d在I0 ，I2中:Follow(E) a=* ，b a=在I5 中:Follow(E) a=* ，b a=Follow(T) a= d a=Follow(T) Follow(E) = d * ，b=所以在I0 ， I2 ， I5中的移进-归约和归约-归约冲突可以由Follow集解决,所以G是SLR(1)文法。构造的SLR(1)分析表如下表：nameACTIONGOTOabd*ET0S2r2r211acc2S5r2r2433S64S75S5r2r4r2436r1r17r315 给出文

24、法GS的LR(1)工程集规族中I0工程集的全体工程。GS为： S BD|D B aD|b D BI0:答：I0：16 给出文法GS的LR(1)工程集规族中I0工程集的全体工程。GS为： S D;D|D D DB|B B a|bI0:答：I0:17 给出文法GS的LR(1)工程集规族中I0工程集的全体工程。GS为： S S;V|V V VaA|A A b(S)| I0:答：I0:18 文法GM及其LR分析表如下，请给出对串dbba*的分析过程。GM: 1) M VbA2) V d3) V 4) A a5) A Aba6) A nameACTIONGOTObda*MAV0r3 S3121acc2S

25、43r24r6S5r665r4r46S7r17S88r5r5答：对串dbba*的分析过程如下表步骤状态栈文法符号栈剩余输入符号动作12345678900302024602467024678024601*d*V*Vb*VbA*VbAb*VbAba*VbA*Mdbba*bba*bba*ba*ba*a*移进用V d归约移进用A 归约移进移进用A Aba 归约用M VbA 归约承受19 文法GS及其LR分析表如下，请给出对输入串da;aoa*的分析过程。GS: 0) SS1) SdSoS2) S dS3) S S;S 4) S a nameACTIONGOTOda;a*S0S2S3S311S4acc2

26、S2S353r4r4r44S2S365S7S4r26r3r3r37S2S388r1S4r1答：输入串da;aoa*的分析过程如下表：步骤状态栈文法符号栈剩余输入符号动作123456789101112 002025025402543025460250257025730257801*d*da*dS*dS;*dS;a*dS;S*dS*dSo*dSoa*dSoS*Sda;aoa*a;aoa*;aoa*;aoa*aoa*oa *oa *oa *a *移进移进用S a 归约移进移进用S a 归约用S S;S 归约移进移进用S a 归约用SdSoS 归约承受20 文法GM及其LR分析表如下，请给出对串dad

27、a*的分析过程。GM: 1) S VdB2) V e3) V 4) B a 5) B Bda6) B 状态ACTIONGOTOdea*SBV0r3 S3121acc2S43r24r6S5r665r4r46S7r17S88r5r5答：对串dada*的分析过程如下表步骤状态栈文法符号栈剩余输入符号动作1234567890020245024602467024678024601*V*Vd*Vda*VdB*VdBd*VdBda*VdB*Sdada*dada*ada*da*da*a*用V 归约移进移进用B a归约移进移进用B Bda 归约用S VdB 归约承受21 文法GE为：EE+T|TTT*F|FF(

28、E)|i试给出句型(E+F)*i的短语，简单(直接)短语,句柄和最左素短语。答：短语有: (E+F)*i ，(E+F) ，E+F ，F ，i 简单(直接)短语有：F ，i 句柄是：F最左素短语是：E+F22 文法GS为：SV VT | ViT TF| T+FF)V* |( 试给出句型ViFi( 的短语，简单(直接)短语,句柄和最左素短语。答：短语有: ViFi( ，ViF ， F ，(简单(直接)短语有: F ，( 句柄是: F 最左素短语是: ViF23 文法GS为：SSdT | TTTG | GG(S) | a试给出句型(SdG)a的短语、简单(直接)短语、句柄和最左素短语。答：句型(Sd

29、G)a的短语：(SdG)0 用正规文法。(2) L2= a0n1n bdm | n0，m0 用二型文法。 答：(1) 描述L1语言的正规文法如下： S aS|AA bA|bB B c(2) 描述L2语言的二型文法如下：S AB A aT T 0T1|01 B bD D dD|d 25 以下语言或文法确切属于按乔姆斯基Chomsky分类的哪种类型,请填在 。1 L1= a0n1nbdm | n0，m 0 ( ) 2 L2= anbnbm | n0,m0 ( ) 3 L3= anbmc| n0,m0 ( ) 4 GA:AaB| BAb|a ( )5 GE:EE+E|E*E|(E)|i ( )答：1

30、 L1= a0n1nbdm | n0，m 0 ( 2 型 ) 2 L2= anbnbm | n0,m0 ( 1型 ) 3 L3= anbmc| n0,m0 ( 3型 ) 4 GA:AaB| BAb|a ( 2型 ) 5 GE:EE+E|E*E|(E)|i ( 2型 )26 按指定类型给出以下语言的文法。(1) L1= candbm| n0,m0 用正规文法。(2) L2= 0na1nbmcm| n0，m 0 用二型文法。答：1解：描述L1语言的正规文法如下：ScAAaA|BBdDDbD|2解：描述L2语言的二型文法如下：SABA0A1|0a1BbBc|27 写出表达式(a+b)/(a-b)-a

31、(a+b*c)的三元式序列答：.(+,a,b).(-,a,b).(/,).(*,b,c).(+,a,).(-,)28 写出表达式(ab*c)/(ab)d的逆波兰表示及三元式序列。答：逆波兰表示：abc*ab/d三元式序列： (*，b，c) (，a，) (，a，b) (/，) (，d)29 将下面的条件语句表示成四元式序列： if ab then *:=a+b*c else *:=b-a;答：(1) ( j, a, b, (3) (2) ( j, , , (7) ) (3) ( *, b, c, T1) (4) ( +, a, T1, T2) (5) ( :=, T2, , *) (6) ( j

32、, , , (9) (7) ( -, b, a, T3) (8) ( :=, T3, , *) (9) ( )30 翻译成四元式序列。Whilea0 b0do Begin *：*1； if a0 then a：a1 else b：b1 End； 答：(1) (j，a，0，5) (2) (j，3) (5) (，1，T1) (6) (：，T1，) (7) (j，a，0，9) (8) (j，12)(9) (，a，1，T2) (10) (：，T2，a) (11) (j，1) (12) (，b，1， T3) (13) (：，T3，b) (14) (j，1) (15)31 文法G(S) ： Sa|(T) TT，S|S 写出句子(a，a)，a)的规归约过程及每一步的句柄。答：句型归约规则句柄(a，a)，a)Saa (S，a)，a)TSS (T，a)，a)Saa (T，S)，a)TT，S T，S (S)，a) TSS (T)，a) SS(T) (T) (S，a) TSS (T，a) Saa (T，S) TT，S T，S (T) S(T)(T) S. z.