遍历AST时区分运算符优先级
Distinguish operator precedence when traversing AST
我有一个 AST 由 解析表达式语法 从目标语言生成,它将通过遍历其节点编译为源语言。一个简单的来源
like (10 + 20) * 2
应该生成以下表示,作为原生 ECMAScript 对象:
var ast = {
"type": "Stmt",
"body": [
{
"type": "Expr",
"expression": {
"type": "BinaryExpr",
"operator": "*",
"left": {
"type": "BinaryExpr",
"operator": "+",
"left": {
"type": "Literal",
"value": 10
},
"right": {
"type": "Literal",
"value": 20
}
},
"right": {
"type": "Literal",
"value": 2
}
}
}
]
};
生成的对象清楚地定义了运算符的优先级,并且评估此源非常容易,但是,当您必须处理括号求解时,从中生成代码是一项非常复杂的任务。
遍历节点生成代码时,优先级完全丢失。我有一个叫做visitor
的函数,它是程序的入口点:
function visitor(node) {
switch (node.type) {
case "Stmt":
return parseStmt(node.body);
}
}
这个简单的语法可以接受多个语句...
function parseStmt(body) {
var stmtList = Array(body.length);
for (var i = 0, len = body.length; i < len; i++) {
stmtList[i] = (function(stmt) {
switch (stmt.type) {
case "Expr":
return parseExpr(stmt.expression);
}
})(body[i]);
}
return stmtList.join(";\n");
}
...和两种类型的表达式:
function parseExpr(expr) {
switch (expr.type) {
case "BinaryExpr":
return parseBinaryExpr(expr);
case "Literal":
return parseLiteral(expr);
}
}
其中 Literal
只处理字符串转换...
function parseLiteral(expr) {
return expr.value.toString();
}
...和BinaryExpr
在求解优先级时有歧义:
function parseBinaryExpr(expr) {
var op = {
left: parseExpr(expr.left),
right: parseExpr(expr.right)
};
switch (expr.operator) {
case "+":
return Codegen.OP_ADD(op.left, op.right);
case "*":
return Codegen.OP_MUL(op.left, op.right);
}
}
这里只支持两个数学运算,代码生成发生在这里:
var Codegen = {
OP_ADD: function(left, right) {
return left + " + " + right;
},
OP_MUL: function(left, right) {
return left + " * " + right;
}
};
当调用 visitor(ast)
返回时,我得到 10 + 20 * 2
,这将计算为 10 + (20 * 2)
而不是 (10 + 20) * 2
,并且在二进制表达式的每一侧插入括号将是一个荒谬的解决方法:(10 + 20) * 2
其中:
function parseBinaryExpr(expr) {
var op = {
left: "(" + parseExpr(expr.left) + ")",
right: "(" + parseExpr(expr.right) + ")"
};
...
这个歧义怎么解决好呢?
我会在 CodeGen
中添加括号而不是 ParseBinaryExpr
:
var Codegen = {
OP_ADD: function(left, right) {
return "(" + left + " + " + right + ")";
},
OP_MUL: function(left, right) {
return "(" + left + " * " + right + ")";
}
};
这将减少多余的括号,尽管您最终还是会得到很多括号。从积极的方面来说,毫无疑问,结果表达式对应于 AST。 (顺便说一句,您还需要在代码生成中为一元运算符添加括号。)
可以通过检查 ParseBinaryExpr
中的运算符优先级来避免所有多余的括号——也就是说,只有当参数的优先级低于二元表达式运算符的优先级时,才用括号括起一个参数-- 但这很容易出错并导致细微的错误。
简单的优先级 table 并查看父表达式是否可以解决问题?
此外,开关中有一个小错误。
var ast = {
"type": "Stmt",
"body": [
{
"type": "Expr",
"expression": {
"type": "BinaryExpr",
"operator": "*",
"left": {
"type": "BinaryExpr",
"operator": "+",
"left": {
"type": "Literal",
"value": 10
},
"right": {
"type": "Literal",
"value": 20
}
},
"right": {
"type": "Literal",
"value": 2
}
}
}
]
};
var precedence = { "*": 0, "+": 1 };
var Codegen = {
OP_ADD: function(left, right) {
return left + " + " + right;
},
OP_MUL: function(left, right) {
return left + " * " + right;
}
};
function visitor(node) {
switch (node.type) {
case "Stmt":
return parseStmt(node.body);
}
}
function parseStmt(body) {
var stmtList = Array(body.length);
for (var i = 0, len = body.length; i < len; i++) {
stmtList[i] = (function(stmt) {
switch (stmt.type) {
case "Expr":
return parseExpr(stmt.expression, null);
}
})(body[i]);
}
return stmtList.join(";\n");
}
function parseExpr(expr, parent) {
switch (expr.type) {
case "BinaryExpr":
return parseBinaryExpr(expr, parent);
case "Literal":
return parseLiteral(expr);
}
}
function parseLiteral(expr) {
return expr.value.toString();
}
function parseBinaryExpr(expr, parent) {
var op = {
left: parseExpr(expr.left, expr),
right: parseExpr(expr.right, expr)
};
var ret = "";
switch (expr.operator) {
case "+":
ret = Codegen.OP_ADD(op.left, op.right);
break;
case "*":
ret = Codegen.OP_MUL(op.left, op.right);
break;
}
if (parent && precedence[expr.operator] > precedence[parent.operator]) {
ret = "(" + ret + ")";
}
return ret;
}
visitor(ast);
或者,如果在另一个表达式中有嵌套的二进制表达式,您总是可以加上括号,这也能达到目的。
if (parent) {
ret = "(" + ret + ")";
}
只需检查父级,因为如果我们已经在二进制表达式中,我们只会传递父级。
我有一个 AST 由 解析表达式语法 从目标语言生成,它将通过遍历其节点编译为源语言。一个简单的来源
like (10 + 20) * 2
应该生成以下表示,作为原生 ECMAScript 对象:
var ast = {
"type": "Stmt",
"body": [
{
"type": "Expr",
"expression": {
"type": "BinaryExpr",
"operator": "*",
"left": {
"type": "BinaryExpr",
"operator": "+",
"left": {
"type": "Literal",
"value": 10
},
"right": {
"type": "Literal",
"value": 20
}
},
"right": {
"type": "Literal",
"value": 2
}
}
}
]
};
生成的对象清楚地定义了运算符的优先级,并且评估此源非常容易,但是,当您必须处理括号求解时,从中生成代码是一项非常复杂的任务。
遍历节点生成代码时,优先级完全丢失。我有一个叫做visitor
的函数,它是程序的入口点:
function visitor(node) {
switch (node.type) {
case "Stmt":
return parseStmt(node.body);
}
}
这个简单的语法可以接受多个语句...
function parseStmt(body) {
var stmtList = Array(body.length);
for (var i = 0, len = body.length; i < len; i++) {
stmtList[i] = (function(stmt) {
switch (stmt.type) {
case "Expr":
return parseExpr(stmt.expression);
}
})(body[i]);
}
return stmtList.join(";\n");
}
...和两种类型的表达式:
function parseExpr(expr) {
switch (expr.type) {
case "BinaryExpr":
return parseBinaryExpr(expr);
case "Literal":
return parseLiteral(expr);
}
}
其中 Literal
只处理字符串转换...
function parseLiteral(expr) {
return expr.value.toString();
}
...和BinaryExpr
在求解优先级时有歧义:
function parseBinaryExpr(expr) {
var op = {
left: parseExpr(expr.left),
right: parseExpr(expr.right)
};
switch (expr.operator) {
case "+":
return Codegen.OP_ADD(op.left, op.right);
case "*":
return Codegen.OP_MUL(op.left, op.right);
}
}
这里只支持两个数学运算,代码生成发生在这里:
var Codegen = {
OP_ADD: function(left, right) {
return left + " + " + right;
},
OP_MUL: function(left, right) {
return left + " * " + right;
}
};
当调用 visitor(ast)
返回时,我得到 10 + 20 * 2
,这将计算为 10 + (20 * 2)
而不是 (10 + 20) * 2
,并且在二进制表达式的每一侧插入括号将是一个荒谬的解决方法:(10 + 20) * 2
其中:
function parseBinaryExpr(expr) {
var op = {
left: "(" + parseExpr(expr.left) + ")",
right: "(" + parseExpr(expr.right) + ")"
};
...
这个歧义怎么解决好呢?
我会在 CodeGen
中添加括号而不是 ParseBinaryExpr
:
var Codegen = {
OP_ADD: function(left, right) {
return "(" + left + " + " + right + ")";
},
OP_MUL: function(left, right) {
return "(" + left + " * " + right + ")";
}
};
这将减少多余的括号,尽管您最终还是会得到很多括号。从积极的方面来说,毫无疑问,结果表达式对应于 AST。 (顺便说一句,您还需要在代码生成中为一元运算符添加括号。)
可以通过检查 ParseBinaryExpr
中的运算符优先级来避免所有多余的括号——也就是说,只有当参数的优先级低于二元表达式运算符的优先级时,才用括号括起一个参数-- 但这很容易出错并导致细微的错误。
简单的优先级 table 并查看父表达式是否可以解决问题?
此外,开关中有一个小错误。
var ast = {
"type": "Stmt",
"body": [
{
"type": "Expr",
"expression": {
"type": "BinaryExpr",
"operator": "*",
"left": {
"type": "BinaryExpr",
"operator": "+",
"left": {
"type": "Literal",
"value": 10
},
"right": {
"type": "Literal",
"value": 20
}
},
"right": {
"type": "Literal",
"value": 2
}
}
}
]
};
var precedence = { "*": 0, "+": 1 };
var Codegen = {
OP_ADD: function(left, right) {
return left + " + " + right;
},
OP_MUL: function(left, right) {
return left + " * " + right;
}
};
function visitor(node) {
switch (node.type) {
case "Stmt":
return parseStmt(node.body);
}
}
function parseStmt(body) {
var stmtList = Array(body.length);
for (var i = 0, len = body.length; i < len; i++) {
stmtList[i] = (function(stmt) {
switch (stmt.type) {
case "Expr":
return parseExpr(stmt.expression, null);
}
})(body[i]);
}
return stmtList.join(";\n");
}
function parseExpr(expr, parent) {
switch (expr.type) {
case "BinaryExpr":
return parseBinaryExpr(expr, parent);
case "Literal":
return parseLiteral(expr);
}
}
function parseLiteral(expr) {
return expr.value.toString();
}
function parseBinaryExpr(expr, parent) {
var op = {
left: parseExpr(expr.left, expr),
right: parseExpr(expr.right, expr)
};
var ret = "";
switch (expr.operator) {
case "+":
ret = Codegen.OP_ADD(op.left, op.right);
break;
case "*":
ret = Codegen.OP_MUL(op.left, op.right);
break;
}
if (parent && precedence[expr.operator] > precedence[parent.operator]) {
ret = "(" + ret + ")";
}
return ret;
}
visitor(ast);
或者,如果在另一个表达式中有嵌套的二进制表达式,您总是可以加上括号,这也能达到目的。
if (parent) {
ret = "(" + ret + ")";
}
只需检查父级,因为如果我们已经在二进制表达式中,我们只会传递父级。