左回帰と右回帰は同じ構文解析ツリーを生成するかどうか？

Question

これは右再帰文法である：

<assign> -> <id> = <exp> 
<id> -> A | B | C 
<exp> -> <term> + <exp> | <temp> 
<term> -> <factor> * <term> | <factor> 
<factor> -> (<exp>) | <id> 

これは左再帰の文法である：

<assign> -> <id> = <exp> 
<id> -> A | B | C 
<exp> -> <exp> + <term> | <term> 
<term> -> <term> * <factor> | <factor> 
<factor> -> (<exp>) | <id> 

それらの文法は文字列B + C + Aで同じ構文解析ツリーを生成しますか？ 次の画像は左回帰です。

しかし、私はそれは、ノードの位置の間で少し異なっている、右再帰のための解析木を描きます。私がやっていることが正しいのか分かりません。だから私は、左回帰と右回帰が2つの異なる解析木を生成するか、同じ解析木でなければならないのだろうか。この問題を明確にするのを助けてください。ありがとう。

Answer 1

左と右の再帰は同じツリーを生成しません。
あなたは文法から容易に見ることができるA+B+C意志「トップレベル」を有する<term> <op> <exp>または<exp> <op> <term>（ 『EXP他にB + C『一場合と、 『A + B』、』ある』は。

で木は、すべての作品が直接一致を得る些細な場合には同一である。両方の文法は、私は異なる構文解析木を期待異なるため
は （例えばA（）assignをスキップ<exp> --> <term> --> <factor> --> <id>

Answer 2

をあろう。右再帰はスワップなります<expr> = <expr> + <term>というラベルの付いたノードの追加と単一展開右の再帰文法は<expr> = <term> + <expr>に拡大されるため、両方の子が入れ替えられます。

数式用のコンパイラを作成しようとすると、さらに重要なことは演算子の優先順位ですが、あなたが何をしているかは不明です。