Smalltalk › Pharo › Pharo Smalltalk Users

Left recursion in PetitParser

_‹ Previous Topic Next Topic _›

Classic

List

Threaded

4 messages Options

Andrew Black

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

Lukas Renggli

Re: 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.

Lukas

--
Lukas Renggli
www.lukas-renggli.ch

Andrew Black

Re: Left recursion in PetitParser

-----Original Message-----
> From: [hidden email] [mailto:[hidden email]] 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

Re: Left recursion in PetitParser

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 <[hidden email]> wrote:

>
>
> -----Original Message-----
>> From: [hidden email] [mailto:[hidden email]] 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