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
