（10 分） else A:=A+2
（只给出最后结果，设 nextstat 当前值为 100） if A<0
-, -, 0 104 107 T1 A 100 T2 A 100
then A:=A+1
j< , A , C , 102
j< , A , 0 , j, -, -,
+ , A, 1, := , T1 , - , j, -, -,
} } } } } } } }
#
E '→ε
T'→ε
五、对于文法 G3，填写下列集合和 G 3 的优先关系表。 G3： E →E+T ∣T T→T*F ∣F F→（E ）∣i + + * （ ） i # > > < > > < FIRSTVT （E ） ={ +, *, (, i } FIRSTVT（T ）={ *, (, i FIRSTVT（F）={ (, i * < > < > > < < （ < < < ） > > = > > < i < < < > > = # > > } }
一、文法 1． 文法定义 G=(VN , V T, P, S)
V N：一组非终结符号 V T：一组终结符号 P： 一组产生式 S： 一个开始符号 2． 文法分类 按对产生式施加不同的限制把文法分成四种类型：
0 型：短语文法 1 型：上下文有关文法 2 型：上下文无关文法 3 型：正规文法（正则文法、线性文法） 3． 涉及的上下文无关文法：算符文法、算符优先文法、LL （1）文法、LR 文法 4． 文法的二义性 5． 文法的实用限制
直接短语：QbR 句柄：QbR
第2 页
四、对于文法 G 2，填写各产生式的选择集合和 G2 的预测分析表。 （15 分） G2：① E →TE' ② E'→+TE’ ③ E'→ε ④ T→FT' ⑤ T') ⑧ F→ i
+ E E' T T' F T'→ε T'→*FT’ F→(E) E'→+TE’ T→FT' T'→ε F→ i *
其它章节的内容比较单一，在复习的基础上重点思考下列问题：
1． 什么叫翻译程序？什么叫汇编程序？什么叫编译程序？ 2． 编译过程分哪几个主要阶段？每个阶段的主要任务是什么？ 3． 单词符号分哪几类？各举出例子。 4． 存储分配有哪几种？影响存储分配策略的主要因素是什么？ 5． 通常参数传递有哪些主要方式？每种方式是如何实现的？ 6． 中间代码通常有哪些类型？各有什么特点？ 7． 什么叫语法制导翻译法？ 8． 试述赋值语句、布尔表达式、IF 语句、WHILE 语句、REPEAT 语句的文法、语义、 翻译目标、文法改造及改造的理由？ 9． 中间代码优化分哪几类？每一类有哪些主要优化技术？ 10．什么叫基本块？如何把中间代码程序划分成基本块？ 11．基本块目标代码生成算法？ 12．目标代码生成中的寄存器分配算法？
第1 页
二、编译过程通常分为哪几个主要阶段？每个阶段的主要功能？（15 分） 答：编译过程通常分为词法分析、语法分析、语义分析、中间代码生成、代 码优化和目标代码生成六个主要阶段。各个阶段的主要功能如下： 词法分析阶段：读入源程序，对构成源程序的字符流进行扫描和分 解，识别出一个个单词，并表示成计算机内部的形式（TOKEN 字） 。 语法分析阶段：在词法分析的基础上，将单词序列分解成各类语法 短语，如“表达式” 、 “语句” 、 “程序”等，确定整个输入串是否构成语 法上正确的程序。 语义分析阶段：审查源程序有无语义错误，为代码生成阶段收集类 型信息。 中间代码生成阶段：将源程序翻译成一种复杂性介于源程序与目标 程序之间的内部形式（中间代码） 。 代码优化：对前阶段产生的中间代码进行等价变换，目的是使将来 生成的目标代码更为高效。 目标代码生成：把中间代码变换成特定机器上的绝对指令代码或可 重定位的指令代码或汇编指令代码。 三、设有文法 G 1 （10 分） 1． 证明句型 QbRae 是规范句型 G1：S→SaQ ∣ Q Q→QbR ∣ R R→cSd ∣ e 证： 因为句型 QbRae 可由文法开始符 S 经过规范推导产生，推导过程如下： S =R> SaQ =R> SaR =R> Sae =R> Qae =R> QbRae 所以句型 QbRae 是规范句型。 2．给出句型 QbRae 的短语，直接短语和句柄： 短语：QbR e QbRae e
--
AVALUE T1 在 R1 中 T2 在 R2 中 T3 在 R1 中 T2 在 R2 中 T3 在 R1 中 T4 在 R2 中 T5 在 R1 中 W 在 R2 中
T5:= T3-T4 W：= T2/T5
T3 独占的 R1 空闲的 R2 释放 R2
第4 页
编译原理复习题
本门课程的重点是语法分析。它包含的内容广（第 3 章：文法；第 5、6、 7 章：分析方法） ，基本概念和基本方法多。为了便于大家复习，现把这四章 的内容归纳如下：
+ , A, 2, := , T2 , - , j, -, -,
七、用基本块代码生成算法生成目标代码。
（15 分）
（假定允许使用 R1 和 R2 寄存器，临时变量 Ti 出基本块后都不活跃） 四元式 T1：= A+B T2：= C-T1 T3：= D*E T4：= F+G 选取 R 空闲的 R1 空闲的 R2 空闲的 R1 释放 R2 目标代码 LD R1 , A ADD R1 , B LD R2 , C SUB R2 , R1 LD R1 , D MUL R1 , E ST R2 , T2 LD R2 , F ADD R2 , G SUB R1 , R2 LD R2 , T2 DIV R2 , R1 ST R2 , W RVALUE R1 中含有 T1 R2 中含有 T2 R1 中含有 T3 R2 中含有 T2 R1 中含有 T3 R2 中含有 T4 R1 中含有 T5 R2 中含有 W
《编译原理》考试卷（ 120 分钟）
班级
一、 填空
学号
姓名
评分
（20 分，每空 1 分）
1．文法 G 包括四个组成部分：一组终结符号，一组非终结符号，一组产生 式，以及一个开始符号。 2．文法按产生式的形式分为四种类型，它们是：0 型文法，又称短语文法； 1 型文法，又称上下文有关文法；2 型文法，又称上下文无关文法；3 型 文法，又称正规文法。 3．最右推导称为规范推导，由规范推导产生的句型称为规范句型。 4． 设 G 是一个文法， S 是它的开始符号，如果 S= *>α， 则称α是一个句型。 仅由终结符号组成的句型是一个句子。 5 对于一个文法 G 而言， 如果 L(G) 中存在某个句子对应两棵不同的语法树， 那么该文法就称为是二义的。 6．通常程序设计语言的单词符号分为五种：基本字、标识符、常数、算符、 界限符。 7．在自底向上分析法中，LR 分析法把“可归约串”定义为句柄，算符优先 分析法把“可归约串”定义为最左素短语。 8．编译中常用的中间代码形式有逆波兰式、三元式、树代码和四元式等。 9．对中间代码优化按涉及的范围分为局部优化，循环优化和全局优化。 10． 局部优化主要包括合并已知量、 利用公共子表达式和删除无用赋值等内容。
三、基本概念（按概念的关联性分组记忆） 1． 直接推出、推导、句型、句子、语言、最左推导、最右推导（规范推导） 、规范 句型 2． 直接归约、归约、短语、直接短语、最左直接短语（句柄） 、素短语、最左素短 语、规范归约（最左归约）
四、基本方法（要求熟练做题） 1． 写递归下降子程序 2． 构造 LL(1)分析表（涉及消除左递归、提左因子、FIRST、FOLLOW、SELECT 集） 3． 构造算符优先分析表（涉及 FIRSTVT 、LASTVT 集）
（15 分） } }
LASTVT （E ） ={ +, *, ), i } LASTVT（T ）={ *, ), i LASTVT（F）={ ), i
第3 页
六、把下面的语句翻译成四元式序列。 while A<C do
100: 101: 102: 103: 104: 105: 106: 107: 108: 109: 110: S.CHAIN=101 j,
SELECT(①)={ ( , i SELECT(②)={ + SELECT(③)={ # , ) SELECT(④)={ ( , i SELECT(⑤)={ * SELECT(⑥)={ + , # , ) SELECT(⑦)={ ( SELECT(⑧)={ i
( E →TE' E '→ε T→FT' ) i E →TE'
二、分析方法 1． 自顶向下分析 递归下降法：分析 LL （1）文法产生的句子；由一组递归过程组成。 LL（ 1）分析法（预则分析法） ：分析 LL （1）文法产生的句子；由一个总控 程序和一个 LL （1）分析表组成。 2． 自底向上分析 算符优先分析法：非规范归约，用“最左素短语”定义“可归约串” ；分析算 符优先文法产生的句子；由一个总控程序和一个算符优先分析表组成。 LR 分析法：规范归约，用“句柄”定义“可归约串” ；分析 LR 文法产生的句 子；由一个总控程序和一个 LR 分析表组成。