web端语法高亮原理:走进jssc的世界(二)

2009-11-07 10:45 | Army

原文见:http://www.army8735.org/2009/11/06/329.html,这里贴不出来格式。

有穷自动机(状态图)

处理词法分析的关键在于建立正确的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语言中标识符的源代码:

as 代码
关于

1. protected function dealWord():void {
2. var start:int = index - 1;
3. var cc:int;
4. //直到不是字母数字下划线美元符号为止
5. while (index <= code.length) {
6. readch();
7. cc = peek.charCodeAt(0);
8. if (Character.isLetterOrDigit(cc) || Character.isUnderline(cc) || Character.isDollar(cc)) {
9. //
10. }
11. else {
12. break;
13. }
14. }
15. //高亮
16. var res:String = code.slice(start, index - 1);
17. if (words.hasKey(res)) {
18. res = HighLighter.keyword(res);
19. }
20. result.append(res);
21. }

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过滤掉。这可能稍微影响一点点性能。

as 代码
关于

1. //字符串处理,单引号或多引号、是否允许转义折行
2. protected function dealString(char:String = "\"", wrap:Boolean = false):void {
3. var start:int = index - 1;
4. var cc:int;
5. while (index <= code.length) {
6. readch();
7. cc = peek.charCodeAt(0);
8. //转义符
9. if (Character.isBackslash(cc)) {
10. readch();
11. //转义符后是回车继续读入下一个
12. if (Character.isEnter(peek.charCodeAt(0))) {
13. readch();
14. }
15. //不允许转义换行跳出
16. if (!wrap && Character.isLine(peek.charCodeAt(0))) {
17. break;
18. }
19. }
20. //行末尾未转义换行或找到结束跳出
21. else if (Character.isLine(cc) || char == peek) {
22. break;
23. }
24. }
25. //高亮
26. result.append(HighLighter.string(HtmlEscape.encode(code.slice(start, index), HighLighter.endTag + getNewLine() + HighLighter.stringStart())));
27. readch();
28. }

//字符串处理,单引号或多引号、是否允许转义折行
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可显示的换行。
识别注释

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

as 代码
关于

1. //处理单行注释
2. protected function dealSingleComment():void {
3. var i:int = code.indexOf("\n", index);
4. index -= 2;
5. //找不到换行符说明是最后一行
6. if (i == -1) {
7. i = code.length;
8. }
9. //本行存入
10. result.append(HighLighter.comment(HtmlEscape.encode(code.slice(index, i))));
11. index = i;
12. readch();
13. }
14. //处理多行注释
15. protected function dealMultiComment():void {
16. depth++;
17. var i:int = code.indexOf("*/", index);
18. index -= 2;
19. //i为-1时直接注释到结尾
20. if (i == -1) {
21. i = code.length;
22. }
23. else {
24. i += 2;
25. }
26. result.append(HighLighter.comment(HtmlEscape.encode(code.slice(index, i), HighLighter.endTag + getNewLine() + HighLighter.commentStart())));
27. //调整索引和深度,并读取当前peek
28. index = i;
29. depth--;
30. readch();
31. }

//处理单行注释
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结尾。这个问题想要统一解决也是相当得麻烦,所以建议大家不要像我一样,为节省并不起眼的程序大小而导致维护困难。

数字的状态图我也不画了,网上随便搜搜都能找到,直接上源码。

as 代码
关于

1. //处理数字
2. protected function dealNumber():void {
3. var cc:int = peek.charCodeAt(0);
4. var start:int = index - 1, i:int = 0;
5. var res:String;
6. //以0开头需判断是否16进制
7. if (Character.isZero(cc)) {
8. readch();
9. cc = peek.charCodeAt(0);
10. //0后面是x或者X为16进制
11. if (Character.isX(cc)) {
12. readch();
13. //寻找第一个非16进制字符,同时最大长度不能超过6(不包括开头的0x)
14. for ( ; i < 6 && index < code.length; i++) {
15. if (!Character.isDigit16(peek.charCodeAt(0))) {
16. break;
17. }
18. readch();
19. }
20. //高亮
21. result.append(HighLighter.number(code.slice(start, index - 1)));
22. return;
23. }
24. //其它非数字退出且不是小数点
25. else if (!Character.isDigit(cc) && !Character.isDecimal(cc)) {
26. result.append(HighLighter.number("0"));
27. return;
28. }
29. }
30. //先处理整数部分
31. while (Character.isDigit(peek.charCodeAt(0))) {
32. readch();
33. }
34. cc = peek.charCodeAt(0);
35. //整数后可能跟的类型L字母
36. if (Character.isLong(cc)) {
37. result.append(HighLighter.number(code.slice(start, index)));
38. readch();
39. return;
40. }
41. //小数部分
42. else if (Character.isDecimal(cc)) {
43. readch();
44. while (Character.isDigit(peek.charCodeAt(0))) {
45. readch();
46. }
47. //小数后可能跟的类型字母D、F
48. if (Character.isFloat(peek.charCodeAt(0))) {
49. readch();
50. res = code.slice(start, index - 1);
51. //防止.f出现
52. if (res.length > 2) {
53. res = HighLighter.number(res);
54. }
55. result.append(res);
56. return;
57. }
58. }
59. cc = peek.charCodeAt(0);
60. //指数E
61. if (Character.isExponent(peek.charCodeAt(0))) {
62. readch();
63. cc = peek.charCodeAt(0);
64. //+-号
65. if (Character.isAdd(cc) || Character.isMinus(cc)) {
66. readch();
67. }
68. //指数后面的数字
69. while (Character.isDigit(peek.charCodeAt(0))) {
70. readch();
71. }
72. }
73. //高亮
74. res = code.slice(start, index - 1);
75. //防止.e之类的出现,即第一个字符是小数点的情况下判断第二个字符是否非数字
76. if (!Character.isDecimal(res.charCodeAt(0)) && !Character.isLetter(res.charCodeAt(1))) {
77. res = HighLighter.number(res);
78. }
79. result.append(res);
80. }

//处理数字
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属性,那就是深度变量)。每当遇到{时深度自增;而遇到}时深度自减。这样就做到了折叠功能——点击每行向下遍历,折叠掉深度比它大的行,遇到相等或小于的时候中断遍历。

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