/gpc

Leightweight generalized parser combinators

Primary LanguageHaskellGNU Affero General Public License v3.0AGPL-3.0

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