army8735

有穷自动机（状态图）

处理词法分析的关键在于建立正确的DFA（确定的有穷自动机），而DFA是如何由NFA（不确定的有穷自动机）构造而来，NFA又是如何从正则表达式演变，不在本文讨论范围之内。我们只需要关心如何去画好这个状态图就行了。

先从最简单的开始。现在来了一串源码，我们的解析器想要识别出关键字if，那么该怎么办呢？下面是它的状态图：

我们把每个圈称作一个状态，圈内的数字用以标识不同的状态，而双边的圈则是终结状态。这个状态图没画完，因为状态4和状态5不是终结状态，却没有转换规则。这不是主要讨论。

一般情况下，状态0被称之为初始状态。解析器会设置一个向前看的哨兵，从左到右遍历源码。假设当前字符是i，很显然，它就是状态0可接受的唯一字符。于是开始执行转换规则，状态0根据规则转换到状态1，继续读入下一个字符。

状态1可接受的字符有2种：f和other。这里other不是说字符串，而是指除f以外的所有字符。假如是other的情况，显然它不是我们想要的关键字if，所以转而进入状态4，进行其它处理——至于处理什么、如何处理，暂时不需要关心，后面会说到；而如果是字符f，这就符合我们的预期，状态1通过规则转换到状态2。

可能你认为已经结束了，但事实并非这么简单。if两个字母是读出了，但却未必是关键字，后面如果跟着一个字母s呢？ifs，它可能是定义的一个变量名，又可能是个方法名。然而不管是什么，总归不是关键字。所以状态2接受2种字符：数字、字母、下划线（js应该还有美元符号$，因为它也可作为变量名组成），这条路通往状态5，我们不管；其它的情况就好办了，空白也好回车也好括号也好，它一定是if关键字，由此进入状态3。

上面说了两个圈儿的是终结状态，识别出if关键字后，状态3就结束了。此时解析器会进行回退，把if后面读入的向前看字符放回源码流中，继续下一次循环。经过这一轮番的解释，相信你能对词法分析有了大概的印象吧。同理，其它的关键字、数字、字符串、注释……也是如此识别的。

或许有人要问：一种语言的关键字那么多，为每个关键字写处理程序岂不是要累死？没错，事实上编译器也不会这样做。上面那个例子只是为了简单起见所举，真正可行的办法是只建立标识符的DFA，将所有标识符识别出来，然后一一对比，看此标识符是否是个关键字。

识别标识符

这是识别js语言标识符的状态图。不难看出，状态3和4都是可能的终结状态（实际上基于最小化DFA数量的原则，它们应该被合并为一个）。在初始状态0时，接受字母、下划线和美元符号，如果读入的向前看字符是的话，那么进入状态1。

状态1接受2种情况：字母、数字、下划线和美元符号，很明显这是js标识符的组成规定。这种情况下会进入状态2，并且状态2也接受同样的情况返回本身状态（标识符的长度是不定的，因此状态2会循环本身），它上面的弧线即表达了这个意思。只有当状态2时读入的向前看字符不是字母、数字、下划线或美元符号任一种的时候，才会进入终结状态3。此时这个标识符也识别出来了，和前面一样，回退继续处理。

状态1还有个接受other的情况，这是当标识符仅由一个字符组成时才会发生的。

以下是jssc中处理ecmascript语言中标识符的源代码：

protected function dealWord():void {
	var start:int = index - 1;
	var cc:int;
	//直到不是字母数字下划线美元符号为止
	while (index <= code.length) {
		readch();
		cc = peek.charCodeAt(0);
		if (Character.isLetterOrDigit(cc) || Character.isUnderline(cc) || Character.isDollar(cc)) {
			//
		}
		else {
			break;
		}
	}
	//高亮
	var res:String = code.slice(start, index - 1);
	if (words.hasKey(res)) {
		res = HighLighter.keyword(res);
	}
	result.append(res);
}

由于语法高亮毕竟还是有别于编译器的词法处理，所以为了简化功能和提高性能，很多地方还是不一样的。比如说上面代码中的index是个int型索引，用以保存向前看字符的下标，而peek则是当前的向前看字符。start保存着状态0时向前看字符的位置。循环体中不停地读入下一个字符（readch()方法），直到不是字母、数字、下划线或美元符号为止——这就是所谓的进入终结状态3——然后截取代码中从start到当前索引的代码。

之后的高亮处理先检查这段代码是否是保留字（words是个HashMap，预先保存着所有关键字），是的话高亮上颜色，不是则原封不动。

识别字符串

字符串的处理相对简单一些。js中单引号和双引号作用完全一样，所以用双引号来举例足够了。初始状态0，遇到引号后进入状态1。

在状态1中稍微有点绕人，如果遇到另外一个引号，那么自然这个字符串就结束了，进入终结状态2。但是要预防引号被转义的情况出现，所以当读到的向前看字符是\时，我们进入状态4，接着读入的任何字符都是被转义掉的，再返回状态1。最后需要注意的是弧线other，它依然回到状态1自己，这样就处理了不定长度的字符串格式。

插嘴一句：在windows的IE中，字符串跨行时所出现的可能不是标准的\n，而是\r\n，这在处理过程中会遇到麻烦。jssc 5对其多添加了一个状态来区分，但是更好的做法应该是在开头就把所有\r过滤掉。这可能稍微影响一点点性能。

//字符串处理，单引号或多引号、是否允许转义折行
protected function dealString(char:String = "\"", wrap:Boolean = false):void {
	var start:int = index - 1;
	var cc:int;
	while (index <= code.length) {
		readch();
		cc = peek.charCodeAt(0);
		//转义符
		if (Character.isBackslash(cc)) {
			readch();
			//转义符后是回车继续读入下一个
			if (Character.isEnter(peek.charCodeAt(0))) {
				readch();
			}
			//不允许转义换行跳出
			if (!wrap && Character.isLine(peek.charCodeAt(0))) {
				break;
			}
		}
		//行末尾未转义换行或找到结束跳出
		else if (Character.isLine(cc) || char == peek) {
			break;
		}
	}
	//高亮
	result.append(HighLighter.string(HtmlEscape.encode(code.slice(start, index), HighLighter.endTag + getNewLine() + HighLighter.stringStart())));
	readch();
}

我想它很明了，无需多做解释。只是要注意最后高亮步骤中要将换行符给替换掉，变成html可显示的换行。

识别注释

本来注释在词法分析中是被扔掉的部分，但在语法高亮中却不能这样做。注释的识别和字符串一样简单：多行注释和字符串类似，以/*开头，*/结尾，它让人省心的地方就是不存在转义问题；而单行注释也一样，//开头直接到行末尾。这里直接附上源码，状态图就懒地画了。

//处理单行注释
protected function dealSingleComment():void {
	var i:int = code.indexOf("\n", index);
	index -= 2;
	//找不到换行符说明是最后一行
	if (i == -1) {
		i = code.length;
	}
	//本行存入
	result.append(HighLighter.comment(HtmlEscape.encode(code.slice(index, i))));
	index = i;
	readch();
}
//处理多行注释
protected function dealMultiComment():void {
	depth++;
	var i:int = code.indexOf("*/", index);
	index -= 2;
	//i为-1时直接注释到结尾
	if (i == -1) {
		i = code.length;
	}
	else {
		i += 2;
	}
	result.append(HighLighter.comment(HtmlEscape.encode(code.slice(index, i), HighLighter.endTag + getNewLine() + HighLighter.commentStart())));
	//调整索引和深度，并读取当前peek
	index = i;
	depth--;
	readch();
}

识别数字

数字可能是最难处理的部分之一了，因为它包含小数。理想的方式是将整数和小数分开处理，jssc 5选择了比较复杂的方式——统一对待。不仅如此，我抽象出来一个方法，用它来尽可能地处理所有语言的数字。在java中，长整型可以以L结尾，浮点型可以以D或F结尾。这个问题想要统一解决也是相当得麻烦，所以建议大家不要像我一样，为节省并不起眼的程序大小而导致维护困难。

这是十进制数字的状态图，而js语言中E后面的+号还可以省略，这点需要额外注意（图上并没有显示出来）。下面是源码：

//处理数字
protected function dealNumber():void {
	var cc:int = peek.charCodeAt(0);
	var start:int = index - 1, i:int = 0;
	var res:String;
	//以0开头需判断是否16进制
	if (Character.isZero(cc)) {
		readch();
		cc = peek.charCodeAt(0);
		//0后面是x或者X为16进制
		if (Character.isX(cc)) {
			readch();
			//寻找第一个非16进制字符，同时最大长度不能超过6（不包括开头的0x）
			for ( ; i < 6 && index < code.length; i++) {
				if (!Character.isDigit16(peek.charCodeAt(0))) {
					break;
				}
				readch();
			}
			//高亮
			result.append(HighLighter.number(code.slice(start, index - 1)));
			return;
		}
		//其它非数字退出且不是小数点
		else if (!Character.isDigit(cc) && !Character.isDecimal(cc)) {
			result.append(HighLighter.number("0"));
			return;
		}
	}
	//先处理整数部分
	while (Character.isDigit(peek.charCodeAt(0))) {
		readch();
	}
	cc = peek.charCodeAt(0);
	//整数后可能跟的类型L字母
	if (Character.isLong(cc)) {
		result.append(HighLighter.number(code.slice(start, index)));
		readch();
		return;
	}
	//小数部分
	else if (Character.isDecimal(cc)) {
		readch();
		while (Character.isDigit(peek.charCodeAt(0))) {
			readch();
		}
		//小数后可能跟的类型字母D、F
		if (Character.isFloat(peek.charCodeAt(0))) {
			readch();
			res = code.slice(start, index - 1);
			//防止.f出现
			if (res.length > 2) {
				res = HighLighter.number(res);
			}
			result.append(res);
			return;
		}
	}
	cc = peek.charCodeAt(0);
	//指数E
	if (Character.isExponent(peek.charCodeAt(0))) {
		readch();
		cc = peek.charCodeAt(0);
		//+-号
		if (Character.isAdd(cc) || Character.isMinus(cc)) {
			readch();
		}
		//指数后面的数字
		while (Character.isDigit(peek.charCodeAt(0))) {
			readch();
		}
	}
	//高亮
	res = code.slice(start, index - 1);
	//防止.e之类的出现，即第一个字符是小数点的情况下判断第二个字符是否非数字
	if (!Character.isDecimal(res.charCodeAt(0)) && !Character.isLetter(res.charCodeAt(1))) {
		res = HighLighter.number(res);
	}
	result.append(res);
}

其它

空白符的处理没什么难度，它不需要被高亮。而js中处理折叠主要是针对符号{和}。我设置了一个叫做depth的变量，用以保存深度（使用firebug的用户可以看到代码行li节点上的name属性，那就是深度变量）。每当遇到{时深度自增；而遇到}时深度自减。这样就做到了折叠功能——点击每行向下遍历，折叠掉深度比它大的行，遇到相等或小于的时候中断遍历。

至于难点中的难点——区分除号和正则，以及正则的状态图处理，这是下一篇要重点讲述的地方。