From: crowl@jade.CS.ORST.EDU (Lawrence Crowl)
Subject: Summary: Compiler Textbooks
Reply-To: crowl@jade.CS.ORST.EDU (Lawrence Crowl)
Organization: Computer Science Department, Oregon State University
Date: Fri, 22 Jan 1993 00:25:58 GMT
Keywords: books, courses, summary

I recently asked this newsgroup to send me recommendations for an
undergraduate compilers textbook.  This posting contains the edited
responses, both from news and mail.  I have also listed some texts we had
lying around.  They have no reviews.

  Steve Lembark <LEMBARK@sysjj.ug.eds.com> writes:

    quick way to get a list of them: call OpAmp Tech. Books and ask for
    their catalog.  If its in print they've got it.  their number is
    +1 800 468 4322.  no, i don't work there.

In addition, Kurt M. Bischoff of Iowa State University sent information
about the Ox attribute grammar compiling system, which may be suitable for
use in a course.  I appended his messages (edited) to the end of this
post.

  Lawrence Crowl		503-737-2554	Computer Science Department
			   crowl@cs.orst.edu	Oregon State University
	      ...!hplabs!hp-pcd!orstcs!crowl	Corvallis, Oregon,  97331-3202

-----------------------------------------------------------------------

Alfred V. Aho, Ravi Sethi, and Jeffrey D. Ullman, "Compilers:
Principles, Techniques, and Tools", Addison Wesley, ISBN
0-201-10088-6.

  Recommended by Kbvelama@top.cis.syr.edu.
  Recommended by Adam Goldberg <adam@microware.com>.

  Manny Powers <mpowers@Bonnie.ICS.UCI.EDU> writes:

    I am an undergraduate at UC Irvine.  Our professor used [Aho,
    Sethi, and Ullman].  This book was packed with a tremendous amount
    of information (we went through 12 chapters in one quarter).  It
    explained subjects very well (although it did get kind of dry once
    in awhile).  Overall I thought it was an excellent book for this
    class.

P. J. Brown, "Writing Interactive Compilers and Interpreters", Wiley,
1979, ISBN 0-471-27609-X (hardbound?), reprinted 1985 ISBN
0-471-10072-2 (paper).

  Recommended by TDARCOS@MCIMAIL.COM (Paul Robinson).

  (John Levine) writes:

    This is a great book, but it ... is long out of print.  If anyone
    can find a source for it, I'd like a copy myself.  [I was mistaken,
    it's still in print in paperback. -John]

  tfj@apusapus.demon.co.uk (Trevor Jenkins) writes:

    This is one of the few books that addresses real implementation
    issues.

    P J Brown has a good writing style, one of the best bits of the
    book is the "Deadly Sins". A list of aphorisms (much like those in
    "Elements of Programming Style" *) dedicated to the compiler
    (interpreter) writer.

  thutt <thutt@MAIL.CASI.NASA.GOV> writes:

    If the book, "Writing Interactive Compilers and Interpreters" in
    paperback form from Wiley is the one that implements a Pascal
    compiler and Pascal interpreter for the 8086 chip, it is truly so
    full of errors in the actual code (generated code as well as the
    compiler itself) as to make it almost useless.

    The practical approach that is taken really leaves a lot out
    (explanation), and the descriptions of the code do not correspond
    very well to the published source.

    (If I have confused the above book, then I apologize.  I am sorry I
    bought the book I did, whatever it is.)

Fischer and LeBlanc, "Crafting a Compiler" (Ada version).

  Recommended by miller@diego.llnl.gov (Patrick Miller).

  mfeldman@seas.gwu.edu (Michael Feldman) writes:

    The language being compiled is a decent Ada subset; the language of
    discourse of the book is Ada. That will get your students started
    very nicely!

  crigler@osceola.cs.ucf.edu (James Crigler) writes:

    When I took the compiler course here, we used the book Prof. Mike
    mentions and I didn't like it.  Caveat: We were using lex/yacc to
    create a compiler, which is, of course (:-) the opposite approach
    to parsing.  (Since I had the class they've gone back to using the
    Dragon book :-) but I can't afford a copy :-(

  robichau@lambda.msfc.nasa.gov (Paul Robichaux) writes:

    Here's a vote _for_ Fischer/LeBlanc. It's the text for the
    undergrad compiler course at Georgia Tech, and the class project
    usually revolves around building a compiler, using a Pascal-ized
    lex/yacc suite for the parser and Pascal for the remainder.

    IMHO the discussion and description in the Ada version of LeBlanc
    is more clear and more appropriate for undergrad courses than the
    dragon book.  YMMV.

  mfeldman@seas.gwu.edu (Michael Feldman) writes:

    ... Fischer/LeBlanc is the only compiler book acknowledging Ada as
    a suitable language in which to write a compiler. ...

    Fischer/LeBlanc provides a lot of very useful code segments,
    procedures, packages, etc., for "Crafting a Compiler" in Ada. The C
    version of their book does the same with C, though the language
    being compiled is _still_ an Ada subset.

    [Refering to James Crigler's comments.]  In my opinion, your
    professor did you a disservice by requiring a book that (1) used
    Ada as the language of discourse and (b) focused on hand-coding a
    compiler, then gave you a project in which you used lex/yacc/C to
    do the actual work. That caused too much "dissonance" and,
    naturally, you had an unpleasant experience. Probably soured you on
    Ada, too.

  Jim Clausing <jac@cis.ohio-state.edu> writes:

    I have had tremendous success with _Crafting a Compiler_ (or
    _Crafting a Compiler in C_, if you prefer C to Ada, though frankly
    I used the Ada version even when teaching the course in Pascal).

  eigenstr@cs.rose-hulman.edu (Todd Eigenschink) writes:

    Our compilers course at Rose-Hulman (targeted for seniors, but
    there's really no restriction) used 'Crafting a Compiler' by
    Fischer and LeBlanc last winter.  I consider myself a fairly bright
    student and didn't have any problems with it at all.  It's not as
    technical as, say, the dragon book, but it covered topics
    adequately (especially considering it's only a 10-week course and
    we had to actually _write_ a compiler).

Fischer and LeBlanc, "Crafting a Compiler" (C version).

  moss@CRAFTY.FOX.CS.CMU.EDU (J. Eliot B. Moss) writes:

    We have been using the Fischer and LeBlanc text (Crafting a
    Compiler, C edition). While every text has its problems, this one
    workes well for a project oriented course.

  arnold@cc.gatech.edu (Arnold Robbins) writes:

    It is much more code-oriented than most books, which makes things
    more solid and easier to grasp.  I did the work to translate the
    original Ada code in "Crafting A Compiler" into C for that book,
    and as a result had to read the book *very* closely; doing so gave
    me an appreciation for how good a book it is.

Holub, "Compiler Design in C"

  hernandz@edmund.cs.andrews.edu (Aldy Hernandez) writes:

    I think the best "textbook" for a compiler class is Holub's
    "Compiler Design in C." (I repeat.... I THINK!)

    It goes over most of the theory and implements all of the theory
    presented.  The book has received very good reviews from almost
    everyone, including "Dr. Dobb's Journal".  It implements most of
    what other compiler textbooks have left out.  Things like
    structures, unions, typedefs, etc.  The author implements a
    workable version of YACC, LEX, and a C compiler.

    Most importantly (to me) is that, when the author's algorithms
    aren't the best, he points you to "good" algorithms in Aho's book
    (or others).

  zell@SEAS.UCLA.EDU (Adam W. Zell) writes:

    a little bit too hackish in the code, for my taste

Robin Hunter, "Compilers: Their Design and Construction Using Pascal",
John Wiley and Sons, 1985, ISBN 0-471-90720-0.

Karen A. Lemone, "Design of Compilers: Techniques of Programming Language
Translation", CRC Press, 1992, ISBN 0-8493-7342-5.

Thomas W. Parsons, "Introduction to Compiler Construction", W. H. Freeman
and Company, 1992, ISBN 0-7167-8261-8.

  Recommended by tm@netcom.com (Toshiyasu Morita).

  James Wilkinson <wilkins@cs.cofc.edu> writes:

    I like the book by Parsons, but I haven't actually _used_ this book
    in a course.  I have used some others, and if I had to choose one
    right now I would choose Parsons.

Thomas Pittman and James Peters, "The Art of Compiler Design: Theory and
Practice", Prentice Hall, 1992, ISBN 0-13-048190-4.

A. T. Schreiner and G. Friedman, "Introduction to Compiler Construction
with UNIX", Prentice-Hall, 1985.

  Recommended by Sebastian.Schmidt@PrakInf.TU-Ilmenau.DE (Sebastian
  Schmidt).

William M. Waite and Lynn R. Carter, "An Introduction to Compiler
Construction", HarperCollins, 1993, ISBN 0-673-39822-6.

  William Waite  <waite@riker.cs.colorado.edu> [an author] writes:

    I have just completed a book for a senior-level undergraduate
    compiler class, co-authored with Dr. L. R. Carter of the Software
    Engineering Institute.  I have been using it in draft form for
    several years, and it was published by HarperCollins in September.
    It's always hard to characterize a book briefly, but I feel that
    this one has significant advantages for an undergraduate course:

    - It presents a complete, balanced picture of the compiler rather
      than the usual emphasis on parsing.
    - It provides general principles for semantic analysis and code
      generation, not simply a collection of special cases.
    - Although the techniques are all based on theory, the book does
      not make that theory its central theme.

    Here is a list of chapters and page counts:

    1.  The Characteristics of a compiler (15pp)
    2.  The Compiler's Interface (27pp)
    3.  Lexical Analysis (31pp)
    4.  Syntactic Analysis (41pp)
    5.  Recursive Descent Parsing (29pp)
    6.  Shift-Reduce Parsing (18pp)
    7.  Managing Contextual Information (41pp)
    8.  Types and Data Mapping (30pp)
    9.  Action Mapping and the Target Program Tree (40pp)
    10. Operator Identification (38pp)
    11. Code Generation (37pp)

    Chapter 2 describes the module interfaces that are used to
    communicate with the outside world, but are not central to compiler
    construction issues (source text input, error reporting and
    external value management).  Chapter 4 explains the general concept
    of syntactic analysis and syntactic error recovery (including how
    the process is specified) without a commitment to a particular
    parsing strategy.  Chapter 7 explains the general principles used
    to analyze all computations over trees, and shows how to implement
    such computations.  Name analysis is used as the primary example in
    this chapter.  Chapter 9 restricts itself to mapping statements and
    mapping expressions in which the operators are not overloaded.
    This restriction is removed in Chapter 10 through the use of a
    general technique for overload resolution that is also useful in
    code generation.

    There is an Appendix containing a complete project to translate a
    simple algebraic language to VAX assembly code.  Our students
    complete this project (or a similar one -- we rotate languages) in
    one semester.

    If you have specific questions, I'd be happy to answer them.  You
    can get a copy of the text by asking your local HarperCollins
    representative or calling John Lenchek at (708)486-2834.

    Our project IS designed for a semester system, but we offer a
    suggestion for truncating it:  Have the students write a "lint"
    program rather than a compiler.  Cover Chapters 1-7, selecting
    either 5 or 6 depending on the parsing method.  Require that their
    "lint" program detect and report lexical errors, syntax errors,
    undefined and multiply-defined symbols, and type agreement errors.
    If you use a language with only integer and Boolean variables and
    no coercions, then you avoid the need for overload resolution.  (A
    suitable language for such a project would be Pascal-, defined by
    Brinch-Hansen in "Brinch-Hansen on Pascal Compilers").

    This approach has the advantage of covering the most significant
    material (structuring the linear input text and managing contextual
    information).  Overload resolution is the only "scientific" aspect
    of the problem not covered.  (Target tree construction and code
    generation are really applications of contextual information and
    overload resolution, while data mapping is straghtforward data
    processing.)  If time permits (and since we are not on a quarter
    system I can't say how likely that is) you can cover overload
    resolution and extend the language to handle reals as well as
    integers.  Because of the systematic technique we advocate for this
    problem, the increase in code complexity is very small, so the
    actual project development time is perhaps half a week longer with
    overload resolution than without it.  Class time required to
    present the technique is somewhat more -- probably in the range of
    four to six one-hour lectures.

Wirth and Gutknecht, "Project Oberon: The design of a compiler and
operating system", Addison-Wesley, 1992, ISBN 0-201-54428-8.

  Recommended by G_DOTZEL@ame.nbg.sub.org (Guenter Dotzel).

  thutt <thutt@MAIL.CASI.NASA.GOV> writes:

    The very best 'practical' book on operating systems and compilers
    that I have seen ...  This contains the (nearly) complete
    implementation of the Oberon operating system, and the complete
    implmentation of a production compiler.  The source is available
    for ftp from neptune.ethz.ch.  Recommended reading.

"A First Course in Compilers Using ANSI C, Lex and Yacc"

  zell@SEAS.UCLA.EDU (Adam W. Zell) writes:

    thin book, skims over theory

"High Level Languages And Their Compilers"

  zell@SEAS.UCLA.EDU (Adam W. Zell) writes:

    Excellent text, with diverse languages discussed

----------------------------------------------------------------------

This message is not to recommend a complete text book, but to tell you
about some software and a paper that can be used for programming projects
in a compilers course.  The approach is for the students to take a small
working compiler, study it, and then add features to the language by
changing the compiler.  The compiler is written as an attribute grammar
which is preprocessed to produce code for Yacc and Lex.

Several professors have expressed that they intend to use Ox in their
compilers courses this Spring.  There is also interest in using Ox for
research and commercial software production.

Kurt M. Bischoff, Computer Science Dept., Iowa State University, Ames,
Iowa bischoff@cs.iastate.edu


             An Attribute Grammar Compiling System
                           based on
                        Yacc, Lex, and C

Ox generalizes the function of Yacc in the way that attribute grammars
generalize context-free grammars.  Ordinary Yacc and Lex specifications
may be augmented with definitions of synthesized and inherited attributes
written in C syntax.  From these specifications, Ox generates a program
that builds and decorates attributed parse trees.  Ox accepts a most
general class of attribute grammars.  The user may specify postdecoration
traversals for easy ordering of side effects such as code generation.  Ox
handles the tedious and error-prone details of writing code for parse-tree
management, so its use eases problems of security and maintainability
associated with that aspect of translator development.

The translators generated by Ox use internal memory management that is
often much faster than the common technique of calling malloc once for
each parse-tree node.

Ox is a Yacc/Lex/C preprocessor, and is designed to bring attribute
grammars closer to the mainstream of Unix-based language development.  Ox
inherits all of the familiar syntax and semantics of Yacc, Lex, and C.  It
is relatively easy to convert programs between Ox code and "pure
Yacc/Lex/C" code.

Ox has been used to build a compiler for a small (eighty grammar rules)
block-structured imperative programming language, and has been tested and
found to be portable among the following systems running Unix:

     Hewlett-Packard PA, 680x0
     Sun 3, SPARCstation
     DECstation 2100, 3100, 5000
     Silicon Graphics Inc. R3000
     NeXT workstation
     Data General AViiON, 88000

The author of Ox is Kurt M. Bischoff (bischoff@cs.iastate.edu), Department
of Computer Science, Iowa State University.

For more information, please send your e-mail address to:

     ox-request@cs.iastate.edu

The following Ox-related documents are available in Postscript format by
electronic mail:

     * User Manual for Ox: An Attribute-Grammar Compiling System
     based on Yacc, Lex, and C, by Kurt M. Bischoff. TR92-30,
     Computer Science Department, Iowa State University, Ames,
     IA, December, 1992.  40 pages.

     * Design, Implementation, Use, and Evaluation of Ox: An
     Attribute-Grammar Compiling System based on Yacc, Lex, and
     C, by Kurt M. Bischoff. TR92-31, Computer Science
     Department, Iowa State University, Ames, IA, December, 1992.
     80 pages.  Includes the text of TR92-30.

     * GPPL: A Small Block-Structured Imperative Programming
     Language Implemented Using Ox, by Kurt M. Bischoff. TR92-32,
     Computer Science Department, Iowa State University, Ames,
     IA, December, 1992.  66 pages.  Includes sample GPPL
     programs and Ox/C source code for the compiler.  GPPL is
     suitable for instruction and experimentation, or as a
     template for design of a block-structured language.

To obtain one of these technical reports, please send an e-mail message
consisting of:

     send tr <TR#>

to almanac@cs.iastate.edu, where <TR#> is one of: TR92-30, TR92-31,
TR92-32.

To obtain an ASCII-format abstract of one of the above, send a message
like:

     send abstract <TR#>

to the same address.

Send questions to: ox-request@cs.iastate.edu.
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
Newsgroups: comp.compilers