编译原理资料汇总.doc

第一章

翻译，是指在计算机中放置一个能由计算机直接执行的翻译程序，它以某一种程序设计语言（源语言）所编写的程序（源程序）作为翻译或加工的对象，当计算机翻译程序时，就将它翻译为与之等价的另一种语言（目标语言）的程序（目标程序）。

编译程序与运行系统合称为编译系统。

源程序的编译（或汇编）和目标程序的执行不一定在同一种计算机上完成。当源程序由另一种计算机进行编译（或汇编）时，我们将此种编译（或汇编）称为交叉编译（或汇编）。

解释程序也以源程序作为它的输入，它与编译程序的主要区别是在解释程序的执行过程中不产生目标程序，而是解释执行源程序本身。

编译程序的主要功能是把用高级语言编写的源程序翻译为等价的目标程序。

编译程序的8个组成部分：

词法分析程序（也称扫描器）

语法分析程序

语义分析程序

中间代码分析程序

代码优化程序

目标代码生成程序

错误检查和处理程序

信息表格的管理程序

编译程序的逻辑结构：(八个组成部分间的控制流程和信息流程)

源程序-（1）词法分析程序-（2）语法分析程序-（3）语义分析程序-（4）中间代码生成-（5）代码优化程序-（6）目标代码生成-目标代码

和以上123456相关联的还有（7）错误检查和处理程序和（8）信息表管理程序。

用形如(Class,Value)的序偶（二元式）作为一个单词的内部表示。Class表示单词的类别，Value是单词的值。

语法分析程序以词法分析程序所输出的用内部编码格式表示的单词序列作为输入，其任务是分析源程序的结构，判别他是否为相应程序设计语言中的一个合法程序。

前后文无关文法CFG

常见的中间代码形式：逆波兰表示、三元式、四元式、树形结构

目标代码生成程序以语义分析（或优化处理）所产生的中间代码作为输入，其功能是根据前面各阶段对源程序进行分析和加工所得到的有关信息，将中间代码翻译为机器语言或汇编语言形式的目标程序。

编译程序的前端：（1）（2）（3）（4）分析部分

编译程序所完成的处理工作只依赖源程序，而与运行目标程序的计算机无关。

14.编译程序的后端：（5）（6）综合部分

只依赖于目标语言

15.抽象语法树AST

第二章

把用一组数学符号和规则来描述语言的方式称为形式描述，而把所用的数学符号和规则称为形式语言。

字母表：由若干元素所组成的有限非空集合，其中每一元素称为符号，又称字母表为符号集。

符号串：用字母表中的符号所组成的任何有限序列称为符号串。

把符号串中所含符号的个数称为符号串的长度。不包含任何符号的符号串称为空符号串。

符号串的前缀、后缀

设x是一个符号串，把从x的尾部删去若干个（≥0）符号之后所余下的部分称为x的前缀。

设x是一个符号串，把从x的头部删去若干个（≥0）符号之后所余下的部分称为x的后缀。

X=abc,则ε、a、ab、abc都是x的前缀；

则ε、c、bc、abc都是x的后缀。

若x的前缀（后缀）不是x本身，则将其称为x的真前缀（真后缀）。

符号串的子串

从一个符号串中删去它的一个前缀和一个后缀之后余下的部分称为该符号串的子串。x的任何前缀和后缀都是x的子串，但子串不一定是x的前缀或后缀。

ε既是前缀、又是后缀、也是子串。

一个符号串x与其自身的n-1次连接称为此符号串的n次方幂。记作

定义

字母表A的正闭包就是由A中字母所构成的一切符号串的集合，而自反传递闭包仅比多包含一个空符号串ε

一个文法G[S]可表示成形如(,,P,S)的四元式，其中,,P,均为非空有限集，分别称为终结符号集，终结符号集和产生式集。S∈，是文法的开始符号。把出现在产生式左部和右部的一切符号组成的集合称为符号集，记做V。

如果一个文法中至少含有一个递归的非终结符号，则将此文法称为递归文法。

如果一个语言是无限的，则定义此语言的文法必然是递归的。

前后文无关文法等价问题是不可判定的，即不存在一种算法，它能判别任意两个前后文无关文法是否等价。

把左部变量为A的产生式称为A-产生式

句型分析，是指构造一种算法，用以判断所给的符号串是否为某一文法的句型。

句型分析的方法：自顶向下的分析自底向上的分析

对于一给定的文法来说，从其开始符号到某一句型，或从一个句型到另一句型的推导序列可能不唯一。

把能由最左推导推出的句型称为左句型。

把能由最右推导推出的句型称为右句型。

最右推导称为规范推导，右句型称为规范句型。

最右推导的逆过程是最左规约。

最左推导的逆过程是最右规约。

最左规约称为规范规约。

对于一个给定的语法树而言，它仅对应于唯一的最左推导和最右推导。

前后文无关文法是否具有二义性是不可判定的。

前后文无关语言的先天二义性也是不可判定的。

一个句型的最左直接短语（即规范分析中，最先被规约的子串）称之为此句型的句柄