Dragon Book Compiler Design

[Geraldine Ferraiz]

CompilersPrinciples, Techniques, and Tools[1] is a computer science textbook by Alfred V. Aho, Monica S. Lam, Ravi Sethi, and Jeffrey D. Ullman about compiler construction for programming languages. First published in 1986, it is widely regarded as the classic definitive compiler technology text.[2]

It is known as the Dragon Book to generations of computer scientists[3][4] as its cover depicts a knight and a dragon in battle, a metaphor for conquering complexity. This name can also refer to Aho and Ullman's older Principles of Compiler Design.

The first edition (1986) is informally called the "red dragon book" to distinguish it from the second edition[5] and from Aho & Ullman's 1977 Principles of Compiler Design sometimes known as the "green dragon book".[5]Topics covered in the first edition include:

Following in the tradition of its two predecessors, the second edition (2006) features a dragon and a knight on its cover, and is informally known as the purple dragon. Monica S. Lam of Stanford University became a co-author with this edition.

In order to cover recent developments and issues, there is an updated second edition from Pearson Education India (4 July 2023), with contributions from Sorav Bansal. This revised and updated edition has new chapters on Programming Language Semantics and Undefined Behaviour Semantics.

This question pertains only to a specific site in the Stack Exchange Network. Questions on Meta Stack Exchange should pertain to our network or software that drives it as a whole, within the guidelines defined in the help center. You should ask this question on the meta site where your concern originated.

If you find yourself in this position, please recommend "Engineering a Compiler" by Keith Cooper/Linda Torczon, or "Modern Compiler Implementation in X" (where X should probably be Java, maybe C), by Andrew Appel. These are excellent introductions to compiler for beginners.

The Dragon Book is a very thorough book, with detailed discussion of theory (especially about parsing). However, this level of detail and theory does not make it a good introductory book. In contrast, the books above present very clearly how to build a compiler, avoiding theory where it is not useful. This makes them superior recommendations for beginners.

The full solution to the problem is don't recommend books you haven't read just because you saw someone else recommend them 20 years ago. Let someone who actually knows the field and has read the books recommend something instead. This is a classic example of people jumping to get rep by just pasting in a standard answer that they actually know nothing about.

Make your own suggestions and if you don't agree with others, vote them down and maybe people will start to see your way. There is nothing wrong with what they are doing in making their suggestions for the book.

While the Dragon Book is certainly very thorough, it is not very clear, or easy to learn from. That was probably acceptable in 1986, or whenever you read it way back when, but there are actual good compiler books now, especially for beginners.

I kinda get your point, it's like people recommending the Knuth books to someone wanting to get started with programming. Whilst iconic, the Knuth books are not the best place to kick things off for a beginner.

Then on each question where you disagree with the recommendation of "the dragon book" post a summary of your conclusions that are relevant to the particular question, (a link to the full review if it's too long to fit nicely in the answer), and your recommendation of your preferred book. Users tend to like answers that have taken the time to explain in detail the pros and cons of both sides. Others will see your review, and perhaps if it is good and people agree they will also link to it. Perhaps others interested in the area will take time to read both books and draw their own conclusions, and up vote your answer.

I saw this same kind of thing with an Operating Systems class in my undergrad degree. The book assigned by the professor was one of the more popular OS books. Very dry, to the point, and was not aimed at beginners. It was still a great book though and an excellent class choice. It was not an easy book for people to start with, but it was still a great resource.

That doesn't make it a bad recommendation in any way though. Lots of CS books tend to not be beginner friendly. They are advanced topics and require a vast array of knowledge to comprehend and understand well.

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 triedto read it? Or at least bought it, and placed it in a prominent positionon their bookshelf? Certainly, you've at least seen the book: the cover(by Jean Depoian) shows a dragon, representing "Complexity of CompilerDesign," about to be slain by a knight with "Data Flow Analysis"armor, a "Syntax Directed Translation" shield, and a "LALRParser Generator" sword.

You haven't tried to read the Dragon Book? Well, you should. Like everybook 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 insoftware, because while reading the book you come to realize that our field--themessiness of daily practice aside--really does have a solid mathematicalfoundation. But in my more honest moments, I have to admit that, try asI might, I've never really understood much in the Dragon Book past aboutpage 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 asthe 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 illustratea topic like this is with some code. You say that regular expressions andfinite-state machines are equivalent? I can appreciate that this is an importantresult, but to understand it I need to see some C code that converts a regularexpression into a two-dimensional array that forms the program for one ofthese 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 (perhapsas simple as a text-pattern searcher, or the macro or script language fora product), you will want Holub's book. It is approachable by programmersin a way that the Dragon Book just isn't.

Several good, readily understandable books on compiler design have beenavailable 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 howhis Small C compiler is put together and feeling that you could "doit yourself."

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

What Holub does in this massive book is amazing. He presents the completeC 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 "othercompiler-compiler system" -- builds a bottom-up, LALR(1) parser likethat built by (YACC), and a C compiler. The C compiler's source code consistslargely, 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 bringsto Compiler Design in C the same attention to detail found in hisearlier The C Companion and On Command (a detailed presentationof the C source code for a command interpreter). Above all, Holub excelsat showing how things work. This has always been my favorite kind of reading,escape reading almost. Such "how it works" writing is quite differentfrom "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 seeinga 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 workedthrough Holub's book, I have a much better idea.

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

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

Often, Holub shows the same thing from multiple angles. For example, hepresents a regular expression, a hand-written recognizer for that expression,a diagram of the equivalent finite-state machine (FSM) to recognize thatexpression, a two-dimensional state table representing the machine, andfinally the C version of the machine, both compressed and uncompressed,with the driver function that uses the tables. Holub walks carefully throughthe 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 tremendousgenerality of the finite-state machine as a way of programming. In essence,an FSM consists of a two-dimensional table "next," with the rowsholding 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 genericand 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 expressionsor grammars with associated C code into state tables), it's interestingto see how they themselves are written. Holub builds LEX by hand, usingrecursive descent. Once you have LEX, you can write LEX.LEX, which wouldbe a table-driven lexical analyzer. Holub leaves this as one of many excellentexercises in the book. (I'm waiting for The Compiler Design in C AnswerBook!) 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-downversion of Llama; then he feeds the scaled-down version of Llama with aLlama input file that creates a Llama parser, "like a snake eatingits tail."

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

The code generated by the C compiler is, oddly enough, not 80x86 or 680x0assembler, much less binary object code, but something called C-Code. Thisis 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.) Whileit would perhaps have been more satisfying to have the compiler generateactual 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 theauthor for $60. I had the usual problems of getting the subdirectories andmake files straight, but these seem unavoidable when working with largequantities of someone else's source code, even source code as well commentedand 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 shotsof this program had been included with the book, perhaps instead of theover 50 pages on curses. The full-screen C compiler -- actually it's occswhose operations can be made full-screen, and the C compiler just inheritsthis like any other occs program -- is built using curses, for which Holubprovides 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 leastvery similar programs--actually work. The Gnu software comes with sourcecode, but I wouldn't want to tackle it without first having read Holub'sbook. I had a strange experience after finishing this book. In preparationfor this review, I took my copy of the Dragon Book down from the shelf yetagain, just to see if it really is such hard going. Oddly enough, I foundthat I actually understand a lot of it past page 200. Clearly this is becauseI've worked through Holub's book. If you, too, have been frustrated tryingto read the Dragon Book, first read Compiler Design in C (whose cover,incidentally, shows four mice operating some sort of cheese-grater/mailboxcontraption). Then try to slay the dragon.

Example 1: Sample FSM. STATE next[NUM_STATES][NUM_INPUTS]; while (state = next(state, input)) if (state == ACCEPT) brake; else do_action(state);

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

Back to top

3a8082e126