Electronic Review of Computer Books

[ERCB Home]

Slaying the Dragon

Review by Andrew Schulman
Copyright (C) Dr. Dobb's Journal, October, 1992

Is there any programmer who hasn't read the "Dragon Book," the classic text on compiler design by Aho, Sethi, and Ullman? Or tried to read it? Or at least bought it, and placed it in a prominent position on their bookshelf? Certainly, you've at least seen the book: the cover (by Jean Depoian) shows a dragon, representing "Complexity of Compiler Design," about to be slain by a knight with "Data Flow Analysis" armor, a "Syntax Directed Translation" shield, and a "LALR Parser Generator" sword.

You haven't tried to read the Dragon Book? Well, you should. Like every book out of AT&T Bell Labs, it is beautifully written and organized. It is one of those few books that can make you pleased to be involved in software, because while reading the book you come to realize that our field--the messiness of daily practice aside--really does have a solid mathematical foundation. But in my more honest moments, I have to admit that, try as I might, I've never really understood much in the Dragon Book past about page 200 (at least that's where the underlining stops in my copy). The problem, for me at least, is that it's one thing to read about a subject such as the equivalence of languages and machines (a strikingly beautiful discovery) and another thing to really see this equivalence.

For me, and I suspect for a lot of programmers, the only way to illustrate a topic like this is with some code. You say that regular expressions and finite-state machines are equivalent? I can appreciate that this is an important result, but to understand it I need to see some C code that converts a regular expression into a two-dimensional array that forms the program for one of these machines.

This is where Allen Holub's book, Compiler Design in C, comes in. If you have ever wanted to understand how your favorite compiler works, or if you have ever needed to write some form of language processor (perhaps as simple as a text-pattern searcher, or the macro or script language for a product), you will want Holub's book. It is approachable by programmers in a way that the Dragon Book just isn't.

Several good, readily understandable books on compiler design have been available for years. Hendrix's A Small C Compiler (M&T Publishing, 1990), which comes with complete C source code for an 8088-based C compiler, is the best example. You walk away from Hendrix's book seeing exactly how his Small C compiler is put together and feeling that you could "do it yourself."

But real compilers, such as Borland C++ or Microsoft C, aren't built using the readily understandable, recursive-descent technique that Hendrix puts to such good use. These compilers are built, in an initially very nonintuitive way, using compiler-compiler tools such as LEX and YACC. LEX takes a set of regular expressions and associated C code, and turns them into the function yylex(), which tokenizes input (such as your .C file). The C code is essentially "event driven:" It is invoked whenever its associated pattern is recognized in the input. YACC takes a grammar and associated C code, and turns them into the function yyparse(), which parses the tokens generated for example by yylex(). The main() routine for a C compiler might consist of little more than a call to yyparse().

What Holub does in this massive book is amazing. He presents the complete C source code for a LEX clone, two different YACC clones (one of which, Llama, builds a top-down LL(1) parser, while the other, occs--the "other compiler-compiler system" -- builds a bottom-up, LALR(1) parser like that built by (YACC), and a C compiler. The C compiler's source code consists largely, not of .C files, but of a LEX file (c.lex) and a YACC file (c.y). The .C files do symbol-table management, manipulation of lvalues and rvalues, code generation, arithmetic operations, and the like.

DDJ readers may know Holub as this magazine's former C columnist. He brings to Compiler Design in C the same attention to detail found in his earlier The C Companion and On Command (a detailed presentation of the C source code for a command interpreter). Above all, Holub excels at showing how things work. This has always been my favorite kind of reading, escape reading almost. Such "how it works" writing is quite different from "how to" writing. The pleasure is not so much a "Hey, I could do that!" feeling (I know I couldn't), but rather that of seeing a little bit of how the software I use every day actually does its stuff. What's Borland C++ doing when it crunches through my .C files? Having worked through Holub's book, I have a much better idea.

The source code itself is presented in an almost ideal way, with each .C file broken up by just the right amount of text. The order in which code is presented is crucial in a book like this, and Holub has made good use of Arachne, a C preprocessor he wrote. Arachne is a version of Knuth's WEB system (which I discussed in the August 1992 DDJ), allowing source code and documentation to be put together in a single input file. Arachne is itself a compiler and, as Holub notes, it stands as "an example of how you can apply the techniques presented in this book to applications other than writing compilers for standard programming languages." Compiler design is a very general-purpose programming skill.

The chief advantage of Holub's book over the other books on this subject is clearly its skillful presentation of a large amount of C code. But Holub does not just fling gobs of source code at you, as so many programming books do. Many authors discuss the implementation of their programs in loving detail, but forget to describe what the program does, or what output it produces. Revealing the workings of a machine, without disclosing what the machine does, is a classic symptom of engineer's disease. Holub's book doesn't suffer from this at all. He walks the reader through each stage of the compiler process, always remembering to point out what the final goal is, what the program's output will look like, and so on. The C code generated by LEX, Llama, and occs is nicely commented and essentially self-documenting. He constantly shows the input to the program, its output, and exactly how the program turned the former into the latter.

Often, Holub shows the same thing from multiple angles. For example, he presents a regular expression, a hand-written recognizer for that expression, a diagram of the equivalent finite-state machine (FSM) to recognize that expression, a two-dimensional state table representing the machine, and finally the C version of the machine, both compressed and uncompressed, with the driver function that uses the tables. Holub walks carefully through the whole process, showing how a LEX tokenizer can take text such as " 1 + 2 * 3" and turn it into a stream of tokens (input for a Yacc grammar) such as NUM PLUS NUM STAR NUM.

One of the points that becomes clear as you read this book is the tremendous generality of the finite-state machine as a way of programming. In essence, an FSM consists of a two-dimensional table "next," with the rows holding states and the columns holding input. A generic "driver" steps through the table; see Example 1.

The goal of programs like LEX and YACC is to produce the table "next." The driver, which is the while (state = next(state, input)) loop, is generic and changes little between programs. In other words, the "next" table really is a program for a virtual machine.

Since LEX and YACC are themselves just compilers (they compile regular expressions or grammars with associated C code into state tables), it's interesting to see how they themselves are written. Holub builds LEX by hand, using recursive descent. Once you have LEX, you can write LEX.LEX, which would be a table-driven lexical analyzer. Holub leaves this as one of many excellent exercises in the book. (I'm waiting for The Compiler Design in C Answer Book!) With the Llama parser, Holub takes a classic bootstrap approach: First, he uses a LEX file (with plenty of C actions) to implement a scaled-down version of Llama; then he feeds the scaled-down version of Llama with a Llama input file that creates a Llama parser, "like a snake eating its tail."

Even in a book close to a thousand pages long, many topics can't be covered in such complete detail. Many efficiency considerations are avoided by the code, though the text contains good pointers to the relevant literature. The chapter on optimization is a good introduction to this subject, though the C compiler itself is nonoptimizing. Many programmers are interested in compiler optimizations (this, after all, is what compiler benchmarks measure, for want of anything better), but popular topics such as peephole optimization and common-subexpression elimination probably can't be fully understood without first digesting the material in Holub's book.

The code generated by the C compiler is, oddly enough, not 80x86 or 680x0 assembler, much less binary object code, but something called C-Code. This is an assembly language-like form of C. (For example, there are no if ,while, or for statements; everything is reduced to its ultimate goto form.) While it would perhaps have been more satisfying to have the compiler generate actual assembler, C-Code is just as good for this book's purpose.

A disk is not included with the book, but is available separately from the author for $60. I had the usual problems of getting the subdirectories and make files straight, but these seem unavoidable when working with large quantities of someone else's source code, even source code as well commented and well organized as this. In any case, ready-to-run DOS.EXEs are provided. The highlight of this package is a fascinating full-screen "visible" C compiler that shows the compiler's operations. I do wish some screen shots of this program had been included with the book, perhaps instead of the over 50 pages on curses. The full-screen C compiler -- actually it's occs whose operations can be made full-screen, and the C compiler just inherits this like any other occs program -- is built using curses, for which Holub provides a really fairly irrelevant (in this context) description.

Even if you have the commercially supported MKS LEX/YACC, or Gnu FLEX/BISON, you will want to get Holub's book to see how these programs--or at least very similar programs--actually work. The Gnu software comes with source code, but I wouldn't want to tackle it without first having read Holub's book. I had a strange experience after finishing this book. In preparation for this review, I took my copy of the Dragon Book down from the shelf yet again, just to see if it really is such hard going. Oddly enough, I found that I actually understand a lot of it past page 200. Clearly this is because I've worked through Holub's book. If you, too, have been frustrated trying to read the Dragon Book, first read Compiler Design in C (whose cover, incidentally, shows four mice operating some sort of cheese-grater/mailbox contraption). Then try to slay the dragon.

Example 1: Sample FSM.
 while (state = next(state, input))
 if (state == ACCEPT)

Compiler Design in C
Allen J. Holub
Prentice-Hall, 1990
924 pages
ISBN 0-13-155045-4

Dr. Dobb's Electronic Review of Computer Books
Created 5/1/96 / Last modified 6/15/96