编译器(Compiler),是一种计算机程序,它会将用某种编程语言写成的源代码(原始语言),转换成另一种编程语言(目标语言)。—— 维基百科

把实现编译器过程中所用到的策略与方法总结起来,这就是编译原理,其主要包含了编译器的构造与优化。

一般来说编译器的内部包含了如下的工作步骤:

  1. 词法分析;
  2. 语法分析;
  3. 语义分析;
  4. 生成中间表示(intermediate representation,IR);
  5. 代码生成;
  6. 优化;

一般来说到生成中间表示这过程中的操作被称为编译器的“前端”,而从IR到最终结果被称为编译器的“后端”。也就是说1 ~ 4步为编译器的前端,而5 ~ 6步为编译器的后端。IR的目的在于保证编译器的跨平台,对于不同的平台,它们的IR表示是一样的,区别只在于代码生成和优化阶段。有了IR,我们在不同平台上编译器的前端就可以复用了,只需要对应不同的平台开发其对应的后端就可以了,减少了工作量。

词法分析

词法分析是编译工作的第一步,它的主要工作是把输入的程序源代码字符流转化为记号(Token)流。例如,对于如下语句,在进行了词法分析操作之后,对应的会生成 inta=0;这几个记号。

1
int a = 0;

一般来说词法分析的实现主要有两种方式:

  1. 手工编码构造词法分析器,手动构造词法分析器的优点是方便对细节进行控制,缺点是比较复杂且容易出错;
  2. 使用词法分析器的生成器(例如:JavaCC, Yacc, Lex),词法分析器的生成器是一种根据给定的规则把输入构建成Token并输出的程序,其优点时使用简单;

出于学习的目的,我们这里主要讨论手工构造词法分析器的方式;至于词法分析器的生成器的方式,你可以任选一个流行的生成器进行深入了解。

数学工具

词法分析阶段会用到以下几个数学工具:

  • 正则表达式(Regular Expression, RE)
  • 确定性有限状态自动机(DFA)
  • 非确定性有限状态自动机(NFA)

手工构造词法分析器的步骤如下,我们通过RE来实现对Token的描述:

下面我们按照此图中的顺序,了解一下在这几个步骤中所用到的算法以及它们的实现方式。

1. Thompson算法

我们已经知道一个RE可能会包含如下几种情况:

  • ε:代表空;
  • c:代表一个输入字符;
  • e1 e1:两个re的连接关系;
  • e1|e2:两个re的选择关系;
  • e1*:闭包,代表一个re重复0次或多次

例如,对于RE a(b|c)*,我们可以创建如下的NFA:

我们发现,RE和NFA的对应关系还是很清晰的,事实上只需要一些简单的递归操作即可以实现从RE到NFA的转换。

2. 子集构造算法

通过不断的构建一个个的状态集合,这些集合都是自动机的所有状态的子集,这就是子集构造算法名字的意义。这种转化算法的本质在于对于每一个状态集合,给该集合一个输入,会得到一个新的状态的集合,通过这种方式来把一个NFA转化为一个DFA。

例如下面这个NFA,我们可以先把它状态集合的转移情况列出来,并用一个二维表来表示:

二维表表示集合间的转移关系:

  • 表中的第一列表示不需要任何输入(即输入ε)进行状态转移;
  • 第二列表示了在当前状态的集合下,对于每个状态输入a,之后把得到的状态组合起来作为一个新的集合;
  • 第三列表示对所有状态输入b,得到最终的状态集合;

上表是对所有的状态集进行a和b的输入操作,之后把新得到的状态集再次输入a和b进行转移得到新的状态集,如此反复输入并转移直到最终到达接受状态。

如果把上表的每个状态集合取个别名,例如1、2、3…,那么我们可以把上表改写成如下的形式,这样使得结构更加的清晰,不过集合和别名之间的对应关系需要被保存下来。

之后,根据上表我们可以的得到这样的一个DFA。至此,NFA到DFA的转化结束。

3. Hopcroft算法

Hopcroft算法是DFA到DFA的转化,其目的是减少DFA的状态和边,对DFA进行简化,这样可以使得后面的操作变得简单。

首先我们需要知道最小状态DFA所需要遵守的规则:

  1. 没有多余状态;

    1. 什么是多余状态? 从这个状态没有通路到达终态:S1;从开始状态出发,任何输入串也不能到达的那个状态:S2
    2. 如何消除多余状态? 删除
  2. 没有两个状态是互相等价;互相等价需满足下面两个条件:

    1. 兼容性(一致性)条件——同是终态或同是非终态
    2. 传播性(蔓延性)条件——对于所有输入符号,状态s和状态t必须转换到等价的状态里

DFA最小化分为以下几步,它主要是根据上面的不可互相等价规则来进行操作的:

  1. 把DFA拆分为非接受状态(N)和接受状态(A)这两个集合;
  2. 对于同样的输入,某个集合中的状态产生了不同的结果(这里的结果不同指的是转移状态所处的集合不同),那么根据结果集合的不同应该把这些状态从该集合拆分为新的集合;
  3. 反复进行第2步,直到不可再拆分,此时的集合就可以构成一个新的DFA;

例如,对于如下的DFA,我们对其进行最小化操作。

  1. 我们根据N和A对其进行拆分,得到集合N {q0, q1, q2, q4}, A {q3, q5}
  2. 对于集合A,任何输入都不能对它们区分,则它们已不可拆分
  3. 对集合N,我们输入e,q0和q1转移到集合N,q2和q4转移到集合A,则集合N可以拆分为N1 {q0, q1}和 N2 {q2, q4}
  4. 集合N2只接受e且转移结果一致(都是转移到A),其不可再区分
  5. 集合N1输入e,q0转移到N1(因为它还是q0状态),q1转移到N2,则N1可以再被拆为{q0}和{q1}
  6. 所有的集合都不可再拆分,现有集合为 {q0}, {q1}, {q2, q4}, {q3, q5} 我们把这些集合生成一个新的DFA,这个新的DFA比初始的6个状态少了两个状态,结构变得简单了。

4. DFA结构解析并生成词法分析器

在上面的我们已经生成了一个符合要求的DFA,现在我们把这个DFA作为输入读入到程序中,然后通过某种方式把这个DFA转化为某种程序易描述的数据结构(例如数组),之后程序利用该结构对输入的字符流(即某种语言的源代码)进行解析。

例如:利用二维数组对DFA结构进行描述,左侧表示当前状态,上方表示输入,框中表示转移结果

从概念上来说,DFA实际上是一个有向图。我们可以通过转移表、跳转表等代码表示来实现对DFA的识别和Token的解析。

对于识别出来的Token,有些Token只有类型(例如:if),有些Token既有类型又有值(例如:101)。

参考:

  1. 【编译原理】:NFA转变为DFA的子集构造法