i
i
icj
Search…
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 语言相同。
Copy link