CL-Yacc — a LALR(1) parser generator for Common Lisp

CL-Yacc is a LALR(1) parser generator for Common Lisp, similar in spirit to AT&T Yacc, Berkeley Yacc, GNU Bison, Zebu, lalr.cl or lalr.scm.

CL-Yacc uses the algorithm due to Aho and Ullman, which is the one also used by AT&T Yacc, Berkeley Yacc and Zebu. It does not use the faster algorithm due to DeRemer and Pennello, which is used by Bison and lalr.scm (not lalr.cl).

CL-Yacc was originally written to compile a grammar for a superset of the C programming language (over 400 productions) that used to routinely parses thousands of lines of C code. (Since then, the code has been rewritten in Caml by Gabriel Kerneis — see CPC.)

Features

• Free Software with very liberal redistribution provisions;
• a single file that you are welcome to distribute with your application;
• reasonable (but not outstanding) performance;
• support for ambiguous grammars (operator precedence and associativity).

CL-Yacc is portable ANSI Common Lisp, and has been successfully tested with CMUCL, SBCL, CLISP, CCL (OpenMCL), ECL and Lispworks. A minor tweak is needed to make it work under Genera. It does not work with GCL, which doesn't grok MAKE-LOAD-FORM.

Compile-time performance is reasonable, although not outstanding: on a Pentium-M at 1.4GHz, compiling a grammar with over 400 productions, 19 conflicts, and a lot of useless shifting takes 9s with CMUCL, 16s with Lispworks, 40s with CLISP. On the same machine, Zebu compiles that grammar in slightly over 4s with CMUCL.

Missing features

CL-Yacc is complete as far as I am concerned: it does what I need, and does it fast enough on my machine. If you're using CL-Yacc, I'd be glad to hear about any features you might be missing.

Here's a list of things that I would like to do:

• error recovery (doing something reasonable on parse failures);

Here's a list of features that users have suggested but that I will probably not implement:

• a mode of operation in which a portable parser is generated that does not use anything in the YACC package (one user has argued that this will allow him to avoid distributing CL-Yacc with his application);
• a convenient syntax for repetitions and optional syntax: you can do that quite easily with additional rules;
• a syntax for overriding operator precedence on a per-rule basis: you can do that quite easily with additional rules.

Documentation

Read the CL-Yacc manual (PDF version).

A full example of a parser written with CL-Yacc can be found in the file calculator.lisp in the CL-Yacc distribution.

Download

Please note: there are a number of patched versions of CL-Yacc floating around the net. Most of them are buggy. Please do not send me any bug reports unless you are sure that your sources come from me.

A tarball of the CL-Yacc sources should be available in my download area.

You can get my CL-Yacc tree by doing

git clone https://github.com/jech/cl-yacc

or browse the source on GitHub.

Juliusz Chroboczek