pacc - a compiler-compiler

git clone git://paccrat.org/pacc

pacc is a compiler-compiler, somewhat like yacc (or bison). Its input is a description of a grammar, and its output is a C function that recognizes strings of that grammar. The significant technical difference is this: yacc reads a context-free grammar (CFGs), and writes a LALR(1) parser; pacc reads a parsing expression grammar (PEG), and writes a packrat parser.

PEGs and packrat parsing offer several advantages over CFGs.

• There is no need for a two-level structure, with a separate lexer (this is essentially a misfeature of CFGs - they are unable to express standard tokenization rules naturally).
• PEGs can “look ahead” in the input as far as they need to. Here is a look-ahead example.
• Despite arbitrary look-ahead, packrat parsers are linear in time and space complexity: O(n) in the size of the input (whereas LALR(1) parsers are O(n²), and fully general CFG parsing is O(n³)).
• PEGs are easy to understand, and pleasant to work with.

The first release of pacc is now available under the GPL. This is an alpha release. The intention is that pacc will mature to be an industrial-strength parser-generator.

pacc is a recursive acronym: pacc: a compiler-compiler. Needless to say, pacc's own parser is written in pacc.