Advanced Compiler Design PDF

Advanced Compiler Design

Objectives

Compilers and interpreters are very widely used. Every programmer uses these tools to execute programs written in high level languages. It is hence essential for a computer scientist to understand the process by which programs written in high-level languages are translated and executed. The main objective of this course is to gain an in depth understanding of the aboveprocess. Most complex software systems are not monolithic; they are programmable using special purpose languages. An understanding of the language translation process thus plays an important role in the design of real life systems.

Overview

In the class, we will discuss the theoretical aspects of designing a compiler. In the projects, you will then apply the theory you have learned in the class to develop a complete compiler for a high level language. The problem of languagetranslation is traditionally decomposed into many phases. Most common are:

• Lexical analysis (analogous to recognizing words in a sentence),
• Parsing (analogous to grouping words into phrases, sentences, paragraphs etc.)
• Semantic Analysis (e.g., type checking), and
• Code generation

All phases use a symbol table to keep track of the properties (types, number of parameters etc.) of each symbol (variables, procedures etc.). In the end, code is generated for an abstract machine which may be interpreted (as in Java), or may be translated further into machine instructions (as in C). We will cover each of these topics in detail.
The compiler will be written in Java. Advanced topics such as program optimization, machine code generation and storage management will be discussed in the lectures.

---

Reading

The course will use the following textbooks:

• Compilers: Principles, Techniques, and Tools, by Aho, Sethi, and Ullman, Addison-Wesley, 1988, 796pp. ISBN 0-201-10088-6.

Slides will be posted as links in the tentative schedule below. Following books are recommended for additional reading:

• Modern Compiler Implementation in Java, by Andrew Appel.
• The Java Programming Language Second Edition by Ken Arnold and James Gosling.

	Date	Topic	Chapter	Projects
1.	Jan 27	Organization. Overview of Compilation. l1	1, 2
2.	Jan 29	Lexical Analysis: Regular Expression & Definitions l3, l4	3.1-3.3
3.	Feb 03	Lexical Analysis: RE<->NFA<->DFA l4, l5, Javacc 1 2 3 4 5 6 7 8 9 10	3.4-3.6
4.	Feb 05	Grammars, Recursive Descent Parsing. l6, l7	4.4	P1 Out
5.	Feb 10	LL Parsing. l8, l9	4.4
6.	Feb 12	Bottom-up Parsing, l10	4.5
7.	Feb 17	LR Parsers, l11	4.7	P1 due, P2 out
8.	Feb 19	Item set construction, 1 2 3 4 SLR, LR, LALR, l12	4.7
9.	Feb 24	Attributes, l16, l17	4.9
10.	Feb 26	Syntax-Directed Translation, l15, att	5.1
11.	Mar 02	Symbol Tables, l13, st	7.6
12.	Mar 04	Name Resolution, l14, l15		P2 due,P3 out
13.	Mar 09	Abstract Syntax Trees l18, ast	5.2
14.	Mar 11	Review for Mid-Term Exam
15.	Mar 16	Mid-Term Exam. Previous: 00e, 00a; 98e, 98a; 97e, 97a, 02
16.	Mar 18	Types: type checking expressions and operations l19	6.1, 6.2
17.	Mar 23	Types & Equivalences l20 TypeChecking.ppt	6.3, 6.4	P3 due, P4 out
18.	Mar 25	Types in OO-languages: method resolution l21	6.5
19.	Mar 30	Intermediate code generation: languages, expressions l22, l24	8.1-8.4
20.	Apr 01	Runtime storage organization l23, pCall	7.2, 7.3
***	Apr 06	Spring recess (no class)
***	Apr 08	Spring Recess (no class)
21.	Apr 13	Intermediate code generation: statements. Optimizations l25, l26	8.4-8.7, 9.4	P4 due, P5 out
22.	Apr 15	Control-Flow Analysis CFA): blocks, flow-graphs, loops l27.5-9.ppt,	9.4,10.1,10.4
23.	Apr 22	CFA: l28.15-24.ppt
24.	Apr 27	Data-Flow Analysis (DFA): l29.25-34.ppt
25.	Apr 29	DFA: dags, bbOpt. Global DFA:paths, reaching defs, struct Progs, l p35-47.ppt
26.	May 04	DFA: iterative solution, structure-based solution, l31