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: 2013-11-25 21:05:36 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

  • Release: pacc-0.1 (wōkòu)

    I'm delighted to announce a new release of pacc, the packrat PEG parser generator for C. See the download page. Read More...

  • Tying the loop tighter

    If it seems to have gone quiet around here recently, that's only partly because it's summer, and the lure of the outdoors is stronger than staying in with my head in a chunk of code. I have been gnawing away at a major subproject: converting a real language based on yacc over to pacc. This has been quite an eye-opener! Read More...

See more news articles

feed