CS304: Compilers (2018.A.01)

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.

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.

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

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

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.

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.

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

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. 

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.

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

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

Study slides 41-67.

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.

Study the slides.

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

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

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

Study these slides.

Study slides 1-5.

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.

Study slides 6 and 7.

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

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.

Read the Basics on pages 1-2.

Read through slide 45.

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.

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

Read slides 46-216.

Read these slides.

Watch the rest of this lecture.

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.

Read these slides.

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

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.

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.

Read Chapter 3 through section 3.1.

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

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).

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.

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.

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.

Read sections 3.7 to 3.13.

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

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.

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

Watch both lectures.

Read sections 3.14 to 3.18.

Read the following notes:

• Notes 10
• Notes 11
• Lecture 4
• Lecture 5
• Lecture 6

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.

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.

Watch these lectures.

Read sections 3.15 to the end of Chapter 3.

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).

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.

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.

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

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.

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

Read Chapter 4 on scope of names and symbol tables.

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

Read these slides.

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

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

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. 

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

Study the very interesting presentation on type checking by proofs.

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.

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

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

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. 

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.

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.

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.

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.

Watch these lectures

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

Read these notes.

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

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

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.

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.

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

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

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.

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

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.

Watch these videos.

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.

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.

Read Chapter 11 through section 11.1.

Read slides 1 through 8.

Read these slides.

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

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.

• Code Optimization
• Global Optimization
• Global Optimization II
  

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

• Introduction to Dataflow Analysis
• 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.

• Introduction to code optimization: instruction scheduling
• Loop optimization: instruction scheduling
• More loop optimizations
• Register allocation
• Parallelization
  
• Memory optimization

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.

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.

Read this article about certification of ANSI C compilers.

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.

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

Read these slides.