On Tuesday, 17 January 2017 at 21:10:17 UTC, Dmitry Olshansky wrote:
On 1/17/17 1:16 PM, Bastiaan Veelo wrote:
On Monday, 16 January 2017 at 22:29:01 UTC, Dmitry Olshansky wrote:
I think left-recursion is better handled at the grammar level.
What I currently have is parser combinators level where adding
this transformation is awkward and too much magic IMO.


Handling left-recursion by grammar transformation often has unwanted
side-effects (operator precedence) and eliminating indirect
left-recursion this way can be impossible in practice. Depending on the complexity of the grammar, even identifying the recursive loop can be a
challenge.

I do not suggest to change the grammar itself, I think that processing of the grammar may perform hidden transformations internally.

Interesting. Would that work with indirect left-recursion? That would be daunting, I fear. It'l still mess with order of operation / associativity, won't it?

Hardening Pegged to deal with the various kinds of
left-recursion was very challenging, but easier than transforming the
grammar I was dealing with (ISO 10206).

Interesting, what kind of hardening?

The trick is to recurse, but knowing when to stop. At a certain point, recursing once more will reduce the length of the matched string. So if you can break recursion when the match stops growing, you are good. This is implemented by memoizing previous recursions. There is an explanation along with literature references in my first PR on left-recursion [1]. However, the PR itself was flawed [2] and received several makeovers [3-5]. In the end, the solution was considerably more complex than the initial PR, involving introspection of the grammar to identify left-recursive loops and the appropriate rules to memoize. We now have complete support for direct, indirect and hidden left-recursion, including multiple intersecting loops and mixed left- and right-recursion. And it does not interfere with general memoization, which is important to speed up PEG parsers [6]. There are some illustrative unit tests in [7] and further.

Bastiaan.

[1] https://github.com/PhilippeSigaud/Pegged/pull/164
[2] https://github.com/PhilippeSigaud/Pegged/pull/165#issuecomment-158914006
[3] https://github.com/PhilippeSigaud/Pegged/pull/168
[4] https://github.com/PhilippeSigaud/Pegged/pull/186
[5] https://github.com/PhilippeSigaud/Pegged/pull/196
[6] Pegged does not memoize at CT though, at the moment.
[7] https://github.com/PhilippeSigaud/Pegged/blob/master/pegged/grammar.d#L2965

Reply via email to