Преобразование дерева AST в другое дерево AST

Question

У меня есть простой парсер PEG, который генерирует дерево AST. Каждый оператор является правильным ассоциативным, поэтому синтаксический анализ A + B + C + D возвращает дерево [1]. Есть ли простой способ преобразовать дерево [1] в одно, которое будет создано левым ассоциативным оператором [2]?

[1] +  [2]  + 
    /\    /\ 
    A +    + D 
    /\   /\ 
    B +   + C 
     /\  /\ 
     C D  A B 

Answer 1

PEG генерирует правильные ассоциативные деревья по умолчанию. Вы можете добавить шаг последующей обработки, чтобы инвертировать его, например:

{ 
    function invert(tree, acc) { 
     if (acc === undefined) { 
      acc = tree[0] 
     } 
     if (tree.length == 1) { 
      return acc; 
     } 
     return invert(tree[2], [acc, tree[1], tree[2][0]]); 
    } 
} 

Start 
    = expr:Expression { 
     return invert(expr) 
    } 

Expression 
    = head:Integer tail:(_ "+" _ Expression)* { 
     var result = [head] 

     for (var i = 0; i < tail.length; i++) { 
      result.push(tail[i][1]) 
      result.push(tail[i][3]) 
     } 

     return result; 
    } 

Integer "integer" 
    = [0-9]+ { return parseInt(text(), 10); } 

_ "whitespace" 
    = [ \t\n\r]*