ASTツリーを別のASTツリーに変換する

Question

私はASTツリーを生成する単純なPEGパーサを持っています。すべての演算子は右結合であるため、構文解析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]*