search

Toxaris / coalgebraic-parsing

0 stars 0 forks source link

Is alive #1

Open b-studios opened 9 years ago

b-studios commented 9 years ago

Equipped the parser with an additional observation isAlive in order to allow for some optimizations.

This PR is for discussion.

b-studios commented 9 years ago

So far the motivation for this PR has been performance (without knowledge whether this is a problem and / or is fixed by this PR). Here comes a new motivation: Error Recovery.

Usually rules for error recovery are sprinkled around the whole grammar. If we have parsers that can inspect the liveness state of another parser, then this parser could feed the missing tokens to the first one. I haven't fully thought this trough - but this might be another interesting usecase for coalgebraic parsing.

Toxaris commented 9 years ago

I'm asking for the motivation because such properties are only semi-decidable in an embedded language (because they depend on Haskell evaluation), so we should decide which way around we approximate before rushing into an implementation.

b-studios commented 9 years ago

BTW, performance wise, I still wait for assertAccept "(many (token 'a'))" "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" (many (token 'a')) to terminate... :)

Toxaris commented 9 years ago

hmm, yes, this is probably fixable by optimizing empty <*> p to empty and empty <|> p to p, which requires detecting empty.

Toxaris commented 9 years ago

I started to look into the many (token 'a') issue, see 815f67e4e139acc5b1b96710b3c33420df7df296.