Pry v0.3.1 is out!

[Bastiaan Veelo via Digitalmars-d-announce]

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