编译原理过程.docx

《编译原理过程.docx》由会员分享，可在线阅读，更多相关《编译原理过程.docx（5页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、编译原理过程及分析石商X园关孝寺要号浣Southwest Jiaotong University Hope College编译原理过程及分析姓名： 王伟学号：20142217(2016.12)西南交通大学希望学院编译原理过程及分析编译原理过程及分析编译器最基本的功能就是把高级语言(例如C/Fortran)编写的代码转化为机器指令(就是01 串)，从这个角度来说它本质上是个转换过程。经典的编译过程主要包括：1、词法分析(Lexical Analysis)词法分析就是从输入代码中识别出各种记号(token),例如对于C语言我们就需要知道 if, else等是语言的关键字，myvar是个标识，而12

2、3myvar不能被识别为一个标识。负责实 现词法分析的模块有时也称为scanner。词法分析的关键当然是语言定义的规那么了，比方哪些是关键词，哪些是合法的标识等, 这些规那么一般是通过正那么表达式(RE, Regular Expression)来给出，运行时从输入缓冲区中 读入一局部，然后看和哪个RE匹配就知道它到底是个什么tokeno下一个问题就是正那么表达式的匹配过程如何实现，经典理论对此都会提到有限状态机 (FSM, Finite State Machine) o关于FSM在可行性计算里一般都会有不少篇幅分析，在编译 里谈到的FSM和RE主要是如何从输入的构成出对应的FSMo构造的过程一

3、般分为三个步骤：(1)根据Thompson构造法从RE构造出对应的非确定性有限状态机(NFA, Non-deterministic Automata)；(2)经过不断计算epison-闭包(也成为可到达集)构造出确定性有限状态机(DFA, deterministic Automata)；(3)将DFA最小化，方法是增量式地合并不可区分(对于同一输入的下一个状态都一样) 的两个状态。2、语法分析语法分析的输入是一连串的token(词法分析的输出)，根据语言的语法规那么不断解析最 后得到一棵抽象语法树(AST, Abstract Syntax Tree),负责语法分析模块通常也被叫做 Parser

4、o在词法分析中，我们经常使用正那么表达式来表示语言所接受的token的规那么，类似 的，在语法分析中，我们使用文法(Grammar)来表示语言的语法规那么，这也早期计算机语言设 计中的研究热点(同样也是大学里学习编译时最容易让人头晕的东西)。编译里常说的文法指的是一种上下文无关文法(Context-Free Grammar),简单地说文 法里包含终结符(terminal,就是26个字符、数字等等)、非终结符(nonterminal,实际是一 种抽象)和产生式(production)。上下文无关文法要求每个产生式的左边必须恰好是一个非终 结符，而右边是0个或多个终结符与非终结符的组合，最后整个文

5、法还必须有一个起始符(某 个终结符)。文法里还有些很重要的基本概念，例如推导(derivation)、归约(reduction)、 二义性(ambiguity)、最左推导等等。文法中最重要的基本概念是FIRST集和FOLLOW集的构造。根据这两个集合就可以很容 易构造出一个预测分析表，每个行的名字是一个非终结符，每个列的名字是一个终结符，如 果每个表格内没有两个以上的项，那么说明是一个LL(1)文法(Left-to-right parse, Leftmost-derivation, 1-symbol lookhead),简单地说就是向右边看一个符号就能确定下一 步动作。当原文法不是LL(1)文

6、法时，可以尝试通过消除左递归(Eliminate Left Recursion) 和提取左因子(Left Factoring)对原文法进行变形得到等价的LL(1)文法。编译原理过程及分析西南交通大学希望学院第二种文法就是 LR(k)文法(Left-to-right parse, Rightmost derivation, k-token lookhead) o这种文法的解释过程一般通过栈辅助实现，中间主要有两种动作：shift (就是 将当前输入入栈)和reduce (选择产生式并从栈中弹出符号执行归约操作)。LR(0)的构成过 程就是从起始符所在的产生式开始构造item,然后对每个item针

7、对每个可能的input构造它 的出边(同样还是一个item),最终所有的item形成一个有限状态机。接下来构造有限状态机, 对于每个状态，如果出边是一个终结符，在对应表格记入shift操作，如果是非终结符那么记 入goto操作。如果S-x.这种item集，那么对每个终结符r,都记入(S, r)位置处为shift 操作。第三种是SLR文法。与LR(0)非常相似，区别在于生成分析表格时，对于S-x.这种item 集，仅仅对于r输入FOLLOW(S)才在r)位置处记入shift操作。最后一种是LALR(l)文法。相对于LR(0)而言引入了活前缀，构造思路仍与LR(0)类似, 但是构造出来的预测分析表

8、更大。综合起来，各文法表述能力:LL (0) LR (0) SLRLALR (1) LR (1) LR (k), LL(1)0在n0的公式中，又包含了(nT) !,这就是递归定义。利用递归方法，可以用有限的语句来定义对象的无限集合。但在递归定义中，应该至少 有一条是非递归的，即初始定义。如上面例子中的第一条，否那么就变成了循环定义，产生逻 辑性错误。n!的递归定义的程序： program find_n; var n: integer;t: longint;procedure fid(n:integer); begin if n=0 then t: =1else编译原理过程及分析西南交通大学希望

9、学院begin find (n-l);t:=t*n end ;end;beginwrite (;readln (n);find (n);writein (n, !二,t)end.递归调用(n进栈)到达结束条件时(n=0, t赋初值1)就停止调用开始返回，再把保存 的值取出(n出栈)，使n恢复原来的值，并计算t,返回主程序，输出结果t。follow集合算法:计算所有非终结符号A的follow (A)集合时，不断应用下面的规那么，直到再没有新的终结符 号可以被加入到任意的follow集合中为止。1、将$放到follow (S)中，其中S是开始符号，而$是输入右端的结束标记。2、如果存在一个产生式A

10、-ciBB ,那么first (B)中除之外的所有符号都在follow (B) 中。3、如果存在一个产生式A- a B,或存在产生式A- Q B B且first ( B )包含e ,那么follow (A)中的所有符号都在follow (B)中。举个例子来说明下，假设有如下文法： EfTE，E -+TE | T-FTT f *FT IF- (E) | id对于每个非终结符号，我们都可以求出其follow集：根据(1),首先将$加入到follow (E)中，即follow (E) = $,由可知，)也应该在 follow (E)中，即 follow (E)=$, ) ；对于E,根据规那么(3)以

11、及产生式，应该将follow (E)加入到follow (E )中，即follow (E，) = ($, ) ；对于T,根据规那么(2)以及产生式，应该将first (Ej加入到follow (T)中，即follow (T) = + ,根据规那么(3),由于first (E5 )包含 ,所以应该将follow (E)加入到follow (T)中，即 follow (T)= + , $, ) ；对于T,根据规那么(3)以及产生式,应该将follow (T)加入到follow (T )中，即follow (T ) = + ,$, ) ；对于F,根据规那么(2)以及产生式，应该将first (T)加

12、入到follow (F)中,即follow (F) = *,根据规那么(3),由于first (T )包含 ,所以应该将follow (T)加入到follow (F)中，即 follow (F) = *, +, $, ) ；3、语义分析(Sematic Analysis)语义分析包括一些经典的问题。(1)类型检查(Type Checking),例如在语法树上a+b看起来是没问题的，因为a和b编译原理过程及分析西南交通大学希望学院都是合法的变量名，并且语法中支持变量间+这种操作。但是可能a是一个字符串，而b是一 个浮点数，这两者之间的+操作就不符合语义规范了，这种问题在这个阶段都会被找出来。(2

13、)符号管理，最经典的问题就是如何管理变量(变量的名字，类型，变量的作用域 (scope)等)，在分析代码时，符号管理肯定是被频繁的搜索，因此它通常会使用hash来组织。4、中间代码(IR, intermediate Representation)生成IR是非常非常重要的，它被引入的初衷是提高编译器开发的效率。IR是编译过程的一 个汇聚点，在IR之前我们通常都认为是编译的前端，而IR之后是编译的后端，这样当编译 器需要多支持一种高级语言时主要工作就是提供一个前端，而当需要移植到一种新的平台上 时主要工作就是提供对应的后端。关于IR的表示典型的有三地址码。IR生成的过程就是将一 棵抽象语法树(这是

14、编译器前端对源代码的理解和抽象)变成一串IR定义的代码(IR指令种类 简单，这便于优化)。这个转换过程都是比拟固定的套路，例如if-else, while/for等基本 结构如何转都是一个固定的套路。5、编译优化这一局部是现代编译器最核心所在，主要有两类，一类是通用的优化手段，比方死代 码删除、循环不变量外提、强度削弱等，另一类就是体系结构相关的，说白了就是某种体系 结构针对某类应用提供了特殊指令，例如intel的MMX, SSE2等等。为支持优化工作的开展, 我们首先需要能够比拟方便的描述代码。最基本的当然是一条指令，但是这个太细微，于是 往上抽象出基本块(Basic Block),这个基本

15、上是所有优化开展必备的工作，然后多个基本块 还可以构成一个超级块(region)。止匕外，经典的方法还包括控制流分析和数据流分析，这里 常用的包括d-u链等。最后一个经典的topic就是寄存器分配。6、目标代码生成这里直接和具体平台相关，这里的平台同时包括软件和硬件，例如哪种目标文件格式 (ELF, PE),哪种平台(指令集)。不过现在编译器一般生成的是字符形式的汇编文件，所以前 面一个问题基本不大，主要影响在后者。编译程序的最后一项任务是生成目标代码。目标代码生成器把中间代码变换成目标代码，通常有3种变换形式：1、立即执行的机器语言代码。这种方式对应静态连接方式，程序中所有地址都重定位，执行 效率最高，但是占用的存储空间最大。2、待装配的机器语言模块。该方式不连接系统共享的程序库，在需要使用的时候会由系统加 载共享程序库。3、汇编语言代码。该方式经过汇编程序汇编后，直接生成可以在操作系统上运行的目标代码。 生成目标代码需要考虑3个影响生成速度的问题：1、是采用什么方法生成比拟短小的目标代码；2、是如何在目标代码中多使用寄存器，减少目标代码访问外部存储单元的次数；3、是如何根据不同平台计算机指令特性进行优化，提高程序运行效率。