编译原理期末复习总结 本文关键词：期末，编译，复习，原理
编译原理期末复习总结 本文简介：编译原理复习资料一、简答题1.什么是编译程序？答：编译程序是一种将高级语言程序(源程序)翻译成低级语言(目标程序)的程序。将高级程序设计语言程序翻译成逻辑上等价的低级语言(汇编语言,机器语言)程序的翻译程序。2.请写出文法的形式定义？答：一个文法G抽象地表示为四元组G=（Vn,Vt,P,S）–其中V
编译原理期末复习总结 本文内容：
编译原理复习资料
一、简答题
1.什么是编译程序？
答：编译程序是一种将高级语言程序(源程序)翻译成低级语言(目标程序)的程序
。
将高级程序设计语言程序翻译成逻辑上等价的低级语言(汇编语言,机器语言)程序的翻译程序。
2.请写出文法的形式定义？
答：一个文法G抽象地表示为四元组
G=（Vn,Vt,P,S）
–
其中Vn表示非终结符号
–
Vt表示终结符号，Vn∪Vt=Ｖ(字母表)，Vn∩Vt=φ
–
S是开始符号，
–
P是产生式，形如：α→β(α∈V+且至少含有一个非终结符号，β∈V*)
3.语法分析阶段的功能是什么？
答：在词法分析的基础上，根据语言的语法规则，将单词符号串分解成各类语法短语(例：程序、语句、表达式)。确定整个输入串是否构成语法上正确的程序。
4.局部优化有哪些常用的技术？
答：优化技术1—删除公共子表达式
优化技术2—复写传播
优化技术3—删除无用代码
优化技术4—对程序进行代数恒等变换（降低运算强度）
优化技术5—代码外提
优化技术6—强度削弱
优化技术7—删除归纳变量
优化技术简介——对程序进行代数恒等变换（代数简化）
优化技术简介——对程序进行代数恒等变换（合并已知量）
5．编译过程分哪几个阶段？
答：逻辑上分五个阶段：词法分析、语法分析、语义分析与中间代码生成、代码优化、目标代码生成。每个阶段把源程序从一种表示变换成另一种表示。
6.
什么是文法？
答：文法是描述语言的语法结构的形式规则。是一种工具，它可用于严格定义句子的结构；用有穷的规则刻划无穷的集合；文法是被用来精确而无歧义地描述语言的句子的构成方式；文法描述语言的时候不考虑语言的含义。
7.
语义分析阶段的功能是什么？
答：对语法分析所识别出的各类语法范畴分析其含义，进行初步的翻译(翻译成中间代码)；并对静态语义进行审查。
8.代码优化须遵循哪些原则？
答：等价原则：不改变运行结果
有效原则：优化后时间更短，占用空间更少
合算原则：应用较低的代价取得较好的优化效果
9.词法分析阶段的功能是什么？
答：
逐个读入源程序字符并按照构词规则切分成一系列单词
任务：
读入源程序，输出单词符号
—
滤掉空格，跳过注释、换行符
—
追踪换行标志，指出源程序出错的行列位置
—
宏展开，……
10.什么是符号表？
答：符号表在编译程序工作的过程中需要不断收集、记录和使用源程序中一些语法符号的类型和特征等相关信息。这些信息一般以表格形式存储于系统中。如常数表、变量名表、数组名表、过程名表、标号表等等，统称为符号表。对于符号表组织、构造和管理方法的好坏会直接影响编译系统的运行效率。
11.什么是属性文法？
答：是在上下文无关文法的基础上，为每个文法符号(含终结符和非终结符)配备若干个属性值，对文法的每个产生式都配备了一组属性计算规则(称为语义规则)。在语法分析过程中，完成语义规则所描述的动作，从而实现语义处理。
12.什么是基本块?
答：是指程序中一顺序执行的语句序列，其中只有一个入口语句和一个出口语句，入口是其第一个语句，出口是其最后一个语句。
13.代码优化阶段的功能是什么？
答：对已产生的中间代码进行加工变换，使生成的目标代码更为高效(时间和空间)。
14.文法分哪几类？
答：文法有四种:设有G=(Vn,Vt,P,S),不同类型的文法只是对产生式的要求不同：
０型文法(短文文法)：
G的每个产生式α?β满足：α∈V+且α中至少含有一个非终结符,β∈V*
１型文法(上下文有关文法)：如果G的每个产生式α?
β均满足|β|>=|α|,仅当Ｓ?ε除外，但S不得出现在任何产生式的右部
２型文法(上下文无关文法)：G的每个产生式为A?β,A是一非终结符，β∈V*
３型文法(正规文法)：G的每个产生式的形式都是：A?αB或A?α，其中A,B是非终结符，α是终结符串。(右线性文法)。
15.循环优化常用的技术有哪些？
答：代码外提；强度削弱；删除归纳变量。
16.什么是算符优先文法？
答：算符文法G的任何终结符a,b之间要么没有优先关系，若有优先关系,至多有中的一种成立,则G为一算符优先文法。
二、计算题
（一）推导、最左推导、最右推导和语法树,复习表达式文法及相关例题。
1.
表达式的推导
例：
G
=
({E},{i,+,*,(,)
},P,E)
P：
E
?
E+E
|
E*E
|
(E)
|
i
答：表达式(i)和(i+i)*i的推导：
E
T
(E)
T
(i)
E
T
E*E
T
(E)*E
T
(E
+
E)*E
T
(i
+
E)*E
T(i
+
i)*E
T
(i
+
i)*i
E
T
E*E
T
E*i
T
(E)*
i
T
(E
+
E)*i
T
(E+
i)*i
T(i
+
i)*i
(i+i)*i的最左推导过程：
E
T
E*E
T
(E)*E
T
(E
+
E)*E
T
(i
+
E)*E
T(i
+
i)*E
T
(i
+
i)*i
(i+i)*i的最右推导过程：
E
T
E*E
T
E*i
T
(E
+
E)*i
T
(E+
i)*i
T(i
+
i)*i
2．语法树
例：对文法G
=
({E},{i,+,*,(,)
},P,E)
P：
E
?
E
+
E
|
E
E
|
(
E
)
|
i
答：
句子(i+i)*i
的语法树：
例：
G
=
({E},{i,+,*,(,)
},P,E)
P：
E
?
E
+
E
|
E
E
|
(
E
)
|
i
答：句子
(
i
i
+
i)的语法树：
(1)
E
T
(E)
T
(E
+
E)
T
(E
E
+
E)
T(i
E
+
E)
T
(ii
+
i)
（二）给定语言求文法
（三）逆波兰式
（四）将for语句和if语句翻译成相应的四元式序列
1.if
2.for
(五)
短语、素短语、最左素短语，FirstVT集和LastVT集的求解方法
(复习第四章
算符优先文法相关内容)
1.
短语、素短语、最左素短语
2.FirstVT集和LastVT集的求解方法
例：设文法为：
E
→#E#；T→F；E→E+T；F→P↑F
|
P；
E→T
；P→(E)；T→T*F；P→i；
3.
算符优先文法
优先关系的定义:
算符优先文法的定义:
三、综合题
1.NFA的确定化和最小化(参看课件第三章62页：例5)
2.自顶向下分析(参看课件第四章（1）67页：综合练习)
例：求对应于下述文法的预测分析表:
E
àTE
E
à
+TE
|ε
T
à
FT
T
àFT
|ε
F
à(E)
|i
答：
1）
首先求first集:
2）
由于ε?First(E
),ε?First(T
),求E
和T
的Follow集:
3）
根据集合的值填表，得到:
例:设文法G(S)：S→(L)
|
aS
|
a
L→L，S
|
S
(1)
消除左递归和回溯；
(2)
计算每个非终结符的First和Follow集；
(3)
构造预测分析表。
答：(1)
消除左递归和回溯：
(2)
(3)构造预测分析表：
3.LR分析方法(参看课件第四章（3）28页及30页)
(附)
1.短语、直接短语、句柄
例：考虑如下文法：
E
=>T
|
E+T
T
=>F
|
T*F
F
=>i
|
(E)
求句型
i1
i2
+
i3的短语、直接短语和句柄
答：E
=>
F
i2
+
i3
E
=>
i1
F
+
i3
E
=>
i1
i2
+
F
E
=>
T
+
i3（T
=>T*F
=>i1
i2）
F=>i
E
=>
i1
i2
+
i3
因此：
短语有：i1,i2,i3,i1*i2,i1*i2+i3
直接短语有：i1,i2,i3
句柄是：
i1
i2
+
i3
不是短语，因为E
=>
i1
E
（E
=>i2
+i3）
2.
什么是语法制导翻译
语法制导翻译：定义翻译所必须的语义属性和语义规则，一般不涉及计算顺序。
语法制导翻译(Syntax-Directed
Translations)：
–
一个句子的语义翻译过程与语法分析过程同时进行。
在文法中，文法符号有明确的意义，文法符号之间有确定的语义关系。属性描述语义信息，语义规则描述属性间的的关系，将语义规则与语法规则相结合，在语法分析的过程中计算语义属性值。
15