编译原理总结

type

status

date

slug

summary

简介

编译程序是计算机系统软件的最重要的组成部分之一，它能够把某一种语言（源语言程序）转换成另一种语言程序，且前者和后者在逻辑上是等价的，像我们常见的诸如C、Java、C++、Pascal等语言都得经过编译程序翻译成计算机所能识别的机器指令后才可以执行。

早期人们认为设计和实现编译程序是十分困难的事情，但经过科学家们40多年的努力，编译理论和技术已经得到迅速发展，现在已经形成了一套比较成熟且系统化的理论和方法，也开发出了许多方便有效的工具。

编译程序从输入源程序到输出目标程序之间通常要经历五个步骤：词法分析，语法分析、语义分析与中间代码生成、优化、目标代码生成。词法分析即对源程序的字符串进行扫描和分解以识别出其中的单词符；语法分析是在词法分析的基础上，根据语言的语法规则，把单词符号串分别成各类语法单位，如“短语”、“子句”和“程序段”等，语法规则通常用上下文无关文法来描述；语义分析和中间代码生成是根据语法分析所识别出的各类语法范畴，分析其含义并进行初步翻译并进行静态的语义检查；优化旨在对上一步生成的中间代码进行加工和变换以在后期生成高效的目标代码；目标代码生成即把优化过后的中间代码变换成在特定机器上的低级语言，这部分通常十分复杂，往往设计到硬件的操作。

上机作业着重实现了编译过程中的前两部分的功能，实现了如下功能：正则表达式转NFA、NFA转DFA、DFA转最小化DFA、Flex进行词法分析、消除文法中的左递归、根据产生式计算First集和Follow集、Yacc和Flex实现简易计算器、用递归下降法计算表达式的值、用符号优先法计算表达式的值、Bison和Flex实现逆波兰表达式计算器、Bison和Flex实现中缀表达式计算器。该实验算法除去使用Flex和Yacc之外，其余全部使用Kotlin语言进行开发，已在Github上开源，项目地址。

正则表达式转NFA

正则式

对于字母表的特殊字符集即为正规式，它的递归定义如下：

和都是上的正规式，它们表示的正规集分别是和

任何，是上的一个正规式，它表示的正规集为

假设和都是上的正规式，那么、和也是正规式

例如，令，正规式表示上所有以为首的字母

非确定有穷自动机(NFA)

一个非确定有限自动机是一个五元式，其中是一个有限集合，代表了元素的状态；是一个有穷字母表；是一个从到的子集的映射，即；是一个非空的初态集；是一个终态集合。

Thompson构造法

对于任意一个正则表达式，首先将构成的元素进行分解，对于每个元素，按照以下方式分解：

对于

对于

对于表达式

代码

NFA转DFA

确定有穷自动机

一个有穷自动机也是一个五元式，其中是一个有限集，它的每一个元素为一个状态；是一个有穷字母表；是一个从至的单值部分映射，意味着：当现行状态为，输入字符为时，将转换到下一个状态，我们称为的一个后继状态；是唯一的初态；是一个终态集（可空）。显然，DFA是NFA的特例，即对于每一个NFA 都存在一个DFA ，使得，证明如下：

首先引进新的初态结点和终结结点，其中，从到的任意状态结点引进一条弧，从中任意状态结点连一条弧到

对NFA 进行变化，重复如下分裂过程直到状态图中的每条弧都被标记为或为中的单个字符，将最终得到的NFA记作，其中

子集构造法

假设是的状态集的子集，定义的闭包为：

若，则
若，那么从出发经过任意条弧所能到状态

假设是的状态集的子集，，那么定义：，是那些可从中的某一状态结点出发经过一条弧而到达的状态结点的全体

假设，构造一张表，表的每行含有项，令表的首行首列为。通常来说，若某行的第一列的状态子集已经确定，我们假设记作，那么置该行的列为，然后检查该行所有的状态子集，若未在表的第一列中出现过，则加入到后面空行的第一列，重复上述过程直到没有新的集合被加到表的第一列中，由于状态的子集个数是有限的，所以该过程一定能在有限步内结束。

假设正规式为，则其对应的NFA如下：

其根据子子集构法所构造出来的状态矩阵如下：

表1

I_a

I_b

代码

最小化DFA

一个确定有限自动机的化简是指寻找一个状态数比少的DFA ，使得。假设和是的两个不同状态，我们称和是等价的，若从出发读出某个字而停于某个终态，那么同样，从出发也能读出同样的字而停于终态。

将一个DFA 的状态最小化的过程旨在将的状态集划分成一些不可相交的子集，使得任何不同的两个子集中的状态都是可以区别的，而同一子集中的任何两个状态都是等价的，最后在每个子集中选出代表，消去它们的等价状态即可。

对的状态集划分的主要步骤：首先把的终态和非终态分开，分成两个子集，形成基本划分。显然，属于这两个不同子集的状态是可区分的，假设当前已含有个子集，记作，并且属于不同子集的状态是可区别的，此时进一步检查中的每个是否可以进一步划分。若对于某个，令，若存在一个输入字符使得不全包含在现行的某一子集中，就将一分为二，假定状态和经弧分别到达状态和，而和属于现行的两个不同子集，那么就将分成两半，一半含有，另一半含有。由于和的状态是可区别的，即存在一个字，将读出而停于终态，而或读不出或虽然可读出但不到达终态，因此字能将状态和区分开来。

一般地，若落入现行中个不同子集，则应将划分成个不相交的组，使得每个组的都落入的同一子集中。重复上述过程，直到分划中所含的子集数不再增长为止。经过上述的划分以后，对于这个的每一个子集，我们选取子集中的一个状态代表其他状态，例如，假定是这样的一个子集，我们即可挑选代表这个子集，在原来的自动机中，凡导入到的弧都改成导入到，然后将从原来的状态集中删除，若中含有原来的初态，则是新的初态；若是终态，则是新终态。可以容易的证明，经如此化简后的DFA 和原来的是等价的，即。

对于正则式：，若采用子集法对其NFA转换成DFA后，根据得到上一节中的状态转换矩阵，如果将其中的状态子集重新命名后，即可得到如下的状态转转换矩阵：

表2

根据该状态矩阵所得到的未化简的DFA如下：

最小化后的DFA结果如下：

代码

Lex实现词法分析器

Lex是Lexical Compiler的缩写，是Unix环境下十分著名的工具，它的主要功能是根据Lex语言生成一个对应的词法分析器的C源码。通常来说，Lex源程序包括两部分：正规式定义和识别规则。若是一个字母表，则上的正规定义式通常是如下形式：，例如用来描述标识符集合：

识别规则是一串如下形式的Lex语句：

其中是一个正规式，称为词形，中除了出现中的字符外，还可以出现正规式左部所定义的任何简名。即是上的一个正规式。由于每个最终都可以化成纯粹上的正规式，因此，每个也同样如此。如果每个是一小段程序代码，它指出了在识别出词型为的单词之后，词法分析器应该采取的动作，这些识别规则完全决定了词法分析器L的功能。

由Lex形成的词法分析器L的工作流程：逐一扫描输入串中的字符，寻找一个最长的字串匹配到某个，将该字串截取下来放到TOKEN缓冲区中，然后L调用动作子程序，当执行完以后，L就把所得的单词符号（种别编码和属性值）交给语法分析器，接着识别下一个单词符号。

可能存在这样的情况，即输入串无法与任何匹配，这种情况应该进行特殊的错误处理，也可能存在一个输入串匹配多个的情况，这种二义性的情况，以Lex中出现在最前面的那个为准。

左递归的消除

自上而下分析

自上而下分析法就是从文法的开始符号出发，向下推导出句子的过程，一般来说，自上而下的分析法可能是带“回溯”的。对于任何输入串，从文法的开始符号（根结点）出发，自上而下地为输入串建立一棵语法树，或者说为输入串寻找一个最左推导。

实现自上而下的带回溯试探法的一种简单途径是让每个非终结符对应一个递归子程序，一旦发现某个候选式和输入串匹配，就用这个候选式去扩展语法树。

然而，这种自上而下分析法存在许多困难和缺点，如果一个文法含有左递归，即存在这样的产生式，会在分析过程中陷入无线的循环，因此，自上而下分析法必须消除文法的左递归性。

消除左递归

直接消除产生式中的左递归还是比较容易的，假设有如下产生式：

其中不以开头，我们可以把的规则改写成如下的形式：

这种形式的文法和原来的形式是等价的，即从推出的符号串是相同的。一般而言，假设关于的全部产生式是：

那么消除消除左递归后的形式为：

通常来说，用上述方法可以把表面的的直接左递归给删除，但这并不意味着已经消除了所有的左递归，例如下列文法：

虽然不存在直接的左递归，但是S、Q、R都是左递归的，例如有：

因此，消除一个隐式的左递归并不是一件容易的事，若一个文法不含回路（形如的推导），也不含以为右部的产生式，那么，执行下述算法可以保证消除左递归。

消除左递归算法

把文法G的所有非终结负按任一种顺序排列成，按此顺序执行如下步骤：

For i: = 1 To n Do

For j: = 1 To i-1 Do

把形如的规则改写成
其中是关于的所有规则

消除关于的直接左递归

例如对于上述文法，令非终结符排序为R、Q、S，把R带入到Q的候选式中，可以把Q的规则变为：

现在的Q同样不含直接左递归，把它带入到S的有关候选式后，S变成：

然后对S消除左递归，得到的文法为：

显然，其中关于Q和R的文法规则已经是多余的，将它们删去即可。

代码

First集和Follow集

First集

我们定义：可以从推导出的所有串首终结符的集合。

若，那么

算法：

不断应用下列规则，直到没有新的终结符或者可以被加入到任何集合中为止

如果是一个终结符，那么

如果是一个非终结符，且，那么如果对于某个，在中且在左右的中（即），就把加入到中，如果对于所有的，在中，那么将加入到

如果，那么将加入到中

Follow集

我们定义：可能在某个句型中紧跟在后面的终结符的集合，如果是某个句型的最右符号，则将结束符#添加到中

算法：

不断应用下列规则，直到没有新的终结符可以被加入到任何集合中为止

将#放入中，其中是开始符号，#是输入右端的结束标记

如果存在一个产生式，那么中除之外的所有符号都在

如果存在一个产生式或存在产生式且包含，那么中的所有符号都在中

代码

递归下降分析法

递归下降法

当一个文法满足LL(1)条件时，我们可以给它构造一个不带回溯的自上而下的分析程序，这个分析过程是由一组递归过程组成的，每个过程对应文法的一个非终结符，这样的分析程序我们称为递归下降分析程序。

算术表达式分析

首先我们需要写出表达式对应的文法：

由于该表达式存在左递归，因此我们需要先将其消除得到如下文法：

然后计算其FIRST集和FOLLOW集：

根据以上的FOLLOW集合，我们可以构造如下的SELECT集：

因此，该文法所有相同左部产生式的SELECT集的交集为空，所以文法是LL(1)文法，因此算数表达式可以用下降分析法进行语法分析。

算符优先分析法

算符优先法特别有利于表达式分析，易于手工实现，其过程是自下而上的规约过程，但这种规约未必是严格的最左规约，也就是说算法优先分析法并不是一种规范规约法。所谓的算符优先分析就是定义算符之间的某种优先关系，借助于这种优先关系寻找“可规约串”和进行规约。通常用下面方法表示任何两个可能相继出现的终结符和的优先关系：

，的优先级低于

，的优先级高于

，的优先级等于

一个文法，如果它的任一产生式的右部不含两个相继（并列）的非终结符号，即不含如下形式的产生式右部，则我们称该文法为算符文法。假设G是一个不含-产生式的算符文法，则对于任何一对终结符：

，当且仅当文法G中含有形如或的产生式

，当且仅当G中含有形如的产生式，而或

，当且仅当G中含有形如的产生式，而或

如果一个算符文法G中的任何终结符对至多只满足上述三关系之一，则称G是一个算符优先文法。通常我们根据产生式构造其优先关系表，然后对每个非终结符计算其FIRSTVT集和LASTVT集。

有了FIRSTVT集和LASTVT集后，就可以通过检查每个产生式的候选式确定满足关系的所有终结符对。

Yacc分析器

Yacc是一个经典的生成语法分析器的工具，它根据用户提供的语言的语法描述的规格说明，自动构造出一个该语言的语法分析器，它能和词法分析器Lex一起使用，把两者生成的C文件共同编译。该实验，我用Yacc写了一个功能比较完善的计算器，不仅支持标准的加减乘除四则运算，还能进行三角函数sin、cos、tan、arcsin、arccos、arctan等函数运算，开根sqrt运算，幂^运算，还包括对数log、ln和自然数的运算。

Bison

Bison和Yacc相类似，基本与Yacc兼容且在其基础之上进行了改进，经常和Flex一起使用，它是一种通用的分析器程序，可以用它生成从简单的计算器到复杂的程序设计语言等多种语言分析器。它向上兼容Yacc，理论上Yacc语法都可以不加更改地使用Bison生成C文件。

逆波兰表达式

逆波兰表达式又叫后缀表达式，在通常的表达式中，二元运算符总是置于与之相关的两个运算对象之间，这种表示法也叫做中缀表达式，而在逆波兰表达式中，每一个运算符都置于其运算对象之后，例如：