typed-peg

Type-safe PEG (Parsing Expression Grammar) parser combinators for Haskell.

Grammar non-terminals are indexed at the type level by their nullability and FIRST sets, so left-recursive grammars are caught at compile time rather than looping at runtime.

Features

• Type-level FIRST-set and nullability tracking
• Compile-time left-recursion detection (type error)
• Indentation-sensitive parsing (PEG.Indent)
• Quasi-quoter for concrete grammar syntax (PEG.QQ)
• Parses any PEG.Stream: String, strict/lazy Text, strict/lazy ByteString

Input streams

A grammar is written once and runs over any stream:

import qualified Data.Text as T

parse arith "1+2*3"              -- Result String Exp
parse arith (T.pack "1+2*3")     -- Result Text   Exp

Character classes produce a chunk of the stream, not a [Char]: matching [a-z]+ against a Text yields a Text slice and copies nothing. Semantic actions that want a String ask for one:

number <- ds:[0-9]+   { Lit (read (chunkToString ds)) }
strlit <- '"' cs:[^"]* '"'   { cs }     -- :: s, no copy

Only unconsS has no default, so adding a stream is one method.

ByteString is read as Latin-1, like Data.ByteString.Char8: fast and correct for ASCII, wrong for multi-byte UTF-8. Decode to Text if that matters.

A Grammar is monomorphic in its stream. To reuse one across several, give it a forall s. Stream s => Grammar s Env _ A signature — but note that makes it a function of a dictionary, so the compiled parser is no longer shared between calls. Bind a monomorphic parser where that matters:

arithString :: String -> Result String Exp
arithString = parse arith
{-# NOINLINE arithString #-}

Quick start

import PEG

-- Define a grammar using the quasi-quoter
-- See examples/Arith.hs for a complete arithmetic expression parser

Grammar size

The nullability and FIRST set of every rule are computed by GHC while it type-checks the grammar, so a grammar's size shows up as compile time. A FIRST set is a type-level list of non-terminal names kept in alphabetical order:

type CalcEnv =
  '[ '("expr" , 'EnvEntry ('MkTy 'False '["atom", "term", "unary"]) Expr)
   , '("term" , 'EnvEntry ('MkTy 'False '["atom", "unary"])         Expr)
   , '("unary", 'EnvEntry ('MkTy 'False '["atom"])                  Expr)
   , '("atom" , 'EnvEntry ('MkTy 'False '[])                        Expr)
   ]

The order is not cosmetic. It gives a set exactly one spelling, which is what lets the union of two FIRST sets be a single merge pass; listing one in some other order is a type error naming the first position that disagrees.

That merge nests one type-family reduction per element of the result, so a grammar with a FIRST set of more than about a hundred non-terminals hits GHC's default reduction limit and reports Reduction stack overflow. Add -freduction-depth=0 to ghc-options if you get there; it is a limit rather than a slowdown, and a union of two 128-element sets takes about 0.3 s once it is lifted.

Patterns

peg-patterns.md works through patterns for specifying languages with PEGs and this library, following Willis and Wu's Design Patterns for Parser Combinators (Haskell 2021) and noting where a PEG differs — committed choice, left recursion as a type error, keywords as negative lookahead — and where typed-peg cannot yet follow. Every fragment in it compiles, in examples/Patterns.hs.

Building

cabal build

Examples

cabal test typed-peg-examples

Benchmarks

bench/ holds a criterion suite that measures typed-peg against megaparsec on seven grammars (arithmetic expressions, CSV, identifier lists, a mini JSON, deeply nested parentheses, and quoted strings spelled two ways) written twice, rule for rule. Both libraries consume byte-identical inputs, and the suite cross-checks that they produce the same result before timing anything.

cabal bench

cabal bench --benchmark-options=--alloc prints bytes allocated per parse instead of running criterion; allocation is the number that separates the two libraries most clearly once the algorithmic differences are gone.

On GHC 9.10.3 against megaparsec 9.8.1, bytes allocated per input byte on the largest input of each group:

ByteString is the cheapest column on five of the seven grammars and beats megaparsec on six. Text costs more than String throughout — the same result the study found for megaparsec, so reach for it for interoperability rather than for speed.

Allocation is deterministic and reproduces exactly. Time is the noisier measurement: on a machine with heterogeneous cores, unpinned runs of the same megaparsec binary varied by up to 1.8x, so only the ratio taken within one run is meaningful.

The reference implementation is Bench.Peg; its megaparsec twin is Bench.Mega. Since PEG ordered choice backtracks unconditionally while megaparsec's <|> does not, every megaparsec alternative that can consume input before failing is wrapped in try, so the two are recognising the same language.

Parsing many inputs

parseWith opts grammar traverses the grammar and returns a compiled closure. Bind it once and reuse it, rather than calling parse grammar input inline in a loop:

myParser :: String -> Result Exp
myParser = parse myGrammar

License

BSD-3-Clause. See LICENSE.