编译原理复习文档.docx

编译原理复习文档.docx

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

编译原理复习文档

编译原理复习总结

⏹题型：

填空、选择、简答题、综合题

第一章编译器概述

复习要点：

1、编译程序的总框架，编译程序工作的大致过程。

2、理解一下概念：

编译、解释、翻译、编译前端、后端、遍

⏹计算机执行用高级语言编写的程序主要有两种途径：

解释和编译

⏹编译：

专指由高级语言转换为低级语言

⏹编译和解释的区别：

是否产生目标程序

⏹编译程序的五个阶段：

词法分析、语法分析、语义分析和中间代码生成、优化、目标代码生成

⏹此外还包括：

表格处理和出错处理

第二章词法分析

复习要点：

1、了解词法分析器的任务

2、掌握状态转换图

3、正规式：

与正规集的转换，判断等价

4、有限自动机：

NFA确定化、DFA最简化、正规式到DFA的转换

⏹词法分析器（扫描器）的任务：

从源程序中识别出一个个具有独立含义的最小语法单位。

⏹扫描器的输出格式：

二元式序列（单词种别，单词符号的属性值）

⏹状态转换图：

结点代表状态，用圆圈○表示。

状态之间用箭弧→连结，弧上的标记指明在射出弧的结点状态下可能出现的输入字符

初始状态接受状态

⏹正规式和有限自动机

●正规式和正规集的转换

●给出正规式，要求写出相应的NFA、DFA

●给出正规集，要求写出相应的NFA、DFA

1、正规式和正规集

●三种运算：

“”读为“或”，“”读为“连接”“*”读为“闭包”

●转换

●正规式等价：

两个正规式所表示的正规集相同，则称两个正规式等价

令Σ是一个有限字母表，则Σ上的正规式及其表示的集合递归定义如下:

1.ε和都是Σ上正规式，它们表示的正规集为{ε}和

2.若a是Σ上的字符，则a是正规式，它表示的正规集为{a}

3.若r和s都是Σ上的正规式，他们表示的正规集记为L（r）和L（s），则

（a）r|s是正规式，表示集合L（r）∪L（s），

（b）rs是正规式，表示集合L（r）L（s），

（c）r*是正规式，表示集合（L（r））*，

（d）（r）是正规式，表示的集合仍然是L（r）。

（加括弧改变优先级、结合性）

⏹有限自动机

1、确定的有限自动机M=（S，Σ，δ，S0，F）其中:

1.S—有穷状态集

2.Σ—输入字母表

3.δ—映射函数（也称状态转换函数）S×Σ→Sδ（s,a）=S’,S,S’∈S,a∈Σ

4.s0—唯一的初始状态s0∈S

5.F—终止状态集ZS

2、不确定的有限自动机M=（S,Σ,δ,S0,F）其中:

1.S—有限状态集（非终极符集合）；

2.Σ—输入字母表（终极符集合）；

3.δ—转换函数S（{}）P（S），即S*到S的幂集（2S）的一种映射；

4.S0—唯一的初始状态集合（非空）S0∈S

5.F—终止状态集合FS

DFA是NFA的特例，对于每个NFAM存在一个DFAM”，使L（M）=L（M”）。

⏹NFA的确定化：

子集法

具有转移的NFA确定化

⏹DFA的化简：

分割法

●一个有穷自动机是化简的它没有多余状态并且它的状态中没有两个是互相等价的。

●对于任一个DFA，存在一个唯一的状态最少的等价的DFA

不含ε弧的NFA确定化举例

例：

把右图确定化

I0={0}

（I0,a）={0,1}=I1

（I0,b）={1}=I2

（I1,a）={0,1}=I1

（I1,b）={1}=I2

（I2,a）={0}=I0

（I2,b）=

⏹例：

化简下图，使其最小化。

⏹从正规式到有限自动机

1、从正规式构造NFA

2、把NFA变成DFA

3、将DFA化简

⏹正规式分裂规则：

第三章语法分析（自上而下）

⏹语法分析器的任务：

按照语言的语法构成规则，识别输入的符号串能否构成一个句子

⏹语法分析的理论基础

上下文无关文法和下推自动机

文法：

描述语言语法结构的形式规则。

乔姆斯基（Chomsky）对文法的分类：

0型文法1型文法2型文法3型文法

文法G=（VT,VN,S,P）

0型文法：

，,（VNVT）*,||1

1型文法：

||||，但S可以例外

2型文法：

A，AVN,（VN∪VT）*

3型文法：

AaB或Aa，A,BVN,aVT

短语文法、上下文有关文法、上下文无关文法、正规文法

⏹分析树：

表示语言的句子结构，推导的图形表示

（1）子树：

除叶子结点之外的任意结点连同它的所有子孙结点构成子树。

（2）句型：

在一棵语法树生长过程中的任何时刻，所有那些叶子结点排列起来就是一个句型。

（3）短语：

子树的末端符号自左到右连成串，相对于子树树根而言称为短语。

●简单短语（直接短语）：

若短语事某子树根经过1步推导得到的，则称之为该子树根的简单短语。

（4）句柄：

句型中的最左简单短语。

注：

句柄是最左归约时要寻找的简单短语。

⏹自上而下：

消除左递归：

消除直接左递归：

PPa|

消除后：

PP’

P’P’|

消除间接左递归：

⏹自上而下语法分析包括：

递归下降分析程序和预测分析程序

预测分析程序：

预测分析表

是一矩阵M[A,a]，其中行标A是非终结符，列标a是终结符或串结束符；矩阵元素M[A,a]是存放A的一个侯选式，指出当前栈顶符号为A且面临读入符号为a时应选的候选式；或者存放“出错标志”，指出A不该面临读入符号a。

●求首符集（First集）

假定是文法G的一个符号串，V*，则First（）＝{a|a……,aVT}

注：

1）若,那么First（）。

2）First（）集合是的所有可能推导出的开头终结符或所组成的集合。

●求随符集（Follow集）

假定S是文法G的开始符号，对于G的任何非终结符A，Follow（A）＝{a|S…Aa…,aVT}

注：

1）若S…A,则规定：

#Follow（A）。

2）Follow（A）集合是指在所有句型中紧跟A之后的终结符或#所组成的集合。

⏹LL

（1）文法：

若文法G的预测分析表M中不含有多重定义项，则称G为LL

（1）文法。

注：

1）LL

（1）文法是无二义的，二义文法一定不是LL

（1）文法。

2）LL的含义是从左到右扫描输入串，采用最左推导分析句子。

3）数字1表示分析句子时需向前看一个输入符号。

证明定理

文法G是LL

（1）文法当且仅当对于G的每个非终结符A的任何两个不同产生式A|有：

1）First（）∩First（）=

2）若First（），则First（）∩Follow（A）=

第四章自下而上语法分析

⏹分析过程思想：

是一个最左归约的过程，从输入串开始，朝着文法的开始符号进行归约，直到达到文法的开始符号为止的过程。

⏹LR：

自左至右扫描，最右推导的逆过程。

⏹LR分析法寻找可归约句柄的依据

历史：

记录在栈内的符号串移进、归约的历史情况

展望：

预测句柄之后可能出现的信息；

现实：

读头下的符号。

⏹LR分析法通过LR分析器来实现。

⏹LR分析器包括两部分：

总控程序和分析表；

分析表——LR分析器的核心

⏹分析表构成：

动作表（ACTION）、转向表（GOTO）

注：

Si表示状态，ai表示终结符，Ai表示非终结符。

⏹动作表ACTION

ACTION[S,a]表示在当前状态S下，面临读头下的符号a所应采取的动作。

注：

该动作有四种可能：

移进、归约、出错、

接受

⏹转向表GOTO

GOTO[S,X]：

若XVT，表示在当前状态下，读入X应转向什么状态；若XVN，表示当前栈顶句柄归约成X后，应转向什么状态。

⏹注：

表中符号的含义：

Sj：

Shiftj，指将读入符号a移进栈内并转到j状态，栈顶变成（j,a）；

rj：

Reducej,按第j号产生式进行归约；

acc：

accept,分析成功；

空白格：

出错标志，若填入相应出错处理程序的编号，便转到相应程序处理。

⏹构造LR（0）分析表的基本思想：

只根据历史信息识别呈现于栈顶的句柄。

注：

LR（0）分析表构造的思想和方法是构造其它LR分析表的基础。

⏹构造LR（0）分析表的基本策略：

构造文法G的一个有限自动机，它能识别文法中的所有活前缀。

活前缀的概念：

指规范句型的一个前缀，这种前缀不含句柄之后的任何符号

活前缀有两种类型：

1）归态活前缀：

活前缀的尾部正好是句柄之尾，这时可以进行归约。

归约之后又成为另一句型的活前缀。

2）非归态活前缀：

句柄尚未形成，需要继续移进若干符号之后才能形成句柄。

⏹构造自动机识别活前缀

对于一个文法G，我们可以构造一个有限自动机，它能识别G的所有活前缀。

由于产生式右部的符号串就是句柄，若这些符号串都已进栈，则表示它已处于归态活前缀，若只有部分进栈，则表示它处于非归态活前缀。

要想知道活前缀有多大部分进栈了，可以为每个产生式构造一个自动机，由它的状态来记住当前情况，此“状态”称为“项目”。

这些自动机的全体就是能识别所有活前缀的有限自动机。

项目:

在文法的每个产生式右部添加一个圆点，就成为G的一个LR（0）项目（简称项目）。

注：

圆点在产生式中的位置不同则是不同项目。

（1）可以把圆点理解为栈内外的分界线。

（2）产生式右部符号串的长度为n，则可以分解为n+1个项目。

（3）产生式Aε只有一个项目A•。

LR（0）分析表的构造算法

⏹构造LR（0）分析表

设C={I0,I1,…In},以各项目集Ik（k＝0，…,n）的k作为状态序号，并以包含S`•S的项目集作为初始状态，同时将G`文法的产生式进行编号。

然后按下列步骤填写ACTION表和GOTO表：

1）若项目Aα•aβ属于Ik状态且GO（Ik,a）=Ij,a为终结符，则置ACTION[k,a]=Sj;即：

移进a，并转向Ij状态。

2）若项目Aα•Ik,则对任何终结符a（包括语句结束符＃）,置ACTION[k,a]=rj;其中，j为产生式A的编号，即根据j号产生式进行归约。

3）若项目S`S•属于Ik,则置ACTION[k,＃]=accept,简写为acc;

4）若GO（Ik，A）=Ij,A是非终结符，则置GOTO[k,A]=j;

5）分析表中凡不能用步骤1至4填入信息的空白项，均置上“出错标志”。

⏹LR（0）文法

定义：

若文法G按上面算法构造出来的分析表不包含多重定义项，则该文法G是LR（0）文法。

SLR分析表

SLR是LR（0）的一种改进，它在归约时除了考虑历史情况之外还考虑了一点现实。

⏹构造SLR分析表的算法

设C={I0,I1,…In},以各项目集Ik（k＝0，…,n）的k作为状态序号，并以包含S`•S的项目集作为初始状态，同时将产生式进行编号。

然后按下列步骤填写ACTION表和GOTO表：

1）若项目Aα•aβ属于Ik状态且GO（Ik,a）=Ij,a为终结符，则置ACTION[k,a]=Sj;即：

移进a，并转向Ij状态。

2）若项目Aα•Ik,则对任何终结符aFollow（A）,置ACTION[k,a]=rj；其中j为产生式A的编号，即根据j号产生式Aα进行归约。

3）若项目S`S•属于Ik,则置ACTION[k,＃]=acc;

4）若GO（Ik，A）=Ij,A是非终结符，则置GOTO[k,A]=j;

5）分析表中凡不能用步骤1至4填入信息的空白项，均置上“出错标志”。

注：

1）若文法G按上面算法构造出来的分析表不包含多重定义项，则该文法G是SLR文法。

2）二义文法决不是LR文法。

3）SLR分析法包含的展望信息是体现在利用了Follow（A）信息，可以解决“归约-归约”冲突

4）SLR分析法没有包含足够的展望信息，不能完全解决“移进-归约”冲突，需要改进。

语法制导翻译和中间代码生成

⏹中间代码四种形式

●逆波兰式

●四元式：

最常用的形式

●三元式

●树形表示法

后缀表示式（逆波兰表达式）

Operand1Operand2Operator

四元式形式:

（Operator,Operand1,Operand2,Result）

控制语句中布尔式E翻译成的四元式为以下三种：

●（jnz,A1,_,P）

IfA1thengotoP

●（jθ,A1,A2,P）

IfA1θA2thengotoP

●（j,_,_,P）

GotoP

注：

这些四元式都是转移四元式，其中P为出口的四元式序号。

与E的真假值相对应的分别为“真出口”和“假出口”两类四元式。

例如：

把语句ifA∨B

解:

（1）（jnz,A,_,（5））;真出口；若A为真，执行S1代码

（2）（j,__,（3））;若A为假，看∨右边的表达式值

（3）（j<,B,D,（5））;真出口;∨右边的表达式值为真

（4）（j,_,_,（P+1））;假出口;∨右边的表达式值为假

（5）S1语句的第一个四元式……

（P）（j,_,_,（q））;执行完S1代码后跳过S2代码段

（p+1）S2语句的第一个四元式……

（q）此语句的后继语句

运行时存储空间的组织和管理

⏹存储单元分配策略

1、静态存储分配

2、动态存储分配

●栈式存储分配

●堆式存储分配

⏹栈式存储管理

1、允许过程（函数）递归调用的数据存储管理

2、程语言的栈式存储管理

1）根据嵌套过程语言的规定，由变量的最小作用域原则，一个过程可以引用包围它的任意外层过程所定义的变量和数组。

所以，运行时过程必须知道它所有直系外层过程的最新活动记录的地址。

2）由于允许递归，过程活动记录的位置是动态变化的。

因此，每个活动记录中必须设法记住直系外层的最新活动记录的位置，以处理递归。

层次显示表display

每进入一个过程，在建立其活动记录区的同时，为它建立一张层次显示表，以登记它所有直系外层最新活动记录的首址和本过程活动记录的首址

注：

直系外层是指从0层开始直到当前过程，即当前过程的所有直系祖先；

第一章引论

翻译器：

能够将一种语言转换成另一种语言的软件，而且后者与前者在逻辑上是等价的。

源语言—>目标语言

编译：

专指由高级语言转换为低级语言。

程序设计语言——>编译程序——>机器语言

解释：

接受某高级语言的一个语句输入，进行解释并控制计算机执行，马上得到这句的执行结果，然后再接受下一句。

特点：

1．编译器：

工作效率高，即时间快、空间省；交互性与动态特性差、可移植性差。

大多数PL采用此种方法翻译

2．解释器：

工作效率低，即时间慢、空间费；交互性与动态特性好、可移植性好。

早期的Basic和现在的Java等。

基本功能：

二者相同

所采用的技术：

从翻译的角度来讲，两种方式所涉及的原理、方法、技术相似。

1.1词法分析

任务：

输入源程序，对构成源程序的字符串进行扫描和分解，识别出一个个的单词。

单词：

是高级语言中有实在意义的最小语法单位，它由字符构成。

词法分析依照词法规则，识别出正确的单词，转换成统一规格，备用。

转换

对基本字、运算符、界限符的转换

标识符的转换

常数的转换

转换完成后的格式：

（单词种别，单词符号的属性值）

二元式表示

（单词种别，单词符号的属性值）

描述词法规则的有效工具是正规式和有限自动机。

1.2语法分析

任务：

根据语言的语法规则，把单词流组成各类语法单位，如：

短语、句子、过程、程序

语法规则：

语言的规则，又称为文法；规定单词如何构成短语、语句、过程和程序。

语法规则通常用上下文无关文法描述。

position:

=initial+rate*60;

表达式的语法特征：

⏹任何一个标识符都是表达式；

⏹任何一个数都是表达式；

⏹如果e1和e2都是表达式，那么

e1+e2

e1*e2

（e1）

也都是表达式

⏹语法分析有两种方法：

推导（Derive）和规约（Reduce）

⏹语法分析过程也可以用一棵倒着的树来表示，这棵树叫做分析树

1.3语义分析

⏹任务：

检查程序的语义正确性，以保证程序各部分能有意义的结合在一起，为以后的代码生成阶段收集类型信息

⏹语义分析阶段的重要工作：

类型检查

1.4中间代码生成

⏹任务：

根据语义规则产生一种介于源语言与目标代码之间的一种中间代码。

中间代码是不依赖于机器但是又便于生成依赖于机器的目标代码的一种结构简单、含义明确的记号系统

⏹中间代码形式：

逆波兰式、四元式、三元式

1.5代码优化

任务：

对前面产生的中间代码进行加工变换，以期在最后阶段能产生更为高效的目标代码。

原则：

等价变换

主要方面：

公共子表达式的提取、合并已知量、删除无用语句、循环优化等。

1.6目标代码生成

任务：

把经过优化的中间代码转化成特定机器上的低级语言代码

目标代码的形式

●绝对指令代码:

可立即执行的目标代码。

●汇编指令代码：

汇编语言程序，需要通过汇编程序汇编后才能运行。

●可重定位指令代码：

先将各目标模块连接起来，确定变量、常数在主存中的位置，装入主存后才能成为可以运行的绝对指令代码。

1.7符号表管理

表格作用：

用来记录源程序的各种信息以及编译过程中的各种状况。

与编译前四阶段有关的表格有：

符号表、常数表、标号表、分程序入口表、中间代码表等。

符号表：

用来登记源程序中的常量名、变量名、数组名、过程名等，记录它们的性质、定义和引用情况。

1.8错误诊断和报告

任务：

如果源程序有错误，编译程序应设法发现错误，并报告给用户。

完成：

由专门的出错处理程序来完成

错误类型：

●语法错误:

在词法分析和语法分析阶段检测出来。

●语义错误：

一般在语义分析阶段检测。

1.9阶段的分组

编译前端：

主要指与源语言有关，与目标语言无关的部分，通常包括词法分析、语法分析、语义分析和中间代码生成，与机器无关部分的代码优化

编译后端：

指与目标机器有关的部分。

如与机器有关的优化、目标代码生成

遍：

对源程序或源程序的中间结果从头到尾扫描一次，并作有关的加工处理，生成新的中间结果或目标程序。

注：

遍与阶段的含义毫无关系。

要在某机器上为某种语言构造一个编译程序，必须掌握下面三个方面的内容：

源语言，目标语言，编译方法。

本章小结：

基本概念：

翻译器、编译器、解释器、源语言、目标语言、前端、后端、遍。

编译过程分哪些阶段？

各个阶段完成的主要功能和采用的主要方法。

第二章词法分析

⏹词法分析器：

实现词法分析的程序

⏹词法分析的任务：

从左至右扫描源程序的字符串，按照词法规则识别出源程序中具有独立含义的最小语法单位——单词。

⏹和用户接口的其他任务：

---滤掉注释和（由空格、制表符等引起的）空白

---其他预处理工作

⏹词法分析器作为一个独立的子程序

2.1　单词及属性

2.1.1　词法记号、模式、词法单元

词法记号：

按照某个模式（或规则）识别出的元素（一组）。

如：

关键字、算符、标识符、常数、标点符号、字符串

词法单元：

被识别出的元素，又称单词，源程序中具有独立含义的最小语法单位。

模式：

产生和识别元素的规则。

词法记号词法单元举例模式的非形式描述

varvarvar

forforfor

relation<,<=,=,…<或<=或=或…

idsum,count,D5由字母开头的字母数字串

num3.1,10,2.8E12任何数值常数

literal“seg.error”引号“和”之间的任意字符串，但引号本身除外

2.1.2　单词的属性

词法分析器的输出形式：

二元式（单词种别，单词符号的属性值）

例：

position:

=initial+rate*60的记号和属性值：

id，指向符号表中position条目的指针

assign_op，

id，指向符号表中initial条目的指针

add_op，+

id，指向符号表中rate条目的指针

mul_op,*

num，整数值60

2.1.3　词法错误

⏹词法分析器对源程序采取非常局部的观点难以发现下面的错误：

fi（a==f（x））…

⏹错误恢复策略

---紧急方式的恢复

---错误修补

2.2　单词的描述和识别

2.2.1　串和语言

首先表述一些基本术语和概念

---符号：

一个抽象实体,是语言中最基本的不可再分的单位。

例如字母是符号,数字也是符号。

---字母表：

符号的非空有限集合，因此字母表也称为字符类或符号集。

例：

={0,1}

---串：

符号的有穷序列，例：

001110是字母表={0,1}上的符号串

---符号串的长度：

如果某符号串x中有m个符号，则称其长度为m，表示为｜x｜=m，如001110的长度是6。

---空符号串：

即不包含任何符号的符号串，用ε表示，其长度为0，即｜ε｜=0

---语言：

字母表上的一个串集。

例：

{,0,00,000,…},{},

---句子：

属于语言的串

⏹串的运算：

---连接：

xy，s=s=s

---积（指数）：

s0为，si为si-1s（i>0）

例1：

例如x=ST，y=abu，则它们的连接xy=STabu，看出｜x｜=2，｜y｜=3，｜xy｜=5

例2：

符号串自身连接n次得到的符号串an定义为aa…aan个aa1=a,a2=aa且a0=ε

例3：

若x=AB则：

x0=ε，x1=AB，x2=ABAB，x3=ABABAB，xn=xxn-1=xn-1x（n>0）

⏹语言的运算

---合并：

LM={s|sL或sM}

---连接：

LM={st|sL且tM}

---指数：

L0是{}，Li是Li-1L

---闭包：

L=L0L1L2…

---正闭包：

L+=L1L2…

例：

若L={a,b},M={c,d}则LM={ac,bc,ad,bd}，L*={ε,a,b,aa,bb,ab,ba,aaa,...}，L+={a,b,aa,bb,ab,ba,aaa,...}。

2.2.2　正规式

正规式：

又称正规表达式，是描述单词构造方法的一种形式化工具，每个正规式r表示一个语言L（r），正规式表示的语言叫正规集。

⏹下面是正规式和它所表示的正规集的递归定义。

令Σ是一个有限字母表，则Σ上的正规式及其表示的集合递归定义如下:

1.ε和都是Σ上正规式，它们表示的正规集为{ε}