Parser.y rewrite with parser combinators

Sven Panne svenpanne at
Tue Oct 9 07:27:40 UTC 2018

Am Di., 9. Okt. 2018 um 09:18 Uhr schrieb Vladislav Zavialov <
vlad.z.4096 at>:

> [...] With parser combinators
> 1. Parse into an expression (linear in the amount of tokens)
> 2. If it turns out we needed a pattern, backtrack and parse into a
> pattern (linear in the amount of tokens) [...]

In a larger grammar implemented by parser combinators it is quite hard to
guarantee that you don't backtrack while backtracking, which would easily
result in exponential runtime. And given the size of the language GHC
recognizes, I can almost guarantee that this will happen unless you use
formal methods. :-)

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <>

More information about the ghc-devs mailing list