前言：感觉之前的内容写的不好，很散很乱。因为之前强行把文章拆成两个部分：原理和代码实现，不应该这样，应该边写代码，写叙述原理。
0X00 if else 的原理与实现
首先我们得认识到 if else 是一个 statement，而不是一个 expression，借此我们写出 if else 的文法：
statement → exprStmt
| ifStmt
| printStmt
| block ;
ifStmt → "if" "(" expression ")" statement ( "else" statement )? ;
凭借文法我们写出 if else 的抽象语法树的格式：
static class If extends Stmt {
If(Expr condition, Stmt thenBranch, Stmt elseBranch) {
this.condition = condition;
this.thenBranch = thenBranch;
this.elseBranch = elseBranch;
}
<R> R accept(Visitor<R> visitor) {
return visitor.visitIfStmt(this);
}
final Expr condition;
final Stmt thenBranch;
final Stmt elseBranch;
}
我们在 parser 中实现 if else 的抽象语法树的生成：
匹配 IF 关键字：
private Stmt statement() {
if (match(PRINT)) {
return printStatement();
}
if (match(LEFT_BRACE)) {
return new Stmt.Block(block());
}
if (match(IF)) {
return ifStatement();
}
if (match(WHILE)) {
return whileStatement();
}
// 将 for 转换成 while
if (match(FOR)) {
return forStatement();
}
return expressionStatement();
}
private Stmt ifStatement() {
// 生成 ifStatement 的抽象语法树
// ifStmt → "if" "(" expression ")" statement ( "else" statement )? ;
consume(LEFT_PAREN, "Expect '(' after 'if'.");
Expr condition = expression();
consume(RIGHT_PAREN, "Expect ')' after if condition.");
Stmt thenBranch = statement();
Stmt elseBranch = null;
if (match(ELSE)) {
elseBranch = statement();
}
return new Stmt.If(condition, thenBranch, elseBranch);
}
接下来我们要在「Interpreter」中执行 if else 的「抽象语法树」
@Override
public Void visitIfStmt(Stmt.If stmt) {
Expr condition = stmt.condition;
Stmt thenBranch = stmt.thenBranch;
Stmt elseBranch = stmt.elseBranch;
if (isTruthy(evaluate(condition))) {
execute(thenBranch);
} else {
execute(elseBranch);
}
return null;
}
在这里出现了一个问题，我们如何判断条件的真假？
A and B 与 A or B，不能把上述两个看做一个「简单的二元表达式」，比如 A or B 只要 A 正确后面的表达式就不用执行了，
所以我们要给逻辑运算定义新的「抽象语法树」格式：
static class Logical extends Expr {
Logical(Expr left, Token operator, Expr right) {
this.left = left;
this.operator = operator;
this.right = right;
}
<R> R accept(Visitor<R> visitor) {
return visitor.visitLogicalExpr(this);
}
final Expr left;
final Token operator;
final Expr right;
}
我们先写出在逻辑运算的文法：（and 运算符的优先级比 or 高）
expression → assignment ;
assignment → identifier "=" assignment
| logic_or ;
logic_or → logic_and ( "or" logic_and )* ;
logic_and → equality ( "and" equality )* ;
然后在 parser 中，生成逻辑运算的「抽象语法树」：
private Expr assignment() {
// expression → assignment ;
// assignment → identifier "=" assignment
// | logic_or ;
// logic_or → logic_and ( "or" logic_and )* ;
// logic_and → equality ( "and" equality )* ;
// 左值可能需要计算我们先跳过计算左值
Expr expr = logic_or();
if (match(EQUAL)) {
Token equal = previous();
Expr value = assignment();
// expr 通过递归，应该得到是一个 Variable，不应该是其他的别的东西
// 否则报错
if (expr instanceof Expr.Variable) {
Token name = ((Expr.Variable) expr).name;
return new Expr.Assign(name, value);
}
error(equal, "Invalid assignment target.");
}
return expr;
}
private Expr logic_and() {
Expr left = equality();
while (match(AND)) {
Token operator = previous();
Expr right = equality();
return new Expr.Logical(left, operator, right);
}
return left;
}
private Expr logic_or() {
Expr left = logic_and();
while (match(OR)) {
Token operator = previous();
Expr right = logic_and();
return new Expr.Logical(left, operator, right);
}
return left;
}
在 Interpreter 中执行语法树：
@Override
public Object visitLogicalExpr(Expr.Logical expr) {
Object left = evaluate(expr.left);
if (isTruthy(left)) {
// 如果是 or 直接返回 left
// 如果是 and 返回 right
// 由返回式的真假判断真假
if (expr.operator.type == TokenType.OR) {
return left;
} else {
return evaluate(expr.right);
}
}
// 左值为假
// 如果是 or 返回右值
if (expr.operator.type == TokenType.OR) {
return evaluate(expr.right);
}
// 如果是 and
// 返回假的左值
return left;
}
0X01 while for 的原理与实现
while 的实现真的很简单。
按照常理，我们得写出 while 的文法：
statement → exprStmt
| ifStmt
| printStmt
| whileStmt
| block ;
whileStmt → "while" "(" expression ")" statement ;
然后写出 while 抽象语法树的格式：
static class While extends Stmt {
While(Expr condition, Stmt body) {
this.condition = condition;
this.body = body;
}
<R> R accept(Visitor<R> visitor) {
return visitor.visitWhileStmt(this);
}
final Expr condition;
final Stmt body;
}
在 Parse 中生成 while 的抽象语法树：
private Stmt whileStatement() {
consume(LEFT_PAREN, "Expect '(' after 'while'.");
Expr condition = expression();
consume(RIGHT_PAREN, "Expect ')' after while condition.");
Stmt body = statement();
return new Stmt.While(condition, body);
}
最后在 Interpreter 中执行抽象语法树：
@Override
public Void visitWhileStmt(Stmt.While stmt) {
Expr condition = stmt.condition;
Stmt body = stmt.body;
while(isTruthy(evaluate(condition))) {
execute(body);
}
return null;
}
for 相对难一些，但是 for 本质上是 while 的语法糖，比如：
for (var i = 0; i < 10; i = i + 1) print i;
// 等价于
{
var i = 0;
while (i < 10) {
print i;
i = i + 1;
}
}
所以我们使用 while 代替 for ，首先我们将 for 写成如下格式：
for (initializer; condition; increment) body
// 转换成
{
initializer;
while(condition) {
increment;
body;
}
}
所以在 parser 中写出：
private Stmt forStatement() {
consume(LEFT_PAREN, "Expect '(' after 'for'.");
Stmt initializer;
if (match(SEMICOLON)) {
initializer = null;
} else if (match(VAR)) {
initializer = varDeclaration();
} else {
initializer = expressionStatement();
}
Expr condition = null;
if (!check(SEMICOLON)) {
condition = expression();
}
consume(SEMICOLON, "Expect ';' after loop condition.");
Expr increment = null;
if (!check(RIGHT_PAREN)) {
increment = expression();
}
consume(RIGHT_PAREN, "Expect ')' after for clauses.");
Stmt body = statement();
if (increment != null) {
body = new Stmt.Block(Arrays.asList(body, new Stmt.Expression(increment)));
}
if (condition == null)
condition = new Expr.Literal(true);
body = new Stmt.While(condition, body);
if (initializer != null) {
body = new Stmt.Block(Arrays.asList(initializer, body));
}
return body;
}
网友评论