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.

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).

Reply via email to