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 to be confused with lalr.cl, which doesn't).

While CL-Yacc has undergone no systematic testing, I use it for compiling a grammar for a superset of « C » (over 400 productions) that routinely parses thousands of lines of « C » code.

Features

• Free Software with very liberal redistribution provisions (COPYING);
• 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 does'nt 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.

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

CL-Yacc is also apt-gettable in Debian etch and emergeable in Gentoo. On other systems, it is ASDF-Installable.

(In order to install Cl-Yacc using ASDF-install, please fetch my key using gpg --keyserver subkeys.pgp.net --recv 0x77FF5F3B and check the key's fingerprint against the one at the bottom of my software page. If you don't know what this is about, please see this tutorial.)

You can get my current CL-Yacc tree from my Darcs repository. Type

$ darcs get http://www.pps.jussieu.fr/~jch/software/repos/cl-yacc

Or, if you're a member of the Point and Click Generation, you may grab the latest sources manually.

Back to my software page.

Juliusz Chroboczek