从零开始的编译器前端之Lexer

这是第三篇文章，打算简单介绍一下Lexer的概念。跟之前的篇幅不同，这部分内容就完全是自己瞎弄出来的了。

不保证正确性但是应该也可以作为一种思路吧。

---

之前也提到过用token组合子来在Parsing过程中进行Tokenization的操作，如果遇到了注释，就会出现问题。像是//这样的注释，会从注释的起始位置一直延伸到行末，又比如/* ... */这样的注释需要一直延伸到*/为止，但是针对单个字符的组合子无法用来匹配长度为2的终结符号。如果用symbol来强行匹配的话会死循环。

卡在这里了……不过有句话是这么说的，没有什么是不能通过抽象解决的，如果不能解决，那就再加一层抽象。如果说组合子不能用在字符串上，那么预先对字符串进行处理，获得一系列token再去对这些token的流进行解析呢？

比如说a = "b" // xxx就可以转化为[Id "a", ASSIGN, Str "b"]（这里直接消除了注释），对于后者来说，组合子应该是可以无障碍地运作的。

这个对字符串进行预处理的过程，就叫Lexer，或者说Lexical analysis，意思是把一个字符串翻译成附加了语义的token的流。

Lexer的写法相比Parser其实原理要简单许多，基本上就是递归循环、模式匹配和字符串处理函数的组合。当然，在实际使用中会遇到各种特殊情况，也会让函数的实现变得更复杂。

首先定义Token的数据类型，基本上就是目标语言中会使用到的关键词、符号和变量常量的集合，或者说，语法里的终结符：

data Token = Numeric String
           | Str String
           | Chr Char
           | Ident String
           | Oper String -- 如果要允许设计自定义运算符的话，有必要用单独的符号来把这些运算符存起来，和普通的变量名区分开来
           | TRU | FLS
           | LPAREN | RPAREN | LBRACKET | RBRACKET 
           | COMMA | SEMI | ASSIGN ...

那么一个tokenize函数的构成基本上是这样的：

tokenize :: String -> [Token]
tokenize [] = []
tokenize ('/' : '*' : xs) = tokenize (drop 2 xs')
    where (_, xs') = matchUntil (isPrefixOf "*/")
tokenize ('/' : '/' : xs) = tokenize (drop 1 xs')
    where (_, xs') = matchUntil (isPrefixOf "\n")
tokenize ('(' : xs) = LPAREN : tokenize xs
tokenize (')' : xs) = RPAREN : tokenize xs
tokenize (',' : xs) = COMMA : tokenize xs
...
tokenize xs = error $ "unrecognized token: " ++ show xs

首先需要注意的是在模式匹配里面最先匹配的应该是更加特殊的字符，然后才是更通用的字符，例如先匹配"""，如果匹配不到再去匹配"。不然的话，这个特殊的分支就会被忽略掉了。

这里的matchUntil的作用是不断匹配当前字符串和回调函数是否对的上，如果对的上的时候停止匹配返回当前位置以前和以后的子串。简单的写一下就可以了。因为是字符串操作，然后整个tokenize函数是线性递归的，所以不会出现死循环的情况。这样一来，对注释的解析也就很简单了：一直匹配直到符合换行符或者注释结尾，然后切掉前面的部分。

matchUntil :: (String -> Bool) -> String -> (String, String)
matchUntil _ [] = ([], [])
matchUntil f b@(x:xs) = if f b
                 then ([], b)
                 else let (a', b') = matchUntil f xs
                      in (x:a', b')

同时也可以注意到，目前的tokenize函数的类型是String -> [Token]，如果把它改造成String -> Int -> Int -> [Token]，是不是就可以在解析过程中把token所在的行列位置存起来呢。

这样做的话首先需要改造一下Token的定义，原先的Token变成TokenType，另外新增Token数据结构：

data Token = Token {
    tokenType :: TokenType,
    line :: Int,
    pos :: Int
} deriving (Eq, Show)

然后把tokenize的每一行签名改为tokenize (...) r p = (Token TOKEN r p : tokenize xs r p)这样的形式。

空格可以用tokenize (x:xs) r p | isSpace x = tokenize xs r (p+1)来解决，对应的，换行可以用tokenize (x:xs) r p | x == '\n' = tokenize xs (r + 1) posBegin来定义。这里需要注意换行的匹配必须在空格前面，否则换行会当作空格来处理。

变量和关键词的解析可以通过另写一个函数来处理，例如这样：

matchCharacterizedToken :: String -> Int -> Int -> Token
matchCharacterizedToken "break" r p = Token BREAK r p
matchCharacterizedToken "case" r p = Token CASE r p
matchCharacterizedToken "continue" r p = Token CONTINUE r p
matchCharacterizedToken "default" r p = Token DEFAULT r p
matchCharacterizedToken "do" r p = Token DO r p
matchCharacterizedToken "else" r p = Token ELSE r p
...
matchCharacterizedToken s r p = Token (Ident s) r p

tokenize (x:xs) | isIdentHead x = matchCharacterizedToken (x : t) r p ++ tokenize xs' r (p + length t + 1)
    where (t, xs') = span isIdentChar xs

注意这里使用了span来处理字符串，从起始点开始向后贪婪地延伸直到不再匹配到属于关键词/变量名的字符，同时记下经过的字符长度。而matchCharacterizedToken本身只是去匹配一系列的预先设定的字符串看是否有属于其中的，这些是关键词。如果都不能匹配中，那么就是变量名。

通过这种方式去处理的话，也可以避免出现例如func和func1会相撞的情况。在一些Parser Generator例如ANTLR或者ocamllex里会出现如果定义了func作为关键词那么就不能以func1作变量名的情况，在这里因为匹配始终是贪婪的，所以不会发生。

对操作符的处理和变量名相似：先贪婪地匹配符合条件的字符，然后去做模式匹配，如果匹配中了某一预设规则就返回这个token，否则返回一个自定义操作符的token。

matchSymbolToken :: String -> TokenType
matchSymbolToken "=>" = ARROW
matchSymbolToken "=" = ASSIGN
matchSymbolToken "&" = AMP
matchSymbolToken "+" = ADD
matchSymbolToken "-" = SUB
matchSymbolToken "*" = MUL
matchSymbolToken "/" = DIV
matchSymbolToken "==" = EQU
matchSymbolToken "!=" = NEQU
...
matchSymbolToken x = Oper x

tokenize (x:xs) r p | isSymbolHead x = Token (matchSymbolToken (x:t)) r p : tokenize xs' r (p + length t + 1)
    where (t, xs') = 
        if x == '.' then span dotSymbolChar xs 
            else span isSymbolChar xs

值得注意的是span的匹配逻辑可以根据吃入的第一个字符的不同情况而不同。这样的话可以稍微提高语法的灵活度，比如说，在读到.的时候只匹配特定的字符，这样的事情。

多行字符串的处理其实就是简单的覆盖到"""之前，包括所有空格和换行符。一条matchUntil就足够了。这里假设多行字符串不需要做插值处理。

至于带有插值处理的单行字符串，需要做的其实就是把完整的字符串分割为不同的字符串片段，还有穿插其间的表达式片段。比如说"1 + 1 = \(1.plus(1))"就可以转换为[Str "1 + 1 = ", LINTR, Numeric "1", DOT, Ident "plus", LPAREN, Numeric "1", RPAREN, RINTR, Str ""]，这里的LINTR和RINTR就是字符串和表达式之间的分隔符。

用这样的思路就可以把表达式和字符串分隔开来，方便在Parser里进行处理。

我在实现自己的语言的时候，这部分的规则分为了两个部分，一部分放在tokenize里进行模式匹配，另一部分由parseSimpleString函数做预处理，简单说，预处理的内容是以"或者\作为起始点，处理反转义符，并且和tokenize联动进行字符串的解析：

• tokenize读到"，用parseSimpleString提取出直到"或者\(或\且并非转义作用的部分，生成一个Str Token，然后把剩下的部分喂给tokenize函数递归处理

  这里还需要记录括号的嵌套深度，以便在右侧进行校对

• tokenize做对表达式的模式匹配，直到吃到)的时候，判断括号数，如果为0则进入字符串模式，生成一个RINTR然后调用parseSimpleString提取出直到下一个"或者\(或者\的部分生成Str，然后再调用tokenize函数

• 以此类推

要数括号的话，就需要一个变量来存储当前有多少个右括号，但是，因为表达式里面可以有字符串，字符串里面也可以有表达式， 嵌套起来的话……所以用来存储左括号的需要是一个栈（aka List），这样的话，tokenize函数的签名就变成了tokenize :: String -> Int -> [Int] -> Int -> Int -> ([Token], Int, [Int])，同时也需要修改之前的模式匹配在读入左右括号的时候修改对应的变量。

由此也可以看到一个本来是很简单的函数可以因为实际需求而变得很复杂，当然，主要思路还是很简单的。

最后需要提到的部分是泛型标注符的解析，因为泛型的语法里面涉及到了左公共部分的问题。

也就是说，比如说func()和func<a, b>()，直接解析的话，会出现无法提取出<a, b>的问题，而把整个func<a, b>当作变量名去解析。

解决方法是在matchCharacterizedToken也就是处理变量名的地方开洞，首先把函数的返回值变成一个列表然后把之前的所有Token都返回为一个singleton list。然后利用span函数来提取出属于变量名字符的部分，对剩下的部分匹配<，>和,，去掉可能的空格，并且提取出不同的Ident Token。

matchCharacterizedToken s r p = Token (Ident name) r p: tokenizeClause clause r (p + length name)
    where (name, clause) = span isIdentChar s
          tokenizeClause "" r p = []
          tokenizeClause (' ':xs) r p = tokenizeClause xs r (p + 1)
          tokenizeClause ('<':xs) r p = Token GENERIC_LEFT r p : tokenizeClause xs r (p + 1)
          tokenizeClause ('>':xs) r p = Token GENERIC_RIGHT r p : tokenizeClause xs r (p + 1)
          tokenizeClause (',':xs) r p = Token COMMA r p : tokenizeClause xs r (p + 1)
          tokenizeClause xs@(x:_) r p | isIdentChar x = Token (Ident ax) r p : tokenizeClause bx r (p + length ax)
              where (ax, bx) = span isIdentChar xs
          tokenizeClause (x:_) _ _ = error $ "unexpected character: " ++ show x ++ " in generic clause at row " ++ show r ++ ", column " ++ show p ++ "."

第八行这里需要限定匹配的字符是变量名字符，否则如果进入的是其他字符，那么span会返回空字符串导致死循环。

仔细一看的话，其实相当于在matchCharacterizedToken里面写了个简单的tokenize函数。虽然可能不是很优雅，但是还是能用的。

Tokenizer可以写的很复杂，不过基本原理就是把裸字符串变成带有语义的token流，然后可能按照不同的需求去添加需要的附加信息。写起来也不复杂，主要就是依靠各种字符串操作（尤其是span）和模式匹配。

总之大概就是这样。