AST-Baum zu einem anderen AST-Baum transformieren

Question

Ich habe einen einfachen PEG-Parser, der einen AST-Baum generiert. Jeder Operator ist rechts assoziativ, so dass die Analyse A + B + C + D einen Baum [1] zurückgibt. Gibt es eine einfache Möglichkeit, den [1] Baum in einen Baum umzuwandeln, der von einem assoziativen Operator links [2] erstellt würde?

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

Answer 1

PEG generiert standardmäßig rechts assoziative Bäume. Sie können einen Nachbearbeitungsschritt hinzufügen, um ihn wie folgt zu invertieren:

{ 
    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]*