Search code examples
parsingcompiler-constructiontreeppl

Left Recursion and Right recursion produce same parse tree or not?

This is Right Recursion Grammar: 

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

This is Left Recursion Grammar:

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

Will those grammar produce the same parse tree for String B + C + A? The following picture is for Left Recursion.

enter image description here

However, i draw the parse tree for the Right Recursion, it is a bit different between position of nodes. I dont know if what i am doing is correct. So I wonder that Left Recursion and Right Recursion produce two different parse tree or should be same parse tree. Please help to clarify this problem. Thanks.

Solution

  • Left and right recursion will not produce identical trees.
    You can see easily from the grammars that A+B+C will at the "top-level' have <term> <op> <exp> or <exp> <op> <term> ("exp" being "B+C" in one case and "A+B" in the other.

    The trees will only be identical in trivial cases where all productions yield a direct match.
    (E.g. A (skipping assign) would be <exp> --> <term> --> <factor> --> <id>