编译原理期末复习总结.docx

编译原理期末复习总结.docx

《编译原理期末复习总结.docx》由会员分享，可在线阅读，更多相关《编译原理期末复习总结.docx（18页珍藏版）》请在冰点文库上搜索。

编译原理期末复习总结

一、简答题

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：

EE+E|E*E|（E）|i

答：

表达式（i）和（i+i）*i的推导：

E（E）（i）

EE*E（E）*E（E+E）*E（i+E）*E（i+i）*E（i+i）*i

EE*EE*i（E）*i（E+E）*i（E+i）*i（i+i）*i

（i+i）*i的最左推导过程：

EE*E（E）*E（E+E）*E（i+E）*E（i+i）*E（i+i）*i

（i+i）*i的最右推导过程：

EE*EE*i（E+E）*i（E+i）*i（i+i）*i

2．语法树

例：

对文法G=（{E},{i,+,*,（,）},P,E）

P：

EE+E|E*E|（E）|i

答：

句子（i+i）*i的语法树：

例：

G=（{E},{i,+,*,（,）},P,E）

P：

EE+E|E*E|（E）|i

答：

句子（i*i+i）的语法树：

（1）E（E）（E+E）（E*E+E）（i*E+E）（i*i+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页：

综合练习）

例：

求对应于下述文法的预测分析表:

ETE'

E'+TE'|ε

TFT'

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+i3E=>i1*F+i3E=>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-DirectedTranslations）：

–一个句子的语义翻译过程与语法分析过程同时进行。

在文法中，文法符号有明确的意义，文法符号之间有确定的语义关系。

属性描述语义信息，语义规则描述属性间的的关系，将语义规则与语法规则相结合，在语法分析的过程中计算语义属性值。