The Packrat Parsing and
Parsing Expression Grammars Page
Introduction
Parsing expression grammars (PEGs) are
an alternative to context free grammars for formally specifying syntax, and
packrat parsers are parsers for PEGs
that operate in guaranteed linear time through the use of memoization.
For a brief technical summary see
the Wikipedia entry on PEGs.
For more in-depth descriptions see
the original PEG paper
and related papers below.
Bryan Ford, the maintainer of this site,
coined the modern terms PEGs and packrat parsing,
but much of their formal theory existed earlier
and all the more recent work on this topic is by others.
Mailing List
The following mailing list is open to anyone
wishing to announce software or papers related to PEGs and packrat parsing,
or discuss ideas and issues:
The PEG Mailing List
PEG/Packrat Parsing Bibliography
The following research papers
develop and explore PEGs and packrat parsing in detail;
most were written by various authors working independently.
The papers are listed chronologically starting from most recent.
Some of the papers have associated code available online.
- Alessandro Warth,
James R. Douglass, and
Todd Millstein,
Packrat parsers can support left recursion.
Workshop on Partial Evaluation and Program Manipulation (PEPM '08),
January 2008.
Describes a general method of extending the PEG model
to support left recursion.
- Ralph Becket and
Zoltan Somogyi,
DCGs + Memoing = Packrat Parsing: But is it worth it?
Practical Aspects of Declarative Languages (PADL '08),
January 2008.
Explores implementation of packrat parsers
in logic programming languages such as Prolog and Mercury.
- Alessandro Warth and
Ian Piumarta,
OMeta: an Object-Oriented Language for Pattern Matching (PDF).
Dynamic Languages Symposium, October 2007.
Presents an extension of PEGs to support
pattern matching of arbitrary structured data
and object-oriented extensibility features.
- Chris Seaton,
A Programming Language Where the Syntax and Semantics
Are Mutable at Runtime
(PDF).
Master's thesis, University of Bristol, May 2007.
Develops Katahdin, a dynamically extensible language
based on PEGs and packrat parsing,
implemented in C#
on Mono.
- Roman Redziejowski,
Parsing Expression Grammar as a primitive recursive-descent parser
with backtracking
(PDF).
CS&P'2006 Workshop.
Explores the implementation of practical parsers defined via PEGs
using little or no memoization.
- Sylvain Schmitz,
Modular Syntax Demands Verification (PDF).
Tech Report I3S/RR-2006-32-FR, Laboratoire I3S,
Université de Nice - Sophia Antipolis,
October 2006.
Develops techniques for analyzing CFGs for ambiguity
and PEGs for disjointness/commutivity of alternatives.
- Robert Grimm,
Better Extensibility through Modular Syntax (PDF).
PLDI, June 2006.
Describes
Rats!,
a practical packrat parsing system
supporting modular and extensible syntax based on PEGs.
- Bryan Ford,
Parsing Expression Grammars:
A Recognition-Based Syntactic Foundation
(PDF).
POPL, January 2004.
Defines PEGs, a theoretical foundation for grammars
more suitable for packrat parsing than context-free grammars
and at a higher level than Birman's TDPL (see below).
- Bryan Ford,
Packrat Parsing:
Simple, Powerful, Lazy, Linear Time
(PDF).
ICFP, October 2002.
Introduces packrat parsing and how to implement it
using the lazy functional programming language Haskell.
Includes working example packrat parsers in Haskell.
- Bryan Ford,
Packrat Parsing:
a Practical Linear-Time Algorithm with Backtracking
(PDF).
Master's thesis, MIT, September 2002.
A more in-depth exploration of
Top-Down Parsing Language (TDPL) and packrat parsing.
Includes a prototype packrat parser compiler-compiler for Haskell,
and various examples including a full Java syntax specification.
- Alexander Birman and Jeffrey D. Ullman,
Parsing algorithms with backtrack.
Information and Control, 23(1):1-34, August 1973.
The original formal theory behind packrat parsing
and parsing expression grammars.
Apparently not available on-line.
- Alexander Birman,
The TMG Recognition Schema (PDF).
Ph.D. dissertation, Princeton, February 1970.
Less readable than the above journal paper,
but available here.
Very large: 24MB scanned PDF!
Projects
The following projects have implemented PEG parsers, parser generators,
and/or combinator libraries in a variety of languages:
Maintainer: Bryan Ford.
Additions or corrections to this page are welcome.