从零开始编写 C 编译器 Chapter 2.1 | Front End

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

Lexer

这部分没新增什么东西，只需要 \(3\) 个 token 类型即可。

字符序列	运算符名称	语义说明
~	Bitwise complement	按位取反
-	Negation	算数负号
--	Decrement	自减运算符

注意到我们新增了 -- 运算符的解析。这是因为目前编译器只支持常量，而 --2 这样的表达式是非法的，我们应在解析阶段报错。如果我们不解析 --，编译器会将 --2 识别为 -(-2) 造成语义上的错误。所以在 Lexer 阶段我们会解析 -- 运算符，但在后续阶段，我们会忽略它。

对应的正则表达式和上一章中的标点符号 ;, ( 一致，这里不做赘述。

Implementation

lib/token.ml:

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

lib/lexer.ml:

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);
    generate_rule "-" (convert_literal T.Hyphen);
    generate_rule "--" (convert_literal T.DoubleHyphen);
    generate_rule "~" (convert_literal T.Tilde);
  ]

Parser

更新新的 AST 定义：

program = Program(function_definition)
function_definition = Function(identifier name, statement body)
statement = Return(exp)
exp = Constant(int) | Unary(unary_operator, exp)
unary_operator = Complement | Negate

为 exp 新增了 Unary 的定义，表示一元操作表达式，由一个 unary-operator 和 exp 组成。 注意现在 exp 的定义是递归的：一个 Unary 内部可能包含另一个 exp。

新定义了 unary_operator 结点，值 Complement 对应 ~ 运算符，值 Negate 对应 - 运算符。

更新后的形式文法：

<program> ::= <function>
<function> ::= "int" <identifier> "(" "void" ")" "{" <statement> "}"
<statement> ::= "return" <exp> ";"
<exp> ::= <int> | <unop> <exp> | "(" <exp> ")"
<unop> ::= "-" | "~"
<identifier> ::= ? An identifier token ?
<int> ::= ? A constant token ?

新增 exp 的产生式规则 <unop> <exp> 和 "(" <exp> ")"。 AST 中不保留括号信息，1、（1) 和 ((((((((1))))))) 在 AST 中均表示为 Constant(1)。注意并没有给出 递减操作符号 -- 的产生式规则，如果遇到 Token.DoubleHyphen 应报错。

<unop> 对应 AST 中的 unary_operator 类型。

对应 parser_exp 的伪代码如下：

parse_exp(tokens):
    next_token = peek(tokens)
    if next_token is an int:
        --snip--
    else if next_token is "~" or "-":
        operator = parse_unop(tokens)
        inner_exp = parse_exp(tokens)
        return Unary(operator, inner_exp)
    else if next_token == "(":
        take_token(tokens)
        inner_exp = parse_exp(tokens)
        expect(")", tokens)
        return inner_exp
    else:
        fail("Malformed expression")

其中的 peek 函数作用为：查看下一个 token 但不消耗它。用以决定应用哪条产生式规则。如果为 一元操作符，首先解析操作符类型，并递归调用 parse_exp 解析操作数，最后构造 Unary 结点。

如果为括号表达式，则首先消耗左括号，递归解析内部表达值，并验证右括号存在。不创建新结点，直接返回内部表达式。

Implementation

lib/Tok_stream.ml

let peek tokens =
  match Stream.peek tokens with
  | Some token -> token
  | None -> raise End_of_stream

lib/parser.ml

(* <unop> ::= "-" | "~" *)
let parse_unop tokens =
  match Tok_stream.take_token tokens with
  | T.Tilde -> Ast.Complement
  | T.Hyphen -> Ast.Negate
  | other -> raise_error ~expected:(Name "a unary operator") ~actual:other

(* <exp> ::= <int> | <unop> <exp> | "(" <exp> ")" *)
let rec parse_exp tokens =
  match Tok_stream.peek tokens with
  | T.Constant _ -> parse_int tokens
  | T.Tilde | T.Hyphen ->
      let opera = parse_unop tokens in
      let inner_exp = parse_exp tokens in
      Unary (opera, inner_exp)
  | T.OpenParen ->
      let _ = Tok_stream.take_token tokens in
      let expr = parse_exp tokens in
      expect T.CloseParen tokens;
      expr
  | other -> raise_error ~expected:(Name "an expression") ~actual:other