I understand the basics of how left-recursion works, and why some people say it's bad. And I've also ready opinions such as:
...like LL and LR parsing, PEGs are often frustrating to use in practise. This is, principally, because they don't support left recursion.
http://tratt.net/laurie/blog/entries/parsing_the_solved_problem_that_isnt
But this leaves me confused.
I haven't read about an actual real-world use case of why you'd even need left-recursion in the first place, especially if there are techniques to convert left recursion to right recursion. In addition, left-recursion feels less intuitive than right-recursion.
What is a real-world use case or need for a left recursive grammar to help me better understand? By "real world" I'm looking for an example grammar that is more human readable than the typical theoretical examples such as:
$A \to B\alpha \mid C$
$B \to A\beta \mid D$
For example:
$filePath \to pathSegment*$
$pathSegment \to pathSegment \mid slash$
$slash \to /$
Part of the reason I ask is b/c left-recursion doesn't seem very intuitive; it seems more intuitive to use right-recursion. And also because I wonder if it's even a practical problem to try to solve.
Update
This makes sense, but seems to be the only major reason:
$E \to E - n \mid n$
converted becomes
$E \to nT*$
$T \to - n$
"10 - 5 - 3" is then parsed:
L-recursive : (((10) - 5) - 3)
R-recusive : (10 (- 5 (- 3)))
http://etymon.blogspot.com/2006/09/why-i-prefer-lalr-parsers.html
Is that all?
Asked By : Lance Pollard
Answered By : Tyler
There are probably better reasons than this, but one nice thing about left recursion is you get parse trees that naturally represent left associativity. You expect 5 + 3 + 2
to be evaluated as (5 + 3) + 2
, but when parsed with the right recursive transformation you show, the parse tree would be the opposite.
This doesn't seem to matter until you start thinking about type coercion (Right word?). Consider 1u / 2u / 1.0f
in C. (1 / 2) / 1.0 = 0 / 1.0 = 0.0
but 1 / (2 / 1.0) = 1 / 2.0 = 0.5
.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/41808
0 comments:
Post a Comment
Let us know your responses and feedback