> 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 <svenpa...@gmail.com> wrote: > > Am Di., 9. Okt. 2018 um 09:18 Uhr schrieb Vladislav Zavialov > <vlad.z.4...@gmail.com>: >> >> [...] 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. _______________________________________________ ghc-devs mailing list ghc-devs@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs
