Skip to content

noughtmare/gpc

Repository files navigation

GPC

GPC is a library providing generalized parser combinators which are able to parse all context-free grammars completely. This includes support for left-recursion and reporting all possible parses of ambiguous grammars.

GPC is currently only a proof of concept. Of course it needs a much more elaborate API, but before that I want to implement disambiguation strategies. I have also not put any effort in making this library performant yet.

Comparison with other parsing techniques

Feature (atto/mega)parsec happy (LALR) Earley GPC
No shift-reduce conflicts βœ”οΈ ❌ βœ”οΈ βœ”οΈ
Left-recusion ❌ βœ”οΈ βœ”οΈ βœ”οΈ
Pure Haskell βœ”οΈ ❌ βœ”οΈ βœ”οΈ
Monadic interface βœ”οΈ ❌ ❌ βœ”οΈ
Polynomial time worst-case ❌ βœ”οΈ βœ”οΈ βœ”οΈ
Linear time worst-case ❌ βœ”οΈ ❌ ❌
Linear time possible βœ”οΈ βœ”οΈ ❌ βœ”οΈ
Disambiguation annotations ❌ ❌ ❌ planned

About

Leightweight generalized parser combinators

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

 
 
 

Contributors