Различать приоритеты операторов при обходе AST

У меня есть AST, сгенерированный грамматикой синтаксического анализа из целевого языка, который будет компилироваться в исходный язык путем обхода его узлов. Простой источник, такой как (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) + ")"
  };
...

Как можно решить эту двусмысленность?


javascript parsing abstract-syntax-tree compiler-construction peg
person Marcelo Camargo    schedule 29.07.2015    source источник
comment
В конечном итоге вам придется использовать () в сериализации, чтобы указать приоритет; источник, из которого вы получили свой AST, тоже должен был бы использовать их (кроме тех случаев, когда он определил + как более высокий приоритет, чем *). Вы можете проверить, возвращает ли parseExpr «простое» или «составное» выражение для условной вставки ().   -  person Kenney    schedule 29.07.2015

Ответы (2)


arrow_upward
1
arrow_downward

Разве простая таблица приоритетов и поиск родительского выражения не могли бы решить эту проблему?

Также была небольшая ошибка в переключателе.

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

Просто проверьте родительский элемент, потому что мы передаем его только в том случае, если мы уже находимся внутри двоичного выражения.

person Luiz Felipe    schedule 29.07.2015

arrow_upward
0
arrow_downward

Я бы добавил круглые скобки в CodeGen, а не в ParseBinaryExpr:

var Codegen = {
  OP_ADD: function(left, right) {
    return "(" + left + " + " + right + ")";
  },
  OP_MUL: function(left, right) {
    return "(" + left + " * " + right + ")";
  }
};

Это приведет к уменьшению количества повторяющихся круглых скобок, хотя вы все равно будете иметь много скобок. С положительной стороны, нет сомнений в том, что полученное выражение соответствует AST. (Кстати, вам нужно будет добавить круглые скобки в генерацию кода для унарных операторов.)

Можно избежать всех лишних скобок, проверив приоритет оператора в ParseBinaryExpr - то есть вы заключаете аргумент в круглые скобки, только если его приоритет меньше приоритета оператора двоичного выражения - но это легко ошибиться и приводит к незаметным ошибкам.

person rici    schedule 29.07.2015