Re: compilers, in a nutshell

ellard@endor.harvard.edu (Dan Ellard) writes:
> If you had a six hours of lecture time to discuss compilers, what would
> you cover? ... My current outline (which is very rough) looks like:
>
> Lecture 1
> 1. What is a compiler?
> 2. Lexical analysis
> 3. Parsing
> CKY
> Recursive descent
> Predictive parsing.


For a short overview, I'd leave out many details about lexical analysis
and parsing, and just describe what parsing does and that there are many
tools to help with this portion of building a compiler.


If you insist on including details, then I'd leave out CKY (hardly used in
commercial compilers) and predictive, and include LL(1) and LALR(1).
(Maybe I misunderstood what you meant by predictive parsing?)


A comment: Even many computer science students, who just take an
introductory course on compilers, come away thinking that lexical analysis
and parsing is all there is to a compiler. If you can, try to avoid
giving that impression.


> Lecture 2
> 1. Intermediate representations.
> 2. Type checking / inference.


If you say more than 2 sentences about type inference, you will probably
lose your audience or be forced to spend the entire 6 hours on it.


What about semantic analysis? There's more to that than just type
checking. Perhaps a word or two about overload resolution, in the sense
that almost every programming language overloads some things (like + on
both integers and floats). This fits with an earlier poster's comment
about including some concepts of programming languages, I think.


> Lecture 3
> 1. Code generation.


Are you including register allocation here? If not, where? At least
mention that this is one of the most important and hardest tasks a good
commercial compiler must perform.


> Lecture 4
> 1. Optimizations.


          A. Machine-independent
                i. alias resolution and analysis
                ii. loop optimization
                iii. common subexpression elimination
                iv. constant propagation and folding
          B. Machine-dependent
                i. branch optimizations (e.g., chaining)
                ii. instruction scheduling
                iii. elimination of redundant instructions (cleanup of code
                          generation mistakes)


Hope this helps.


--
Bill Leonard
Harris Computer Systems Division
2101 W. Cypress Creek Road
Fort Lauderdale, FL 33309
bill@ssd.csd.harris.com
--

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