Re: Parser.y rewrite with parser combinators

backtrack while backtracking <...> I can almost guarantee that this will happen unless you use formal methods

That is a great idea, I can track backtracking depth in a type-level natural number and make sure it doesn't go over 1 (or add justification with performance analysis when it does). Formal methods for the win :-) On Tue, Oct 9, 2018 at 10:27 AM Sven Panne wrote:

Am Di., 9. Okt. 2018 um 09:18 Uhr schrieb Vladislav Zavialov :

...

[...] 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. :-)

Cheers, S.