[Solved]: What is a real-world use-case/need for a left-recursive grammar?

Problem Detail: 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 Balpha mid C$ $B to Abeta 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 3.2K people like this

Download Related Notes/Documents