编译原理流程简介

你的名字 2021-06-11 15:12 592阅读 0赞

![这里写图片描述][70]  
![这里写图片描述][70 1]

--------------------

**词法分析(lexical analysis / scanning)**  
词法分析是编译的第一步，主要任务是读入源程序的输入字符（将代码一个字符一个字符的读入），将其组成词素（一个字符序列），生成并输出一个词法单元序列。由于负责读取程序源码，它还有一些其他任务。如：过滤程序中的注释和空白（合并空格，删除换行符、制表符等）；将编译器生成的错误消息与源程序的位置联系起来（给错误赋予行号）。下图为词法单元和词素之间关系：  
![这里写图片描述][70 2]  
词法分析使用正则表达式来表示一个匹配模式，然后根据各个需要识别的词法单元的匹配模式来构造出代码。在这其中首先要构造出状态转换图，使得词法分析器在扫描输入串的过程中寻找和某个模式匹配的元素，然后根据一组状态转移图构造出一个词法分析器。如下图：  
![这里写图片描述][70 3]  
如果在状态0时看到“=”，那么直接从状态5返回信息，如果看到“<”表明进入状态1，然后继续往下扫描。如果没有看到“<”“=”“>”，表明此处没有relop的词素，该状态图不会使用。  
这只是手工将正则表达式转成状态转移图，词法分析器生成工具Lex使用不确定的/确定的有穷自动机根据一组正则表达式集合构造出状态转移图。

词法分析器一般产生如下格式词法单元：

<token-name, attribute-value>

其中token-name表示词法分析过程中的抽象符号，类似于为该词法单元赋予唯一id，而attribute-value指向存储词法单元相关信息的符号表中的某一条。如前图的赋值语句，这条词法语句中的词素将会被映射成如下词法单元，用于下一阶段的语法分析。  
![这里写图片描述][70 4]

符号表：用于记录程序中使用的变量名，并收集每个名字的各种属性有关信息。包括一个名字的存储分配、类型、作用域等信息。对于过程名字，还包括参数数量、参数类型、每个参数传递方法，以及返回类型。

--------------------

**语法分析(syntax analysis / parsing)**  
语法分析使用词法分析产生的词法单元的第一个分量来建立树形中间表示。从而给出词法单元流的语法结构，常用表示方法为语法树。树的内部节点表示一个运算，此节点的子节点表示运算的分量。在编译器的后续阶段将会使用该语法树来分析程序，并生成目标程序。前图的赋值语句语法树如图所示。  
![这里写图片描述][70 5]

--------------------

**语义分析(semantic analyzer)**  
语义分析利用前面生成的语法树和符号表来检查源程序是否符合语言定义。同时收集类型信息，以便在代码生成过程中使用。  
因此语义分析的一个重要作用就是类型检查，编译器检查每一个运算符是否具有合法的运算分量。另外对于某些语言允许自动类型转换，编译器需要根据自动类型转换规则，对数据类型进行转换。  
![这里写图片描述][70 6]

--------------------

**中间代码生成**  
在将源程序翻译成目标程序的过程中，编译器会根据需要产生多个中间表示。如在语法分析和语义分析阶段产生的语法树。在对源程序完成语法和语义分析后，编译器一般会产生一个低级的类似机器语言的中间表示。该中间表示应该易于生成并且很容易翻译成目标程序。如三地址代码表示会将源程序转成一组具有三个运算分量的类汇编语言：  
![这里写图片描述][70 7]  
每一个指令一般具有三个运算分量，每个赋值语句右边只有一个运算符。之所以如此细化，是因为程序的执行是有先后顺序的，比如上图的乘法应该在加法之前完成，通过指令的顺序完成逻辑算法的运算顺序。

--------------------

**代码优化**  
代码优化是在代码优化步骤试图优化改进中间代码，以便生成更好的目标代码，“更好”可能是以更快、更短或者更能耗低为目标。如上述赋值语句，上面的60要使用inttofloat算法转成float类型，但显然如果直接在编译时刻将60一劳永逸的改成60.0，就可以消除inttofloat运算，而在代码中t3只用于使用一次，且仅用于传递值，因此可以直接将t3的值赋给id1。从而减少指令数：  
![这里写图片描述][70 8]

--------------------

**代码生成**  
代码生成器以源码中间表示生成目标语言，如果目标语言是机器代码，那就要为每个变量指定寄存器或内存位置。代码生成的一个至关重要的方面就是合理的分配寄存器以存在变量值。如上述代码使用寄存器R1，R2：  
![这里写图片描述][70 9]  
![这里写图片描述][70 10]

--------------------

**其他**  
1、上述步骤拆分的很细，但在实际过程中，多个步骤可以合并在一起，如前端步骤词法分析、语法分析、语义分析以及中间代码生成可以组合成一趟（pass），而代码优化可以作为可选趟，然后可以有一个以生成目标代码的后端趟。

摘自《编译原理》

[70]: /images/20210520/51f25cfb7045424c9ff7dd024ba07709.png
[70 1]: /images/20210520/68a2238573f247fc8b99d58cded97b83.png
[70 2]: /images/20210520/6ab53a0c52244d9584fd53227e327326.png
[70 3]: /images/20210520/fe9d670ecd4e40d3a26d0b9f49bab392.png
[70 4]: /images/20210520/3b3131c33ec44b0d8412dd98b0c48ba7.png
[70 5]: /images/20210520/4d3d9f3addf9446bb892fe17ca52ecfe.png
[70 6]: /images/20210520/e27c7e9ef18f457c83f60300e40cf1a9.png
[70 7]: /images/20210520/dc8e7ea6df0041328d21af92c5e6aeca.png
[70 8]: /images/20210520/775cc47955e34916bf543111829cefc2.png
[70 9]: /images/20210520/e8fe1ecfd9d84630a881bca230f0585d.png
[70 10]: /images/20210520/34621007819545c18a2698b389acaa48.png