CODEWITHSUNDEEP
parsingcompiler-constructiontreeppl
kp2349
kp2349

Reputation: 89

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.

Upvotes: 2

Views: 1881

Answers (2)

hochl
hochl

Reputation: 12940

Since both grammars are different I would expect different parse trees. The right recursion would swap the addition and the single expansion on the node at the top that is labeled <expr> = <expr> + <term>. The right recursion grammar would expand to <expr> = <term> + <expr> so both children would be swapped.

If you are trying to write a compiler for mathematical expressions a thing that matters more is operator precedence, but not sure what you are up to.

Upvotes: 2

rpy
rpy

Reputation: 4013

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>

Upvotes: 3

Related Questions