Suggestions for a compilers course (summary)

Three weeks ago, I posted a request for ideas for a *second* compiler
course (for grad students with weak CS backgrounds).


I got some very good replies, and am summarizing them here.
Thanks to all for their help -- Alex


Alexander Glockner
Asst. Professor, Dept. of Computer Science
Bowie State University Bowie MD 20715 USA
(301) 464-6609 (voice)
(301) 464-7827 (fax)
glockner@cosc.bsu.umd.edu


-------------------------------------------------------
>From davidm@igor.rational.com


>Advanced topics in compiler design and construction.


Some things that are probably of importance to students are:


Garbage collection (useful even if you are not writing a compiler)
Denotational/Algebraic Semantics (very lightly) Implementation of classes
(in C++ and also Simula 67 - in Simula you have concurrency issues)
Allocation of objects on stacks (including dynamic allocation as required
by Ada) and on heaps (which, of course, immediately raises the garbage
collection problem)


>Automated compiler tools and compiler compilers.


The problem with this is, once you get them hacking grammars with
lex/yacc, they aren't going to get much else done for the semester.


>Advanced code optimization techniques.


Just basic techniques from the dragon book is about all you can cover in
the time available. It is probably important to get across the idea that
data flow analysis is the solution of sets of equations on the ring of
Booleans since this idea is one every programmer should have in their
tool-kit.


-------------------------------------------------------
>From jhummel@esp.ICS.UCI.EDU


If it's possible, I'd switch to another textbook, most likely Aho, Sethi,
and Ullman, "Compilers: Principles, Techniques, and Tools." This is
considered THE ref for standard compilers for imperative languages. It
has a chapter on optimization which would be fun to discuss.


You might want to consider using the various compiler tools available,
e.g. PCCTS from Purdue. This way, you could build more of the compiler --
i.e., PCCTS is a more powerful lex/yacc.


-------------------------------------------------------
>From basile@soleil.serma.cea.fr


I would also have a look (or teach) into the contents of :


Andrew W. APPEL
Compiling with Continuations
Cambridge Univ. Press 1992, 262 pages
ISBN 0-521-41695-7.
-------------------------------------------------------
>From sasghm@unx.sas.com


I take it that the course is not intended to cover *all* of the following
topics


Advanced topics in compiler design and construction.
Automated compiler tools and compiler compilers.
Advanced code optimization techniques.
Role of compilers in natural language processing.


but rather that this is a representative list of *possible* topics.


Advice: Don't try to do too much. It is better to do something more
limited in full depth than to do a variety of stuff very shallowly.


A major problem in a course of this sort is that it is virtually
impossible to do anything worthwhile from scratch -- just not enough time.


An alternative -- and a good *practical* alternative -- is to take an
existing parser generator that you could get the source for (say bison or
Berkeley YACC) and modify it in various specific ways. Simply in coming
to understand the code one achieves quite a good understanding of the
fundamental issues and techniques.


If you'd rather not mess with parser generators, you can do the same thing
with a code generator. Get the GNU C compiler source and mess about with
the code generator and optimizer parts. Possible projects:


Add additional types (keywords, semantics, etc.)
Add a BCD type and support operations on it.
Add a "set" type to C.
Add better error diagnostics and recovery.
etc.


The advantage of this approach is that you have *something* to start with
and people can begin real work at once. Otherwise, you get to the end of
the semester, and nothing (or nothing very worthwhile) has been done.




Valuable books I have made use of are the Fischer/Leblanc plus:


_The Theory and Practice of Compiler Writing_
by Tremblay and Sorenson (this may be the best
all around compiler book I have seen)


_Compiler Design Theory_ by Lewis, Rosenkrantz and Stearns
(This book is pretty old. The thing you want in it is the
appendix on grammar transformations.)
-------------------------------------------------------
>From wendt@ives.CS.ColoState.EDU


You might try to get ahold of the forthcoming book "Optimization in
Compilers" by Fran Allen, Ken Zadeck, and others. It is a thorough survey
of optimization techniques.
-------------------------------------------------------


>From Nasir.Abbas@UC.Edu


...at University of Cincinnati (ECE Dept), we have just finished our
Advanced Compiler course for this quarter.


In this course, we covered mainly techniques of optimization, efficient
and new methods of code generation and Machine defintions more from the
practical and research point of view. We did not follow any particular
text book but we were given copies of research papers and we used to have
informal discussions and presentations on these papers.


Then, the projects for the quarter were mainly organized around the
analysis of the GCC compiler. Code generation, machine definition,
optimization etc were a few I can recall. Some students also chose to do
something different such as survey papers on techniques of optimization
and other topics relating to compiler design.


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


>From spunya@galileo.eng.wayne.edu


Hi!
These are some of the references which might be useful to you.
Some may be in very detail but in the field of Parallelizing
compilers these are standard refs.
Regards
Swamy Punyamurtula




REFERENCES ON PARALLELIZING COMPILERS


PC1. A: Michael Wolfe and Utpal Banerjee
T: Data Dependence and its applications in paralle processing.
J: International journal of parallel programming
I: Vol. 16, No. 2 April 1987, pp 137-178.


PC2. A: Michael Wolfe
T: Optimizing Supercompilers for Supercomputers
B: Pitman Publishing, The MIT press Cambridge, 1989
C: SCIENCE QA 76.5 W585 1989


PC3. A: Zhiyuan Li, Pen-chung Yew, Chuan-qi zhu
T: An efficient data dependence analysis for Parallelizing Compilers.
J: IEEE Transactions on Parallel and Distributed Systems
I: Vol. 1, No.1, January 1990 pp 26-34.


PC4. A: Randy Allen and Ken Kennedy
T: Automatic translation of FORTRAN programs to vector form.
J: ACM transactions on Programming Languages And Systems (TOPLAS)
I: Vol. 9, No. 4, October 1987, pp 491-542


PC5. A: Jingke Li and Marina Chen
T: Compiling Communication efficient programs for massively parallel
machines.
J: IEEE transactions on Parallel and Distributed systems.
I: Vol. 2, No.3, July 1991, pp 361-375


PC6. A: J. Ramanujam and P. Sadayappan
T: Compile-Time Techniques for Data Distribution in Distributed
Memory machines.
J: IEEE Transactions on parallel and Distributed Systems.
I: Vol. 2, No.4, October 1991 pp 472-482.


PC7. A: Charles Koelbel and Piyush Mehritra
T: Compiling Global Name-Space Parallel loops for Distributed
Execution
J: IEEE Transactions on Parallel and Distributed Systems
I: Vol. 2, No. 4, October 1991, pp 440-451.


PC8. A: Shahid H. Bokhari
T: Partitioning Problems in parallel, Pipelined, and Distributed
Computing.
J: IEEE Transactions on Computers.
I: Vol. 37, No.1, January 1988, pp 48-57.


PC9: A: Constantine D. Polychronopoulos
T: Parallel Programming and compilers
B: Kluwer Academic Publishers Boston/London, 1988
C: SCIENCE QA 76.6 .P653 1988


PC10: A: Roland Ruhl and Marco Annaratone
T: Parallelization of FORTRAN code on Distributed-Memory Parallel
Processors
J: Proceedings of 4th International Conference on Supercomputing,
I: June 1990, pp 342-353


PC11: A: Milind Girkar and Constantine D. Polychronopoulos
T: Partitioning Programs for parallel Execution
J: Proceedings of the 1988 ACM International Conference on
Supercomputing.
I: July 4-8, 1988, pp 216-229


PC12: A: Frances Allen, Michael Burke, Ron Cytron et. al.
T: A Frame work for determining Useful Parallelism.
J: Proceedings of the 1988 ACM International Conference on
supercomputing.
I: July 4-8, 1988, pp 207-215.


PC13: A: Eric Mohr, David A. Kranz and Robert H. Halstead
T: Lazy Task Creation: A Technique for Increasing the Granularity of
Parallel Programs.
J: IEEE Transactions on Parallel and Distributed computing Systems.
I: Vol. 2, No. 3, July 1991, pp 274-280.


PC14: A: Charles Koelbel and Piyush Mehrotra
T: Supporting Shared data structures on Distributed Memory
Architectures.
J: Proceedings of the 2nd ACM-SIGPLAN symposium on PPPP.
I: March 1990, pp 177-186.


PC15: A: J. Ramanujam and P. Sadayappan
T: A Methodology for Parallelizing programs for Multicomputers and
Complex Memory multiprocessors
J: Proceedings of Supercomputing'89
I: Nov. 1989 pp 637-646.


PC16: A: Utpal Banerjee
T: Dependece analysis for Supercomputing
B: Kluwer Academic Publishers 1988.
C: SCIENCE QA 76.5.B264 1988


PC17: A: Michael Wolfe
T: Data dependence and Program restructuring
J: The Journal of Supercomputing
I: Vol #4, 1990, pp 321-344


PC18: A: David Callahan, Ken Kennedy
T: Compiling Programs for Distributed-Memory Multiprocessors
J: The Journal of Supercomputing
I: Vol #2, 1988, pp. 151-169.


PC19: A: Marina Chen, Young-il Choo, Jingke Li
T: Compiling Parallel Programs by Optimizing Performance
J: The Journal of Supercomputing
I: Vol #2, 1988, pp 171-207.


PC20: A: Michael Wolfe
T: Advanced Loop Interchanging
J: Proceedings of ICPP
I: 1986, pp 536-543


PC21: A: Peiyi Tang and Pen-Chung Yew
T: Processor Self-scheduling for Multiple-Nested Parallel loops
J: Proceedings of ICPP
I: 1986, pp 528-535


PC22: A: C.D. Polychronopoulos, D.J. Kuck and David A. Padua
T: Execution of Parallel Loops on Parallel Processor Systems
J: Proceedings of ICPP
I: 1986, pp 519-527


PC23: A: Vincent A. Guarna, Jr.
T: A Techinique for Analyzing POinter and Structure References
in Parallel Restructuring Compilers
J: Proceedings of ICPP
I: 1988, pp 212-220


PC24: A: Gyungho Lee
T: Automatic Restructuring of Comditional Cyclic Loops
J: Proceedings of ICPP
I: 1988, pp 42-45


PC25: A: Hans Zima with Barbara Chapman
T: Supercompilers for Parallel and Vector Computers
B: ACM Press 1990
I: SCIENCE QA 76.6 Z56 1990


PC26: A: Gelernter, Nicolau and Padua
T: Languages and Compilers for Parallel Computing
B: Pitman Publishing, MIT Press
I: SCIENCE QA 76.7 .L38 1990


PC27: A: Nicolau, Gelernter, Gross and Padua
T: Advances in Languages and Compilers for Parallel Processing
B: Pitman Publishing, The M.I.T. Press
I: SCIENCE QA 76.7 .A38 1991


-------------------------------------------------------
>From nes!dave@phx.mcd.mot.com


I am a graduate student at Arizona State University, and am currently
pursuing a Masters in language processing. I am taking a class (CSC 545
Programming Language Design) where we are given a compiler written by an
undergraduate in the compiler construction I class, and ask to add "real"
language features to it. These "real" features include:
(1) Nested procedures and parameter passing (using Ada's notation
of in out and inout).


(2) Object oriented features including procedure overloading,
and class objects (encapsulation of data and operations)
and a simple form of inheritance.


(3) Exception handling (similar to Ada's)


(4) Multitasking (as with threads or Ada's tasks)


(5) Complex data types including unconstrained arrays and i
dynamic records


The project involves doing choice 1, and any one other option (the
student's option). The project is required to be done in Ada (our
instructor's favorite language) - this seems to make some options easier
(tasking and exception handling). The second half of the course involves
formal semantics.


The texts are as follows:
Organization of Programming Languages,
by Bernd Teufel, Springer Verlang
ISBN 0-387-82315-8


Introduction to the Theory of Programming Languages,
by Meyer, Prentice Hall
ISBN 0-13-498510-9


This course is probably not EXACTLY like what you will teach, however, the
Springer Verlag book is EXCEPTIONAL at discussing language features and
how them impact languages and compilers. Since your students have already
had the basics of compiler writing, it would be a disservice to repeat
that - challenge them (that is what I expect out of my professors).


Additionally, an very good paper that describes block structure (essential
for modern programming languages and also gives good insight for the
compiler writer is:
        "The Contour Model of Block Structured Processes"
by JB Johnston, SIGPlan Notices vol 6, pp 1-54, Feb 71.


Though not used by the instructor, I am using the following article to
help me with the overloading of procedures (I haven't finished reading it
yet, however it seems very promising (from an implementation point of
view)


        Static Type Checking of Multi-Methods"
by Rakesh Agrawal, Linda G. DeMichiel, Bruce G. Lindsay
Procedings OOPSLA 91 pp 113-128 (SIGPLAN Notices vol 26, #11 Nov 91)


Additionally, at ASU, ther is a professor, Dr. Aryeh Faltz, who does two
classes (one is a 400-level undergraduate elective, the other a 500 level
post grad) on natural language processing using parsers built with Prolog.
It is an exceptional course (I've been told, I have not yet taken it).
Dr. Faltz specializes in natural language understanding. He may be
amenable to talking with you about books he uses in that course.
Unfortunately I do not have an E-Mail address for him - you could try
calling him at ASU - the computer science office at ASU is (602) 965-3190.


-------------------------------------------------------
>From leermake@prl.philips.nl


Well, I've just finished a book entitled "The Functional Treatment of
Parsing". It explains recent developments in parsing theory, using modern
functional methods (but in no way advocates the use of functional
languages). It explains how to do shift-reduce parsing without stacks,
Earley parsing without parse matrix, how to parse attribute grammars (for
compilers and natural language), and much more. All subjects are treated
in a unified, functional, way. Code optimization is not included. The book
will be published around July 1, by Kluwer. [Please email Rene for
further information]


Rene Leermakers
Institute for Perception Research
PO Box 513
5600 MB Eindhoven, The Netherlands
leermake@prl.philips.nl
-------------------------------------------------------
>From donawa@binkley.cs.mcgill.ca Fri Mar 12 10:38:59 1993
Hi Alex,
      I helped TA a course under Prof Laurie Hendren
(hendren@lucy.cs.mcgill.ca), and the students learned quite a lot from the
assignments, although they all had a CS background, so you might have to
scale down their projects.


The front end used lex/yacc (as usual), an AST upon which extensive type
checking was performed. The optimizations were left up to the student's
imaginiation, but included constant propogation.


The code generation phase used a neat tool called burg, which is a code
generator-generator. It takes a yacc like specification of tree patterns,
traverses the tree (i.e. the AST generated by the front-end), and matches
sub-trees. It works bottom up and finds the best match for the largest
sub-tree.


It produces quite good code and is quite fast. iburg is the dynamic
programming version of burg (not as fast, but more flexible).


Burg takes a rather unpleasent looking specification, so a front end is
usually written. We have one here for burg (iburg is compatible and is
easier to debug so I recommend it over burg for a course), and if you're
interested I can forward it to you.


If you'd like more details, please contact Laurie (above email address).
-------------------------------------------------------


>From triemer@RUBY.CON.WESLEYAN.EDU Tue Mar 16 13:02:32 1993


To give you the importance of lex and yacc - every single pd software that
I have ported to the 3b2s (Where I do most of my work) - has involved lex
and yacc. ...And I know that the experience I had with the one compiler
course I had did not prepare to write my first little compilers - it was
in fact only when I threw out the high falutin stuff about lambda
calculus, that I got anything done.


...but a really nifty project would be to add some features to the gcc
compiler - even if they don't get any really wonderful additions added,
the experience of climbing through the code would give them a really good
insight into how compilers are built.
-------------------------------------------------------
--

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