typed-peg

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

Grammar non-terminals are checked at the type level — a reference is a key whose type is the result of the rule it names — and left-recursive grammars are caught when the grammar is written rather than looping at runtime. Checking a grammar costs GHC time and memory linear in its size: a 1024-rule grammar type-checks in about a second.

Features

• Non-terminal references checked at the type level
• Left recursion, a repetition that cannot consume input, an undefined non-terminal and a duplicate rule reported at the splice, naming the rule
• 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 s) 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
import PEG.QQ (pegGrammar)

data Exp = Lit Int | Add Exp Exp | Mul Exp Exp

[pegGrammar|
  %name  arith
  %start expr

  expr   :: Exp <- t:term ts:(o:[+] u:term)*     { foldl addOp t ts }
  term   :: Exp <- f:factor fs:(o:[*] g:factor)* { foldl addOp f fs }
  factor :: Exp <- n:number / '(' e:expr ')'
  number :: Exp <- ds:[0-9]+ { Lit (read (chunkToString ds)) }
|]

That declares the grammar's key type, one constructor per rule,

data ArithEnv s a where
  ArithEnv_expr   :: ArithEnv s Exp
  ArithEnv_term   :: ArithEnv s Exp
  ...

a binding per rule (arith'expr :: Stream s => PExp s (ArithEnv s) Exp, ...), and arith :: Stream s => Grammar s (ArithEnv s) Exp. Run it with parse arith "1+2*3". The module needs GADTs.

A rule's result type is the one thing the grammar does not determine — it comes from the Haskell in the semantic action — which is what the :: T annotations are for. They are claims, and GHC checks them: each is the signature of that rule's binding, so an annotation that disagrees with what the body returns is a type error reported against the rule.

A grammar that needs a value from outside — a file name for error positions, a table of operators — takes it as a parameter:

[pegGrammar|
  %name   lang
  %stream String
  %param  file :: FilePath
  %start  program
  ...
|]
-- lang :: FilePath -> Grammar String (LangEnv String) Program

pegRules remains, for a rule set that is only part of a grammar or that is combined with hand-written PExp combinators. Its non-terminals are a type-level list written out by hand, and the grammar is a Grammar s (InEnv env) a; examples/Compat.hs and examples/Patterns.hs show that style. See examples/Arith.hs, examples/Layout.hs and examples/MiniPython.hs for the generated one.

Grammar size, and what is checked where

A grammar's size shows up as compile time, because every reference in it is a constraint GHC has to solve. How much each one costs depends on what the reference points into.

A declared key type — what pegGrammar generates — makes a reference a constructor, NT ArithEnv_term, whose type GHC checks without looking at the rest of the grammar. The cost is linear in the number of rules (ghc -fno-code, GHC 9.10; bench-compile/):

The 27-rule MiniPython grammar in examples/ takes 0.43 s and 57 MiB.

A type-level list is what nt @"expr", pegRules and pegGrammar in expression position use. A reference carries a proof of where its rule sits in the list, There (There Here), and GHC's evidence for it grows with the rule's depth and the size of the list, so the total grows faster than the grammar. An entry of that list is a rule's name and the type it returns:

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

Entries used to carry more: each rule's nullability and its FIRST set, the non-terminals that can begin it. That is what made left recursion a type error — an Acyclic constraint checked that no rule was in its own FIRST set — and it was also, measurably, the entire cost of compiling a large grammar. A FIRST set grows with the grammar, so the environment was quadratic in the number of rules, and each of the two reference constraints per rule was solved against the whole of it. Removing it took a 64-rule grammar from 15 s to 2 s, and a 128-rule one from more than two minutes to 5 s. bench-compile/ has the measurements.

Nullability and FIRST sets are still computed — by PEG.Analysis, in ordinary Haskell, when the quasi-quoter runs, in time linear in the grammar. It is what reports left recursion, a nullable repetition, an undefined non-terminal or a duplicate rule from the splice, naming the rule and the chain of head references that closes the cycle:

Arith.hs:8:13: error: [GHC-39584]
    • pegRules:
      left-recursive non-terminal: expr
        the cycle is expr -> term -> factor -> expr
        a PEG cannot backtrack into a committed choice, so this rule
        would not consume input before calling itself

A PEG does not memoise, so A B / A C parses A twice when B fails. The quasi-quoters factor such alternatives into A (B / C) when they are consecutive, which keeps a grammar whose precedence levels are written that way linear in the input rather than exponential in its nesting.

So the checks divide like this:

The second half of that table is the trade. A Rules chain assembled by hand from RCons, without a quasi-quoter, is checked for reference errors only: a rule that begins with itself compiles and loops. And pegRules analyses its block open-world, since two blocks can be combined, so left recursion that closes across two blocks is reported by neither it nor GHC. Writing the grammar as one pegGrammar closes both gaps — it is closed-world, so every reference resolves and every cycle is visible — and it is also the fastest to compile, because it declares a key type instead of a list.

Since nothing recomputes what PEG.Analysis concludes, the typed-peg-analysis test-suite checks it against a separate statement of what nullability and a FIRST set mean, over the grammars in examples/ and a few hundred generated ones.

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.