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

[ agpl, library, parsing ] [ Propose Tags ] [ Report a vulnerability ]

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]

library symantic-parser

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

library symantic-parser:parsers

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.1), 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]
Tested with ghc ==9.0.1
License AGPL-3.0-or-later
Copyright Julien Moutinho <julm+symantic-parser@sourcephile.fr>
Author Julien Moutinho <julm+symantic-parser@sourcephile.fr>
Maintainer Julien Moutinho <julm+symantic-parser@sourcephile.fr>
Category Parsing
Bug tracker https://mails.sourcephile.fr/inbox/symantic-parser
Source repo head: git clone git://git.sourcephile.fr/haskell/symantic-parser
Uploaded by julm at 2021-07-11T20:03:03Z
Distributions
Downloads 551 total (4 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.0.20210703

[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 a 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.

  • No dependency upon 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) for writing grammar productions, but are experimental, but I do not understand them that much and do not feel confortable to maintain them in case their authors abandon them.

  • No dependency upon dependent-map by keeping observed sharing in def and ref combinators, instead of passing by a DMap. And also when introducing the join-points optimization, where fresh TemplateHaskell names are also directly used instead of passing by a DMap.

  • No support (yet?) for general purpose registers in the Machine producing the TemplateHaskell splices. Hence symantic-parser generates parser much slower than ParsleyHaskell, comparable to attoparsec in the Brainfuck benchmark.

  • License is AGPL-3-or-later not BSD-3-Clause.

  • 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 using automatic transformations, see Symantic.Typed.Trans.

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