javascript - 遍历 AST 时区分运算符优先级

Question

我有一个由目标语言的解析表达式语法生成的 AST，该语法将通过遍历其节点来编译为源语言。一个简单的来源 像 (10 + 20) * 2 应该生成以下表示形式，作为 native 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) + ")"
  };
...

如何以好的方式解决这种歧义？

Answer 1

一个简单的优先级表并查找父表达式难道不能解决这个问题吗？

此外，开关中存在一个小错误。

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 + ")";
  }

只需检查父级，因为只有当我们已经在二进制表达式中时，我们才会传递父级。