About hidden left-recursion

[veelo]

This is a bit of a bummer. Grammars with hidden left-recursion can be processed and some input will be matched correctly, but it seems that this is input that also would have been matched if the grammar were rewritten to take the hiding optional out of the recursive cycle (thus describing a different language). Input that really depends on hidden left-recursion will not be matched currently.

The out-commented assert in this test is an example of valid but failing input. I have described the mechanics of this in my message to Nicolas Laurent, https://github.com/norswap/autumn_dev/issues/1.

I hope someone smarter than me will see a solution, but I have a feeling it won't be possible to support in linear time, and probably add a lot of complexity...

Still there is the possibility that I have completely overlooked something, this is not really my field :-)

[PhilippeSigaud]

Well, that's wonderfully cool already, to have Pegged deal with left recursion and mutual recursion. When people write grammars , left recursion emerge naturally (hidden less so). I'll merge the pull request. Could you please modify the docs to reflect this? We need to indicate somewhere that there is this slight limitation.

On Tue, Nov 17, 2015 at 12:14 AM, veelo notifications@github.com wrote:

This is a bit of a bummer. Grammars with hidden left-recursion can be processed and some input will be matched correctly, but it seems that this is input that also would have been matched if the grammar were rewritten to take the hiding optional out of the recursive cycle (thus describing a different language). Input that really depends on hidden left-recursion will not be matched currently.

The out-commented assert in this test is an example of valid but failing input. I have described the mechanics of this in my message to Nicolas Laurent, norswap/autumn_dev#1 https://github.com/norswap/autumn_dev/issues/1.

I hope someone smarter than me will see a solution, but I have a feeling it won't be possible to support in linear time, and probably add a lot of complexity...

Still there is the possibility that I have completely overlooked

something, this is not really my field :-)

You can view, comment on, or merge this pull request online at:

https://github.com/PhilippeSigaud/Pegged/pull/165 Commit Summary

• Newline.
• Incomplete unittest for hidden left-recursion.

File Changes

• M pegged/grammar.d https://github.com/PhilippeSigaud/Pegged/pull/165/files#diff-0 (33)

Patch Links:

• https://github.com/PhilippeSigaud/Pegged/pull/165.patch
• https://github.com/PhilippeSigaud/Pegged/pull/165.diff

— Reply to this email directly or view it on GitHub https://github.com/PhilippeSigaud/Pegged/pull/165.

[veelo]

With help from Nicolas Laurent I have come to the conclusion (https://github.com/norswap/autumn_dev/issues/1#issuecomment-158513693) that it will be possible to properly support hidden left-recursion in Pegged, but it needs more work and requires introspection of the grammar: We need to be able to identify one single expression in every left-recursive cycle of a grammar. Apart from solving issues this will also reduce the overhead that was introduced in #164.

[nordlow]

Can somebody please explain what hidden left-recursion us?

[veelo]

@nordlow Hidden left-recursion is left-recursion "hidden" behind a non-terminal that can succeed without consuming input, like an optional:

Grammar:
    A <- B? A 'a'
    B <- 'b'

Hidden left-recursion can be less visible, like variations on

Grammar:
    A <- B A 'a'
    B <- 'b'*

Of course indirect left-recursion can be hidden as well.