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: 2014-07-07 18:44:01 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

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

Feeding finale

That was almost too easy. It took just a few minutes to implement $ as new syntax to indicate feeding points (the new node type in the AST is called cafe), then update the cooker, eat a few test cases, and wash up by removing the -r option. Read More...

See more news articles

feed