4
$\begingroup$

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?

$\endgroup$

1 Answer 1

4
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.