symantic-parser: Parser combinators statically optimized and staged via typed meta-programming

Main differences with respect to ParsleyHaskell

• Primitive grammar combinators are extensible, including the optimization pass for which they are the current top-level combinator.

• Error messages are based upon the farthest input position reached (not yet implemented in ParsleyHaskell) and there is a preliminary support for error messages based upon labeled failures.

• Minimal input length checks ("horizon" checks) required for a successful parsing are statically computed using a polyfix to see beyond calls to subroutines, which is not (yet) possible in ParsleyHaskell.

• Symantics are used for grammars productions instead of GHC plugins: lift-plugin, idioms-plugin or parsley-garnish for users. Those provide convenient syntaxic-sugar (by quoting an Haskell expression as itself and its TemplateHaskell equivalent), but I do not understand them that much and do not feel confortable to maintain them in case their authors abandon them.

• Fresh TemplateHaskell names are used directly (when observing sharingm introducing join-points, etc.) instead of a detour depending upon dependent-map.

• Code is a common published under the copyleft license AGPL-3.0-or-later, instead of the more liberal BSD-3-Clause of ParsleyHaskell.

• Testing grammars have their generated machines and TemplateHaskell splices followed by golden tests.

Main goals

• For me to better understand ParsleyHaskell, and find a manageable balance between simplicity of the codebase and features of the parser. And by doing so, challenging and showcasing symantic techniques.

• To support the parsing of tree-like data structures instead of only string-like data structures. Eg. to validate XML using RelaxNG in symantic-xml or to perform routing of HTTP requests in symantic-http-server. This is currently done in those packages using megaparsec, but megaparsec is not conceived for such input, and is less principled when it comes to optimizing, like merging alternatives.

Implementation techniques

Typed Tagless-Final

The syntax of grammars are term-level combinators defined in type-classes, and their semantics are data-types having instances of those type-classes. And the same technique is applied for machine instructions and grammar productions.

For automatic deriving, DefaultSignatures are supplied, see Symantic.Typed.Derive.

For pattern-matching, data-families indexed by the syntaxic type-class are supplied, see Symantic.Typed.Data.