Symparsec
Type level string (Symbol) parser combinators. Reify to runtime parsers with
guaranteed identical behaviour.
It's a Parsec-like for Symbols; thus, Symparsec.
Previously named symbol-parser.
Requires GHC 9.6 for singling parsers.
Features
- Define parsers compositionally, largely as you would on the term level.
- Pretty parse errors.
- Hopefully decent performance.
- Reify parsers to term level with guaranteed identical behaviour via a
healthy dose of singletons.
Examples
ghci> import Symparsec
ghci> :k! Run (Drop 3 :*>: Isolate 2 NatDec :<*>: (Drop 3 :*>: NatHex)) "___10___FF"
...
= Right '( '(10, 255), "")
Why?
Via GHC.Generics, we may inspect Haskell data types on the type level.
Constructor names are Symbols. Ever reify these, then perform some sort of
checking or parsing on the term level? Symparsec does the parsing on the type
level instead. Catch bugs earlier, get faster runtime.
Design
The parser
A parser is a 4-tuple of:
- a consuming character parser; given a character and a state, returns
Cont s: keep going, here's the next state s
Done r: parse successful with value r
Err E: parse error, details in the E (a structured error)
- an end handler, which takes only a state, and can only return
Done or Err
- an initial "raw" state
- a state initializer, which turns the initial "raw" state into the first state
value (the indirection here assists singling)
Running a parser is simple:
- initialize state
- parse character by character until end of input, or
Done/Err
Parsers may not communicate with the runner any other way. This means no
backtracking, chunking etc. This is a conscious decision, made for simplicity.
Note that due to character parsers being consuming, we often need to do a bit of
"internal lookahead", where we check if we expect to consume any more
characters, and if not then emit a Done. It also means that non-consuming
parsers such as Take 0 are invalid for non-empty strings. The state
initializer should be used to catch such cases.
This is a rough overview of parser design. See the code and/or Haddock
documentation for precise details.
Pitfall: Character parsers always consume
There is no backtracking or lookahead, that you do not implement yourself. This
keeps the parser execution extremely simple, but breaks null parsers such as
Drop 0, so these must be handled specially (unless you don't getting mind
stuck type families on misuse).
For concrete examples, see the implementation of Drop and Literal.
Pitfall: Not all parsers are definable
- No changing parser state. Thus, parsers such as
Try :: Parser s r -> Parser (s, [Char]) r are not definable. Parsers may not backtrack.
- Combinators such as
<|> can emulate backtracking, but they are complex and
hard to reason about (they may have bugs!).
Feature: Parsers may be reified to use at runtime, with guaranteed same behaviour
TODO
Contributing
I would gladly accept further combinators or other suggestions. Please add an
issue or pull request, or contact me via email or whatever (I'm raehik
everywhere).
License
Provided under the MIT license. See LICENSE for license text.
