Summary: Compiler Textbooks

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

Return to the comp.compilers page.
Search the comp.compilers archives again.