词法分析

词法分析是编译器前段的第一个阶段，它将源代码按照一定的规则分割为记号流，然后传递给语法分析器进行下一步处理。在词法分析中，需要记录下源代码的信息，以供后续阶段使用。

词法分析有ad-hoc和自动机识别两种方式。自动机识别时，需要手工构造正则表达式并输入自动机，然后自动机根据正则表达式生成NFA。直接解析NFA开销过大，所以需要把NFA转化成为DFA。这时候得到的DFA有许多可以精简的状态，所以可以做DFA最小化，然后得到最小的DFA。这样自动机就可以自动识别并返回记号。

正则表达式到 NFA

正则表达式到 NFA 有 McMaughton-Yamada-Thompson 算法，涉及到贴图原因，这里就不讲了。

从 NFA 到 DFA 的转换

由于 NFA 对于一个输入符号可以选择不同的转换，它还可以执行输入上的 ε 转换，所以直接对 NFA 进行模拟不方便，需要转换成 DFA。NFA 到 DFA 可以由子集构造法（subset construction）构造。

输入：一个 NFA N; 输出：一个 DFA D; 方法：该算法为 D 构造一个转换表 Dtran。D 的每一个状态是 NFA 中状态的集合。在该算法之前需要引入如下几个操作：

ε-closure(s) 	能够从 NFA 的 s 状态只通过 ε 转换到达的状态集合；
ε-closure(T)	能够从 T 中某个 NFA 状态 s 开始，只通过 ε 转换达到的状态集合；
move(T, a)		能够从 T 中某个状态 s 出发通过标号为 a 的转换到达的 NFA 状态的集合；

该算法有一个记录新产生的 D 的状态的表：Dstates，在算法开始时，为 ε-closure(s) 产生一个状态做为起始状态。将起始状态放入工作列表。对于工作列表中的状态 T ，找出任意输入 a 能到达的集合 C = move(T, a) ，求得 C 对应的状态 ε-closure(C)，如果 ε-closure(T) 状态没有包含在 Dstates 中，则创建一个新状态并加入工作列表。最后将 Dtran[T, a] = C。

该算法伪代码如下：

A = ε-closure(s0);
Dstate.insert(A);
queue.push(A);
while (!queue.empty()) {
	T = queue.front(); queue.pop();
	for (auto i : input) {
		C = ε-closure(move(T, i));
		if (Dstate.count(C) == 0) {
			Dstate.insert(C);
		}
		Dtran[T][i] = C;
	}
}
return Dtran;

其中的 ε-closure(T) 可以通过下面的代码得到

ε-closure(T) {
	stack.push(T.states);
	res = null;
	while (!stack.empty()) {
		s = stack.pop();
		for (auto i : 所有NFA状态) {
			if (s 有一条 ε 转换到 i && res.count(i) == 0) {
				res.insert(i);
				stack.push(i);
			}
		}
	}
	return res;
}

DFA 状态最小化

对于一个NFA，当把它确定化之后，得到的DFA所具有的状态数可能并不是最小的。其原因之一，就在于上面所给出的确定化算法没有考虑到DFA中具有某种“同一性“的一些状态可加以合并的问题。所谓一个DFA M状态数的最小化，是指构造一个等价的DFA M′，而后者有最小的状态数。所谓状态数最小，指的是对于原来状态中任意两个状态，能被划分到一组当且仅当对于所有输入，这两个状态都到达同一个组，这样所得到的分组组成的状态，即状态数最小化。

现在，让我们来看一下简单的 Hopcroft 算法：

// 基于等价类的思想
split(S) 
	foreach (character c) 
		if (c can split S)
			split S into T1, ..., TK

hopcroft() 
	split all nodes into N, A
	while (set is still changes) 
		split(all S)

c can split S 的意思是如果 S 集合中存在两个状态可以通过 c 转移到不同的目标状态，那么就是可以切分（split）的。而一开始的 split 的目的是将一般状态和接受状态，这样做的目的是为了保证最后切分完成后，不存在任意一个由接受状态和一般状态组成的状态（因为这样就不知道这里是不是该接受）。

DFA 模拟

输入：一个以eof结尾的字符串x，DFA 的开始状态为 s0 ，接受状态为 F ，转换函数为 move; 输出：如果 D 接受 x ，返回 yes，否则返回 No；方法：对于每一个输入字符 c ，当前状态的值 s 由状态 move 函数得到，直到文件尾。如果 s 在 F 中，则返回 yes，否则返回 no ；

算法伪代码如下：

s = s0;
c = nextChar();
while (c != eof) {
	s = move(s, c);
	c = nextChar();
}
if (F.contain(s)) 
	return "yes";
else 
	return "no";

因为这里得到的 DFA 其实就是一个有向图，所以程序可以使用有向图表示方式来表示 move 。

实践

在实践中，需要处理标识符、关键字、字符串常量等进行特殊处理。关键字有多种表示方法，可以硬编码到 TOKEN 中，如 TOKEN_IF ，也可以当作标识符处理，也就是说，当词法分析器分析出标识符后，与已知的关键字进行比较，从而区分关键字和标识符。

在这里我采用单独编码关键字部分，那么Token部分设计就分为Kind、Keyword:

public enum Keyword {
	KEYWORD_ELSE, 		// "else"
	KEYWORD_IF, 		// "if"
	KEYWORD_RETURN, 	// "return"
	KEYWORD_WHILE, 		// "while"
	KEYWORD_BREAK,		// "break"
	KEYWORD_CONTINUE,	// "continue"
	KEYWORD_FUNCTION,
	KEYWORD_VAR,		// var
}

public enum Kind {
	TOKEN_ADD, 		// "+"
	TOKEN_DIV,		// /
	TOKEN_MOD,		// %
	TOKEN_AND, 		// "&&"
	TOKEN_OR,		// ||
	TOKEN_ASSIGN, 	// "="
	TOKEN_EQ,		// "eq"
	TOKEN_COMMER, 	// ","
	TOKEN_DOT, 		// "."
	TOKEN_EOF, 		// EOF
	TOKEN_ID, 		// Identifier
	TOKEN_LBRACE, 	// "{"
	TOKEN_LBRACK, 	// "["
	TOKEN_LPAREN, 	// "("
	TOKEN_LT, 		// "<"
	TOKEN_GT,		// ">"
	TOKEN_LEQT,		// "<="
	TOKEN_GEQT,		// ">="
	TOKEN_NOT, 		// "!"
	TOKEN_NUM, 		// IntegerLiteral
	TOKEN_FLOAT,	// float literal
	TOKEN_RBRACE, 	// "}"
	TOKEN_RBRACK, 	// "]"
	TOKEN_RPAREN, 	// ")"
	TOKEN_SEMI, 	// ";"
	TOKEN_SUB, 		// "-"
	TOKEN_TIMES, 	// "*"
	TOKEN_KEYWORD,	// 
	TOKEN_CHAR,
	TOKEN_STRING,
}

Token部分需要记录相关信息：

public class Token {
	public Kind kind; 		
	public Keyword keyword;
	public char c;
	public Integer num;
	public Float fnum;
	public String lexeme; 	
	public Integer lineNum;
	public Integer col;
}

当然，这样设计肯定不合理的，考虑到这部分内容更多是为了完成，就采取这种编码方式更少的了。

在lexer中，主要采用ad-hoc，即手工编写：

	switch (c) {
	case '%':
		kind = Kind.TOKEN_MOD;
		break;
	case '+':
		kind = Kind.TOKEN_ADD;
		break;
	case '-':
		kind = Kind.TOKEN_SUB;
		break;
	...
	}

这里对数据的处理方式肯定是不对的，要使用String table才是好办法。

string table

字符串比较耗时比较大，并且代码中标识符重用率也比较多，所以可以使用 string table 来记录出现过的标识符，这样不仅省了空间，在判断是否相等时的时间开销也降低了。

比较简单的实现方式是对每个标识符进行 hash ，然后将每个 hash 值放入一个桶中进行分类。每次插入的时候就在桶中进行匹配，没有找到则插入，否则返回原来实例的索引即可。