crafting-interpreters4

这一节的关键是parsing interpreters，据说是书中最为重要的部分之一。其实等看完了之后发现，应该就是所谓的优先级转换。看完了这一篇还是对前端解析中优先级的处理有了更深的认识，知道了具体是怎么实现的，甚至可以根据自己的需求，调整运算优先级。

parsing

parser的目的有两个

• 给一个合法的token序列，输出对应的AST（参数树）
• 给一个不合法的参数序列，探测其中的error并输出

设想

parse的意义在于能够将一个句子(一行由token组成的代码)识别成这个语句由什么部分构成。也就是做和上一章相反的事情。上一章的一部分内容是根据规则生成code，这一部分则是检查code是否符合规则以及将code划分成不同部分。

expression     → literal
               | unary
               | binary
               | grouping ;

literal        → NUMBER | STRING | "true" | "false" | "nil" ;
grouping       → "(" expression ")" ;
unary          → ( "-" | "!" ) expression ;
binary         → expression operator expression ;
operator       → "==" | "!=" | "<" | "<=" | ">" | ">="
               | "+"  | "-"  | "*" | "/" ;

parsing中很重要的一件事是处理优先级。例如以下的对于“等式”的表示形式，注意我们通常把优先级较低的放在前面的位置，优先级较高的放在靠后的位置。

expression     → equality ;
equality       → comparison ( ( "!=" | "==" ) comparison )* ;
comparison     → term ( ( ">" | ">=" | "<" | "<=" ) term )* ;
term           → factor ( ( "-" | "+" ) factor )* ;
factor         → unary ( ( "/" | "*" ) unary )* ;
unary          → ( "!" | "-" ) unary
               | primary ;
primary        → NUMBER | STRING | "true" | "false" | "nil"
               | "(" expression ")" ;

具体算法

考虑一下，如何将上述equality()变成代码？如下

private Expr equality() {
  Expr expr = comparison();

  while (match(BANG_EQUAL, EQUAL_EQUAL)) {
    Token operator = previous();
    Expr right = comparison();
    expr = new Expr.Binary(expr, operator, right);
  }

  return expr;
}

第二行的comparison()代表了上面规则中需要左侧递归解析的comparison。我们把它储存为本地变量。在这之后，我们逐层递归解析表达式，所依据的规则就是上面表中的顺序。

在equality中我们调用了comparison()，如下所示

private Expr comparison() {
    Expr expr = term();

    while (match(GREATER, GREATER_EQUAL, LESS, LESS_EQUAL)) {
        Token operator = previous();
        Expr right = term();
        expr = new Expr.Binary(expr, operator, right);
    }

    return expr;
}

结构和上面的十分类似，其实根本就是递归地进行下一步解析，注意这里递归最后的结果就是得到两个term，最后合成一个binary表达式。

term的内容如下，可以看出其实结构都很相似，先左递归，之后获取运算符，再右递归。在term后面是factor，也是完全一样的结构

private Expr term() {
    Expr expr = factor();

    while (match(MINUS, PLUS)) {
        Token operator = previous();
        Expr right = factor();
        expr = new Expr.Binary(expr, operator, right);
    }

    return expr;
}

private Expr factor() {
   Expr expr = unary();

   while (match(SLASH, STAR)) {
     Token operator = previous();
     Expr right = unary();
     expr = new Expr.Binary(expr, operator, right);
   }

   return expr;
 }

然后是unary，也就是单目运算符。可以看到这里只匹配一个参数。

private Expr unary() {
    if (match(BANG, MINUS)) {
        Token operator = previous();
        Expr right = unary();
        return new Expr.Unary(operator, right);
    }

    return primary();
}

最后到了primary，也就是最下端的数字，字符串等基本参数。到这里时一定会反向递归上去。

private Expr primary() {
    if (match(FALSE)) return new Expr.Literal(false);
    if (match(TRUE)) return new Expr.Literal(true);
    if (match(NIL)) return new Expr.Literal(null);

    if (match(NUMBER, STRING)) {
        return new Expr.Literal(previous().literal);
    }

    if (match(LEFT_PAREN)) {
        Expr expr = expression();
        consume(RIGHT_PAREN, "Expect ')' after expression.");
        return new Expr.Grouping(expr);
    }
}

注意最后会匹配括号。在这里又可能产生一个新的表达式。如果我们发现右侧括号没有，就触发一个错误。

总结一下，这里主要将一个已经识别为token的代码识别成句法结构。采用的主要方式是递归识别，按照优先级一层一层识别(其实本质上编译器关于优先级的识别方式原理就在这里，按照从前到后的顺序结合为表达式)，直到最底层的整数，字符串或者左括号。

作为练习，看一下下面的式子

a == b == c == d == e

首先这是一个expression，首先会把他识别为equation（因为等号优先级最低）然后进入comparison()，进入term(),factor(),unary()，然后没有识别到感叹号或者负号，就进入primary()这里会把A的token特性拿出来，判断是数字还是字符串。然后逐层倒着递归上去。一直到equaliyt()中的equal_equal时终止，识别到等号表达式，并再次递归。

一直到最后一个等号，也就是d == e时，可以进入以下代码的第四行，将**刚才得到的表达式结果作为Expr.Binary()**的左侧expr，结合为一个表达式，并且再逐层递归回去。可以看到我们这样得到的优先级就是

(a == (b == (c == (d == e))))

也就是从右向左。这是符合我们预期的。

while (match(BANG_EQUAL, EQUAL_EQUAL)) {
    Token operator = previous();
    Expr right = comparison();
    expr = new Expr.Binary(expr, operator, right);
}

错误处理

没看太明白，后续补..

测试

从结果上来看，我们确实完成了前端解析的工作。其实最重要的还是上面提到的，将表达式根据优先级转换为抽象参数树。