[Haskell-cafe] Parser left recursion

Brandon Allbery allbery.b at gmail.com
Sun Feb 24 15:46:43 CET 2013


On Sun, Feb 24, 2013 at 6:31 AM, Martin Drautzburg <Martin.Drautzburg at web.de
> wrote:

> Just a silly quick question: why isn't right-recursion a similar problem?
>

Very roughly:

Left recursion is:  let foo n = n + foo n in ...
Right recursion is:  let foo 1 = 1; foo n = n + foo (n - 1) in ...

In short, matching the tokens before the right recursion will constitute an
end condition that will stop infinite recursion --- if only because you'll
hit the end of the input.   Left recursion doesn't consume anything, just
re-executes itself.

-- 
brandon s allbery kf8nh                               sine nomine associates
allbery.b at gmail.com                                  ballbery at sinenomine.net
unix, openafs, kerberos, infrastructure, xmonad        http://sinenomine.net
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20130224/59cc99bd/attachment.htm>


More information about the Haskell-Cafe mailing list