Left recursion in PetitParser
I have a PetitParser question. A small part of my grammar is like this: expression := constant / namedSend / ... namedSend := receiver dot namedMessage / ... receiver := expression This is of course left-recursive. I believed the "all the rest is magic" blurb and just went ahead and wrote it as given above. I get an infinite recursion when I run the parser. I know how to left-factor the grammar by hand. But should I have to? How powerful is thy magic, Lukas? Andrew
I know how to left-factor the grammar by hand. But should I have to? How powerful is thy magic, Lukas?
There is no magic. You can fix the problem by wrapping one of the parsers in the cycle with #memoize. That could be done automatically (#cycleSet finds the cycles), but I would rather refactor the grammar as it leads to extremely inefficient parsers. If you want to build complicated expression grammars (where typically left-recursion occurs) it might be useful to use the PPExpressionParser, see the class comment for an example. Lukas -- Lukas Renggli www.lukas-renggli.ch
-----Original Message-----
From: pharo-users-bounces@lists.gforge.inria.fr [mailto:pharo-users-bounces@lists.gforge.inria.fr] On Behalf Of Lukas Renggli Sent: 21 January 2011 14:39 To: A friendly place where any question about pharo is welcome Subject: Re: [Pharo-users] Left recursion in PetitParser
I know how to left-factor the grammar by hand. But should I have to? How powerful is thy magic, Lukas?
There is no magic.
You can fix the problem by wrapping one of the parsers in the cycle with #memoize. That could be done automatically (#cycleSet finds the cycles), but I would rather refactor the grammar as it leads to extremely inefficient parsers.
If you want to build complicated expression grammars (where typically left-recursion occurs) it might be useful to use the PPExpressionParser, see the class comment for an example.
I got my parser working by refactoring the grammar; Using not to do a little look-ahead and direct things down the correct path helped. I saw the tests for memoize, and get the idea of how to use it. But I don't find a cycleSet method anywhere ... Andrew
PPParser>>#cycleSet is contained in the package PetitAnalyzer. You can get it from the PetitParser repository at http://source.lukas-renggli.ch/petit. The package contains all kinds of reflective facilities to query and transform grammars. Lukas On 31 January 2011 16:35, Andrew Black <t-ablack@microsoft.com> wrote:
-----Original Message-----
From: pharo-users-bounces@lists.gforge.inria.fr [mailto:pharo-users-bounces@lists.gforge.inria.fr] On Behalf Of Lukas Renggli Sent: 21 January 2011 14:39 To: A friendly place where any question about pharo is welcome Subject: Re: [Pharo-users] Left recursion in PetitParser
I know how to left-factor the grammar by hand. But should I have to? How powerful is thy magic, Lukas?
There is  no magic.
You can fix the problem by wrapping one of the parsers in the cycle with #memoize. That could be done automatically (#cycleSet finds the cycles), but I would rather refactor the grammar as it leads to extremely inefficient parsers.
If you want to build complicated expression grammars (where typically left-recursion occurs) it might be useful to use the PPExpressionParser, see the class comment for an example.
I got my parser working by refactoring the grammar; Â Using not to do a little look-ahead and direct things down the correct path helped.
I saw the tests for memoize, and get the idea of how to use it. Â But I don't find a cycleSet method anywhere ...
  Andrew
-- Lukas Renggli www.lukas-renggli.ch
participants (2)
-
Andrew Black -
Lukas Renggli