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
I do not suggest to change the grammar itself, I think that processing
of the grammar may perform hidden transformations internally.
The trouble is that one can be happily implementing a parser or
designing a grammar when suddenly for some input the parser hangs
indefinitely. Users are likely quick to blame the parser lib, while in
fact it is the grammar that has left-recursion. Hitting that roadblock
is a real bummer.
In some cases the grammar is a given (by a standard for example) and
transforming it to combat left-recursion can obfuscate it beyond
recognition. 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?