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

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...

A new bug

Unfortunately, there are too many projects in this world, and pacc has been neglected for too long. However, I have been looking at one of those other projects recently, in fact, the one that convinced me I needed to write pacc in the first place! A new bug has turned up. (Hooray?) Read More...

See more news articles

feed