Topic Name Description
Course Introduction Page Course Syllabus
Page Course Terms of Use
1.1.1: Compiler Definitions, Terminology, and Anatomy of a Compiler URL Massachusetts Institute of Technology: S. Amarasinghe and M. Rinard's "Introduction to Computer Language Engineering"

For a definition of a compiler and some terminology, study slides 13-26. For an anatomy of a compiler see slides 27-47. For examples of optimization see slides 48-76. These slides have good examples of compiler output for a given input and a lot of examples of optimizations. A compiler translates a high-level language to a low-level language.

URL Stanford University: Keith Schwarz's "Introduction to Compilers"

For a slightly different overview of compilers, study slides 8-47. These slides make an analogy between compilation and the equivalence-preserving transformations of an electrical circuit.

URL Wikipedia: "Compilers"

Read the short paragraph on Related Techniques, which defines related terms: language translator, assembler, disassembler, and decompiler.

1.1.2: History URL Wikipedia: "Compilers"

Read the interesting history of the early compilers and computer pioneers, such as Grace Hopper, who worked on the first COBOL compiler.

URL Torben Ægidius Mogensen's "Basics of Compiler Design, Chapter 1: Introduction"

Read sections 1.1, 1.2, and 1.3. Note that "compile" means to translate from a high-level language, used by humans, to a low-level language used by a computer. A high-level language uses concepts, objects, and tasks performed by a human, whereas a low-level or machine language uses concepts, objects, and tasks performed by machines.

The input language to a compiler, typically a programming language, is called the source language. The output language of a compiler is called the target language or object code, typically an assembly language or machine language. 

The author describes seven phases of a compiler. The middle phase is called Intermediate Code Generation. The intermediate code is independent of a particular target machine. One of the back-end phases is called Machine Code Generation, which translates the machine-independent code to machine-dependent code for a particular computer.

The need for compilers arises from the need for high-level languages, which are more relevant for problem solving and software development by humans. Moreover, high-level languages are machine independent.

1.1.3: Other Applications URL Torben Ægidius Mogensen's "Basics of Compiler Design, Chapter 1: Introduction"

Read section 1.4, which gives reasons for studying compilers. In the discussion, the author suggests other applications for compiler techniques and tools. He specifically mentions domain-specific languages. Other applications derive from techniques and methods used in compilers. For example, if the input to a software system can be described using a formal grammar, then lexical- and syntax-phase techniques may be the most effective and efficient to use for inputting, verifying, and representing the data for processing. Front-end techniques can also be applied via software tools to the enforcement of development and programming standards and procedures. Knowledge of compiler techniques and methods helps in the design of new programming languages, new hardware architectures, generation of software applications, and the design of software tools.

1.1.4: Hardware Compilation URL Wikipedia: "Compilers"

Read the short paragraph on Hardware Compilation. Note that hardware compilation refers to the translation of a software program to a hardware representation.

1.2.1: One-Pass vs. Multi-Pass URL Wikipedia: "Compilers"

Read the paragraph on one-pass and multi-pass compilers. This distinction was more relevant in the early days of computing, when computer memory was limited and processing time was much slower compared to current computers.

A "pass" refers to reading and processing the input, i.e., source or source representation. A one-pass compiler is simpler to implement. However, more sophisticated processing, such as optimizations, may require multiple passes over the source representation.

The compiler is composed of components, which perform the steps of the compilation process. Some of the components may make a separate pass over the source representation--thus, the name of multi-pass. Multi-pass compilers are used for translating more complex languages (for example, high-level language to high-level language), and for performing more complete optimizations. Moreover, multi-pass compilers are easier to verify and validate, because testing and proof of correctness can be accomplished for the smaller components. Multi-pass compilers are also used for translation to an assembler or machine language for a theoretical machine, and for translation to an intermediate representation such as bytecode. Bytecode, or pcode (portable code), is a compact encoding that uses a one-byte instruction, and parameters for data or addresses, to represent the results of syntax and semantic analysis. The bytecode or pcode is independent of a particular machine. It is executed by a virtual machine residing on the target machine. 

1.2.2: Structure of a Compiler URL Stanford University: Keith Schwarz's "CS143 Course Overview"

Read the CS143 Course Overview handout. You have studied the lecture "Introduction to Compilers" already. The handout gives an overview of the structure of a compiler with a good explanation.

This overview describes the front-end process, or analysis stage, of the compilation process. The intermediate code used as an example is TAC, three-address code. The front end, or analysis, consists of lexical analysis, syntax analysis or parsing, semantic analysis, and intermediate code generation. Lexical analysis may be preceded by preprocessing, depending on the language and the development environment.

It also explains the back-end, or synthesis state, of the compilation process, which includes intermediate code optimization, object code generation, and object code optimization. The symbol table and error-handling topics apply to both the front end and to the back end. The section on one-pass versus multi-pass complements the previous explanation of the number of "passes" that a compiler uses.

The handout also has a very good section on history, which helps us understand why the structure of a compiler is as described in previous sections. Read the Historical Perspective section, which shows the important influence of programming languages on the development of compilers.

2.1: Motivation for Formal Languages URL Massachusetts Institute of Technology: S. Amarasinghe and M. Rinard's "Specifying Languages with Regular Expressions and Context-Free Grammars"

Study slides 2 - 8, and slides 38 - 41. Regular and context-free languages are introduced. Also, read slides 68 - 70.

URL Stanford University: Keith Schwarz's "Formal Grammars"

Read pages 10 - 11, which give some history of FORTRAN and ALGOL.

2.2: Formal Grammars URL Massachusetts Institute of Technology: S. Amarasinghe and M. Rinard's Lecture 3: "Introduction to Shift-Reduce Parsing"

Study slides 41-67.

URL Stanford University: Keith Schwarz's "Lexical Analysis"

Read pages 1 - 10. Formal languages are defined by formal grammars. Regular and context-free grammars are applied in scanning and parsing of programming languages. Formal grammars define the syntax of a formal language.

2.3: Syntax of Formal Languages URL University of California, Berkeley: Paul Hilfinger's "Parsing"

Study the slides.

2.4: Semantics of Formal Languages URL University of California, Berkeley: Paul Hilfinger's "Static Semantics Overview"

Study slides 1 - 7. Note that these slides are associated with the lecture below.

Page University of California, Berkeley: Paul Hilfinger's "Lecture 16"

Watch this video from 12:12 to 15:00, where Professor Hilfinger talks about semantics.

3.1: Definitions URL Massachusetts Institute of Technology: S. Amarasinghe and M. Rinard's "Specifying Languages with Regular Expressions and Context-Free Grammars"

Study slides 9 - 33. These slides describe and give examples of regular languages/regular expressions and their corresponding finite state machine.

URL University of California, Berkeley: Paul Hilfinger's "Lexical Analysis, Regular Expressions"

Study these slides.

URL University of California, Berkeley: Paul Hilfinger's "FSA"

Study slides 1-5.

3.2: Some Results and Examples of FSAs URL Massachusetts Institute of Technology: S. Amarasinghe and M. Rinard's "Specifying Languages with Regular Expressions and Context-Free Grammars"

Study slides 34 - 76. These slides give results and examples of conversion from a non-deterministic finite state automaton (NFA) to a deterministic finite state automaton (DFA); regular expressions or strings; context free grammars and pushdown automata (PDA); and context sensitive grammars and Turing machines. They also introduce parsing and abstract syntax trees.

URL University of California, Berkeley: Paul Hilfinger's "FSA"

Study slides 6 and 7.

3.3: Some Applications of FSA URL University of California, Berkeley: Paul Hilfinger's "FSA"

Study slides 8 to the end. These notes repeat some of the material from section 3.2 and provide additional practice in applying FSAs.

4.1: Lexical Analysis Introduction and Overview Page University of California, Berkeley: Paul Hilfinger's "Lecture 2"

Watch from the 4-minute mark to the 30-minute mark, and from the 37-minute mark to the end. This video gives you a glimpse into lexical analysis, which will be studied in more depth in the remaining sections of this unit.

4.2: Requirements for a Scanner URL Stanford University: Keith Schwarz's "Lexical Analysis"

Read the Basics on pages 1-2.

URL Stanford University: Keith Schwarz's "Lexical Analysis Notes"

Read through slide 45.

4.3: Review of Regular Expressions, FSAs, and Regular Languages URL Torben Ægidius Mogensen's "Basics of Compiler Design, Chapter 2: Lexical Analysis"

Look over Chapter 2 on Lexical Analysis. If you are comfortable with this material, just review it. If you feel you are somewhat uncomfortable with this material, read or study it to become comfortable with it; it is the foundation for much of our work on compilers.

A regular expression has associated non-deterministic finite automata (NFA) that accept it. 

The recognition of a regular expression in a regular language can be done in several ways: by operating on the expression directly, using an NFA, or using a DFA. Also, an automaton can be transformed to an equivalent having fewer states. The size (that is, the number of states) and the speed of the automaton determine the most efficient way to recognize a regular expression. Note in section 2.7 of the reading the time estimates for processing an expression by a DFA and by an NFA.

Regular languages include many languages and can be used for many applications, including scanners. Further, given regular languages, their union, concatenation, repetition, set difference, and intersection are also regular languages--we say that regular languages are closed under these operations. Regular languages can be expressed, equivalently, using regular expressions, NFAs, or DFAs. A key limiting characteristic of regular languages is seen from DFAs. A DFA is a finite automaton, and, thus, can remember only a finite number of symbols. Hence, a DFA cannot recognize a string of the type an b cn, for any n (because for any n it will require an infinite number of states to remember the number of a's). Most computer languages are not regular and we will need to use a larger formal language class to parse them.

4.4: Design of a Scanner URL Stanford University: Keith Schwarz's "Lexical Analysis"

Read from page 3 to the end, including Scanner Implementation 1 and 2, and the FORTRAN I Case Study.

URL Stanford University: Keith Schwarz's "Lexical Analysis Notes"

Read slides 46-216.

4.5: Construction of a Scanner URL University of California, Berkeley: Paul Hilfinger's "Lexical Analysis, Regular Expressions"

Read these slides.

Page University of California, Berkeley: Paul Hilfinger's "Lecture 2"

Watch the rest of this lecture.

URL Stanford University: Keith Schwarz's "FLEX in a Nutshell"

Read these notes. FLEX is a scanner generator. It produces a scanner, given a description of the patterns to be identified and actions to take for each token.

URL Stanford University: Keith Schwarz's "Introduction to FLEX"

Read these slides.

URL Torben Ægidius Mogensen's "Basics of Compiler Design, Chapter 2: Lexical Analysis"

Read section 2.9.1. Scanners are usually not written anew, but are generated by tools called scanner (or parser) generators.

URL The Flex Project: Vern Paxson, Will Estes, and John Millaway's The Flex Manual

Review this manual, which contains details on the Flex scanner generator. The link will take you to the introduction section of the manual. Use the links at the top of each page to navigate to the next page of the resource, reading up through section "24 Limitations". For further information, feel free to browse other parts of the manual, including the "Additional Readings" and "FAQ" sections.

4.6: Verification and Validation of a Scanner Page Tom Niemann's "Tutorial on Lex and Yacc"

Scanners for production compilers or software systems must be verified (by proof, demonstration, review, or test, that shows that the requirements, design, and performance specifications are met) and validated (also by proof, demonstration, review, or test that shows that the scanner satisfies the needs of its users and its role in a larger containing system--either compiler or system application). The amount of effort expended in verifying and validating a scanner is dependent on the purpose and intended use of the scanner. For both verification and validation, the description of the input language must be shown to be correct. If the scanner is generated, then the quality of the scanner depends on the reliability and effectiveness of the generator.

In this exercise, you will be introduced to LEX and YACC, which stand for Lexer (short for lexical analyzer) and Yet Another Compiler-Compiler. They are generators, i.e. programs that generate other programs, in this case, a scanner and a parser. Our focus in this Unit 4 Assessment will be on LEX, actually, FLEX - which stands for Fast Lexer. Read this tutorial on LEX; it provides a concise description of LEX and YACC. Then, complete the exercises on this page.

5.1: Parser Introduction and Overview URL Torben Ægidius Mogensen's "Basics of Compiler Design, Chapter 3: Syntax Analysis"

Read Chapter 3 through section 3.1.

URL University of California, Berkeley: Paul Hilfinger's "Parsing"

Read these notes. This material overlaps some of the readings later in the class. However, they add additional information and have a practical perspective.

5.2: Requirements of a Parser URL Wikipedia: "Parsing"

Read the following three paragraphs: "Programming languages," "Overview of the process," and "Types of Parsers." Requirements of a parser include: build internal representation of the input tokens (which come from the scanner); check that the input string of tokens is legal in the language of the compiler (i.e., that it can be derived from the start symbol); and determine the derivation steps for the input string of tokens. In addition, the parser should be reliable, efficient (how efficient depends on the intended use), user friendly (i.e., provide clear, accurate messages), and supportable (assuming that the parser will be used for a long time).

5.3: Functions of a Parser URL Torben Ægidius Mogensen's "Basics of Compiler Design, Chapter 3: Syntax Analysis"

Read subsections 3.4 - 3.6. The functions of a parser include: building an internal representation of the derivation tree and related parser information, and resolving ambiguities of the language pertaining to the input string of tokens.

URL Stanford University: Keith Schwarz's "Top-Down Parsing"

Read slide 4. The first bullet is a requirement statement and the third bullet is a function statement. An additional function is the output of meaningful and accurate messages, including error messages.

5.4: Formal Language Considerations URL Torben Ægidius Mogensen's "Basics of Compiler Design, Chapter 3: Syntax Analysis"

This subsection is just a review of what has been covered in units 2 and 3. Read subsections 3.2 and 3.3. The main idea is that context free languages are used to build efficient parsers, but are supplemented with special techniques to resolve ambiguities.

5.5.1: Top-Down Parsers URL Torben Ægidius Mogensen's "Basics of Compiler Design, Chapter 3: Syntax Analysis"

Read sections 3.7 to 3.13.

URL Stanford University: Keith Schwarz's "Top-Down Parsing"

Read these notes, as well as these slides from Lecture 3 and Lecture 4.

URL Massachusetts Institute of Technology: S. Amarasinghe and M. Rinard's "Top-Down Parsing"

This material overlaps some of the previous readings. However, it presents the material using examples. Scan over the slides, studying those that you feel will benefit you.

URL University of California, Berkeley: Paul Hilfinger's "Top-Down Parsers"

This material overlaps previous readings, but provides a practical view. Look over the material and study the parts you feel will benefit you.

Page University of California, Berkeley: Paul Hilfinger's "Lecture 7" and "Lecture 8"

Watch both lectures.

5.5.2: Bottom-Up Parsers URL Torben Ægidius Mogensen's "Basics of Compiler Design, Chapter 3: Syntax Analysis"

Read sections 3.14 to 3.18.

URL Stanford University: Keith Schwarz's "Bottom-Up Parsing"
URL Massachusetts Institute of Technology: S. Amarasinghe and M. Rinard's "Introduction to Shift-Reduce Parsing"

This material overlaps some of the previous readings. However, it presents the material using examples. Scan over the slides, studying those that you feel will benefit you.

URL University of California, Berkeley: Paul Hilfinger's "Earley's Algorithm" and "Bottom-Up Parsing"

This material overlaps previous readings, but provides a practical view. Look over the material and study the parts you feel will benefit you.

Read these notes, as well as the notes for Lecture 12.

Page University of California, Berkeley: Paul Hilfinger's "Lectures 10-14"

Watch these lectures.

5.6: Construction of a Parser URL Torben Ægidius Mogensen's "Basics of Compiler Design, Chapter 3: Syntax Analysis"

Read sections 3.15 to the end of Chapter 3.

URL Stanford University: Keith Schwarz's "Bottom-Up Parsing"

Read Notes 12, 14, and 16. Read the slides for lectures 5 (264 to the end), 6 (48 to the end), and 7 (91 to the end).

URL Massachusetts Institute of Technology: S. Amarasinghe and M. Rinard's "Parse Table Construction"

This material overlaps, but also complements, some of the previous readings. Scan over the slides, studying those that you feel will benefit you. In particular, in the introduction to shift-reduce parsing, study slides 60 to the end.

5.7: Verification and Validation of a Parser Page Tom Niemann's "Tutorial on LEX and YAC"

In this exercise, you will be introduced to LEX and YACC, which stand for Lexer (short for lexical analyzer) and Yet Another Compiler-Compiler. They are generators, i.e. programs that generate other programs, in this case, a scanner and a parser. Our focus in this Assessment will be on YACC. Read the part of the tutorial on YACC. This tutorial explains YACC and how YACC and LEX interface. LEX and YACC are the original programs, and just as Flex is an open software version for LEX, Bison is an open software version for YACC.

6.1: Syntax-Directed Translation and Attribute Grammars URL Torben Ægidius Mogensen's "Basics of Compiler Design, Chapter 5: Interpretation"

Read Chapter 5 on interpretation, where execution of a program takes place as the derivation is produced.

URL Stanford University: Keith Schwarz's "Syntax-Directed Translation"

Study the definitions and examples. Syntax-directed translation and attribute grammars are techniques for using the parser to drive the translation directly. Attributes are properties of grammar symbols, and the attributes take on values. Rules associated with each grammar production specify how to compute the value of the attributes.

6.2: Intermediate Representation URL Massachusetts Institute of Technology: S. Amarasinghe and M. Rinard's "Intermediate Formats"

Study the slides on intermediate representations. Data, as well as computations and flow of control, have intermediate representations.

URL Torben Ægidius Mogensen's "Basics of Compiler Design, Chapter 4: Scopes and Symbol Tables"

Read Chapter 4 on scope of names and symbol tables.

6.3.1: Scope Checking of Names in a Program URL Stanford University: Keith Schwarz's "Semantic Analysis"

Read the notes and the slides for an overview of semantic analysis.

6.3.2: Static vs. Dynamic Scope Checking URL University of California, Berkeley: Paul Hilfinger's "Static Semantics Overview"

Read these slides.

6.3.3: Type Checking URL Torben Ægidius Mogensen's "Basics of Compiler Design, Chapter 6: Type Checking"

Read Chapter 6, which presents an overview of type checking, nicely organized: symbol table environment, type checking for expressions, functions, and then, for programs.

6.3.3.1: Type Expressions, Type Equivalence, Type Inference, and What to Check URL Massachusetts Institute of Technology: S. Amarasinghe and M. Rinard's "Semantic Analysis"

Study the slides on type systems and what to check for when building intermediate representations for various language constructs.

URL University of California, Berkeley: Paul Hilfinger's "Types"

Read slides 2 through 14 and use them as a review or supplement to the above readings. Slides 15 through 31 give examples of type inference for the languages Prolog, Java, and Python. 

Page University of California, Berkeley: Paul Hilfinger's "Lectures 18-21"

These lectures correspond to the notes and are optional. They may be helpful in understanding some of the notes.

6.3.3.2: Type Systems as Proof Systems-Type Checking as Proofs URL Stanford University: Keith Schwarz's "Type Checking"

Study the very interesting presentation on type checking by proofs.

URL University of California, Berkeley: Paul Hilfinger's "Type Inference and Unification"

Read slides 1 through 8. The slides are somewhat formal and present a "type calculus." Use these slides to add to your understanding of types.

Page University of California, Berkeley: Paul Hilfinger's "Lecture 22"

This video corresponds to these notes and is optional. If it adds to the notes and helps you, watch it.

6.3.3.3: Applications of Type Proofs URL Stanford University: Keith Schwarz's "Type Checking II"

Study the application of the type proof system (introduced above) to the detection of type errors.

6.3.3.4: Type Equations, Unification and Binding of Type Expressions URL University of California, Berkeley: Paul Hilfinger's "Type Inference and Unification"

Study slides 8 through 19. The slides supplement the readings above with type examples. A binding is a substitution of a type expression for a type variable. 

6.4: Verification and Validation of Semantic Analysis URL Torben Ægidius Mogensen's "Basics of Compiler Design, Chapter 6: Type Checking"

Complete exercises 6.1 and 6.2 on pages 143 and 144.

These exercises will give you some practice with semantic analysis and are based on Chapter 6, which covers type checking. Then check your answers against the Answer Key.

7.1: Overview of Runtime Environments URL Stanford University: Keith Schwarz's "Runtime Environments"

Read this handout, which discusses data representations and their organization in memory for a program. After semantic analysis, intermediate representations are encoded. This is the last step of the "front-end" of the compilation process. The relationship of front ends to back ends can be many-to-one or one-to-many. In the former case, a single back end is used for several languages, each handled by its own front end. In the latter case, one front end handles the input, source language, and the back end is used for several target machines, each having its own back end.

URL Stanford University: Keith Schwarz's "Runtime Environments Slides"

Read the functions of IR generation on slides 6 and 7. Some requirements for IR generation are on slide 8. Encoding of primitive types and arrays are discussed on slides 19 through 37 for additional coverage. 

Scope of a variable is the lexical area of a program in which the variable can be used. Extent, or lifetime, is the period of time that a variable exists.

See slides 38 through 118 for a discussion of the stack, activation trees, closure and coroutines, and parameter passing.

URL University of California, Berkeley: Paul Hilfinger's "Introduction to Runtime Organization"

Read these notes. In this presentation, IR is treated as part of code generation, and it has a lot of detail on the run-time encoding for procedures and functions.

Page University of California, Berkeley: Paul Hilfinger's "Lectures 25-27"

Watch these lectures

7.2: More Complicated Representations: Objects and Inheritance URL Stanford University: Keith Schwarz's "Runtime Environments II"

Read these slides, which describe the encoding of objects, inheritance, and dynamic type checking, including difficulties and solutions.

7.3: Encoding of Exceptions and OOP (Object-Oriented Programs) URL University of California, Berkeley: Paul Hilfinger's "Exceptions, OOP"

Read these notes.

Page University of California, Berkeley: Paul Hilfinger's "Lectures 28-30"

Scan over these and watch the parts that will benefit you.

8.1: Introduction to Intermediate Code Generation URL Torben Ægidius Mogensen's "Basics of Compiler Design, Chapter 7: Intermediate-Code Generation"

Read Chapter 7, which discusses generation to a relatively low-level intermediate language. Section 7.9 overlaps some of the previous readings.

URL Stanford University: Keith Schwarz's "Intermediate Representation"

Intermediate representation of a source program may be part of the front end, may be part of the back end, depending on the design of the compiler and its intended use, or may be simply called the "middle part" of the compiler between the front end and back end. Handout 23 covers IR in the context of code generation.

8.2: Detailed Example: Three Address Code (TAC) URL Stanford University: Keith Schwarz's "TAC Examples"

TAC is a generic assembly language. Read this handout, and then the associated slides. Slides 1 through 149 give examples of TAC statements, function calls and encoding of objects.

8.3: Additional Intermediate Language Generation Examples URL University of California, Berkeley: Paul Hilfinger's "Code Generation"

These notes discuss generation of intermediate code for a stack machine, stack machine with accumulator, and for a TAC machine. 

Page University of California, Berkeley: Paul Hilfinger's "Lecture 31"

This lecture is optional, and is listed as an aid if you have any questions on the notes.

8.4: Generation of Machine Code URL Torben Ægidius Mogensen's "Basics of Compiler Design, Chapter 8: Machine-Code Generation"

Read Chapter 8. It describes the translation from a low-level intermediate language to machine code. This translation addresses the handling of restrictions on the machine language; for example, a finite number of registers is a restriction of a target machine and its machine language. The intermediate language assumes an unlimited number of registers, i.e., virtual register machine.

URL University of California, Berkeley: Paul Hilfinger's "Registers, Functions, Parameters"

Read these notes on generation of machine code from intermediate code.

URL Torben Ægidius Mogensen's "Basics of Compiler Design, Chapter 9 and Chapter 10"

Read Chapters 9 and 10. Chapter 9 overlaps the above reading, and is a supplementary discussion of the problem of mapping a large number of variables used in an intermediate language translation into a smaller number of registers, plus memory locations available on the target machine. Chapter 10 covers function calls using a stack, activation records, and frame pointers. Look over these chapters and read the parts that will add to your understanding of register allocation and function calls.

Page University of California, Berkeley: Paul Hilfinger's "Lectures 32-34"

Watch these videos.

URL Stanford University: Keith Schwarz's "Register Allocation" and "Garbage Collection"

Read these notes, as well as the ones on Garbage Collection. These are very well-done formal presentations and give a lot of detail. Register allocation, linear scan and Chaitin's algorithm are explained. Regarding garbage collection, reference counting, mark-and-sweep, and stop-and-copy are explained.

8.5: Verification and Validation of Code Generation URL Torben Ægidius Mogensen's "Basics of Compiler Design, Chapter 7: Intermediate-Code Generation"

Do Exercise 7.1 on page 173 and Exercise 8.2 on page 189.

These exercises will give you some practice with code generation and are based on Chapter 7, which covers intermediate code generation, and Chapter 8, which covers machine code generation. Intermediate code can be high level, i.e. close to the input language, or low level, i.e. close to the target machine language, and, hence, though Exercise #2 jumps to Chapter 8, the process of syntax directed translation is the same. These exercises illustrate the process for syntax directed translation to intermediate code or machine code. You can check your answers against the Answer Key.

9.1: The What and Why of Code Optimizations URL Torben Ægidius Mogensen's "Basics of Compiler Design, Chapter 11: Analysis and Optimisation"

Read Chapter 11 through section 11.1.

9.2: Fundamentals of Code Optimization URL University of California, Berkeley: Paul Hilfinger's "Local Optimization"

Read slides 1 through 8.

URL Massachusetts Institute of Technology: S. Amarasinghe and M. Rinard's "Introduction to Program Analysis and Optimization"

Read these slides.

9.3: Local Intermediate Code Optimizations: Definitions and Examples URL Stanford University: Keith Schwarz's "IR Optimization"

Read pages 1 through 10 of the handout, and the associated lecture notes, which are an excellent unified formal treatment of the topic.

9.4: Global Intermediate Code Optimizations: Definitions and Examples URL University of California, Berkeley: Paul Hilfinger's "Global Optimization"

Read these slides. Global optimization uses forward analysis (e.g., constant propagation), which moves information forward, and backward analysis (e.g., liveness), which moves information backward. Note slide 5, which states that dynamic properties of a program are undecidable.

URL Stanford University: Keith Schwarz's "Code Optimization", "Global Optimization", and "Global Optimization II"

Read these pages, which cover the material in more detail and present it in a unified formal way using semilattices.

URL Massachusetts Institute of Technology: S. Amarasinghe and M. Rinard's "Introduction to Dataflow Analysis" and "Foundations of Dataflow Analysis"

Read these slides. They repeat some of the material from above readings. However, they are an excellent review, and go into detail on the formalism that underlies global optimizations.

9.5: Code Optimization URL Massachusetts Institute of Technology: S. Amarasinghe and M. Rinard's "Notes for Lectures 13-18"

Read these slides. If you find a part that is helpful and adds to your knowledge of optimizations, read it. These slides repeat some of the material from above readings. However, they are an excellent review, concise and clear, and reinforce key points. They also provide additional examples.

9.6: Verification and Validation of Code Optimization URL Torben Ægidius Mogensen's "Basics of Compiler Design, Chapter 11: Analysis and Optimisation"

Do Exercise 11.1 parts a) and b) on page 254.

This exercise will give you some practice with code optimization and is based on Chapter 11, which covers analysis and optimization. The exercise uses common subexpression elimination as an example of optimization. You can check your answers against the Answer Key.

10.1: Compiler Verification and Validation URL Wikipedia: "ANSI C"

Read this article about certification of ANSI C compilers.

Page Unit 10 Assignment

Review verification and validation of lexical analyzers, parsers, semantic analyzers, code generators, and code optimizers. In this unit (Unit 10) and in these exercises, we combine the ideas of those sections and look at an integrated approach to the verification and validation of the compiler as a whole.

11.1: Compiler Summary and Next Steps URL Stanford University: Keith Schwarz's "Code Optimization"

Read slides 226 through 234, which provide a concise outline of the topics covered in our course.

URL University of California, Berkeley: Paul Hilfinger's "Notes for Lecture 39"

Read these slides.

Page University of California, Berkeley: Paul Hilfinger's "Lecture 39"

Watch this video.