编译原理复习题及答案.docx

资源描述

《编译原理复习题及答案.docx》由会员分享，可在线阅读，更多相关《编译原理复习题及答案.docx（34页珍藏版）》请在三一办公上搜索。

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

2、归约速度快 B 对文法限制少 7 一个LR文法合并同心集后若不是LALR文法( B ) A 则可能存在移进/归约冲突 B 则可能存在归约/归约冲突 C 则可能存在移进/归约冲突和归约/归约冲突 8 下面说法正确的是( A ) A Lex是一个词法分析器的生成器 B Yacc是一个语法分析器 9 下面说法正确的是( A ) A 一个正规文法也一定是二型文法 B 一个二型文法也一定能有一个等价的正规文法 10 编译原理是对(C)。 A、机器语言的执行 B、汇编语言的翻译 C、高级语言的翻译 D、高级语言程序的解释执行 A ) 11 (A)是一种典型的解释型语言。 ABASIC BC CFORTR

3、AN DPASCAL 12 把汇编语言程序翻译成机器可执行的目标程序的工作是由(B)完成的。 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出错

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

5、最右推导对应的语法树必定相同 B最左推导和最右推导对应的语法树可能不同 C最左推导和最右推导必定相同 D可能存在两个不同的最左推导，但它们对应的语法树相同 22 正则文法(A)二义性的。 A. 可以是 B. 一定不是 C. 一定是 23 (B)这样一些语言，它们能被确定的有穷自动机识别，但不能用正则表达式表示。 A. 存在 B. 不存在 C. 无法判定是否存在 24 给定文法AbA|ca，为该文法句子的是(C) A. bba B. cab C. bca D. cba 25 设有文法GS：SS1|S0|Sa|Sc|a|b|c，下列符号串中是该文法的句子有(D) A. ab0 B. a0c01 C

6、. a0b0a D. bc10 26 文法G产生的(D)的全体是该文法描述的语言。 A句型 B. 终结符集 C. 非终结符集 D.句子 27 若文法G定义的语言是无限集，则文法必然是(A) A递归的 B.上下文无关的 C.二义性的 D.无二义性的 28 描述一个语言的文法是(B) A唯一的 B. 不唯一的 C.可能唯一 29 一个文法所描述的语言是(A) A唯一的 B. 不唯一的 C.可能唯一 30 采用自上而下分析，必须(A)。 A、消除回溯 B、消除左递归 C、消除右递归 D、提取公共左因子 31 编译过程中，语法分析器的任务是(A) 分析单词的构成分析单词串如何构成语句分析语句是如何

7、构成程序分析程序的结构 A. B. C. D. 32 词法分析器的输入是( A)。 A符号串 B源程序 C语法单位 D目标程序 33 两个有穷自动机等价是指它们的(C)。 A状态数相等 B有向弧数相等 D状态数和有向弧数相等 C所识别的语言相等 34 若状态k含有项目“A”，且仅当输入符号aFOLLOW(A)时，才用规则“A ”归约的语法分析方法是(D)。 ALALR分析法 BLR(0)分析法 CLR(1)分析法 DSLR(1)分析法 35 若a为终结符，则A a为(B)项目。 A归约 B移进 C接受 D待约 36 在使用高级语言编程时,首先可通过编译程序发现源程序的全部和部分(A)错误。

8、A.语法 B.语义 C.语用 D.运行 37 乔姆斯基(Chomsky)把文法分为四种类型，即0型、1型、2型、3型。其中3型文法是(B) A. 非限制文法 B.正则文法 C.上下文有关文法 D.上下文无关文法 38 一个句型中的(A)称为该句型的句柄。 A. 最左直接短语 B.最右直接短语 C. 终结符 D. 非终结符 39 在自底向上的语法分析方法中，分析的关键是(D) A. 寻找句柄 B. 寻找句型 C. 消除递归 D. 选择候选式 40 在自顶向下的语法分析方法中，分析的关键是(C) A. 寻找句柄 B. 寻找句型 C. 消除递归 D. 选择候选式 41 在LR分析法中，分析栈中存放的

9、状态是识别规范句型(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 按逻辑上划分，编译程序第三步工作是(A) A. 语义分析 B. 词法分析 C. 语法分析 D. 代码生成 46 在语法分析处理中，FIRST集合、FOLLOW集合

10、均是(B) A. 非终结符集 B.终结符集 C. 字母表 D. 状态集 47 编译程序中语法分析器接收以(A)为单位的输入。 A. 单词 B.表达式 C. 产生式 D. 句子 48 编译过程中，语法分析器的任务就是(B) A. 分析单词是怎样构成的 B. 分析单词串是如何构成语句和说明的 D. 分析程序的结构 C. 分析语句和说明是如何构成程序的 49 若一个文法是递归的，则它所产生的语言的句子(A)。 A.是无穷多个 B.是有穷多个 C.是可枚举的 D.个数是常量 50 识别上下文无关语言的自动机是(C) A. 下推自动机 B. NFA C. DFA D. 图灵机 51 编译原理各阶段工作都

11、涉及(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*1 C. 0(1|10)*1 D. 1(10|01)*0 54 与(a|b)*(a|b)等价的正规式是(C)。 A.a*| b* B.(ab)*(a|b) C. (a|b)(a|b)* D.(a|b)* 55 (D)文法不是LL(1

13、|k0 60 若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. bbaa B. abba C. abab D. aabb 64 有限状态自动机能识别(C) A.上下文无关语言 B.上下文有关语言 C.正规语言 D.0型文法定义的语言

14、 65 已知文法G是无二义的，则对G的任意句型(A) A.最左推导和最右推导对应的语法树必定相同 B.最左推导和最右推导对应的语法树可能相同 C.最左推导和最右推导必定相同 D.可能存在两个不同的最左推导，但他们对应的语法树相同 66 (B)不是DFA的成分 A.有穷字母表 B.多个初始状态的集合 C.多个终态的集合 D.转换函数 67 与逆波兰式(后缀表达式)ab+c*d+对应的中缀表达式是(B) A. a+b+c*d B. (a+b)* c+d C. (a+b)* (c+d) D. a+b*c+d 68 后缀式abc+d+可用表达式(B)来表示。 A( (a+b)c)+d B(a+(bc)

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

17、OW集非终结符 S H M A FIRST集 a. a ，d. a ，e ， a ，e. FOLLOW集 # . # . d ，b b. 由于predictpredict=ad = predictpredict=a ，ed ，b = predictpredict= a e = 所以该文法是LL(1)文法，LL(1)分析表如下表。 S H M A a aH. aMd Ab. aM. d d. b e Ab e. # 5 判断下面文法是否为LL(1)文法，若是，请构造相应的LL(1)分析表。 SaD DSTe| TbH|H Hd| 答：首先计算文法的 FIRST集和FOLLOW集如下表。非终

18、结符 S D T H a a， b，d， d， FIRST集 FOLLOW集 #，b，d，e. #，b，d，e e e 由于predictpredict=a# ，b ，d ，e = predictpredict=be = predictpredict= d e = 所以该文法是LL(1)文法，LL(1)分析表如下表： S D T H a aD. STe e H. b bH d H. d. # 6 判断下面文法是否为LL(1)文法，若是，请构造相应的LL(1)分析表。 SaD DSTe| TbM MbH HM| 答：文法的 FIRST集和FOLLOW集非终结符 S D T M H FIRST

19、集 a. a ， b. b. b ， FOLLOW集 # ，b # ，b e. e. e. 由于predictpredict=a# ，b= predictpredict= b e = 所以该文法是LL(1)文法，LL(1)分析表如下表： a e b # S D T M H aD. STe bM bH M. 7 某语言的拓广文法G为： (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 存在移进-归约和归约-归约冲

20、突，所以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)= b Follow(B)= a ,# 在I0中: Follow(D) d= b d= Follow(B) d= a ,# d= Follow(D) Follow(B)= ba ,# = 在I3中: Follow(S) a=#a= 所以在I0，I3中的移进-归约和归约-归约冲突可以由Follow集解决,所以G是SLR(1)文法, 构造的

21、SLR(1)分析表如下表： ACTION 状态 b 0 1 2 3 r4 S5 d S4 a r6 S6 # r6 acc r2 S 1 D 2 B 3 GOTO 4 5 6 r3 r5 r1 r5 8 给出与正规式R*ba等价的NFA。答：与正规式R等价的NFA如下图 9 给出与正规式R*a 等价的NFA。答：与正规式R等价的NFA如下图 10 给出与正规式 R*b等价的NFA。答：与正规式R等价的NFA如下图 11 将下图的NFA确定化为DFA。答：用子集法确定化如下表 I X,1,2 1,2. 1,2,3 1,2,Y 确定化后如下图： Ia 1,2. 1,2. 1,2,Y

22、 1,2. Ib 1,2,3 1,2,3 1,2,3 1,2,3 状态 X 1 2 3 12 将下图的NFA确定化为DFA。答：用子集法确定化如下表 I X,0,1,3 0,1,3. 2,3,Y. 1,3. 2,Y. Y. 确定化后如下图 Ia 0,1,3 0,1,3 1,3. . 1,3. . Ib 2,3,Y 2,3,Y Y. 2,Y. Y. . 状态 X 1 2 3 4 Y 13 某语言的拓广文法G为： (0) ST (1) T aBd| (2) B Tb| 证明G不是LR(0)文法而是SLR(1)文法，请给出SLR(1)分析表。答：拓广文法G，增加产生式ST 在项目集I0中：

23、有移进项目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，中的移进-归约和归约-归约冲突可以由Follow集解决，所以G

24、是SLR(1)文法。构造的SLR(1)分析表如下表。 SLR(1)分析表 ACTION name a 0 1 2 3 4 S2 S2 b r2 r2 S6 d r4 S5 # r2 acc r2 T 1 4 B 3 GOTO 5 6 r1 r3 r1 14 某语言的文法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

25、Eb (4) T a G的LR(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)分析表如下表： ACTION name a 0 1 2 3 S2 S5 b r2 r2 d S6 # r2 acc r2

27、 1) M VbA 2) V d 3) V 4) A a 5) A Aba 6) A ACTION name b d a # M A V GOTO 0 1 2 3 4 5 6 7 8 答： r3 S4 r2 r6 r4 S7 r5 S3 S5 S8 acc r6 r4 r1 r5 1 6 2 对串dbba#的分析过程如下表步骤 1 2 3 4 5 6 7 8 9 状态栈 0 03 02 024 0246 02467 024678 0246 01 文法符号栈 # #d #V #Vb #VbA #VbAb #VbAba #VbA #M 剩余输入符号 dbba# bba# bba# ba# ba#

28、 a# # # # 移进用V d归约移进用A 归约移进移进用A Aba 归约用M VbA 归约接受动作 19 文法GS及其LR分析表如下，请给出对输入串da;aoa#的分析过程。 GS: 0) SS 1) SdSoS 2) S dS 3) S S;S 4) S a name ACTION GOTO d 0 1 2 3 4 5 6 7 8 答： S2 S2 S2 S2 a S3 r4 S7 r3 r1 ; S4 r4 S4 r3 S4 a S3 S3 S3 S3 # acc r4 r2 r3 r1 S 1 5 6 8 输入串da;aoa#的分析过程如下表：步骤 1 2 3 4

29、 5 6 7 8 9 10 11 12 0 02 023 025 0254 02543 02546 025 0257 02573 02578 01 状态栈 # #d #da #dS #dS; #dS;a #dS;S #dS #dSo #dSoa #dSoS #S 文法符号栈剩余输入符号 da;aoa# a;aoa# ;aoa# ;aoa# aoa# oa # oa # oa # a # # # # 动作移进移进用S a 归约移进移进用S a 归约用S S;S 归约移进移进用S a 归约用SdSoS 归约接受 20 文法GM及其LR分析表如下，请给出对串dada#的分析

30、过程。 GM: 1) S VdB 2) V e 3) V 4) B a 5) B Bda 6) B ACTION 状态 d 0 1 2 3 4 5 6 7 8 答：对串dada#的分析过程如下表步骤 1 2 3 4 5 6 7 8 9 0 02 024 0245 0246 02467 024678 0246 01 状态栈 # #V #Vd #Vda #VdB #VdBd #VdBda #VdB #S 文法符号栈剩余输入符号 dada# dada# ada# da# da# a# # # # 动作用V 归约移进移进用B a归约移进移进用B Bda 归约用S VdB 归约接

31、受 r3 S4 r2 r6 r4 S7 r5 e S3 a S5 S8 # acc r6 r4 r1 r5 S 1 B 6 V 2 GOTO 21 文法GE为：EE+T|T TT*F|F F(E)|i 试给出句型(E+F)*i的短语，简单(直接)短语,句柄和最左素短语。答：短语有: (E+F)*i ，(E+F) ，E+F ，F ，i 简单(直接)短语有：F ，i 句柄是：F 最左素短语是：E+F 22 文法GS为： SV VT | ViT TF| T+F F)V* |( 试给出句型ViFi(的短语，简单(直接)短语,句柄和最左素短语。答：短语有: ViFi( ，ViF ， F ，( 简

34、n0，m 0用二型文法。答：解：描述L1语言的正规文法如下： ScA AaA|B BdD DbD| 解：描述L2语言的二型文法如下： SAB A0A1|0a1 BbBc| 27 写出表达式(a+b)/(a-b)-a(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 x:=a

35、+b*c else x:=b-a; 答： (1) ( j, a, b, (3) (2) ( j, , , (7) ) (3) ( *, b, c, T1) (4) ( +, a, T1, T2) (5) ( :=, T2, , x) (6) ( j, , , (9) (7) ( -, b, a, T3) (8) ( :=, T3, , x) (9) ( ) 30 翻译成四元式序列。 While a0 b0 do Begin X：X1； if a0 then a：a1 else b：b1 End；答： (1) (j，a，0，5) (2) (j，3) (5) (，1，T1) (6) (：，T1，

36、) (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) Sa a (S，a)，a) TS S (T，a)，a) Sa a (T，S)，a) TT，S T，S (S)，a) TS S (T)，a) SS(T) (T) (S，a) TS S (T，a) Sa a (T，S) TT，S T，S (T) S(T) (T) S

展开阅读全文