一直以来，我都认为编译原理的作用不大，所以导致我对编译原理的知识忘却完了。今日刷leetcode是碰到一道判断字符串转换成数字的题目，正常来说，都是暴力模拟，我也是这么干的，但是当我了看到题解时，我眼前一亮，我觉得编译原理也不是那么无用，故而有了这篇文章的出现。

题目相关

具体的题目链接如下：

传送门

这里的题解用到了《编译原理》的词法分析相关知识，而我已经还回去了。。。所以在这里重新复习一下。

所以本文将以此题为引，重新拾起相关的编译原理知识。

词法分析

1. 从正规式到NFA

词法分析器的构造一般方法和步骤：

  • 描述：用正规式对模式进行描述

  • 构造NFA：为每个正规式构造一个NFA；

  • 确定化：将NFA转换成等价的DFA；

  • 最小化：优化DFA，使其状态数最少；

  • 构造词法分析器：由DFA构造词法分析器。

    如下图所示的流程。

image-20200629115223193

以下分割线以内的内容选读：

1. 正规式是个啥？

​ 所谓正规式，又叫正规表达式，它是表示模式的一种重要方法。编译过程的第一个阶段，词法分析就是要将输入的源程序按照某种固定的模式将它翻译成编译器可以识别的，而将这种模式用正规式表达出来，也是做词法分析器的第一步。

​ 正规表达式的表达方式比较像正则表达式，建立正规表达式时，可以先定义简单的正规表达式，然后用它们构造出更复杂的正规表达式。定义在字母表正规表达式的规则如下：

​ a) $ \varepsilon $是正规表达式，他表示{$ \varepsilon $}，即包含空串的集合。

​ b) 如果a是字母表$\Sigma$ 的符号，那么a是正规表达式，表示{a}，也就是包含符号穿a的集合。

​ c) 假定r和s都是正规表达式，分别表示语言L(r)和L(s),则:

​ i). (r)|(s)是正规表达式，表示 $L(r) \cup L(s)$

​ ii). (r)(s)是正规表达式，表示$L(r)L(s)$

​ iii). (r)*是正规表达式，表示$(L(r))*$

​ iv). (r)是正规表达式，表示$(L(r))$

​ 注意，该规则式递归定义的。

2. NFA是啥？DFA呢？

所谓NFA，即不确定的有穷自动机，是一个由以下几个部分组成的数学模型：

  1. 一个状态的有穷集合S。
  2. 一个输入符号集合$\Sigma$,即输入符号字母表。
  3. 一个转换函数move，它把由状态和符号组成的二元组映射到状态集合。
  4. 状态${s_0}$是唯一的开始或终止状态。
  5. 状态集合F是接受(或终止)状态集合。

NFA可以用带标记的有向图表示，成为转换图，其节点是状态，有标记的边表示转换函数。

下图给出了识别语言(a|b)*abb的NFA的转换图。这个NFA的状态集合是{0,1,2,3},输入符号表{a,b},状态0是开始状态，状态3是接受状态，用双圈表示。

image-20200630162049180

所谓DFA，即确定的有穷自动机，是不确定的有穷自动机的特例，其中:

  1. 没有一个状态具有 $ \varepsilon $转换，即在输入上的转换。
  2. 对每个状态s和输入符号a，最多只有一条标记为a的边离开s。

确定的DFA在任何状态下，对任一输入符号，最多只有一个转换。

同样对于上边的例子，同样是识别语言(a|b)*abbDFA转换图，想要的DFA转换图如下:

image-20200630163142416

3. 它们俩有啥不同的？

其实从定义可以看出来，NFA最大的特点是它的不确定性，即在当前状态下对同以自负有多于一个的下一状态转移。

  • 定义: move函数是1对多的。对于上边的例子，NFA的move函数为:
1
move={move(0,1)=0,move(0,a)=1,move(0,b)=0,....}
  • 状态转换图： 统一状态有多于一条边标记相同自负转移到不同的状态:

image-20200630165047598

我相信你已经明白了它俩的区别了，NFA识别记号存在的问题：

  • 只有尝试了全部可能的路径，才能确定一个输入序列不被接受，而这些路径的条数随着路径长度的增长成指数增长。
  • 识别过程需要大量的回溯，时间复杂度升高且算法趋于复杂。

说到构造DFA，我们为啥不直接从正规式直接构造呢？

  • 机器构造需要规范算法。
  • 正规式到NFA：有规范的一对一构造算法。
  • DFA到分析器：有便于记号识别的算法。

从正规式到NFA的常用算法: Thompson算法

输入: 字母表 $\Sigma$上的正规式r

输出： 接收L(r)的NFA N

方法如下：

  1. 对$\varepsilon $，构造NFA $N(\varepsilon)$接受${\varepsilon}$;

image-20200630171101964

  1. 对$\Sigma$上的每个字符a，构造NFA N(a)接受{a};

image-20200630171205322

  1. 若N(p)和N(q)是正规式p和q的NFA，则

    a. 对正规式p|q，构造NFA N(p|q)接受$L(p) \cup L(q)$;

    image-20200630171513645

    b. 对正规式pq,构造NFA N(pq)接受L(p)L(q)

    image-20200630171615475

    c. 对正规式p，构造NFA N(p)接受L(p*);

    image-20200630171717626

    d. 对于正规式(p)，使用p本身的NFA，不再构造。

例： 使用ThomPsons算法构造正规式r=(a|b)*abb的NFA N(r)。

解： 首先分解正规式，自下而上分解树形结构如下:

image-20200630172056236

然后开始构造：

  • a|b

image-20200630173022577

  • (a|b)*

image-20200630172959930

  • 结果

image-20200630172900090

2. 从NFA到DFA

​ 上一节已经讲过，NFA进行匹配时，需要遍历所有可能的情况才能找到当输入是否能别识别，所以我们需要将NFA进行确定化。

并行法确定化不怎么实用，这里不讲了，只讲相关概念。

> $\varepsilon-闭包(T)$: 从状态T出发，不经任何字符到达的状态全体。
>
> smove(S,a): 从状态T出发，不经任何字符达到的状态全体。与move(s,a)的唯一区别： 用状态集取代状态。

这里讲子集法构造DFA。

算法的伪代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
Dstates={ $\varepsilon-闭包(T)$ }
while Dstats有未标记状态T loop
	标记T；
	for 每个字符a loop
		U:= $\varepsilon-闭包(smove(T,a))$
		if U非空 then
			Dtran[T,a]:=U;
			if U不在Dstates中 then
				U作为未标记状态加入Dstates;
			end if
		end if
	end loop;
end loop;

这算法看的我很懵逼。。。所以直接从例子着手吧。

上一届已经给出了正规式r=(a|b)*abb的NFA N(r)，接下来用上述算法来构造对应的DFA：

:= 表示 将前面的状态集定义为后面的字母表示

  1. $\varepsilon-闭包({0}=\{0,1,2,4,7\}) := A$
  2. $\varepsilon-闭包(smove(A,a)):=\{3,8,6,7,1,2,4\}:=B$
  3. $\varepsilon-闭包(smove(A,b))=\{5,6,7,1,2,4\}:=C$
  4. $\varepsilon-闭包(smove(B,a))=\{3,8,6,7,1,2,4\} ==B$
  5. $\varepsilon-闭包(smove(B,b))=\{5,9,6,7,1,2,4\} :=D$
  6. $\varepsilon-闭包(smove(C,a))=\{3,8,6,7,1,2,4\} ==B$
  7. $\varepsilon-闭包(smove(C,a))=\{5,6,7,1,2,4\} ==C$
  8. $\varepsilon-闭包(smove(D,a))=\{3,8,6,7,1,2,4\} ==B$
  9. $\varepsilon-闭包(smove(D,b))=\{5,10,6,7,1,2,4\} :=E$
  10. $\varepsilon-闭包(smove(E,a))=\{3,8,6,7,1,2,4\} ==B$
  11. $\varepsilon-闭包(smove(E,b))=\{3,8,6,7,1,2,4\} ==C$

将上述的DFA画图，如下所示:

image-20200630184146410

3. 最小化DFA

最小化DFA的算法如下：

输入： DFA D=$\{S,\Sigma,move,s0,F\}$

输出: 等价的$D’=\{S’,\Sigma,move’,s0’,F’\}(D’状态数最少)$

方法执行步骤如下：

  1. 初始划分$\prod {\rm{ = \{ S - F,F1,F2,}}…{\rm{\} }}$,其中，Fi是F的子集，接受不同记号。

  2. 应用下述过程构造新的划分 ${\prod_{new}} $:

    for $\prod$的每一个组G loop

    ​ 划分G，G的两个状态s和t在同一组的充要条件：

    ​ $\forall {\rm{a}}(move(s,a) \in Gi \wedge move(t,a) \in Gi) $

    ​ 用新划分的组替代G，形成新的划分${\prod_{new}} $

    end loop;

    1. 若${\prod{new}} = \prod$则 $${\prod{final}:=\prod} \prod=:{\prod_{new}} $$且转2；

    2. 在${\prod_{final}}$每个组中选一个代表si’,是的D中从Gi所有状态出发的状态转移D‘中均从si’出发，D中所有转向Gi中的状态转移在D’中均转向si’。含有D中s0的状态组G0的代表s0’称为D’的初态，D中所有含F中状态的Gj的代表sj’构成D’的终态集F’；

    3. 删除死状态，即不是终态且对所有输入字符均转向其自身，或从初态不可到达的状态。

总结一下，主要步骤如下：

1.初始划分：终态与非终态；

2.利用可区分的概念，反复分裂划分中的组Gi，直到不可再分裂；

3.由最终划分构造D’，关键是选代表和修改状态转移；

4.消除可能的死状态和不可达状态。

下面还是用上面的例子说明，DFA如上幅图所示，下载开始简化如图所示的DFA

解：

所有的状态转移为：

1
2
3
4
5
m(A,a)=B, m(A,b)=C
m(B,a)=B, m(B,b)=D
m(C,a)=B, m(C,b)=C
m(D,a)=B, m(D,b)=E
m(E,a)=B, m(E,b)=C

  1. 初始化划分$\prod1=\{ABCD,E\}$

  2. 反复分裂划分中的组：

    a). m(D,b)=E —> $\prod2=\{ABC,D,E\}$

    b). m(B,b)=D —> $\prod3=\{AC,B,D,E\}$

    c). 所以 $\{\prod_{final}\}=\{ABC,D,E\}$

  3. 根据${\prod_{final}}$构造D‘

    a. 用A代表AC组

    b. 修改状态转移,用0123，代替ABDE

    image-20200630200203772

4. 由DFA构造词法分析器

1. 表驱动型的词法分析器

1). 由数据结构存放DFA；

2). 根据表结构，用最长匹配原则进行编码匹配词法。

回到题目题解

现在回过头去看题解。。。豁然开朗！！！

希望你也能用到这些知识吧。。

参考书籍

  • 《编译原理》第一版 机械工业出版社, 李建中

最后更新： 2023年02月22日 00:00

原始链接： /2020/06/30/20200630-编译原理复习/

赏
× 请我吃糖~
打赏二维码