编译原理过程

西南交通大学希望学院编译原理过程及分析编译原理过程及分析姓名：王伟学号：20142217（2016.12）西南交通大学希望学院编译原理过程及分析编译原理过程及分析编译器最基本的功能就是把高级语言(例如C/Fortran)编写的代码转化为机器指令(就是01串)，从这个角度来说它本质上是个转换过程。经典的编译过程主要包括：1、词法分析(LexicalAnalysis)词法分析就是从输入代码中识别出各种记号(token)，例如对于C语言我们就需要知道if,else等是语言的关键字，myvar是个标识，而123myvar不能被识别为一个标识。负责实现词法分析的模块有时也称为scanner。词法分析的关键当然是语言定义的规则了，比如哪些是关键词，哪些是合法的标识等，这些规则一般是通过正则表达式(RE，RegularExpression)来给出，运行时从输入缓冲区中读入一部分，然后看和哪个RE匹配就知道它到底是个什么token。下一个问题就是正则表达式的匹配过程如何实现，经典理论对此都会提到有限状态机(FSM,FiniteStateMachine)。关于FSM在可行性计算里一般都会有不少篇幅分析，在编译里谈到的FSM和RE主要是如何从输入的构成出对应的FSM。构造的过程一般分为三个步骤：(1)根据Thompson构造法从RE构造出对应的非确定性有限状态机(NFA,Non-deterministicAutomata)；(2)经过不断计算epison-闭包(也成为可到达集)构造出确定性有限状态机(DFA,deterministicAutomata)；(3)将DFA最小化，方法是增量式地合并不可区分(对于同一输入的下一个状态都一样)的两个状态。2、语法分析语法分析的输入是一连串的token(词法分析的输出)，根据语言的语法规则不断解析最后得到一棵抽象语法树(AST,AbstractSyntaxTree)，负责语法分析模块通常也被叫做Parser。在词法分析中，我们经常使用正则表达式来表示语言所接受的token的规则，类似的，在语法分析中，我们使用文法(Grammar)来表示语言的语法规则，这也早期计算机语言设计中的研究热点(同样也是大学里学习编译时最容易让人头晕的东西)。编译里常说的文法指的是一种上下文无关文法(Context-FreeGrammar)，简单地说文法里包含终结符(terminal，就是26个字符、数字等等)、非终结符(nonterminal，实际是一种抽象)和产生式(production)。上下文无关文法要求每个产生式的左边必须恰好是一个非终结符，而右边是0个或多个终结符与非终结符的组合，最后整个文法还必须有一个起始符(某个终结符)。文法里还有些很重要的基本概念，例如推导(derivation)、归约(reduction)、二义性(ambiguity)、最左推导等等。文法中最重要的基本概念是FIRST集和FOLLOW集的构造。根据这两个集合就可以很容易构造出一个预测分析表，每个行的名字是一个非终结符，每个列的名字是一个终结符，如果每个表格内没有两个以上的项，那么说明是一个LL(1)文法(Left-to-rightparse,Leftmost-derivation,1-symbollookhead)，简单地说就是向右边看一个符号就能确定下一步动作。当原文法不是LL(1)文法时，可以尝试通过消除左递归(EliminateLeftRecursion)和提取左因子(LeftFactoring)对原文法进行变形得到等价的LL(1)文法。西南交通大学希望学院编译原理过程及分析第二种文法就是LR(k)文法(Left-to-rightparse,Rightmostderivation,k-tokenlookhead)。这种文法的解释过程一般通过栈辅助实现，中间主要有两种动作：shift（就是将当前输入入栈）和reduce（选择产生式并从栈中弹出符号执行归约操作）。LR(0)的构成过程就是从起始符所在的产生式开始构造item，然后对每个item针对每个可能的input构造它的出边(同样还是一个item)，最终所有的item形成一个有限状态机。接下来构造有限状态机，对于每个状态，如果出边是一个终结符，在对应表格记入shift操作，如果是非终结符则记入goto操作。如果S-x.这种item集，那么对每个终结符r，都记入(S,r)位置处为shift操作。第三种是SLR文法。与LR(0)非常相似，区别在于生成分析表格时，对于S-x.这种item集，仅仅对于r输入FOLLOW(S)才在(S,r)位置处记入shift操作。最后一种是LALR(1)文法。相对于LR(0)而言引入了活前缀，构造思路仍与LR(0)类似，但是构造出来的预测分析表更大。综合起来，各文法表述能力：LL(0)LR(0)SLRLALR(1)LR(1)LR(k)，LL(1)LR(1)递归下降分析算法：递归作为一种强有力的数学和算法描述工具在Pascal语言中被广泛使用。一个函数、过程、概念或数学结构，如果在其定义或说明内部又直接或间接地出现有定义本身的引用（在过程或自定义函数中，又包含自己调用自己），则称它们是递归的或者是递归定义的。一个递归算法仅使用少量的程序编码就可描述出解题所需要的多次重复计算而不需要设计循环结构。使用递归求解问题，通常可以将一个比较大的问题层层转化为一个与原问题相类似的规模较小的问题来求解，进而最终导致原问题的解决。例如：n!的定义，我们知道，在数学中n!一般定义为：在n0的公式中，又包含了（n-1）!，这就是递归定义。利用递归方法，可以用有限的语句来定义对象的无限集合。但在递归定义中，应该至少有一条是非递归的，即初始定义。如上面例子中的第一条，否则就变成了循环定义，产生逻辑性错误。n!的递归定义的程序：programfindn;varn:integer;t:longint;procedurefid(n:integer);beginifn=0thent:=1elsen!=1若n=0n×(n-1)!若n0西南交通大学希望学院编译原理过程及分析beginfind(n-1);t:=t*nend;end;beginwrite(‘n=’);readln(n);find(n);writeln(n,‘!=’,t)end.递归调用（n进栈）达到结束条件时（n=0，t赋初值1）就停止调用开始返回，再把保存的值取出（n出栈），使n恢复原来的值，并计算t，返回主程序，输出结果t。follow集合算法:计算所有非终结符号A的follow（A）集合时，不断应用下面的规则，直到再没有新的终结符号可以被加入到任意的follow集合中为止。1、将$放到follow（S）中，其中S是开始符号，而$是输入右端的结束标记。2、如果存在一个产生式A→αBβ，那么first（β）中除ε之外的所有符号都在follow（B）中。3、如果存在一个产生式A→αB，或存在产生式A→αBβ且first（β）包含ε，那么follow（A）中的所有符号都在follow（B）中。举个例子来说明下，假设有如下文法：①E→TE'②E'→+TE'|ε③T→FT'④T'→*FT'|ε⑤F→（E）|id对于每个非终结符号，我们都可以求出其follow集：根据（1），首先将$加入到follow（E）中，即follow（E）=｛$｝，由⑤可知，）也应该在follow（E）中，即follow（E）=｛$，）｝；对于E'，根据规则（3）以及产生式①，应该将follow（E）加入到follow（E‘）中，即follow（E'）=｛$，）｝；对于T，根据规则（2）以及产生式①，应该将first（E'）加入到follow（T）中，即follow（T）=｛+｝，根据规则（3），由于first（E'）包含ε，所以应该将follow（E'）加入到follow（T）中，即follow（T）=｛+，$，）｝；对于T'，根据规则（3）以及产生式③，应该将follow（T）加入到follow（T‘）中，即follow（T'）=｛+，$，）｝；对于F，根据规则（2）以及产生式③，应该将first（T'）加入到follow（F）中，即follow（F）=｛*｝，根据规则（3），由于first（T'）包含ε，所以应该将follow（T'）加入到follow（F）中，即follow（F）=｛*，+，$，）｝；3、语义分析(SematicAnalysis)语义分析包括一些经典的问题。(1)类型检查(TypeChecking)，例如在语法树上a+b看起来是没问题的，因为a和b西南交通大学希望学院编译原理过程及分析都是合法的变量名，并且语法中支持变量间+这种操作。但是可能a是一个字符串，而b是一个浮点数，这两者之间的+操作就不符合语义规范了，这种问题在这个阶段都会被找出来。(2)符号管理，最经典的问题就是如何管理变量(变量的名字，类型，变量的作用域(scope)等)，在分析代码时，符号管理肯定是被频繁的搜索，因此它通常会使用hash来组织。4、中间代码(IR,intermediateRepresentation)生成IR是非常非常重要的，它被引入的初衷是提高编译器开发的效率。IR是编译过程的一个汇聚点，在IR之前我们通常都认为是编译的前端，而IR之后是编译的后端，这样当编译器需要多支持一种高级语言时主要工作就是提供一个前端，而当需要移植到一种新的平台上时主要工作就是提供对应的后端。关于IR的表示典型的有三地址码。IR生成的过程就是将一棵抽象语法树(这是编译器前端对源代码的理解和抽象)变成一串IR定义的代码(IR指令种类简单，这便于优化)。这个转换过程都是比较固定的套路，例如if-else，while/for等基本结构如何转都是一个固定的套路。5、编译优化这一部分是现代编译器最核心所在，主要有两类，一类是通用的优化手段，比如死代码删除、循环不变量外提、强度削弱等，另一类就是体系结构相关的，说白了就是某种体系结构针对某类应用提供了特殊指令，例如intel的MMX，SSE2等等。为支持优化工作的开展，我们首先需要能够比较方便的描述代码。最基本的当然是一条指令，但是这个太细微，于是往上抽象出基本块(BasicBlock)，这个基本上是所有优化开展必备的工作，然后多个基本块还可以构成一个超级块(region)。此外，经典的方法还包括控制流分析和数据流分析，这里常用的包括d-u链等。最后一个经典的topic就是寄存器分配。6、目标代码生成这里直接和具体平台相关，这里的平台同时包括软件和硬件，例如哪种目标文件格式(ELF,PE)，哪种平台(指令集)。不过现在编译器一般生成的是字符形式的汇编文件，所以前面一个问题基本不大，主要影响在后者。编译程序的最后一项任务是生成目标代码。目标代码生成器把中间代码变换成目标代码，通常有3种变换形式：1、立即执行的机器语言代码。这种方式对应静态连接方式，程序中所有地址都重定位，执行效率最高，但是占用的存储空间最大。2、待装配的机器语言模块。该方式不连接系统共享的程序库，在需要使用的时候会由系统加载共享程序库。3、汇编语言代码。该方式经过汇编程序汇编后，直接生成可以在操作系统上运行的目标代码。生成目标代码需要考虑3个影响生成速度的问题：1、是采用什么方法生成比较短小的目标代码；2、是如何在目标代码中多使用寄存器，减少目标代码访问外部存储单元的次数；3、是如何根据不同平台计算机指令特性进行优化，提高程序运行效率。