Различают приоритет оператора при обходе AST

Question

У меня есть 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) + ")" 
    }; 
... 

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

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

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

Answer 2

Я хотел бы добавить скобки в CodeGen, а не в ParseBinaryExpr:

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

Это приведет к уменьшению числа избыточных скобок, хотя вы все равно в конечном итоге с большим количеством скобок. С положительной стороны нет сомнений в том, что полученное выражение соответствует АСТ. (Вам также нужно добавить скобки в код gen для унарных операторов.)

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