从零开始编写 C 编译器 Chapter 3.1 | Frontend

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

添加对二元运算符 +、-、*、/、% 的支持。

Lexer

新增 4 种 token，Plus、Star、Slash、Percent。- 在 Unary 中已经作为 Hyphen 添加了，在 Lexer 阶段不会区分 token 在语义上的区别。

Parser

新增 二元表达式 和 二元运算符。定义如下：

exp = Constant(int)
    | Unary(unary_operator, exp)
    | Binary(binary_operator, exp, exp)
binary_operator = Add | Subtract | Multiply | Divide | Remainder

在 Parser 中需要区分 Unary negate 和 Binary Subtract，取决于 Hyphen 在表达式的哪个位置出现。

二元表达式也可以嵌套，这时需要注意操作符的优先级。例如表达式 1 + 2 * 3，正确的解析应该为 1 + (2 * 3)，对应的 AST 如下。+ 的两个操作数应该为 1 和 (2 * 3)。

Binary (Add, 
        Constant(1),
        Binary (Star, Constant(2), Constant(3))

不区分优先级，很可能解析出如下的 AST吗，即解析为 (1 + 2) * 3，根节点为 *，两个操作数为 (1 + 2) 和 3。

Binary (Multiply,
        Binary (Add, Constant(1), Constant(2),
        Constant(3))

同时对于同优先级的运算，应该符合 左结合律，即 1 + 2 + 3 + 4 应解析为 ((1 + 2) + 3) + 4。

我们很自然可以写出如下的产生式规则:

<exp> ::= <int> | <unop> <exp> | "(" <exp> ")" | <exp> <binop> <exp>

一个二元表达式包括一个表达式，然后是一个二元运算符，然后是另一个表达式。这确实是正确的形式文法，但是不能正确的通过 递归下降解析器 进行解析。<exp> ::= <exp> <binoop> <exp> 是左递归的，即一个 非终结符 出现在最左边第一个位置。当调用 parse_exp 的时候，由于左边第一个符号为 <exp>，会继续调用 parse_exp；此时依然可能满足上述规则，继续调用 parse_exp... parse_exp 在未消耗任何 token 就进行递归，会导致无穷的递归。

refactor Grammar

一种不太讨巧的方法是，通过重写产生式规则来避免左递归。考虑如下的形式文法：

<exp> ::= <term> { ("+" | "-") <term> }
<term> ::= <factor> { ("*" | "/" | "%") <factor> }
<factor> ::= <int> | <unop> <factor> | "(" <exp> ")"

将优先级进行分层，定义为不同的非终结符，这样就只有唯一的解析诸如 1 + 2 * 3 的方法，且不会产生左递归。其中花括号表示重复，即一个单独的 <exp> 可以通过 +、- 运算符连接无穷个 <term>，例如 <term> + <term> - <term>

表达式 1 + 2 * 3 的解析如下：

exp1 = 1 + term1
term1 = 2 * 3

这种方法虽然可行，但随着运算符优先级层数的增加，会变的越来越笨重。目前我们已有三个优先级层级（如果将 <factor> 计入在内），之后每新增一个优先层级，都需要新定义一个非终结符，且为每个已有的非终结符新增对该非终结符的产生式规则，同时还需要编写新的 parse 函数。

Precedence Climbing

优先级爬升(Precedence Climbing) 是一个更简洁的解析二元运算符方法。它能够处理形如 <exp> <binop> <exp> 的产生式规则，同时正确遵循每个二元运算符的优先级。在优先级爬升方法中，每个运算符都被赋予一个数值型的优先级（precedence level），而 parse_exp 函数在调用时会接收一个最小优先级（minimum precedence level）作为参数，接下来的解析部分优先级只能高于这个最小优先级。这样当解析 1 + 2 * 3 的时候，解析完 1 +时，在解析右操作数时，可以正确解析 2 * 3 而不是将 2 作为右操作数。

我们可以使用优先级爬升来解析二元表达式，同时继续使用递归下降来解析语言中的其他结构。新的形式文法如下：

<exp> ::= <factor> | <exp> <binop> <exp>
<factor> ::= <int> | <unop> <factor> | "(" <exp> ")"
<binop> ::= "-" | "+" | "*" | "/" | "%"

将之前的 <exp> 重新命名为 <factor>，因为该符号可以在一个表达式中作为因子出现。唯一区别为，现在 () 内可以出现二元表达式。这意味着 (1 + 2) 是一个 <factor>，然而 -1 + 2 不是一个 <factor> 而是 <exp>，因为 <unop> <exp> 不是 <factor> 的产生式规则。

一个 <exp> 要么是一个二元运算，要么是一个 <factor>。由于 <exp> 和 <factor> 的文法规则相互引用，因此用于解析这两个符号的函数是相互递归（mutually recursive）的。但他们都生成相同的 AST 结点，即 exp 结点。

解析 factor 的伪代码如下：

parse_factor(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_factor(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 factor")

和上一张 parse_exp 的代码很像，只是在不同位置调用 parse_factor 和 parse_exp。

对于 parse_exp，先考虑一个化简的版本：仅处理 + 和 - 运算符，只需要实现左结合。在这种情况下，右操作数只能为 <factor>。可以使用如下伪代码来处理：

parse_exp(tokens):
    left = parse_factor(tokens)
    next_token = peek(tokens)
    while next_token is "+" or "-":
        operator = parse_binop(tokens)
        right = parse_factor(tokens)
        left = Binary(operator, left, right)
        next_token = peek(tokens)
    return left

首先处理第一个 factor 作为左操作数，消耗运算符后，通过 parse_factor 获得下一个 factor,即右操作数。之后将其封装为 AST 结点，并该结点作为新的左操作数。

接下来考虑添加运算符优先级。此时右操作数可能不再是 factor 而是 exp。考虑 1 + 2 * 3 + 4 应解析为 (1 + (2 * 3)) + 4。整个表达式的右操作数为一个 factor 4。而内部表达式的右操作数为 exp (2 * 3)。可以发现，如果最外层的运算符为+、-，且右操作数为一个 exp，则该 exp 中的运算符必须为 *、/、%。如果最外层运算符为 *、/、% 时，右操作数必定为一个 factor。即 e1 <binop> e2 时，e2 中所有运算符优先级必须严格高于 <binop>。

这样就可以在上述伪代码基础上稍作修改，得到完整的 parse_exp 代码：

parse_exp(tokens, min_prec):
    left = parse_factor(tokens)
    next_token = peek(tokens)
    while next_token is a binary operator and precedence(next_token) >= min_prec:
        operator = parse_binop(tokens)
        right = parse_exp(tokens, precedence(next_token) + 1)
        left = Binary(operator, left, right)
        next_token = peek(tokens)
    return left

当 next_token 的优先级高于当前 op(即 min_prec，当前允许解析的最低优先级) 的时候，递归解析子表达式作为右操作数。反之，则返回上一级函数调用，执行左结合。

例如输入 1 + 2 * 3 + 4，假设优先级 * 为 \(20\)，+ 为 \(10\)。

parse_exp(1 + 2 * 3 + 4, min_prec=0)
  left = parse_factor(1 + 2 * 3 + 4) → 1
  peek(+ 2 * 3 + 4) → '+'，prec('+') = 10 ≥ 0，进入循环

    operator = '+'
    right = parse_exp(2 * 3 + 4, min_prec=11)
      parse_exp(2 * 3 + 4, 11):
        left = parse_factor(2 * 3 + 4) → 2
        peek(* 3 + 4) → '*'，prec('*') = 20 ≥ 11，进入循环

          operator = '*'
          right = parse_exp(3 + 4, min_prec=21)

            parse_exp(3 + 4, 21):
              left = parse_factor(3 + 4) → 3
              peek(+ 4) → '+'，prec('+') = 10 < 21，不进入循环
              返回 left = 3

          right = 3
          left = (2 * 3)
          peek(+ 4) → '+'，prec('+') = 10 < 11，不进入循环
        返回 left = (2 * 3)

    right = (2 * 3)
    left = (1 + (2 * 3))
    peek(+ 4) → '+'，prec('+') = 10 ≥ 0，继续循环

      operator = '+'
      right = parse_exp(4, min_prec=11)

        parse_exp(4, 11):
          left = parse_factor(4) → 4
          peek(EOF) → 无运算符，不进入循环
          返回 4

      right = 4
      left = ((1 + (2 * 3)) + 4)
      peek(EOF) → 无运算符，退出循环

  返回 ((1 + (2 * 3)) + 4)

Implementation

函数式语言中，变量不可修改，所以写循环稍微费点劲。通过辅助函数 parse_exp_loop 通过递归来实现。

parse_exp min_prec tokens =
  (* like acc in tail recursive, initial value of left-associative *)
  let initial_factor = parse_factor tokens in
  let next_token = Tok_stream.peek tokens in
  let rec parse_exp_loop left token =
    match get_precedence token with
    (* 1 + (2 * 3) => the right subexpression must have higher precedence than
       left *)
    | Some prec when prec >= min_prec ->
        let operator = parse_binop tokens in
        let right = parse_exp (prec + 1) tokens in
        let result = Ast.Binary (operator, left, right) in
        parse_exp_loop result (Tok_stream.peek tokens)
    (* otherwise, just left-associative *)
    | _ -> left
  in
  parse_exp_loop initial_factor next_token