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