search

ollef / Earley

Parsing all context-free grammars using Earley's algorithm in Haskell.
BSD 3-Clause "New" or "Revised" License
360 stars 24 forks source link

Disambiguate/Filter productions #61

Open expipiplus1 opened 1 year ago

expipiplus1 commented 1 year ago

Once the parser finishes parsing some ambiguity, it would be really nice to expose this ambiguity to the user, rather than just multiplying the output by this ambiguity size.

For example disambiguate :: ([a] -> b) -> Prod a -> Prod b or more generally ([a] -> [b]) -> Prod a -> Prod b.

I had a look at naively changing some things in parse and following the types but was unable to get this to work without better understanding the algorithm.

The discussion here makes it seem as though this is actually non-trivial! https://github.com/ollef/Earley/issues/18

Perhaps some important reading: https://dinhe.net/~aredridel/.notmine/PDFs/Parsing/SCOTT%2C%20Elizabeth%20-%20SPPF-Style%20Parsing%20From%20Earley%20Recognizers.pdf

expipiplus1 commented 1 year ago

OK, after taking some time to actually understand what's going on I think I've got this working for nonterminals at least, and think I see a way to get it working for terminals also.