This page is no longer maintained — Please continue to the home page at www.scala-lang.org

Re: My starred items

3 replies
Laurence Tratt
Joined: 2010-10-14,
User offline. Last seen 42 years 45 weeks ago.

[Thanks to Tony Sloane for pointing me at this thread]

Alex Repain wrote:

> I've been working this summer on packrat algorithms and left-recursion
> support, using Scala as a main tool. While documenting on the subject, it
> appeared that the implementation of the Scala 2.8 Packrat parsers was using
> the algorithm we were studying ( here are the original algorithm
> description a report about the Scala parser combinator implementation of it
> ).
>
> Our implementation of the algorithm was failing on some tricky
> left-recursion cases, so I tried to achieve them using Scala's parser
> combinators, and I obtained the same failing results.

I too noticed what I consider to be problems with the Warth et al. algorithm
a couple of years back. I should note that Alex - when I last spoken to him
- didn't agree that these were problems (and I respect his reasons for doing
so), so this isn't a widely accepted fact yet.

The basic problem I noted is that rules which are both left-recursive and
right-recursive give parses which I wouldn't have expected. I tried to
narrow down both the problem and also possible solutions (both in
restricting the set of input grammars; and in providing an alternative
algorithm). This proved rather trickier than I had first expected, and
therefore I wouldn't put money on my solutions being perfect. The draft
paper (which I've been spectacularly unsuccessful in getting published) is
here:

http://tratt.net/laurie/research/publications/papers/tratt__direct_left_...

I am currently turning this into a technical report, so at least the paper
will be citeable. There is also a link in the paper to code against which
you can test left-recursive PEGs, if you wish.

If anyone has any comments, suggestions, or questions, please feel free to
ask further on the list or to my personal e-mail address.

Yours,

Laurie

Alex Repain
Joined: 2010-07-27,
User offline. Last seen 1 year 31 weeks ago.
Re: Re: My starred items
This is quite interesting indeed. I have not tested your algorithm yet, but it seems you took the problem very differently compared to our way.

Your paper is firstly interesting because you present "algorithm 1", which is REALLY easier to understand than the original Warth et al.'s solution, yet a PEG equivalent to it. That's good for me : as a matter of fact, I failed to understand exactly whereWrath et al.'s algorithm was wrong, although some parse results were obviously unexpected. That's why we built another solution from the scratch (yet strongly inspired by the concepts taken from Wrath et al.'s work). I will keep studying your paper, at least for that reason !

Yet, I'm not sure that your fix to the algorithm is really fixing the whole thing, or just the left/right recursion mix problem. The example I provided here before is not falling in that special case of right and left recursion mixed, and the results are still incorrect with Wrath et al.'s. I shall test your implementation on my sample grammars to find out.

As about our solution, the first big difference with Wrath et al.'s work is that it relies on intricated seed-growing, instead of one growth at a time only.
I'm working on a paper about that, I'll mail you about once it finished*.

Alex Repain

* Well, I'm only a master course student who has been doing a research internship, my writings would probably suck for publishing, but whatever ...


2010/10/14 Laurence Tratt <laurie [at] tratt [dot] net>
[Thanks to Tony Sloane for pointing me at this thread]

Alex Repain wrote:

> I've been working this summer on packrat algorithms and left-recursion
> support, using Scala as a main tool. While documenting on the subject, it
> appeared that the implementation of the Scala 2.8 Packrat parsers was using
> the algorithm we were studying ( here are the original algorithm
> description a report about the Scala parser combinator implementation of it
> ).
>
> Our implementation of the algorithm was failing on some tricky
> left-recursion cases, so I tried to achieve them using Scala's parser
> combinators, and I obtained the same failing results.

I too noticed what I consider to be problems with the Warth et al. algorithm
a couple of years back. I should note that Alex - when I last spoken to him
- didn't agree that these were problems (and I respect his reasons for doing
so), so this isn't a widely accepted fact yet.

The basic problem I noted is that rules which are both left-recursive and
right-recursive give parses which I wouldn't have expected. I tried to
narrow down both the problem and also possible solutions (both in
restricting the set of input grammars; and in providing an alternative
algorithm). This proved rather trickier than I had first expected, and
therefore I wouldn't put money on my solutions being perfect. The draft
paper (which I've been spectacularly unsuccessful in getting published) is
here:

 http://tratt.net/laurie/research/publications/papers/tratt__direct_left_recursive_parsing_expression_grammars.pdf

I am currently turning this into a technical report, so at least the paper
will be citeable. There is also a link in the paper to code against which
you can test left-recursive PEGs, if you wish.

If anyone has any comments, suggestions, or questions, please feel free to
ask further on the list or to my personal e-mail address.

Yours,


Laurie
--
http://tratt.net/laurie/ -- Personal
http://fetegeo.org/      -- Free text geocoding
http://convergepl.org/   -- The Converge programming language

Alex Repain
Joined: 2010-07-27,
User offline. Last seen 1 year 31 weeks ago.
Re: Re: My starred items
After testing some of your grammars and working around the resulting parse trees with our algorithm, it seems it doesn't solve the problem you are pointing out, and that we have been addressing two different issues of the original algorithm. We were focused on how to accept more languages, with more intricated left-recursion cases, but didn't check our parse trees, and it seems they are as right-associative as when parsed by Wrath et al.'s algorithm. Your point about the greedy match in PEG parsers is quite interesting also.

2010/10/14 Repain Alex <alex [dot] repain [at] gmail [dot] com>
This is quite interesting indeed. I have not tested your algorithm yet, but it seems you took the problem very differently compared to our way.

Your paper is firstly interesting because you present "algorithm 1", which is REALLY easier to understand than the original Warth et al.'s solution, yet a PEG equivalent to it. That's good for me : as a matter of fact, I failed to understand exactly whereWrath et al.'s algorithm was wrong, although some parse results were obviously unexpected. That's why we built another solution from the scratch (yet strongly inspired by the concepts taken from Wrath et al.'s work). I will keep studying your paper, at least for that reason !

Yet, I'm not sure that your fix to the algorithm is really fixing the whole thing, or just the left/right recursion mix problem. The example I provided here before is not falling in that special case of right and left recursion mixed, and the results are still incorrect with Wrath et al.'s. I shall test your implementation on my sample grammars to find out.

As about our solution, the first big difference with Wrath et al.'s work is that it relies on intricated seed-growing, instead of one growth at a time only.
I'm working on a paper about that, I'll mail you about once it finished*.

Alex Repain

* Well, I'm only a master course student who has been doing a research internship, my writings would probably suck for publishing, but whatever ...


2010/10/14 Laurence Tratt <laurie [at] tratt [dot] net>
[Thanks to Tony Sloane for pointing me at this thread]

Alex Repain wrote:

> I've been working this summer on packrat algorithms and left-recursion
> support, using Scala as a main tool. While documenting on the subject, it
> appeared that the implementation of the Scala 2.8 Packrat parsers was using
> the algorithm we were studying ( here are the original algorithm
> description a report about the Scala parser combinator implementation of it
> ).
>
> Our implementation of the algorithm was failing on some tricky
> left-recursion cases, so I tried to achieve them using Scala's parser
> combinators, and I obtained the same failing results.

I too noticed what I consider to be problems with the Warth et al. algorithm
a couple of years back. I should note that Alex - when I last spoken to him
- didn't agree that these were problems (and I respect his reasons for doing
so), so this isn't a widely accepted fact yet.

The basic problem I noted is that rules which are both left-recursive and
right-recursive give parses which I wouldn't have expected. I tried to
narrow down both the problem and also possible solutions (both in
restricting the set of input grammars; and in providing an alternative
algorithm). This proved rather trickier than I had first expected, and
therefore I wouldn't put money on my solutions being perfect. The draft
paper (which I've been spectacularly unsuccessful in getting published) is
here:

 http://tratt.net/laurie/research/publications/papers/tratt__direct_left_recursive_parsing_expression_grammars.pdf

I am currently turning this into a technical report, so at least the paper
will be citeable. There is also a link in the paper to code against which
you can test left-recursive PEGs, if you wish.

If anyone has any comments, suggestions, or questions, please feel free to
ask further on the list or to my personal e-mail address.

Yours,


Laurie
--
http://tratt.net/laurie/ -- Personal
http://fetegeo.org/      -- Free text geocoding
http://convergepl.org/   -- The Converge programming language


Laurence Tratt
Joined: 2010-10-14,
User offline. Last seen 42 years 45 weeks ago.
Re: Re: My starred items

On Fri, Oct 15, 2010 at 05:36:17PM +0200, Repain Alex wrote:

Dear Alex,

> After testing some of your grammars and working around the resulting parse
> trees with our algorithm, it seems it doesn't solve the problem you are
> pointing out, and that we have been addressing two different issues of the
> original algorithm. We were focused on how to accept more languages, with
> more intricated left-recursion cases, but didn't check our parse trees, and
> it seems they are as right-associative as when parsed by Wrath et al.'s
> algorithm.

Ah, that's a bit unfortunate but as I said, not everyone yet thinks that the
right-associative parses you're seeing are a problem. I do, of course; but,
when I spoke to him 18 months or so ago, Alex Warth didn't (though he might
feel differently now - I don't know). So it's not a settled matter yet.

> Your point about the greedy match in PEG parsers is quite interesting also.

From my point of view, this is the heart of the matter.

[Your first e-mail]
>> Your paper is firstly interesting because you present "algorithm 1", which
>> is REALLY easier to understand than the original Warth et al.'s solution,
>> yet a PEG equivalent to it. That's good for me : as a matter of fact, I
>> failed to understand exactly whereWrath et al.'s algorithm was wrong,
>> although some parse results were obviously unexpected.

I originally spent a couple of days banging my head against a wall, because
I didn't understand exactly how the Warth et al. algorithm was working, and
I couldn't really understand the explanation. If my simpler version of the
same thing helps people understand the original algorithm, I'll consider
that a useful contribution in and of itself.

Yours,

Laurie

PS: I apologise for buggering up the subject line... Mea culpa.

Copyright © 2012 École Polytechnique Fédérale de Lausanne (EPFL), Lausanne, Switzerland