1.9 使用 AST - 计算器

icj

Search…

icj

使用 JavaScript 来实现解释器和编译器系列教程

1.7 解析算术表达式 - 左递归和其消除法

1.8 解析算术表达式 - 优先级与结合性

1.9 使用 AST - 计算器

1.10 流程控制

编译器篇

1.9 使用 AST - 计算器

我们已经可以解析算术表达式了，基于此我们可以进一步来实现一个计算器。
为了可以将打印我们的表达式的执行结果，在实现函数调用的语法之前，我们先实现一个支持打印执行结果的语法：
print ::= "print" expr
这样对于语句 print 1 + 2 + 3 来说，它会先执行 1 + 2 + 3 然后打印执行的结果。
语法添加完毕后，第一步还是先完善词法解析器：
TokenType.PRINT = "print";
​
class Lexer {
  next() {
    this.skipWhitespace();
    const ch = this.src.peek();
    // ...
    if (ch === "h") return this.readHi();
    if (ch === "p") return this.readPrint();
    // ...
    throw new Error(this.makeErrMsg());
  }
​
  readPrint() {
    const tok = new Token(TokenType.HI);
    tok.loc.start = this.getPos();
    const print = this.src.read(5);
    assert.ok(print === "print", this.makeErrMsg());
    tok.loc.end = this.getPos();
    tok.value = "print";
    return tok;
  }
}
添加一个新的 Token 类型 TokenType.PRINT，在 Lexer::next 中增加对该关键字的预测分支，以及解析该关键字的 Lexer::readPrint 方法。
接着我们来完善语法解析器：
class PrintStmt extends Node {
  constructor(loc, value) {
    super(NodeType.PRINT_STMT, loc);
    this.value = value;
  }
}
​
NodeType.PRINT_STMT = "printStmt";
​
class Parser {
  parseProg() {
    // ...
    while (true) {
      // ...
      if (tok.type === TokenType.NUMBER) stmt = this.parseExprStmt();
      if (tok.type === TokenType.PRINT) stmt = this.parsePrintStmt();
      node.body.push(stmt);
    }
    // ...
  }
​
  parsePrintStmt() {
    const node = new PrintStmt();
    let tok = this.lexer.next();
    node.loc.start = tok.loc.start;
    node.value = this.parseExpr();
    node.loc.end = this.lexer.getPos();
    return node;
  }
}
我们新增了一个节点类型 NodeType.PRINT_STMT 已经它的定义 PrintStmt。在 Parser::parseProg 中，我们增加了预测 print 语句的分支，Parser::parsePrintStmt 负责解析 print 语句。
接着完善 Visitor：
class Visitor {
  visitPrintStmt(node) {}
​
  visitStmt(node) {
    switch (node.type) {
      case NodeType.EXPR_STMT:
        return this.visitExprStmt(node);
      case NodeType.SAY_HI:
        return this.visitSayHi(node);
      case NodeType.PRINT_STMT:
        return this.visitPrintStmt(node);
    }
  }
}
我们增加了 visitPrintStmt 方法，留给子类去实现。在 visitStmt 中，增加了对 NodeType.PRINT_STMT 类型的识别和处理。
最后，我们来完善 InterpretVisitor：
class InterpretVisitor extends Visitor {
  visitProg(node) {
    node.body.forEach(stmt => this.visitStmt(stmt));
  }
​
  visitBinaryExpr(node) {
    const left = this.visitExpr(node.left);
    const op = node.op.type;
    const right = this.visitExpr(node.right);
    switch (op) {
      case "+":
        return left + right;
      case "-":
        return left - right;
      case "*":
        return left * right;
      case "/":
        return left / right;
      case "**":
        return left ** right;
    }
  }
​
  visitPrintStmt(node) {
    console.log(this.visitExpr(node.value));
  }
​
  visitNumLiteral(node) {
    return parseInt(node.value);
  }
}
在 visitNumLiteral 中，我们将字符串通过 parseInt 转换成了整型，注意我们在定义数字的语法规则时，具有可选的前导零，当时做这样的选择，也是顺带利用了 JS 中 parseInt 方法的功能。visitBinaryExpr 中，我们对于两个操作数，我们分别调用 visitExpr 来取它们的值，然后根据不同的操作符执行了相应的运算，并返回运行结果，这样使得操作数取值的 visitExpr 调用总是可以拿到值：来自 parseInt 或者子节点的运算结果。visitPrintStmt 的操作就是打印运算的结果，对于求值则是委托给了 visitExpr 来完成。
我们可以来试一试运行语句 print 1 + 2 ** 3 * 5：
const code = `print 1 + 2 ** 3 * 5`;
const src = new Source(code);
const lexer = new Lexer(src);
const parser = new Parser(lexer);
​
const ast = parser.parseProg();
const visitor = new InterpretVisitor();
visitor.visitProg(ast);
我们将会得到输出 41。因为我们的 hi 语言使用了和 JS 相同的运算符优先级和结合性，所以大家也可以将表达式 1 + 2 ** 3 * 5 直接粘贴到浏览器的控制台，来验证执行的结果是否和 hi 语言相同。

1.8 解析算术表达式 - 优先级与结合性

1.10 流程控制

Last modified 3yr ago

Copy link