Re: Re:Book: symbol table, type system, code generation?

  james.grosbach@Microchip.COM (James Grosbach) writes:
> I recently obtained _Advanced Compiler Design and Implementation_ by
> Steven Muchnick and at least on first impression it's quite
> nice. Chaper 3 covers symbol table design, and chapter 6 discusses
> code-generator generation.


I do not recommend this book if you want to learn about code
generation.


In Chapter 6 (on code selection) it concentrates on the
Graham-Glanville approach (what the book calls "syntax-directed"
although it has nothing to do with the syntax of the source language),
which has been superseded by tree parsing (which is both easier to use
and at least as powerful as the Graham-Glanville approach). Finally
it shortly discusses tree parsing in the context of Twig; AFAIK Twig's
top-down method has quadratic complexity, in contrast to the linear
bottom-up methods employed in BEG, burg, iburg etc. And IMO bottom-up
tree-parsing using dynamic programming as presented in [emmelmann+89]
is easier to understand than the explanation of Twig given in the
book.


In Section 9.2 (on basic block dependence graphs for instruction
scheduling) the algorithm presented for building the graph compares
every instruction with every other instruction, resulting in quadratic
complexity and redundant dependence edges. A linear method that
introduces fewer redundant edges is known (and even if you don't know
it, it's not that hard to figure out), but it is not even mentioned.


I hope the book is better on the material with which I am not that
familiar. I have not yet read the chapters on register allocation and
instruction scheduling, so I cannot comment on them.


@InProceedings{emmelmann+89,
    author = {Helmut Emmelmann and Friedrich-Wilhelm Schr\"oer and
                                    Rudolf Landwehr},
    title = {{BEG} -- a Generator for Efficient Back Ends},
    crossref = "sigplan89",
    pages = "227--237"
}


- anton
--
M. Anton Ertl Some things have to be seen to be believed
anton@mips.complang.tuwien.ac.at Most things have to be believed to be seen
http://www.complang.tuwien.ac.at/anton/home.html
--

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