识别活前缀的DFA 如下：
I0： S I1： E?E?T?E?T*F
6、一个编译程序的代码生成要着重考虑哪些问题?（6分）
S??.S S??S. 7、编译过程中可进行的优化如何分类？最S?.BB B 8分） I常用的代码优化技术有哪些？（I2： B?.ab 5： B 8?、有哪些存储分配策略？并叙述何时用何SBB. B?.b b S?B.B B?.ab b 种存储分配策略？（8分） B?.b a 9、请将表达式-(a+b)*(c+d)-(a+b)分别表
a b 示成三元式、间接三元式和四元式序列。（12 I3： I4： 分） b B?a.B B?b. a B?.ab 二（每小题10分，共80分）简答题
B?.b 1.画出编译程序的总体结构图，简述各部分的主要功能。 B 2. 已知文法G[E]:
I6： E→ET+|T T→TF* | F F→F^ | a
B?aB. 试证：FF^^*是文法的句型，指出该句型的
短语、简单短语和句柄.
LR(0)分析表如下： 3．为正规式(a|b) *a(a|b)构造一个确定的
有限自动机。 状态 Action Goto 4． 设文法G(S)： a b # S B 2 S→(L)|a S|a 0 S3 S4 1 L→L，S|S 1 acc 5 (1) 消除左递归和回溯； 2 S3 S4 6 (2) 计算每个非终结符的FIRST和3 S3 S4 FOLLOW4 R3 R3 R3 ； 5 R1 R1 R1 (3) 构造预测分析表。 5．6 R2 R2 R2 已知文法 A->aAd| aAb|ε
判断该文法是否SLR（1）文法，若是构造相编译原理H卷
2、令文法G为 应分析表，并对输入串ab#给出分析过程。
6． 构造算符文法G[H]的算符优先关系（含N?D|ND
＃）。 D?0|1|2|3|4|5|6|7|8|9 G[H]：H→H;M|M （1） 文法G的语言L（G）是什么？
M→d|aHb （4分）
7．已构造出文法G（S） （2） 给出句子34和568的最左推导
（1）S BB 和最右推导。（6分）
（2）B aB 5、令文法G为：
（3）B b E?E?T|T1）。给出DFA图 T?T?F|F
2）.给出LR分析表 F??E?|i3）．假定输入串为abaab，请给出LR分析过证明E?T?F是它的一个句型，指出这个
程（即状态，符号，输入串的变化过程）。 句型的所有短语、直接短语和句柄。（12分）
26
8． 将下面的语句翻译成四元式序列： while A if A=1 then C:=C+l else while A≤ D do A:=A+2； 9． 对下面的流图， (1)求出流图中各结点N的必经结点集D(n)， (2)求出流图中的回边， (3)求出流图中的循环。 H卷答案 {2,3,4} {2,3,5} {2,3,4,Y} 最小化： {2,3,5} {2,3} {2,3,5} {0,1,2,3,4,5},{6}{0,1,2,3,4,5}0?{1,3,5} {0,1,2,3,4,5}1?{0,1,2,3,4},{5},{6}{0,1,2,3,4}?{1,3,5}0{0,1,2,3},{4},{5},{6}{0,1,2,3}0?{1,3} {0,1,2,3}1?{1,2,4}{0,1},{2,3}{4},{5},{6}{0,1}0?{1} {0,1}1?{1,2}{2,3}0?{3} {2,3}1?{4}{0},{1},{2,3},{4},{5},{6} 5解：短语: E+T*F, T*F 直接短语: T*F 句柄: T*F 6答：代码生成器的设计要着重考虑目标代码的质量问题，而衡量目标代码的质量主要 2解：(1) L(G1)是0~9组成的数字串 从占用空间和执行效率两个方面综合考虑。 (2) 最左推 导:7答：依据优化所涉及的程序范围，可以分 为：局部优化、循环优化和全局优化。 N?ND?DD?3D?34最常用的代码优化技术有1. 删除多余运 N?ND?NDD?DDD?5DD?56D?568算；2. 代码外提；3. 强度削弱；4. 变换 循环控制条件；5. 合并已知量与复写传播； 最右推6. 删除无用赋值 导: 8答：静态分配策略：如果在编译时能确定N?ND?N4?D4?34数据空间的大小，则可采用静态分配方法： N?ND?N8?ND8?N68?D68?568在编译时刻为每个数据项目确定出在运行 时刻的存储空间中的位置。动态分配策略：3解： 如果在编译时不能确定运行时数据空间的 大小，则必须采用动态分配方法。允许递归 0 过程和动态申请释放内存。包括：栈式动态X 1 2 3 4 5 Y 1 ? 分配和堆式动态分配 ? 1 0 1 1 9解： 三元式 确定化： 间接三元式 0 (1) (+ a, 1 b) {X} φ 间接三元式序列 间接码表{1,2,3} φ φ (2) (+ c, φ d) {1,2,3} {2,3} (1) (+ a, b) {2,3,4} (1) (3) (* {2,3,4} (1), (2)) {2,3} {2,3} 27 (2) (+ c, d) (2) 出现错误， (4) (- (3), /) 出错处理程序对发现的错误都及时进行处(3) (* (1), (2)) (3) 理。 (5) (+ a, b) 2． 【解答】 (4) (- (3), /) (4) 该句型对应的语法树如下：该句型相对于E (6) (- (4), (5)) 的短语有FF^^*；相对于T的短语有FF^^*,F;(5) (- (4), (1)) (1) 相对于F的短语有F^;F^^;简单短语有F;F^; 句柄为F. (5) 四元式 (1) (+, a, b, t1) (2) (+, c, d, t2) (3) (*, t1, t2, t3) (4) (-, t3, /, t4) (5) (+, a, b, t5) (6) (-, t4, t5, t6) 二．简答题 1． 【解答】 编译程序的总体结构图如图1.2所示。 词法分析器：输入源程序，进行词法分析，输出单词符号。 语法分析器：在词法分析的基础上，根据语言的语法规则（文法规则）把单词符号串分 解成各类语法单位，并判断输入串是否构成语法上正确的“程序”。 中间代码生成器：按照语义规则把语法分析器归约（或推导）出的语法单位翻译成一定 形式的中间代码，比如说四元式。 优化：对中间代码进行优化处理。 目标代码生成器：把中间代码翻译成目标语言程序。 表格管理模块保存一系列的表格，登记源程序的各类信息和编译各阶段的进展情况。编 译程序各阶段所产生的中间结果都记录在表格中，所需信息多数都需从表格中获取，整个编 译过程都在不断地和表格打交道。 出错处理程序对出现在源程序中的错误进行处理。此外，编译的各阶段都可能 4． 【解答】 (1) S→(L)|aS’ S’→S|ε L→SL’ L’→SL’|ε 评分细则：消除左递归2分，提公共因子2分。 (2) FIRST和FOLLOW FIRST)S)＝{(，a} FOLLOW(S)＝{#，，，)} FIRST(S’)＝{，a,ε} FOLLOW(S’)＝{#，，，)} FIRST(L)＝{(，a} FOLLOW(L)＝{ )} FIRST(L’)＝{，，ε} FOLLOW(L’〕＝{ )} 5． 【解答】 (1)拓广文法 (0)S->A (1) A->aAd (2)A-> aAb (3)A->ε (2)构造识别活前缀的DFA FOLLOW(A)={d,b,#} 对于状态I0：FOLLOW(A)∩{a}=Ф 对于状态I1：FOLLOW(A)∩{a}=Ф 因为，在DFA中无冲突的现象，所以该文法是SLR(1)文法。 (3)SLR(1)分析表 状态 ACTION GOTO a B d # A 0 S2 r3 r3 r3 28 1 1 acc 2 S2 r3 r3 r3 3 3 S5 S4 态 ACTION GOTO a b # S B 0 s3 s4 1 2 1 acc 2 S3 S4 5 4 r1 r1 r1 5 r2 r2 r2 (4)串ab#的分析过程 步骤 状态栈 符号栈 当前字符 剩余字符串 动作 1 0 # a b# 移进 2 02 #a b # 归约A->ε 3 023 #aA b # 移进 4 0235 #aAb # 归约A-> aAb 5 01 #A # 接受 7． 【解答】 （1）LR分析表如下： （2）分析表 状 3 s3 s4 6 4 r3 r3 5 R1 R1 r1 6 R2 R2 R2 (3) 句子abaab的分析过程 表:句子abaab的分析过程 步骤 状态 符号栈 输入串 所得产生式 0 #0 # abaad# 1 #03 #a baad# 2 #034 #ab aab# B→b 3 #036 #aB aab# B→aB 4 #02 #B aab# 5 #023 #Ba ab# 6 #0233 #Baa b# 7 #02334 #Baab # 8 #02336 #BaaB # 9 #0236 #BaB ad# 10 #025 #BB 29 ad# 11 #01 #S d# 12 # # d# 13 识别成功 111 (j,_,_,108) /*转回内层while语句开始处*/ 112(j,_,_,100) /*转回外层while语句开始处*/ 8． 【解答】 该语句的四元式序列如下（其中E1、E2和E3分别对应：A 100 (j<,A,C,102) 101(j,_,_,113） /*E1为F*/ 102 (j<,B,D,104) /*El为T*/ 103 (j,_,_,113) /*El为F*/ 104 (j=,A,1,106) /*Ez为T*/ 105 (j,_,_,108） /*EZ为F*/ 106 (＋,C,1,C) /*C:=C+1*/ 107 (j,_,_,112) /*跳过else后的语句*/ 108 (j≤,A,D,110) /*E3为T*/ 109 (j,_,_,112) /*E3为F*/ 110 (＋,A,2,A) /*A:=A+2*/ 113编译原理I卷 第 3 题 何谓翻译程序、编译程序和解释程序？它们三者之间有何种关系？ 第 5 题 编译程序大致有哪几种开发技术？ 第 1 题 文法 G＝({A,B,S},{a,b,c},P,S)其中 P 为： S→Ac|aB A→ab B→bc 写出 L(G[S])的全部元素。 第３题 为只包含数字、加号和减号的表达式，例如 9-2＋5，3-1，７等构造一个文法。 第 4 题 已知文法 G[Z]： Z→aZb|ab 写出 L(G[Z])的全部元素。 第 5 题 写一文法，使其语言是偶正整数的集合。 要求： (1) 允许 0 打头； (2)不允许 0 打头。 8.文法 G[S]为： S→Ac|aB A→ab B→bc 该文法是否为二义的？为什么？ 第 9 题 考虑下面上下文无关文法： S→SS*|SS+|a (1)表明通过此文法如何生成串 aa+a*，并为该串构造语法树。 30