RE:从零开始的编译器编写 05 词法分析器(2) 木灵的炼金工作室

本节我们来讲讲如何从正则表达式转化为DFA。
对于一般的正则表达式来讲,我们只需要在它的每一个位置设立一个标记,将每一个标记抽象为DFA的状态,并根据表达式推知其支持的操作即可。这种做法在之后的SLR语法分析中也会用到。只要正则表达式是无二义的,那么这在逻辑上就是不难的,在实现上也不难。

比如对于正则表达式$\bold{0}\bold{X}\bold{digit16}^+(\bold{U\ or\ u})$,我们依据符号,依照输入进入,将其分出五个阶段,分别对应输入$\epsilon$(空集)、$\bold{0}$、$\bold{0}\bold{X}$、$\bold{0}\bold{X}\bold{digit16}^+$、$\bold{0}\bold{X}\bold{digit16}^+(\bold{U\ or\ u})$,从而可以简单地写出一个DFA。

正则表达式与NFA的转换

但对于一些不太标准的正则表达式,我们可能就需要使用一些固定的算法来生成其自动机。

首先,我们公认:不是所有的正则表达式都对应一个DFA,二义性的正则表达式不能满足“每一个状态对于一个输入仅存在唯一的动作选择”,因此它不能有DFA。但,它也是正则,状态机能够表达的模式是正则的超集,因此我们可以将二义的正则转化为同样具有二义的NFA。

McMaughton-Yamada-Thompson算法

我们约定算法中出现的NFA均有且仅有一个入位置和一个出位置:由于NFA允许存在空转换边(即$\epsilon$边),这个性质是很容易维护的。

  1. 基元表达式:对于单个字符$a$(特殊地,$a$可以是$\epsilon$),我们可以构造一个非常简单的转换图:
    自动机单元
  2. 求并运算$a\ or\ b$:新建一个开始节点$S_{new}$,$S_{new}$发出两条$\epsilon$边,分别指向求并运算左右两侧对应自动机ab的开始节点$S_a$和$S_b$(start边直接指向的节点)。然后,新建一个结束节点$F_{new}$,令求并运算左右两侧对应自动机的结束节点$F_a$和$F_b$各发出一条$\epsilon$边指向它,同时令$F_a$和$F_b$不再是结束节点,令$F_{new}$为新的结束节点。
  3. 顺序连接运算$ab$:将b的开始节点替换为a的结束节点,a的开始节点作为$ab$的新开始节点,b的结束节点作为$ab$的新结束节点
  4. 闭包运算$a*$:最为复杂,首先用一条$\epsilon$边从a的结束节点$a_f$指向a的开始节点$a_s$,然后,新建一个开始节点$s_{new}$和结束节点$f_{new}$,以$\epsilon$边连接:$s_{new}\rArr a_s$、$s_{new}\rArr f_{new}$、$a_s\rArr f_{new}$

至此,我们成功地将一个正则转化为了一个NFA。

NFA转DFA

想要把NFA转为DFA,我们首先需要知道NFA如何在模式匹配中起作用。

NFA的使用方法

NFA存在二义性,即一个输入串可能对应数个NFA状态,那么一个非常自然的想法就是:我们同时维护NFA的所有状态,每当输入一个新的字符,我们遍历目前拥有的所有状态,然后更新之:失配状态删除,新增状态插入。

但想想这样的算法都会觉得慢。所以我们需要将NFA转化为DFA的算法。

NFA转DFA

将NFA转化为DFA的算法与我们实际使用NFA进行匹配的过程相似,都是将等价的若干NFA状态合并为一个DFA状态。等价状态中包含接受状态的为DFA接受状态,包含入状态的为DFA开始状态。这种算法很简单而且一般很少用,因此不写出具体过程。通过这样的算法,我们将NFA匹配的复杂度转移到了“编译期”。

于是,我们在数学上完成了正则表达式->匹配算法这一过程,我们拥有了针对于复杂度相当于正则表达式的词法规则的分析方法。结合上一节中的编码技巧,我们就可以成功编写一个词法分析器。


Copyright AmachiInori 2017-2021. All Right Reserved.
Powered By Jekyll.
amachi.com.cn