Overview

We will cover the following topics: 1. Lexical Analysis (scanning ) 2. Syntax Analysis (parsing ) 3. Context-sensitive Analysis 4. Intermediate Representations 5. Code Generation 6. Code Improvement Techniques The textbook for this course is \Compilers: Principles, Techniques, and Tools" by Aho, Sethi, and Ullman. Overhead transparencies are available in postscript format on the World Wide Web from

http://www.cs.tamu.edu/ rwerger/
CPSC 434

Lecture 1, Page 1

Class-taking technique
I use overhead transparencies all transparencies are on the Web you should still take some notes

I'll tell you where we are in the book I don't lecture directly from the book You need to read the book you need to start by refreshing your C++ skills

CPSC 434

Lecture 1, Page 2

Compilers
What is a compiler?

a program that translates an executable program in one language into an executable program in another language the compiler typically lowers the level of abstraction of the program we expect the program produced by the compiler to be better, in some way, than the original

CPSC 434

Lecture 1, Page 3

Motivation
Why build compilers? Why study compiler construction? Why attend class?

Reasons: compilers provide an essential interface between applications and architectures compilers embody a wide range of theoretical techniques compiler construction teaches programming and software engineering skills

CPSC 434

Lecture 1, Page 4

Role of Compilers
High-level programming languages increase programmer productivity better maintenance portable Low-level machine details instruction selection addressing modes pipelines registers & cache instruction-level parallelism Compilers are needed to e ciently bridge the gap!

CPSC 434

Lecture 1, Page 5

Isn't it a solved problem?

Machines have continued to change since they have been invented

Changes in architecture ) changes in compilers

new features present new problems changing costs lead to di erent concerns must re-engineer well-known solutions

Signi cant di erences in performance

CPSC 434

Lecture 1, Page 6

Interest
Compiler construction shows us a microcosmic view of computer science. arti cial greedy algorithms intelligence learning algorithms graph algorithms algorithms union- nd network ows dynamic programming dfa's for scanning theory parser generators lattice theory for analysis allocation and naming systems locality synchronization pipeline management architecture memory hierarchy management instruction set use
Inside a compiler, all these things come together. As a result, compiler construction is challenging and fun.
CPSC 434
Lecture 1, Page 7

Compiler Construction
Compilers are large, complex pieces of software.

By working on compilers, you'll learn to use programming tools (compilers, debuggers) program-generation tools ( ex, yacc, bison) software libraries (sets, collections) simulators (spim)

Hopefully you will also enhance your software engineering skills.

CPSC 434

Lecture 1, Page 8

Experience
You have used several compilers. What qualities do you want in a compiler? Here is a list: 1. Correct code 2. Output runs fast 3. Compiler runs fast 4. Compile time proportional to program size 5. Support for separate compilation 6. Good diagnostics for syntax errors 7. Works well with the debugger 8. Good diagnostics for ow anomalies 9. Cross language calls 10. Consistent, predictable optimization

CPSC 434

Lecture 1, Page 9

My Biases
My own research: compiling for parallel architectures parallelizing C++ exploring the language/compiler/runtime/architecture interface adaptive parallel processing: customizing compilation process to application

CPSC 434

Lecture 1, Page 10

Some Advice

Compiler construction is one of the most time-consuming undergraduate level programming courses.

Be prepared to spend a lot of time on projects if you don't have much programming experience in UNIX and C++. Be prepared to lose a lot of sleep if you don't start projects early!

CPSC 434

Lecture 1, Page 11

Next Class
I'll try to give you an overview of how a compiler works and what I think is important.

Things to do:

read Aho, Sethi, and Ullman, Chapters 1, 2, 3 read the manual page for ex learn to use a Web browser such as Netscape

CPSC 434

Lecture 1, Page 12