2022年编译原理练习题及答 .pdf

《2022年编译原理练习题及答 .pdf》由会员分享，可在线阅读，更多相关《2022年编译原理练习题及答 .pdf（15页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、2013-5-1 第一章练习题（绪论）一、选择题1编译程序是一种常用的软件。A) 应用B) 系统C) 实时系统D) 分布式系统2编译程序生成的目标代码程序是可执行程序。A) 一定B) 不一定3编译程序的大多数时间是花在上。A) 词法分析B) 语法分析C) 出错处理D) 表格管理4将编译程序分成若干“遍”将。A) 提高编译程序的执行效率；B) 使编译程序的结构更加清晰，提高目标程序质量；C) 充分利用内存空间，提高机器的执行效率。5编译程序各个阶段都涉及到的工作有。A) 词法分析B) 语法分析C) 语义分析D) 表格管理6词法分析的主要功能是。A) 识别字符串B) 识别语句C) 识别单词D) 识

2、别标识符7若某程序设计语言允许标识符先使用后说明，则其编译程序就必须。A) 多遍扫描B) 一遍扫描8编译方式与解释方式的根本区别在于。A) 执行速度的快慢B) 是否生成目标代码C) 是否语义分析名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 15 页 - - - - - - - - - 2013-5-1 9多遍编译与一遍编译的主要区别在于。A) 多遍编译是编译的五大部分重复多遍执行，而一遍编译是五大部分只执行一遍；B) 一遍编译是对源程序分析一遍就立即执行，而多遍编译是对

3、源程序重复多遍分析再执行；C) 多遍编译要生成目标代码才执行，而一遍编译不生成目标代码直接分析执行；D) 多遍编译是五大部分依次独立完成，一遍编译是五大部分交叉调用执行完成。10编译程序分成“前端”和“后端”的好处是A)便于移植B)便于功能的扩充C)便于减少工作量D)以上均正确名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 15 页 - - - - - - - - - 2013-5-1 第二章练习题（文法与语言）一、选择题1 文法 G 产生的 (1) 的全体是该文法描述的

4、语言。A.句型 B. 终结符集 C. 非终结符集D. 句子2若文法 G 定义的语言是无限集，则文法必然是 (2) A递归的 B 上下文无关的 C 二义性的 D 无二义性的3 Chomsky 定义的四种形式语言文法中， 0 型文法又称为(A)文法；1 型文法又称为(C) 文法； 2 型语言可由(G) 识别。A 短语结构文法 B 上下文无关文法 C 上下文有关文法 D 正规文法E 图灵机 F 有限自动机 G 下推自动机4一个文法所描述的语言是(A)；描述一个语言的文法是(B)。A 唯一的 B 不唯一的 C 可能唯一，也可能不唯一二、构造文法以生成下列语言：1 an bnn0 G=（S ，a，b ，

5、 S， P） ，其中 P = S | aSb 2 an bmn，m1 G=（S，A，B，a，b， S， P） ，其中 P = S AB，AaaA，BbbB3 an , bmn，m1 G=（S，A，B，a，b， S， P） ，其中 P = S A | B，AaaA，BbbB 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 15 页 - - - - - - - - - 2013-5-1 4. L = w | w 是不含两个相邻1 的 0、1 串 G=（S , A ，0，1，

6、S， P） ，其中 P = S0 | 1 | 0S | 1A， A 0S0 5能被 5 整除的整数集合。GS: SFNC F+ | - | C0 | 5 NAN |A0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 以下更准确：GS: SFC |FNMC F+ | - | C0 | 5 N1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 MAM |A0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理

7、- - - - - - - 第 4 页，共 15 页 - - - - - - - - - 2013-5-1 第四章练习题（词法分析）一、设语言 L 是由奇数个 a 和偶数（可以是 0）个 b 组成的符号串之集。1. 构造识别 L 的 DFA ；一、12. 给出定义 L 的正规文法；2S=aA|bB A=aS|bC B=bS|aC C=bA|aB （其它习题见本章课件）名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 15 页 - - - - - - - - - 2013-5

8、-1 第五章练习题（自上而下语法分析）1、 已知文法 G(E) ET | ET TF | T * F F(E) | i (1) 给出句型 (T * Fi)的最右推导及画出语法树；(2) 给出句型 (T * Fi)的短语、素短语。1）最右推导：E= E+T = E+F = E+i = T+i = T*F+i 2）句型 T*F+i 的短语：T*F+i T*F i 素短语：T*F i 2、给出文法GS: S - aSb | P P - bPc | bQc Q - Qa | a 1) 它是 Chomsky 哪一型文法？2) 它是不是LL(1) 文法？若不是，求消除左递归、提取公共左因子名师资料总结 -

9、 - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 15 页 - - - - - - - - - 2013-5-1 后的文法 G 。3) 证明所有 (a)左递归、 (b)由公共左因子的文法均不是LL(1)文法。4) G 是不是 LL(1) 文法，试用预测分析表证实。1）2 型文法2）不是 LL(1) 文法 , 转换：G S: S - aSb | P P - bK K - Pc | Qc Q - aW W - aW |3) LL(1) 为从上往下推导，若存在左递归，即形如P-P 的产生式，则面

10、对 FIRST(P)的符号，会反复用 P-P进行往下推导， 无法终止，故左递归文法不是LL(1) 文法。有公共左因子的文法存在形如P-a|a 的产生式，那么，当面对属于 FIRST(a) 的终结符时，无法确定用P-a还是用 P- a 匹配，也就是说存在多重入口，所以有公共左因子的文法不是LL(1)文法。4）FIRST(S)=a, b, FIRST(P)=b , FIRST(K)=b, a, FIRST(Q)=a, FIRST(W)=a, ; FOLLOW(S)=#, b , FOLLOW(P)=#, b, c=FOLLOW(K), 名师资料总结 - - -精品资料欢迎下载 - - - - -

11、- - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 15 页 - - - - - - - - - 2013-5-1 FOLLOW(Q)= c = FOLLOW(W) LL(1) 预测分析表：a b c # S S -aSb S - P P P - bK K K -Qc K - Pc Q Q - aW W W - aW W -表中没有多重入口，故文法G 是 LL(1) 文法。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页

12、，共 15 页 - - - - - - - - - 2013-5-1 第六章练习题（自下而上语法分析-优先分析法）1. 已知文法 G(S) Sa | (T) TT , S | S 写出句子 (a，a)，a)的规范归约过程及每一步的句柄。1、答：句型归约规则句柄(a，a)，a)Saa (S，a)，a)TSS (T ，a)，a)Saa (T ，S)，a)TT ，ST，S (T) ，a)S(T)(T) (S，a)TSS (T，a)Saa (T，S)TT ，ST，S (T)S(T)(T) S （其它习题见本章课件）名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - -

13、 - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 15 页 - - - - - - - - - 2013-5-1 第七章练习题（自下而上语法分析-LR 分析法）(习题见本章课件 ) 第八章练习题（语义分析）1. 写出表达式 (ab*c)/(ab)d 的逆波兰表示、三元式序列及三地址结构的四元式序列。1. 逆波兰表示：abc*ab/d三元式序列： (*，b，c) (，a，) (，a，b) (/， ) (， d)四元式序列： T1= b * c T2= a + T1 T3= a + b T4 = T2 / T3 T5 = T4 d 名师资料总结 - - -精品资料

14、欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 15 页 - - - - - - - - - 2013-5-1 2写出语句if a0a0 goto 102 101 goto 107 102 if aC goto L2 B:=B+1 goto L1 L2: write A halt 1.程序流图2. 给定基本块：Read C A:=0 B:=1 L1: A:=A+B if BC goto L2 B:=B+1 goto L1 L2: write A halt B1B2B3B4名师资料总结 - - -精品资

15、料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 12 页，共 15 页 - - - - - - - - - 2013-5-1 A:=3*5 B:=E+F C:=A+12 D:=E+F A:=D+12 C:=C+1 E:=E+F 假定出基本块后，只有 A 、 C 、 E 是活跃的，给出用 DAG 图完成优化后的代码序列。2.化简后的的四元式序列为C := 28 A := D+12 E := E+F 3. 对下面的四元是式序列：A=0 I=1 L1: B=J+1 C=B+I A=C+A If I=100 goto L

16、2 I=I+1 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 13 页，共 15 页 - - - - - - - - - 2013-5-1 Goto L1 L2: write A Halt (1)画出其控制流程图(2) 求出循环并进行循环的代码外提和强度削弱优化。3. (1) A=0 I=1 L1: B=J+1 C=B+I A=C+A If I=100 goto L2 I=I+1 Goto L1 L2: write A Halt B1 B2 B3 B4 名师资料总结 - - -精品

17、资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 14 页，共 15 页 - - - - - - - - - 2013-5-1 (2) (3)A=0 I=1 L1: A=C+A If I=100 goto L2 I=I+1 C=C+1 Goto L1 L2: write A Halt B1 B2 B3 B4 B=J+1 C=B+I B2名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 15 页，共 15 页 - - - - - - - - -