CSE 413 Autumn 2007

Introduction to Compilers

Programming Language Implementation Techniques

• Interpreter: Analyze a program written in some source language and execute the commands in that program as they are analyzed.  Examples: Perl, AWK, Scheme, Ghostscript (Postscript previewer), etc.
• Compiler: Translate a program written in some source language to a target language.  The compiler itself is written in some implementation language.   Some examples:

Source Language	Target Language
C++	x86 assembly language
Java	Java virtual machine
Java virtual machine	SPARC or x86 machine code (JIT)
Ada	Java virtual machine
COBOL	IBM mainframe machine language
TeX/LaTeX	dvi
dvi	Postscript
Postscript	PDF
Database query (SQL)	sequence of database engine commands
VHDL	hardware model checker input

Why Study Compilers?

• Understand how high-level languages are implemented (what does all that stuff in the debugger mean anyway?)
• Insight into how to write high-level programs that can be implemented efficiently and effectively - interaction between languages and hardware, instruction sets, caches and memory hierarchies.
• Techniques that originated in compilers show up in many guises.  Parsing is everywhere: command lines, dialog boxes, network protocols, XML applications.
• You might even write a compiler someday!

A (very short) History

• 1950's.  Existence proof.  FORTRAN I (1954).  Good enough to compete with hand-optimized code.
• 1960's.  Algol 60: formal notation for syntax; stack frames, recursive function calls; LISP, COBOL.
• 1970's.  More ado about syntax; formal methods for dealing with compiler front end.
• 1980's - 1990's.  Optimization, systematic approaches to back end of compiler, exotic languages (object-oriented and functional languages) and exotic architectures (RISC vs CISC, parallel and networked machines, memory hierarchies).

Basic Structure of a Compiler

Front end - analysis

• Lexical analysis (scanner).  Convert character stream source program to token stream
• Parser.  Read token stream and generate some intermediate form (typically syntax trees)
• Static semantics.  Declarations, type checking -- symbol table

Back End - synthesis

• "Optimization" - many types of code improvement transformations and resource allocation decisions.
• Code generation for target machine

There are many choices for how to structure a compiler.  The GNU compiler collection (GCC) and many commercial systems have a suite of front ends (C/C++, Fortran, Pascal, Java, ...), a common middle end (optimization and transformations that are independent of the source language and machine), and multiple back ends (code generators for different targets - x86, MIPS, SPARC, PowerPC, Java VM, ...)

Interfaces between phases:  Variety.  Some may be function calls, others actual data structures giving explicit intermediate representation (streams, abstract syntax trees, etc.).

Example

What we have:

     /* a very short code fragment */  
     if (x > y) 
        y = 42 * x; 
     else // don't do this if x > y
        x = f(x+17);

What we want:

     load  x     ; jump to L1 if x <= y
     cmp   y
     ble   L1
     load  42     ; y = 42 * x;
     mul   x
     store y
     jmp   l2
 L1: load  x     ; x = f(x+17)
     add   17
     push
     call  f
     store x
 L2:

How do we get from here to there?  The first task is to analyze the input and reconstruct the program structure.

Lexical analysis: Break the program into a token stream, hiding the details of reading the input and source program layout, and discarding whitespace.  This is often called scanning.  Result:

   IF LPAREN ID(x) GT ID(y) RPAREN ID(y) GETS INT(42) 
   TIMES ID(x) SCOLON ELSE ID(x) GETS ID(f) LPAREN ID(x)
   PLUS INT(17) RPAREN SCOLON EOF

Parsing: Read the token stream and analyze the underlying grammatical structure of the input.  Most production compilers build explicit parse trees.  For the project in CSE 413, we won't build the parse tree explicitly, but we will still analyze the phrase structure of the program.  

Usual interface with between parser and scanner: parser calls method in the scanner when it needs to read the next token.

When we've gotten this far, we can generate code based on the information discovered during the analysis.

References

There are many books about programming languages and compilers.  Here are a couple you might find useful.  Copies are on reserve in the Engineering library.

Compilers: Principles, Techniques, and Tools, Alfred Aho, Ravi Sethi, and Jeffrey Ullman; Addison-Wesley, 1986 (corrected printing 1988), new edition 2007.  This has been the standard text for compiler courses for many years.  Chapters 1 & 2 cover basically all that we will see in CSE 413.

Programming Language Pragmatics, Michael L. Scott; Morgan Kaufmann, 2nd ed, 2006.  This would be an ideal textbook for CSE 413, but it covers far more, and in more depth, than we can possibly manage in 10 weeks.  Good source for supplemental reading though.