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

[ agpl, library, parsing ] [ Propose Tags ]

This is a work-in-progress experimental library to generate parsers, leveraging Tagless-Final interpreters and Typed Template Haskell staging.

This is an alternative but less powerful/reviewed implementation of ParsleyHaskell. See the paper by Jamie Willis, Nicolas Wu, and Matthew Pickering, admirably well presented at ICFP-2020: Staged Selective Parser Combinators.


[Skip to Readme]

Modules

[Index] [Quick Jump]

  • Language
    • Haskell
      • TH
        • Language.Haskell.TH.HideName
        • Language.Haskell.TH.Show
  • Symantic
    • Symantic.Parser
      • Symantic.Parser.Grammar
        • Symantic.Parser.Grammar.Combinators
        • Symantic.Parser.Grammar.ObserveSharing
        • Symantic.Parser.Grammar.Optimize
        • Symantic.Parser.Grammar.Production
        • Symantic.Parser.Grammar.View
        • Symantic.Parser.Grammar.Write
      • Symantic.Parser.Machine
        • Symantic.Parser.Machine.Generate
        • Symantic.Parser.Machine.Input
        • Symantic.Parser.Machine.Instructions
        • Symantic.Parser.Machine.Optimize
        • Symantic.Parser.Machine.Program
        • Symantic.Parser.Machine.View

Flags

Manual Flags

NameDescriptionDefault
dump-core

Dump GHC's Core in HTML

Disabled
disable-ormolu-check

Remove ormolu from build-tool-depends. Temporary hack while Nixpkgs' haskellPackages.ormolu remains broken.

Disabled

Use -f <flag> to enable a flag, or -f -<flag> to disable that flag. More info

Downloads

Maintainer's Corner

Package maintainers

For package maintainers and hackage trustees

Candidates

Versions [RSS] 0.0.0.20210101, 0.0.0.20210102, 0.1.0.20210201, 0.2.0.20210703, 0.2.1.20210803
Change log ChangeLog.md
Dependencies array, attoparsec (>=0.13), base (>=4.10 && <5), bytestring (>=0.10), containers (>=0.5.10.1), deepseq (>=1.4), directory (>=1.3), filepath (>=1.4), ghc-prim, hashable (>=1.2.6), megaparsec (>=9.0), pretty (>=1.1), process (>=1.6), strict (>=0.4), symantic-base (>=0.2), symantic-parser, tasty (>=0.11), tasty-golden (>=2.3), template-haskell (>=2.16), text (>=1.2), transformers (>=0.4), unix (>=2.7), unordered-containers [details]
License AGPL-3.0-or-later
Copyright Julien Moutinho <julm+symantic-parser@sourcephile.fr>
Author Julien Moutinho <julm+symantic-parser@sourcephile.fr>
Maintainer mailto:~julm/symantic-parser@todo.hut.sourcephile.fr
Category Parsing
Home page https://git.hut.sourcephile.fr/~julm/symantic-parser
Bug tracker https://todo.hut.sourcephile.fr/~julm/symantic-parser
Source repo head: git clone https://git.hut.sourcephile.fr/~julm/symantic-parser
Uploaded by julm at 2021-08-31T19:22:00Z
Distributions
Downloads 540 total (13 in the last 30 days)
Rating (no votes yet) [estimated by Bayesian average]
Your Rating
  • λ
  • λ
  • λ
Status Docs uploaded by user
Build status unknown [no reports yet]

Readme for symantic-parser-0.2.1.20210803

[back to package description]

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.