确定性有穷自动机实现单词、数字和注释扫描

介绍

通过将整段的字符串结成单词，扫描器 可以显著简化语法分析的难度。而构造分词扫描器的通用方法就是使用 正则表达式 和 有穷自动机。有时设计一个新语言的第一步就是实现正则引擎，以便方便地测试词法分析，但是直接编码来产生自动机也是可行的，并且在词类较少时更方便调试和修改。

• 下面我们所说的 单词（token） 指的是一类具有特殊含义的字符串，为了与通常的单词（word）区分开，这种 单词 都使用粗体。

在代码中，扫描器是这样的东西：

interface Scanner<T> {           // 输入单元类型为 T 的有状态的扫描器
	val length: Int              // 匹配状态：当前匹配的长度
	val complete: Boolean        // 匹配状态：是否在可接受的结束状态
	operator fun invoke(char: T) // 输入一个 T 类型的单元 char
	fun reset()                  // 重置内部状态
}                                //

基于自动机的扫描器包含一系列 状态，其中有且仅有一个是起始状态，并有一部分状态是可接受的结束状态。每次扫描开始时，状态机从起始状态出发，对每一个输入单元发生一次状态转移，直到所有单元都输入到扫描器或扫描器因不合法的字符落入到不存在/错误的的状态中。

通过非常简单的代码就可以实现一个自动机引擎：

/**
 * 确定性自动机扫描器
 * @param table  状态转移表（*行序号从 1 开始*，*0 表示错误状态*）
 * @param ending 合法结束状态
 * @param map    字符到转移表列序号的映射关系（*-1 表示无效字符*）
 */
class DFA<T>(
	private val table: List<List<Int>>,
	private val ending: Set<Int>,
	private val map: (T) -> Int
) : Scanner<T> {
	// 当前状态（序号）
	// 正数表示正在匹配
	// 负数表示匹配失败前的最后状态，即能匹配的部分的结束状态
	private var state = 1

	override var length: Int = 0; private set
	override val complete get() = abs(state) in ending

	override operator fun invoke(char: T) {
		if (state > 0) {
			state = map(char)
				// 是一个有意义的字符
				.takeIf { it >= 0 }
				// 查找转移表
				?.let { table[state - 1][it] }
				// 不导致错误状态
				?.takeIf { it != 0 }
				// 匹配长度增加
				?.also {   length }
				// 否则标记匹配结束
				?: -state
		}
	}

	override fun reset() {
		state = 1
		length = 0
	}
}

上面的代码展示了我实现的自动机引擎。其中类的构造参数描述了某一个状态机实例的结构。

• table 是用数字表示的状态转移表，表的每一行表示一个状态，每一列表示在某状态下针对一类输入字符将转移到哪个状态；
• ending 是合法结束状态的集合，状态机根据当前状态是否集合中的元素判断匹配是否完成；
• map 是实际输入字符到状态转移表列的映射关系。用 -1 列表示转到错误状态；

这是数字扫描器实际使用的状态机参数，后面会讲到如何决定这些参数：

table = //     0   1   d   b   h   x   .    //
listOf(listOf( 2, 11, 11,  0,  0,  0, 12),  // 1  -> ε
	   listOf(11, 11, 11,  3,  0,  7, 12),  // 2  -> 0
	   listOf( 4,  4,  0,  0,  0,  0,  5),  // 3  -> 0b
	   listOf( 4,  4,  0,  0,  0,  0,  5),  // 4  -> 0b...
	   listOf( 6,  6,  0,  0,  0,  0,  0),  // 5  -> 0b... .
	   listOf( 6,  6,  0,  0,  0,  0,  0),  // 6  -> 0b... . ...
       listOf( 8,  8,  8,  8,  8,  0,  9),  // 7  -> 0x
       listOf( 8,  8,  8,  8,  8,  0,  9),  // 8  -> 0x...
       listOf(10, 10, 10, 10, 10,  0,  0),  // 9  -> 0x... .
       listOf(10, 10, 10, 10, 10,  0,  0),  // 10 -> 0x... . ...
       listOf(11, 11, 11,  0,  0,  0, 12),  // 11 -> ...
       listOf(13, 13, 13,  0,  0,  0,  0),  // 12 -> ... .
       listOf(13, 13, 13,  0,  0,  0,  0)), // 13 -> ... . ...
ending = 
setOf(2, 4, 6, 8, 10, 11, 13),
map = 
{ c: Char ->
    when (c.toLowerCase()) {
        '0'         -> 0  // 0
        '1'         -> 1  // 1
        in '0'..'9' -> 2  // d
        'b'         -> 3  // b
        in 'a'..'f' -> 4  // h
        'x'         -> 5  // x
        '.'         -> 6  // .
        else        -> -1 // e
    }
}

实现一个基于自动机的扫描器有三个步骤：

1. 根据要扫描的 单词 的特征设计识别 单词 的正则表达式；
2. 直接将正则表达式（及其连接、选择和 Kleene 星号等元操作）转化为包含空转移的非确定性自动机 NFA；
3. 对NFA进行约化和化简得到确定性有穷自动机 DFA；

示例

虽然编译原理是每个计算机专业学生的必修课，但网上其实连能正确扫描 C 语言风格注释的 DFA 实现也很难找到。此处就以这个为例子介绍如何构造自动机扫描器。

1. 正则

   C 语言风格的注释有两种形式：

   • 嵌入型 /* … */
   • 行尾型 // …

   第一步先写出辨别这两种注释的正则表达式：

   • 嵌入型 /*(?*)*/
   • 行尾型 //(?*)

   其中小括号内的 * 是 Kleene 星号，表示匹配任意字符任意次。

2. NFA

   正则对应的 NFA 如图所示。现在先假设我们直接使用换行符分句，因此两种形式都不接受换行符，行尾型也不需要换行符来结束，因此可以直接简化到自环，不必再写出 Kleene 星号。

   

3. DFA

   由上图已经可以清晰地看到对于注释扫描来说，输入字符只有 3 类：

   | 字符 | 代号 | 列号 |
   | :–: | :–: | :–: |
   | / | / | 0 |
   | | | 1 |
   | 其他 | e | 2 |

   因此可以简化 DFA，主要操作就是：

   • 消除 ε 转换的歧义性；
   • 消除相同符号的歧义性；

   转化后如图：

   

4. 编写代码

   // ------ //  /  *  e    //
   listOf(listOf(2, 0, 0),  // 1 -> ε
          listOf(3, 4, 0),  // 2 -> /
          listOf(3, 3, 3),  // 3 -> // ...
          listOf(6, 5, 6),  // 4 -> /*
          listOf(7, 5, 6),  // 5 -> /* ... *
          listOf(6, 5, 6),  // 6 -> /* ...
          listOf(0, 0, 0)), // 7 -> /* ... */
   setOf(5, 7),
   { c: Char ->
       when (c) {
           '/'  -> 0
           '*'  -> 1
           else -> 2
       }
   }

数字扫描器

如图：

• NFA

  

• DFA