Lexer

發表於   |   分類於

前面

说起来，我的这些个总结如果放到简历上给人看，大概会堵了不少实习机会吧，毕竟个人痕迹以及倾向表现的太重……

总结一下之前在编译课程上学到的东西，能写多少写多少吧，能代码示例就用代码示例，理论大部分人不喜欢，我也不喜欢，况且前面文里也有提到学到的编译理论大部分都还给老师去了。其实我倒是觉得把个编译搞得让人觉得索然无味大部分时候都是理论太多，讲了也不知道能干嘛……

就从词法分析开始吧。

正文

Lexer的主要目的是将源代码文件切割成一个个的词素（lexeme），然后这些词素与其代表的类型、所在行号、列号等一系列属性组成一个记号（Token），以得到一个Token Stream来供语法分析使用。相对来Lexer说还是比较容易理解与实现的，至少比LR分析要好理解。

呃，概念性的东西就不多讲了，举个例子：

1
while (result) { print ("Hello"); }

上面的一句代码可以切分由下列Token组成：

1
2
3
4
5
6
7
8
9
10
11
while  -> 关键字while，第0行，第0列
(      -> 左小括号，第0行，第6列
result -> 标识符，第0行，第7列
)      -> 右小括号，第0行，第13列
{      -> 左大括号，第0行，第15列
print  -> 函数名，实际上也是标识符，第0行，第17列
(      -> 左小括号，第0行，第24列
"Hello"-> 字符串，第0行，第25列
)      -> 右小括号，第0行，第32列
;      -> 分号，第0行，第33列
}      -> 右大括号，第0行，第35列

可以看到空格是被略去了的。事实上，词法分析在进行分析的时候是将空格以及Tab都过滤掉了，当然还有换行。

假定我们要实现一个类似于“C”的脚本语言，它的Tokens的类型包含：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
enum TokenCode
{
  TK_START, // 解析开始
  TK_PLUS, TK_MINUS,T K_MUL, TK_DIV,T K_MOD, // + - * / %
  TK_GT, TK_LT, TK_EQUAL, TK_LQ, TK_GQ, TK_NEQ, // > < ==  <= >= !=
  TK_ASSIGN, TK_DOT, // = .(成员运算符)
  TK_AND, TK_OR, // && ||
  TK_OPENPA, TK_CLOSEPA, TK_OPENBRKT, TK_CLOSEBKT, TK_OPENBRE, TK_CLOSEBRE, // ( ) [ ] { }
  TK_SEMI, TK_COMMA, // ; ,
  TK_INT, TK_FLT, TK_STRING, // int float string
  TK_CSTR, TK_CLASS, TK_FUNC, // 常量字符串 class func
  TK_WHILE, TK_CONTINUE, TK_BREAK, // while continue break
  TK_IF, TK_IFELSE, TK_ELSE, // if ifelse else
  TK_RETURN, // return
  TK_POINTER, //  ->
  TK_LIST, // list
  TK_IDENT, // 标识符
  TK_EOF, // end of file
  TK_SELF, // self
};

然后是Token的结构：

1
2
3
4
5
6
struct Token
{
  string m_lexeme;
  int m_lineNum;
  int m_tkCode;
};

注意，为了集中说明词法分析，这里暂且不引入符号表，只需要暂时先保留这个概念即可：标识符在语法分析阶段是要到符号表中进行查找的，并且符号表在链接阶段也是一个核心数据结构。另外标识符有时候可能是一个结构体或者一个函数，此时还需要一个指向表示标识符类型的指针。这些都将会在语法、语义分析的时候使用到。

Lexer的实现

直观上看，Lexer其实就是一个字符一个字符，同类型的Token下按照最长读取原则来进行读取到一个Stack中，当Token类型发生改变的时候将Stack中的所有字符拿出来与关键字进行比较以确定结果标识符还是关键字。

基于以上描述，我们就有了一个简单实用的实现方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
int curCode = TK_START;
char* stream = srcFile;
char curChar = *stream;
char charStack[MAX_ID_LEN];
int stackTop = -1;
vector<Token> tokens;
while(true)
{
  if (curCode == TK_START)
  {
    if (isAlpha(curChar) )
    {
      Token* tk = readId(stream,charStack,stackTop,tokens);
      isKeyWord(tk);
    }
    else if (isNumber(curChar))
    {
      Token* tk = readNumber(stream,charStack,stackTop,tokens)
    }
    ...
    else if(isEOF(curChar))
    {
      break;
    }
  }
}

在此方法中，对于ifqwe这样的串一定不能在读到if之后就去与关键字比较，这样得到的结果是错误的，所以在readId处理之后再去判断它是不是关键字。

貌似没看到状态机？实际上状态机已经是有了的：对于ifqwe[2]这样的串，很显然readId在读到[的时候已经可以意识到标识符已经读完了，此时就可以切换curCode为初始状态再进行读取。

然而上述方法需要进行字符串的比较，即便是采用了HashTable，其时间耗费也是在O(N)+的。为了提高效率，我们自然是想要一个O(N)的解决方案。

这个方案需要使用到字典树，在前面基于状态的编程一文中已经介绍过了。相比前面一种方法，该方法在编码上要稍微麻烦一些——要多维护一棵树，而且空间耗费也多起来了，并且有一些注意事项（至少是在我编码的时候出现过的）：在构建字典树的时候，对于具有共同前缀的关键字，例如：if与ifelse，最好先构建if的路径，再构建ifelse的路径。因为先构建if，那么i->f需要首先设置f后面的所有指针都是空的，接下来的if->else直接把代表e的槽覆盖掉就可以了；而如果先处理ifelse，那么在处理if的时候就要小心，不要将已经建好的路径破坏掉了（如果按照i->f->结束，无匹配，i->f->else的路径就会断掉）。

结束

关于Lexer的实现，我知道的也就是前面的两种方案，其中第一种方案易于编码，简单直观，第二种则需要稍微花点心思。就我看过的一些资料而言，方案一用得更多一些（当然这些都只是教材，而并非商业级的东西，然而貌似Lua的Lexer也是采用第一种方案的），我自己两种方案都使用过，也踩过一些坑，上面也已经提到过了。总的来讲实现一个玩具级的Lexer并非一个难事。

最后说一下语法高亮（Syntax Lighting）的问题。

实际上语法高亮并不会涉及到语法分析跟语义分析，只需要词法分析就够了，唯一的要点在于采用语法分析的程序需要编辑器能够嵌入一个实时词法分析引擎，并进行字体渲染的工作，输入自动补完同样是这个要求。当然如果是要用Pretty Print进行重新排版，那么除了词法分析器，还需要用到语法分析（之前做Pretty Print的时候用到了语法分析，因此不确定只用词法分析是否可以做到，不过感觉有点悬）。

补充：

花了差不多一天时间为本文写了对应的代码，按照第一种方式写的。时间仓促，一定有考虑不周的地方，比如一些各种错误处理等。代码（VS2015通过，使用到了Win32的API）可以在这里找到。附上截图：

这是要解析的代码：

code1

这是词法分析的结果：

result01
result02

重新打印后的代码高亮效果:

snytaxlighting