完整word版编译原理基本概念word文档良心出品.docx

1、完整word版编译原理基本概念word文档良心出品1 编译程序编译程序是一种翻译程序，它将高级语言所写的源程序翻译成等价的机器语言或汇编语言的目标程序。2 词法分析（Lexical analysis或Scanning）和词法分析程序（Lexical analyzer或Scanner）词法分析阶段是编译过程的第一个阶段。这个阶段的任务是从左到右一个字符一个字符地读入源程序，即对构成源程序的字符流进行扫描然后根据构词规则识别单词(也称单词符号或符号)。词法分析程序实现这个任务。词法分析程序可以使用lex等工具自动生成。 3 语法分析（Syntax analysis或Parsing）和语法分析程序（

2、Parser） 语法分析是编译过程的一个逻辑阶段。语法分析的任务是在词法分析的基础上将单词序列组合成各类语法短语，如“程序”，“语句”，“表达式”等等.语法分析程序判断源程序在结构上是否正确.源程序的结构由上下文无关文法描述.4 语义分析（Syntax analysis）及中间代码生成语义分析是编译过程的一个逻辑阶段. 语义分析的任务是对结构上正确的源程序进行上下文有关性质的审查, 进行类型审查.例如一个C程序片断:int arr2,b;b = arr * 10; 源程序的结构是正确的. 语义分析将审查类型并报告错误:不能在表达式中使用一个数组变量,赋值语句的右端和左端的类型不匹配.语义分析时

3、，根据语句的含义，可对它进行翻译，用另一种语言形式（比源语言更接近于目标语言的一种中间代码或直接用目标语言）来描述这种语义。5 代码优化代码优化的任务是对前阶段产生的中间代码进行等价变换或改造，以期获得更为高效的，即省时间和空间的代码。6 目标代码生成目标代码的生成的任务是将中间代码变换成特定机器上的绝对指令代码或可重定位的指令代码或汇编指令代码。7 遍8 前端（Frontend）和后端（Back end）有时，常常把编译的过程分为前端(front end)和后端(back end)，前端由那样一些阶段组成：这些阶段的工作主要依赖于源语言而与目标机无关。通常这些阶段包括词法分析、语法分析、语义

4、分析和中间代码生成，某些优化工作也可在前端做，也包括与前端每个阶段相关的出错处理工作和符号表管理工作。 后端工作指那些依赖于目标机而一般不依赖源语言，只与中间代码有关的那些阶段，即目标代码生成，以及相关出错处理和符号表操作。编译程序和解释程序9 Lex一个词法分析程序的自动生成工具。它输入描述构词规则的一系列正规式,然后构建有穷自动机和这个有穷自动机的一个驱动程序,进而生成一个词法分析程序.10 Yacc 一个语法分析程序的自动生成工具。它接受语言的文法,构造一个LALR(1)分析程序.因为它采用语法制导翻译的思想,还可以接受用C语言描述的语义动作,从而构造一个编译程序. Yacc 是 Yet

5、 another compiler compiler的缩写.11 源语言（Source language）和源程序（Source program）被编译程序翻译的程序称为源程序,书写该程序的语言称为源语言.12 目标语言（Object language or Target language）和目标程序（Object program or Target program） 编译程序翻译源程序而得到的结果程序称为目标程序, 书写该程序的语言称为目标语言.13 中间语言（中间表示）（Intermediate language(representation)） 在进行了语法分析和语义分析阶段的工作之后，

6、有的编译程序将源程序变成一种内部表示形式，这种内部表示形式叫做中间语言或中间表示或中间代码。所谓“中间代码”是一种结构简单、含义明确的记号系统，这种记号系统复杂性介于源程序语言和机器语言之间，容易将它翻译成目标代码。另外，还可以在中间代码一级进行与机器无关的优化。常见的中间代码形式有：逆波兰式、三元式、四元式、树形表示和三地址代码。14 文法（Grammars） 文法是用于描述语言的语法结构的形式规则。文法G定义为四元组(VN，V T，P，S)。其中VN为非终结符号(或语法实体，或变量)集；V T为终结符号集；P为产生式(也称规则)的集合；产生式(规则)是形如或 a :=b 的(a , b)有

7、序对,其中(VNV T)*且至少含有一个非终结符，而(VNV T)*。VN，V T和P是非空有穷集。S称作识别符号或开始符号，它是一个非终结符，至少要在一条规则中作为左部出现。 一个文法的例子: G=( VN =A，R, P =0,1 ，P =A0R，A01,RA1, S =A) 15 文法分类（A hierarchy of Grammars） 著名语言学家Noam Chomsky定义了四类文法和四种形式语言类，文法的四种类型分别是0型、1型、2型和3型。几类文法的差别在于对产生式施加不同的限制，分别是： 0型文法(短语结构文法)(phrase structure grammars)： 设G=

8、(VN，V T，P，S)，如果它的每个产生式是这样一种结构(VNV T)*且至少含有一个非终结符，而(VNV T)*，则G是一个0型文法。 1型文法（上下文有关文法）(context-sensitive grammars)： 设G=(VN，V T，P，S)为一文法|，若P中的每一个产生式均满足|，仅仅S除外，则文法G是1型或上下文有关的。 2型文法（上下文无关文法）(context-free grammars)： 设G=(VN，V T，P，S)，若P中的每一个产生式满足：是一非终结符，(VNV T)*则此文法称为2型的或上下文无关的。 3型文法（正规文法）(regular grammars)：

9、 设G=(VN，V T，P，S)，若P中的每一个产生式的形式都是AaB或Aa，其中A和B都是非终结符，a是终结符，则G是3型文法或正规文法。 0型文法产生的语言称为0型语言。 1型文法产生的语言称为1型语言，也称作上下文有关语言。 2型文法产生的语言称为2型语言，也称作上下文无关语言。 3型文法产生的语言称为3型语言，也称作正规语言。 16 句型（Sententialform），句子（Sentence）和语言（Language）设GS是一文法，如果符号串x是从识别符号推导出来的，即有Sx，则称x是文法GS的句型。若x仅由终结符号组成，即Sx，xV T*，则称x为GS的句子。 文法G所产生的语言

10、定义为集合xSx，其中S为文法识别符号，且xV T*。可用L(G) 或L(GS)表示该集合。 17 推导（Derive）和语法树（Parse tree） 推导的概念：分别定义V*中的符号之间的关系直接推导、长度为n（n1）的推导和长度为n（n0）的推导： （1）如是文法G=(VN，V T，P，S)的规则（或说是P中的一个产生式），和是V*中的任意符号，若有符号串v，w满足： v，w则说v（应用规则）直接产生w，或说，w是v的直接推导，或说，w直接归约到v，记做vw。 （2）如果存在直接推导的序列： vw0 w1 w2 wnw，（n0） 则称v推导出（产生）w（推导长度为n），或称w归约到v。记

11、作vw。 （3）若有vw，或vw，则记作。 语法树（推导树）的概念：给定文法G=(VN，V T，P，S)，对于G的任何句型都能构造与之关联的语法树（推导树）。这棵树满足下列4个条件： 每个结点都有一个标记，此标记是V的一个符号。 根的标记是S。 若一个结点n至少有一个它自己除外的子孙，并且有标记A，则A肯定在VN中。 如果结点n的直接子孙，从左到右的次序是结点n1，n2， ，nk，其标记分别为A1，A2，Ak，那么AA1A2，Ak一定是P中的一个产生式。 18 二义文法（Ambiguous grammer）如果一个文法存在某个句子对应两棵不同的语法树，则说这个文法是二义的。或者说，若一个文法中

12、存在某个句子，它有两个不同的最左(最右)推导，则这个文法是二义的。 19 短语，句柄 (phrase , sentence handle)令G是一文法，S是文法的开始符号，是文法G的一个句型。如果有：且则称是句型相对与非终结符 A的短语。特别，如有则称是句型相对于规则A的直接短语 (也称简单短语)。一个句型的最左直接短语称为该句型的句柄。 20 正规式（regular expression）和它所表示的正规集（regular set）设字母表为,辅助字母表 =,，.，*,(,)。1. 和都是上的正规式，它们所表示的正规集分别为和； 2.任何a，a是上的一个正规式，它所表示的正规集为a； 3.假

13、定1和2都是上的正规式，它们所表示的正规集分别为L(1)和L(2)，那么，(1)，12，12和2*也都是正规式，它们所表示的正规集分别为L(1)，L(1)L(2)，L(1)L(2)和(L(1) *。4.仅由有限次使用上述三步骤而定义的表达式才是上的正规式，仅由这些正规式所表示的字集才是上的正规集。 21 确定的有穷状态自动机DFA(deterministic finite automaton)和不确定的有穷状态自动机NFA(nondeterministic finite automaton)我们这里是把DFA和NFA作为正规集的识别工具而介绍的。DFA定义如下：一个确定的有穷自动机(DFA)M

14、是一个五元组：M=(K, ，f，S，Z)其中 1.K是一个有穷集，它的每个元素称为一个状态；2. 是一个有穷字母表，它的每个元素称为一个输入字符,所以也称为输入符号字母表;3.f是转换函数，是在KK上的映像，即，如f(ki,a)= kj( kiK, kjK)就意味着，当前状态为ki，输入字符为a时，将转换到下一状态kj，我们把kj称作ki的一个后继状态;4.SK是唯一的一个初态；5.ZK，是一个终态集，终态也称可接受状态或结束状态。NFA定义如下;一个不确定的有穷自动机(NFA)M是一个五元组，M=(K, ，f，S，Z)其中 1.K是一个有穷集，它的每个元素称为一个状态；2. 是一个有穷字母表

15、，它的每个元素称为一个输入字符； 3. f是一个从K*到K的子集的映像.4. SK，是一个非空初态集;5. ZK，是一个终态集。 DFA和NFA的等价定理：对于每个NFA M，存在一个DFA M，使得L（M）L（M），即M和M是等价的。 22 最小状态DFA(reduced DFA or minimum DFA) 我们说一个确定的有穷自动机是化简了的，即是说，它没有多余状态并且它的状态中没有两个是互相等价的，这种DFA也叫做最小状态DFA。一个DFA可以通过消除多余状态和合并等价状态而转换成一个与之等价的最小状态DFA。 24FIRST集设G=(VN，V T，P，S)是上下文无关文法 FIRS

16、T()=a，aV T，, V *若，则规定FIRST()。 25FOLLOW集设G=(VN，V T，P，S)是上下文无关文法，AVN，是开始符号FOLLOW(A)=a且aV T，aFIRST()，V T*，V + 若，且，则#FOLLOW(A)。也可定义为：FOLLOW(A)=a|Aa,aV T 若有A，则规定#FOLLOW(A) 这里我们用作为输入串的结束符，或称为句子括号，如：输入串。 26SELECT集给定上下文无关文法的产生式A AVN，V *，若，则SELECT(A)= FIRST() 如果，则SELECT(A)=FIRST()FOLLOW(A)。 27左递归文法（Left recu

17、rsive grammar） 一个文法含有下列形式的产生式时。 a)AA AVN，V * b)ABB A,BVN，、V * 在a)中也可称为含有左递归的规则或称直接左递归，在b)中为A称文法中含有左递归或间接左递归，文法中只要含有a)或含有b)或二者皆有均认为文法是左递归的。 28LL（1）文法 满足如下条件的上下文无关文法称为LL（1）文法：对每个非终结符A的两个不同产生式， A，A，满足 SELECT（A）SELECT（A）其中、不同时能。 LL（1）文法的含义是：第一个L表明自顶向下分析是从左向右扫描输入串，第二个L表明分析过程中将用最左推导，1表明只需向右看一个符号便可决定如何推导即选

18、择哪个产生式（规则）进行推导，类似也可以有LL（K）文法，也就是需向前查看K个符号才可确定选用哪个产生式。通常采用K1，个别情况采用K2。 29递归子程序法（Recursive-descent） 递归子程序法是LL（1）文法的分析程序的一种实现方法。它对应文法中每个非终结符编写一个递归过程，这种分析程序由这一系列递归过程的相互调用来完成语法分析工作。 30移进归约分析（shiftreduce analysis） 自底向上分析方法，也称移进归约分析法，它的实现思想是对输入符号串自左向右进行扫描，并将输入符逐个移入一个后进先出栈中，边移入边分析，一旦栈顶符号串形成某个句型的句柄时，（该句柄对应某产

19、生式的右部），就用该产生式的左部非终结符代替相应右部的文法符号串，这称为一步归约。重复这一过程直到归约栈中只剩文法的开始符号时则为分析成功，也就确认输入串是文法的句子。 31算符文法，算符优先文法(Operator Grammar，Operator Precedence Grammar) 设有文法G，若G中没有形如UVW的规则，其中V和W为非终结符，则称G是一个算符文法(Operator Grammar)，即OG文法。设有一不含产生式的算法文法G，如果对任意两个终结符对a，b之间至多只有、和三种关系的一种成立，则称G是一个算符优先文法(Operator Precedence Grammar)，

20、即OPG文法。 32最左素短语（Most left prime phrase） 设有文法GS，其句型的素短语是一个短语 ，它至少包含一个终结符，并除自身外不包含其它素短语，句型的最左边的素短语称最左素短语。 33LR分析 是一种自底向上的语法分析技术,通常称为LR(K).L是说从左至右扫描输入串,R是说分析过程所形成的推导是最右推导,K是指在做分析决策时向前察看K个输入符号.LR分析可用于一大类上下文无关文法,是一种最常用的无回朔的移进归约分析, 一个LR分析器由分析栈、分析表和总控程序3个部分组成。LR分析器总控程序根据LR分析表，执行4种可能的动作：移进、规约、接受（acc）和报错。34属

21、性文法（Attribute grammar） 形式上讲，一个属性文法是一个三元组，（，），一个上下文无关文法；一个属性的有穷集和关于属性的断言或谓词的有穷集。每个属性与文法的某个非终结符或终结符相联。每个断言与文法的某产生式相联。如果对中的某一输入串而言（句子），中的所有断言对该输入串的语法树结点的属性全为真，则该串也是语言中的句子。编译程序的静态语义审查工作就是验证关于所编译的程序的断言是否全部为真。属性分为两类：综合属性和继承属性。35语法制导翻译（Syntax-directed translation） 在语法分析过程中，随着分析的步步进展，根据每个产生式所对应的语义子程序（或语义规则描

22、述的语义动作）进行翻译的办法称作语法制导翻译。 36数组内情向量（array dope vector） 一般编译程序对数组说明的处理是把数组的有关信息汇集在一个叫做“内情向量”或“信息向量”的表格中，以便以后计算数组元素的地址时引用这些信息。每个数组有一个内情向量。其中的信息包括，数组的类型，维数，各维的上、下界，以及数组的首地址。编译程序处理数组说明的主要工作是把内情向量登录在符号表中，这些属性信息是确定存储分配时数组所占空间的大小和数组元素位置的依据。 37符号表（symbol table）在编译程序中符号表用来存放源程序中出现的有关标识符的属性信息，这些信息集中反映了标识符的语义特征属性

23、,为进行上下文语义审查和进一步的翻译使用。 编译程序处理标识符时主要涉及两部分内容，其一是标识符本身，其二是标识符相关的信息。符号表上有三种操作：填入、查找和更新。符号表的查找方法有顺序查找、二分查找和散列（杂凑）查找法。38运行时的环境及存储空间所谓运行时的环境是指目标计算机的寄存器和存储器的结构，以及用来管理存储器并保存执行过程所需要的信息。存储空间包括用户定义的各种类型的数据对象所需要的存储空间、调用过程所需要的连接单元和组织输入/输出所需要的缓冲区及保留中间接过和传递参数所需要的临时单元。存储空间通常被划分为：目标区、静态数据区、栈区和堆区。39静态存储分配（Static storag

24、e allocation）如果在编译时能确定目标程序运行中所需的全部数据空间的大小，编译时安排好目标程序运行时的全部数据空间，确定每个数据对象的存储位置，称这种分配策略为静态存储分配。40动态存储分配（Dynamic storage allocation）如果一个程序设计语言允许递归过程、可变数组或允许用户自由申请和释放空间，那么，就需要采用动态存储管理技术。因为对于这种程序在编译时无法知道它在运行时需要多大的存储空间，它所需要的数据空间的大小需待程序运行时动态地确定。有两种动态存储分配方式：栈式（stack）和堆式（heap）。41四元式(quadruples) 四元式是一种中间代码的形式,

25、是一个有四个域的纪录结构: 四个域分别称为 op,arg1,arg2 和 result 即操作符,运算对象1, 运算对象2 和运算结果.一个例子:( + ,a, b, c) 42Display表 为能存取非局部变量而纪录外包过程的活动记录地址的数组。即每进入一个过程后，在建立它的活动记录的同时建立一张嵌套层次显示表display。这里所提到的“嵌套层次”，是指过程定义的层数，始终假定主程序的层数为0，因此主程序称为0层过程。如某过程p是在层次为i的过程q内定义的，并且q是包围p的直接外层，那么p的过程层数为i+1。display是一个指针数组d，也可看做是一个小栈，自顶向下每个单元依次存放着现

26、行层，直接外层，直至最外层（0层，主程序层）等每一层过程的最新活动记录的地址。 43活前缀(viable prefixes) 和拓广文法若是文法G中的一个规范推导。如果符号串是的前缀，则称是G的一个活前缀。也就是说是规范句型的前缀，但它的右端不超过该句型句柄的末端。这里S为对原文法G加了产生式S，S为原文法G的开始符号，S为拓广后文法G的开始符号。 44LR(0)项目和LR(0)项目集规范族(LR(0)items and canonical collection of sets of LR(0) items)文法G的产生式的右部适当位置添加有一个圆点则称为一个LR(0)项目。根据小圆点的位置和

27、圆点后是终结符还是非终结符，将一个文法的全部LR(0)项目分为四类：归约项目、移进项目、待约项目和接受项目。根据圆点所在的位置和圆点后是终结符还是非终结符把项目分为以下几种：移进项目，形如 A a ，其中 ， (VNV T)*待约项目，形如 A B ，其中 ， (VNV T)*归约项目，形如 A ，其中 (VNV T)*接受项目，形如 S S 构成识别一个文法活前缀的DFA项目集(状态)的全体称为这个文法的LR(0)项目集规范族。45同心集所谓同心的LR(1)项目集是指在两个LR(1)项目集中，除搜索符不同之外，核心部分是相同的。46代码优化（Code Optimization）所谓代码优化，

28、实质上是对代码进行等价变换，使得变换后的代码运行结果与变换前代码运行结果相同，而运行速度加大或占用存储空间少，或两者都有。 代码优化通常分为两大类：与机器相关的优化和与机器无关的优化。与机器无关的优化，常见的优化技术：删除公共子表达式（删除多余运算）、代码外提、强度削弱、变换循环控制条件（删除归纳变量）、合并已知量、复写传播和删除无用赋值。依据优化所涉及的范围分为：局部优化、循环优化和全局优化。47基本块（Basic block）和DAG 所谓基本块，是指程序中一顺序执行的语句序列，其中只有一个入口语句和一个出口语句。执行时只能从其入口语句进入，从其出口语句退出。如果有向图中任一通路都不是环路

29、，则称该有向图为无环路有向图，简称。基本块的DAG表示可用于代码优化。 在一个基本块内，可以执行三种优化：删除多余运算、合并已知量、删除无用赋值。48控制流程图（流图）（Control flow graph）一个控制流程图就是具有唯一首结点的有向图。所谓首结点，就是从它开始到控制流程图中任何结点都有一条通路的结点。 我们可以把一个控制流程图表示成一个三元组（，），其中，代表图中所有结点集，代表图中所有有向边集，代表首结点。控制流程图简称为流图。 49循环（Loop） 在程序流图中，称具有下列性质的结点序列为一个循环： 它们是强连通的。也即，其中任意两个结点之间，必有一条通路，而且该通路上各结

30、点都属于该结点序列。如果序列只包含一个结点，则必有一有向边从该结点引到其自身。 它们中间有且只有一个是入口结点。因此，我们定义的循环就是程序流图中具有唯一入口结点的强连通子图，从循环外要进入循 环，必须首先经过循环的入口结点。所谓入口结点，是指序列中具有下述性质的结点：从序列外某结点，有一有向边引到它，或者它就是程序流图的首结点。 50必经结点（dominators）和必经结点集（dominators set）在程序流图中，对任意两个结点m和n，如果从流图的首结点出发，到达n的任一通路都要经过m，则称m是n的必经结点，记为m DOM n。流图中结点的所有必经结点的集合，称为结点n的必经结点集，记为D（n）。51回