pacc logo

pacc — a compiler-compiler

pacc-0.1 released!

November 2013: a new release of pacc is now available for download.

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.
  • 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 second release, pacc-0.1 (wōkòu) is now available under the GPL. This is an beta 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.

Last updated: 2015-05-24 19:45:30 UTC

Donate

Support the development of pacc with a donation! We accept donations in BitCoin or via PayPal who handle almost any other form of payment.

News

Users

One thing that pacc has lacked all the way along is users. It turns out to be really hard to write decent code without those darned users probing the dark corners. Read More...

Default expressions

I finally got round to implementing a simple but highly useful feature in the language, which I'm calling default expressions. It's probably simplest to explain by showing the test case: Read More...

See more news articles

feed