编译原理练习题及答案.doc

第一章练习题（绪论）一、选择题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) 识别标识符7若某程序设计语言允许标识符先使用后说明，则其编译程序就必须 。A) 多遍扫描 B) 一遍扫描8编译方式与解释方式的根本区别在于 。A) 执行速度的快慢B) 是否生成目标代码C) 是否语义分析 9多遍编译与一遍编译的主要区别在于 。A) 多遍编译是编译的五大部分重复多遍执行，而一遍编译是五大部分只执行一遍；B) 一遍编译是对源程序分析一遍就立即执行，而多遍编译是对源程序重复多遍分析再执行；C) 多遍编译要生成目标代码才执行，而一遍编译不生成目标代码直接分析执行；D) 多遍编译是五大部分依次独立完成，一遍编译是五大部分交叉调用执行完成。10编译程序分成“前端”和“后端”的好处是 A)便于移植B)便于功能的扩充C)便于减少工作量D)以上均正确第二章练习题（文法与语言）一、选择题 1 文法 G 产生的 (1) 的全体是该文法描述的语言。 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 可能唯一，也可能不唯一 二、构造文法以生成下列语言：1an bnn0G=（S，a，b， S， P），其中P = S e | aSb 2an bmn，m1G=（S，A，B，a，b， S， P），其中P = S AB，AaaA，BbbB3an , bmn，m1G=（S，A，B，a，b， S， P），其中P = S A | B，AaaA，BbbB4. L = w | w是不含两个相邻1的0、1串G=（S , A，0，1， S， P），其中P = S0 | 1 | 0S | 1A， A 0S0 5能被5整除的整数集合。GS: S FNCF + | - | eC 0 | 5N AN | eA 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9以下更准确：GS: S FC |FNMCF + | - | eC 0 | 5N 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9M AM | eA 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9第四章练习题（词法分析）一、设语言L是由奇数个a和偶数（可以是0）个b组成的符号串之集。1.构造识别L的DFA；一、12. 给出定义L的正规文法；2 S=aA|bB A=aS|bC B=bS|aCC=bA|aB（其它习题见本章课件）第五章练习题（自上而下语法分析）1、 已知文法G(E)ET | ETTF | T * FF(E) | i(1) 给出句型(T * Fi)的最右推导及画出语法树；(2) 给出句型(T * Fi)的短语、素短语。1）最右推导： E= E+T = E+F = E+i = T+i = T*F+i2）句型T*F+i 的短语： T*F+i T*F i 素短语： T*F i 2、给出文法GS:S - aSb | PP - bPc | bQcQ - Qa | a1) 它是Chomsky哪一型文法？2) 它是不是LL(1)文法？若不是，求消除左递归、提取公共左因子后的文法G。3) 证明所有(a)左递归、(b)由公共左因子的文法均不是LL(1)文法。4) G是不是LL(1)文法，试用预测分析表证实。1）2型文法2）不是LL(1)文法, 转换：GS:S - aSb | PP - bKK - Pc | QcQ - aWW - aW |3) LL(1)为从上往下推导，若存在左递归，即形如P-P 的产生式，则面对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),FOLLOW(Q)= c = FOLLOW(W) LL(1)预测分析表：abc#SS -aSbS - PPP - bKKK -QcK - PcQQ - aWWW - aWW -表中没有多重入口，故文法G是LL(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，S T，S(T)，a) S(T) (T)(S，a) TSS(T，a) Saa(T，S) TT，S T，S(T) S(T)(T) S（其它习题见本章课件）第七章练习题（自下而上语法分析-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 d2写出语句if a0a0 goto 102 101 goto 107102 if aC goto L2B:=B+1goto L1L2: write AhaltRead CA:=0B:=1B=1AL1: A:=A+Bif BC goto L2B:=B+1goto L1L2: write AhaltB1B2B3B41.程序流图 2.给定基本块： 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=0I=1L1: B=J+1C=B+IA=C+AIf I=100 goto L2I=I+1Goto L1L2: write AHalt(1) 画出其控制流程图(2) 求出循环并进行循环的代码外提和强度削弱优化。3.(