retagged by
898 views
3 votes
3 votes
Is operator precedence parser the only parser that accepts left recursive grammar?
retagged by

1 Answer

Best answer
1 votes
1 votes

No. Left recursion is a problem for Top-Down parsers. Bottom-Up Parsers are fine with left recursion.

formal grammar that contains left recursion cannot be parsed by a LL(k)-parser or other naive recursive descent parser unless it is converted to a weakly equivalent right-recursive form. In contrast, left recursion is preferred for LALR parsers because it results in lower stack usage than right recursion

link: https://en.wikipedia.org/wiki/Left_recursion#Accommodating_left_recursion_in_top-down_parsing

The top-down parser had a problem with left recursion precisely because it needed to build top-down. To build top-down, it needed to know about all the plus signs to come, because these needed to be fitted into the parse tree above the current plus sign. But when building bottom-up, we don't need to know anything about the plus signs that will be above the current one in the parse tree. We can afford to wait until we encounter them.

But if working bottom-up solves the left recursion problem

link: http://jeffreykegler.github.io/Ocean-of-Awareness-blog/individual/2014/11/ll.html

https://stackoverflow.com/a/4317204/6430403

selected by

Related questions

0 votes
0 votes
1 answer
1
jatin khachane 1 asked Jun 7, 2017
480 views
E → E + E | E * E | ( E ) | idWhat will be operator precedence for above grammar.Is precedence differs due to ambiguity
0 votes
0 votes
1 answer
3
0 votes
0 votes
1 answer
4
saumya mishra asked Jun 15, 2018
2,132 views
What is the difference between operator grammar and operator precedence grammar?