从零开始编写 C 编译器 Chapter 1.1 | Lexer

Note: 所有代码、定义、术语命名都参考 Nora Sandler 的书籍 Write a C Compiler

Lexer

Lexer 读取源代码文件，将其转换为 有序的 token 列表。由于 C 语言语义不依赖缩进，所以我们不用将 空白字符(whitespace) 视为 token，但在 python 中需要维护。

对于上篇中提到的最简 C 程序，它的 token 列表应该长这样：

Token	Description
int	A Keyword
main	An identifier, whose value is "main"
(	An open parenthesis
void	A keyword
)	A close parenthesis
{	An open brace
return	A keyword
2	A constant, whose value is “2”
;	A semicolon
}	A close brace

术语 identifier 表示由 ASCII 字母或下划线开头，后接任意数量字母、下划线和数字组成的字符串。constant 表示由由一个或多个数字组成的字符串。identifier 和 constant 都需额外维护一个值，但其他类型不用，只用维护一个单独的符号。对于现在处理的程序，constant 中只可能出现一个 int 类型的常数。

上述 token 可以通过正则表达式来进行匹配，本文采用 PCRE 语法，所有 token 类型对应的 regex 见下表:

Token 类型	regex str
Identifier	[a-zA-Z_]\w*\b
Constant	[0-9]+\b
Int	int\b
Void	void\b
(	\(
)	\)
{	\{
}	\}
;	;

所有 identifier、constant、keyword 必须以单词边界(结束；即 123; 是合法常量，因为以非字符 \w 结束。但 123bar 非法：123和bar没有通过单词边界分割，应当视为一个 token，但 identifier 不能以数字开头，Constant 中不能出现字母。即无法找到一条规则进行匹配。

上述就是所有目前需要了解的 token 知识点，接下来我们开始实现一个最简 Lexer。伪代码如下：

while input isn't empty:
    if input starts with whitespace:
        trim whitespace from start of input
    else:
        find longest match at start of input for any regex in Table 1-1
        if no match is found 
            raise an error
        else 
            convert matching substring into a token
            remove matching substring from start of input

大概流程就是删除开头的空格，在所有的正则模式中进行匹配，找到最长匹配开头的规则。如果没找到则报错，找到了则转换为 Token.t，将其插入 token 列表，删除子串，并进行下一次匹配。

首先我们定义 token type，一个枚举体完事(ocaml 中的枚举体可以额外携带一个任意类型的值。cpp 中可以定义一个 map 来进行 Token.t 到 value 的映射)：

type t = 
  (* tokens with contents *)
  | Identifier of string
  | Constant of int
  (* Keywords *)
  | KWInt
  | KWReturn
  | KWVoid
  (* punctuation *)
  | OpenParen
  | CloseParen
  | OpenBrace
  | CloseBrace
  | Semicolon

之后定义匹配模式，这里使用一个 List 来维护，这样后续遍历该 List 即可。添加 ANCHORED 来进行限制，使得只能从字符串开头进行匹配。 ocaml 没有内置的正则匹配引擎，我们使用 ocaml-re 库来进行匹配。

type match_rule = {
  re : Re.re; (* the regex string to match a token *)
  converter : string -> Tokens.t; 
  (* a handler which convert matched string to token *)
}

let generate_rule regex_str converter = 
  {re = Re.Pcre.regexp ~flags:[ `ANCHORED ] regex_str; converter}

let match_rules = 
  [
    generate_rule {_|[A-Za-z_][A-Za-z0-9_]*\b|_}  convert_identifier;
    generate_rule {_|[0-9]+\b|_}                  convert_constant;
    generate_rule {_|\(|_}                        (convert_literal T.OpenParen);
    generate_rule {_|\)|_}                        (convert_literal T.CloseParen);
    generate_rule {_|\{|_}                        (convert_literal T.OpenBrace);
    generate_rule {_|\}|_}                        (convert_literal T.CloseBrace);
    generate_rule ";"                             (convert_literal T.Semicolon);
  ]

对于每种模式，单独使用一个函数来进行 string -> Token.t 的转换，并将其绑定到 match_rule 的 converter 字段。

(* convert string to Tokens.t *)
(* tips 1: treat keywords like special identifiers *)
let convert_identifier = function
  | "int"     ->   T.KWInt
  | "return"  ->   T.KWReturn
  | "void"    ->   T.KWVoid
  | other     ->   T.Identifier other

(* convert string to int *)
let convert_constant str = 
  try T.Constant (int_of_string str)
  with Failure _ -> raise (LexError ("Invalid constant: " ^ str))

(* convert literal characters like "(" or ";" to Tokens.t *)
let convert_literal tok_type _ = tok_type

同时我们还需要维护一个当前字符串匹配成功的模式列表，单独使用一个结构体来存储 成功匹配的规则 和 成功匹配的子串 ：

type matched_string = {
  matched_rule : match_rule; (* which rule it matched *)
  matched_substring : string; (* substring matched with regex token_match.re *)
}

进行匹配的函数也很容易写。Re.exec_opt regex_str str 将主串str 根据 模式串regex_str 进行匹配，匹配成功返回一个列表 optione group，group 中存放所有匹配成功的子串。例如 Re.exec_opt "ABC" "ABC;ABC;ABC" 返回 ["ABC", "ABC", "ABC"]。 Lexer 中只需要第一个匹配成功的 token，所以通过 get 来获取第一个匹配成功的子串。匹配失败则产生一个 None。

let find_match s rule = 
  match Re.exec_opt rule.re s with
  | Some group ->
      let substr = Re.Group.get group 0 in
      Some { matched_substring = substr; matched_rule = rule}
  | None -> None

删除字符串前面的空格同样也可以使用正则表达式来完成，匹配模式串 \s+ 即可 。Re.exec_opt 返回的 group 可以通过 offset 获得成功匹配的子串对于串首的偏移量，丢掉这部分即可。

let count_leading_ws s = 
  let ws_re = Re.Pcre.regexp ~flags:[ `ANCHORED ] {|\s+|} in
  match Re.exec_opt ws_re s with
  | Some group -> 
      let _, end_pos = Re.Group.offset group 0 in
      Some end_pos
  | None -> None

之后就是主 Lexer 的逻辑了, 基本和伪代码的流程差不多。

let rec lexer input = 
  if input = "" then []
  else
    match count_leading_ws input with
    (* have whitespace front of input *)
    | Some end_pos -> lexer (StringUtil.drop end_pos input)
    | None ->
    (* match_result contains all matched_strings that matched succesfully *)
      let match_result = List.filter_map (find_match input) match_rules in
      match match_result with
      (* cannot match any pattern *)
      | [] -> raise (LexError 
        ("Unrecognized token at: " ^ String.sub input 0 (min 10 (String.length input))))
      | _ ->
          let longest = 
            List.fold_left
              (fun acc m -> if String.length m.matched_substring > String.length acc.matched_substring then m else acc)
              (List.hd match_result)
              (List.tl match_result)
          in
          let token = longest.matched_rule.converter longest.matched_substring in
          let remaining = StringUtil.drop (String.length longest.matched_substring)
            input in
          token :: (lexer remaining)

至此一个最简单的 Lexer 就写完了，后续会逐渐增加 token 的类型，最终支持整个 C 语言。在 github 仓库中我额外编写了一个 print_matches 来打印整个 token list。如果不出意外的话，对于本章的程序，应该输出如下东西：

./main.exe return_2.c --lex
Int 
Identifier 
Characters 
Void 
Characters 
Characters 
Return 
Constant 
Characters 
Characters

和 return_2.c 比较一下，可以看到正确生成了对应的 token list.

int main(void) {
	return 2;
}