- About Scala
- Documentation
- Code Examples
- Software
- Scala Developers

# Re: My starred items

Thu, 2010-10-14, 11:52

[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

Fri, 2010-10-15, 16:37

#2
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>

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

Sun, 2010-10-17, 16:47

#3
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.

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>