• Welcome
• Introduction
• The Scanner
• The Parser
• The Semantic Analyzer
• The Intermediate Code Generator
• The Optimizer
• The Code Generator

Hello, and welcome to the course readings for Drew Davidson's EECS 665, "Compiler Construction". This set of course notes has been shaped by me (Drew) in order to serve as a written companion to the course lectures and discussions offered as part of EECS665. As such, it's written pretty informally, and will often draw on my personal observations and experience. These readings are not intended to serve as a standalone reference for compiler topics or as a guide for building a compiler. Thus, I'll start these readings with a disclaimer exactly opposite of most textbooks: it is not for a general audience, and it is intended to be read straight through from start to back.

Some additional disclaimers: In the interest of brevity, these readings will occasionally adopt a definition and stick to it without fully exploring alternative definitions, or considering all implications of the definition. If you feel that a superior definition exists, please do let me know. Furthermore, the readings constitute a living document, updated and refined when possible. If you see a typo, mistake, or even just something where you'd like some more writing, please do let me know.

While much of the material in the course readings has been updated, modified, or written by me, it is based originally on a set of readings created by Susan Horwitz at the University of Wisconsin-Madison. In the interest of providing the best possible guide to the subject, I will frequently read or re-read classic textbooks on compilers, and whatever course materials from other classes might be floating around on the internet. It is my intention to synthesize this information and provide wholly original material herein. That being said, if you see an example or text in the readings that you feel has not been appropriately credited to an external source, please contact me at your earliest convenience so that we can arrange for the material to be taken down, cited, or come to another arrangement.

What is a compiler? A common answer amongst my students is something like "A program that turn code into a program", which is honestly not bad (if a bit imprecise). Without dwelling overly much on the messy details, let's refine this definition and run with it. For this class, we'll say that a compiler is:

• A recognizer of some source language S.
• A translator (of programs written in S into programs written in some object or target language T).
• A program written in some host language H

Here's a simple pictorial view:

A compiler operates in phases; each phase translates the source program from one representation to another. Different compilers may include different phases, and/or may order them somewhat differently. A typical organization is shown below.

Below, we look at each phase of the compiler, giving a high-level overview of how the code snippet position = initial + rate + 60 is represented throughout the above workflow.

The Scanner

The scanner performs lexical analysis, which means to group the input characters into the fundamental units of the source language. If some character(s) of input fails to correspond to a valid group, the scanner may also report lexical errors.

Some terminology for lexical analysis:

• The scanner groups the characters into lexemes (sequences of characters that "go together").
• Each lexeme corresponds to a token; the scanner forwards each token (plus maybe some additional information, such as a position within at which the token was found in the input file) to the parser.

The definitions of what is a lexeme, token, or bad character all depend on the source language.

The errors that a scanner might report are usually due to characters that cannot be a valid part of any token.

The Parser

The parser performs syntactic analysis, which means to group the tokens of the language into constructs of the programming language (such as loops, expressions, functions, etc). A good analogy is to think of the scanner as building the "words" of the programming language, and the parser as building the "sentences" or "grammatical phrases" of the source program.

• Groups tokens into "grammatical phrases", discovering the underlying structure of the source program.
• Finds syntax errors. For example, the source code
  5 position = ;
  could correspond  to the sequence of tokens:
  intlit id assign semicolon
  All are legal tokens, but that sequence of tokens is erroneous.
• Might find some "static semantic" errors, e.g., a use of an undeclared variable, or variables that are multiply declared.
• Might generate code, or build some intermediate representation of the program such as an abstract-syntax tree.

The semantic analyzer checks for (more) "static semantic" errors, e.g., type errors. It may also annotate and/or change the abstract syntax tree (e.g., it might annotate each node that represents an expression with its type).

Example:

Abstract syntax tree before semantic analysis:

Abstract syntax tree after semantic analysis:

The Intermediate Code Generator

The intermediate code generator translates from abstract-syntax tree to intermediate code. One possibility is 3-address code (code in which each instruction involves at most 3 operands). Below is an example of 3-address code for the abstract-syntax tree shown above. Note that in this example, the second and third instructions each have exactly three operands (the location where the result of the operation is stored, and two operators); the first and fourth instructions have just two operands ("temp1" and "60" for instruction 1, and "position" and "temp3" for instruction 4).

		temp1 = inttofloat(60)
		temp2 = rate * temp1
		temp3 = initial + temp2
		position = temp3

The Optimizer

The optimizer tries to improve code generated by the intermediate code generator. The goal is usually to make code run faster, but the optimizer may also try to make the code smaller. In the example above, an optimizer might first discover that the conversion of the integer 60 to a floating-point number can be done at compile time instead of at run time. Then it might discover that there is no need for "temp1" or "temp3". Here's the optimized code:

		temp2 = rate * 60.0
		position = initial + temp2

The Code Generator

The code generator generates assembly code from (optimized) intermediate code. For example, the following x64 code might be generated for our running example:

        movl    rate(%rip), %eax
        imull   $60, %eax, %edx
        movl    initial(%rip), %eax
        addl    %edx, %eax
        movl    %eax, position(%rip)

It's worth noting that the above representation of the running example is still a text file, though one that the compiler proper considers to be the final output. There is still work left to be done before we have an executable program. Usually, a collection of programs, collectively referred to as a compiler toolchain, work in sequence to build the executable:

• The assembler transforms an assembly code file (such as one produced by the compiler) into a relocatable, which is either an object file (typically given the .o extension) or a library (typically given the .so or .a extension, for a dynamically-linked or statically-linked library, respectively).
• The linker merges the various object files and static libraries output by the assembler into a single executable.

When it comes time for the program to actually be run, the loader maps the executable file into memory (alongside whatever dynamic libraries may be required) as a process, and then hands control to the operating system to actually begin execution of the program. In modern workstation computing, the loader is integrated into the Operating System, but in some legacy, specialized, and embedded systems the loader is still a distinct program.

Students who use compilers like gcc or llvm are often surprised at the existence of distinct "post-compilation" steps to produce an executable. Indeed the term "compiler" is often used to refer to the full "compiler toolchain".

Nevertheless, the workflow from compilation, to assembly, to linkage, is represented as a series of distinct modules within many popular compilers, and each of the tools can be invoked separately. For example, running the toolchain for C gcc can be accomplished using cc (the c compiler proper), as (the gnu assembler), and ld (the gnu linker).

• Overview
• Finite-State Machines
  • Example: Pascal Identifiers
  • Self Study #1
  • Example: Integer Literals
  • Formal Definition
  • Deterministic and Non-Deterministic FSMs
  • How to Implement a FSM
• Regular Expressions
  • Self Study #2
  • Example: Integer Literals
  • The Language Defined by a Regular Expression
• Using Regular Expressions and Finite-State Machines to Define a Scanner
  • Self Study #3

OverviewL

Recall that the job of the scanner is to translate the sequence of characters that is the input to the compiler to a corresponding sequence of tokens. In particular, each time the scanner is called it should find the longest sequence of characters in the input, starting with the current character, that corresponds to a token, and should return that token.

It is possible to write a scanner from scratch, but it is often much easier and less error-prone approach is to use a scanner generator like lex or flex (which produce C or C++ code), or jlex (which produces java code). The input to a scanner generator includes one regular expression for each token (and for each construct that must be recognized and ignored, such as whitespace and comments). Therefore, to use a scanner generator you need to understand regular expressions. To understand how the scanner generator produces code that correctly recognizes the strings defined by the regular expressions, you need to understand finite-state machines (FSMs).

A finite-state machine is similar to a compiler in that:

• A compiler recognizes legal programs in some (source) language.
• A finite-state machine recognizes legal strings in some language.

In both cases, the input (the program or the string) is a sequence of characters.

A FSM is applied to an input (a sequence of characters). It either accepts or rejects that input. Here's how the FSM works:

• The FSM starts in its start state.
• If there is a edge out of the current state whose label matches the current input character, then the FSM moves to the state pointed to by that edge, and "consumes" that character; otherwise, it gets stuck.
• The finite-state machine stops when it gets stuck or when it has consumed all of the input characters.

An input string is accepted by a FSM if:

• The entire string is consumed (the machine did not get stuck), and
• the machine ends in a final state.

The language defined by a FSM is the set of strings accepted by the FSM.

The following strings are in the language of the FSM shown above:

• x
• tmp2
• XyZzy
• position27

The following strings are not in the language of the FSM shown above:

• 123
• a?
• 13apples

Let us consider another example of an FSM:

An FSM is a 5-tuple: $(Q,\Sigma,\delta,q,F)$

• $Q$ is a finite set of states ($\{\mathrm{S,A,B}\}$ in the above example).
• $\Sigma$ (an uppercase sigma) is the alphabet of the machine, a finite set of characters that label the edges ($\{+,-,0,1,...,9\}$ in the above example).
• $q$ is the start state, an element of $Q$ ($\mathrm{S}$ in the above example).
• $F$ is the set of final states, a subset of $Q$ ({B} in the above example).
• $\delta$ is the state transition relation: $Q \times \Sigma \rightarrow Q$ (i.e., it is a function that takes two arguments -- a state in $Q$ and a character in $\Sigma$ -- and returns a state in $Q$).

Here's a definition of $\delta$ for the above example, using a state transition table:

Deterministic and Non-Deterministic FSMsL

There are two kinds of FSM:

1. Deterministic:
   • No state has more than one outgoing edge with the same label.
2. Non-Deterministic:
   • States may have more than one outgoing edge with same label.
   • Edges may be labeled with $\varepsilon$ (epsilon), the empty string. The FSM can take an $\varepsilon$-transition without looking at the current input character.

Example

Here is a non-deterministic finite-state machine that recognizes the same language as the second example deterministic FSM above (the language of integer literals with an optional sign):

Sometimes, non-deterministic machines are simpler than deterministic ones, though not in this example.

A string is accepted by a non-deterministic finite-state machine if there exists a sequence of moves starting in the start state, ending in a final state, that consumes the entire string. For example, here's what happens when the above machine is run on the input "+75":

It is worth noting that there is a theorem that says:

For every non-deterministic finite-state machine $M$, there exists a deterministic machine $M'$ such that $M$ and $M'$ accept the same language.

How to Implement a FSM

The most straightforward way to program a (deterministic) finite-state machine is to use a table-driven approach. This approach uses a table with one row for each state in the machine, and one column for each possible character. Table[j][k] tells which state to go to from state j on character k. (An empty entry corresponds to the machine getting stuck, which means that the input should be rejected.)

Recall the table for the (deterministic) "integer literal" FSM given above:

The table-driven program for a FSM works as follows:

• Have a variable named state, initialized to S (the start state).
• Repeat:
  • read the next character from the input
  • use the table to assign a new value to the state variable
  until the machine gets stuck (the table entry is empty) or the entire input is read. If the machine gets stuck, reject the input. Otherwise, if the current state is a final state, accept the input; otherwise, reject it.

Regular Expressions

Regular expressions provide a compact way to define a language that can be accepted by a finite-state machine. Regular expressions are used in the input to a scanner generator to define each token, and to define things like whitespace and comments that do not correspond to tokens, but must be recognized and ignored.

As an example, recall that a Pascal identifier consists of a letter, followed by zero or more letters or digits. The regular expression for the language of Pascal identifiers is:

letter . (letter | digit)*

Often, the "followed by" dot is omitted, and just writing two things next to each other means that one follows the other. For example:

letter (letter | digit)*

In fact, the operands of a regular expression should be single characters or the special character epsilon, meaning the empty string (just as the labels on the edges of a FSM should be single characters or epsilon). In the above example, "letter" is used as a shorthand for:

a | b | c | ... | z | A | ... | Z

To understand a regular expression, it is necessary to know the precedences of the three operators. They can be understood by analogy with the arithmetic operators for addition, multiplication, and exponentiation:

Regular Expression Operator	Analogous Arithmetic Operator	Precedence
|	plus	lowest precedence
.	times	middle
*	exponentiation	highest precedence

So, for example, the regular expression:

$\mathrm{letter}.\mathrm{letter} | \mathrm{digit}\mathrm{^*}$

$(\mathrm{letter}.\mathrm{letter}) | (\mathrm{digit}\mathrm{^*})$

Example: Integer LiteralsL

Let's re-examine the example of integer literals for regular-expressions:

The Language Defined by a Regular ExpressionL

Every regular expression defines a language: the set of strings that match the expression. We will not give a formal definition here, instead, we'll give some examples:

Using Regular Expressions and FSMs to Define a ScannerL

There is a theorem that says that for every regular expression, there is a finite-state machine that defines the same language, and vice versa. This is relevant to scanning because it is usually easy to define the tokens of a language using regular expressions, and then those regular expression can be converted to finite-state machines (which can actually be programmed).

For example, let's consider a very simple language: the language of assignment statements in which the left-hand side is a Pascal identifier (a letter followed by one or more letters or digits), and the right-hand side is one of the following:

• ID + ID
• ID * ID
• ID == ID

Token	Regular Expression
assign	"="
id	letter (letter | digit)*
plus	"$+$"
times	"$*$"
equals	"="."="

These regular expressions can be converted into the following finite-state machines:

Given a FSM for each token, how do we write a scanner? Recall that the goal of a scanner is to find the longest prefix of the current input that corresponds to a token. This has two consequences:

1. The scanner sometimes needs to look one or more characters beyond the last character of the current token, and then needs to "put back" those characters so that the next time the scanner is called it will have the correct current character. For example, when scanning a program written in the simple assignment-statement language defined above, if the input is "==", the scanner should return the EQUALS token, not two ASSIGN tokens. So if the current character is "=", the scanner must look at the next character to see whether it is another "=" (in which case it will return EQUALS), or is some other character (in which case it will put that character back and return ASSIGN).

2. It is no longer correct to run the FSM program until the machine gets stuck or end-of-input is reached, since in general the input will correspond to many tokens, not just a single token.

Furthermore, remember that regular expressions are used both to define tokens and to define things that must be recognized and skipped (like whitespace and comments). In the first case a value (the current token) must be returned when the regular expression is matched, but in the second case the scanner should simply start up again trying to match another regular expression.

With all this in mind, to create a scanner from a set of FSMs, we must:

• modify the machines so that a state can have an associated action to "put back N characters" and/or to "return token XXX",
• we must combine the finite-state machines for all of the tokens in to a single machine, and
• we must write a program for the "combined" machine.

For example, the FSM that recognizes Pascal identifiers must be modified as follows:

with the following table of actions:

And here is the combined FSM for the five tokens (with the actions noted below):

with the following table of actions:

We can convert this FSM to code using the table-driven technique described above, with a few small modifications:

• The table will include a column for end-of-file as well as for all possible characters (the end-of-file column is needed, for example, so that the scanner works correctly when an identifier is the last token in the input).
• Each table entry may include an action as well as or instead of a new state.
• Instead of repeating "read a character; update the state variable" until the machine gets stuck or the entire input is read, the code will repeat: "read a character; perform the action and/or update the state variable" (eventually, the action will be to return a value, so the scanner code will stop, and will start again in the start state next time it is called).

• Overview
• Example: Simple Arithmetic Expressions
• Formal Definition
• Example: Boolean Expressions, Assignment Statements, and If Statements
• Self-Study #1
• The Language Defined by a CFG
• Leftmost and Rightmost Derivations
• Parse Trees
• Self-Study #2

Recall that the input to the parser is a sequence of tokens (received interactively, via calls to the scanner). The parser:

• Groups the tokens into "grammatical phrases".
• Discovers the underlying structure of the program.
• Finds syntax errors.
• Perhaps also performs some actions to find other kinds of errors.

The output depends on whether the input is a syntactically legal program; if so, then the output is some representation of the program:

• an abstract-syntax tree (maybe + a symbol table),
• or intermediate code,
• or object code.

We know that we can use regular expressions to define languages (for example, the languages of the tokens to be recognized by the scanner). Can we use them to define the language to be recognized by the parser? Unfortunately, the answer is no. Regular expressions are not powerful enough to define many aspects of a programming language's syntax. For example, a regular expression cannot be used to specify that the parentheses in an expression must be balanced, or that every ``else'' statement has a corresponding ``if''. Furthermore, a regular expression doesn't say anything about underlying structure. For example, the following regular expression defines integer arithmetic involving addition, subtraction, multiplication, and division:

digit+ (("+" | "-" | "*" | "/") digit+)*

Example: Simple Arithmetic ExpressionsL

We can write a context-free grammar (CFG) for the language of (very simple) arithmetic expressions involving only subtraction and division. In English:

• An integer is an arithmetic expression.
• If exp₁ and exp₂ are arithmetic expressions, then so are the following:
  • exp₁ - exp₂
  • exp₁ / exp₂
  • ( exp₁ )

And here is how to understand the grammar:

• The grammar has five terminal symbols: intliteral minus divide lparen rparen. The terminals of a grammar used to define a programming language are the tokens returned by the scanner.
• The grammar has one nonterminal: Exp (note that a single name, Exp, is used instead of Exp₁ and Exp₂ as in the English definition above).
• The grammar has four productions or rules, each of the form:
  Exp $\longrightarrow$ ...
  A production left-hand side is a single nonterminal. A production right-hand side is either the special symbol $\varepsilon$ (the same $\varepsilon$ that can be used in a regular expression) or a sequence of one or more terminals and/or nonterminals (there is no rule with $\varepsilon$ on the right-hand side in the example given above).

A more compact way to write this grammar is:

Intuitively, the vertical bar means "or", but do not be fooled into thinking that the right-hand sides of grammar rules can contain regular expression operators! This use of the vertical bar is just shorthand for writing multiple rules with the same left-hand-side nonterminal.

A CFG is a 4-tuple $\left( N, \Sigma, P, S \right)$ where:

• $N$ is a set of nonterminals.
• $\Sigma$ is a set of terminals.
• $P$ is a set of productions (or rules).
• $S$ is the start nonterminal (sometimes called the goal nonterminal) in $N$. If not specified, then it is the nonterminal that appears on the left-hand side of the first production.

Example: Boolean Expressions, Assignment Statements, and If StatementsL

The language of boolean expressions can be defined in English as follows:

• "true" is a boolean expression, recognized by the token true.
• "false" is a boolean expression, recognized by the token false.
• If exp₁ and exp₂ are boolean expressions, then so are the following:
  • exp₁ || exp₂
  • exp₁ && exp₂
  • ! exp₁
  • ( exp₁ )

Here is a CFG for a language of very simple assignment statements (only statements that assign a boolean value to an identifier):

Stmt $\;\longrightarrow\;$ id  assign  BExp  semicolon

We can "combine" the two grammars given above, and add two more rules to get a grammar that defines a language of (very simple) if-statements. In words, an if-statement is:

1. The word "if", followed by a boolean expression in parentheses, followed by a statement, or
2. The word "if", followed by a boolean expression in parentheses, followed by a statement, followed by the word "else", followed by a statement.

Here is the combined context-free grammar:

The language defined by a context-free grammar is the set of strings (sequences of terminals) that can be derived from the start nonterminal. What does it mean to derive something?

• Start by setting the "current sequence" to be the start nonterminal.
• Repeat:
  • find a nonterminal $X$ in the current sequence;
  • find a production in the grammar with $X$ on the left (i.e., of the form $X$ → $\alpha$, where $\alpha$ is either $\varepsilon$ (the empty string) or a sequence of terminals and/or nonterminals);
  • Create a new "current sequence" in which $\alpha$ replaces the $X$ found above;
  until the current sequence contains no nonterminals.

Thus, we arrive either at $\varepsilon$ or at a string of terminals. That is how we derive a string in the language defined by a CFG.

Below is an example derivation, using the 4 productions for the grammar of arithmetic expressions given above. In this derivation, we use the actual lexemes instead of the token names (e.g., we use the symbol "-" instead of minus).

Exp $\Longrightarrow$ Exp - Exp$\Longrightarrow$ 1 - Exp$\Longrightarrow$ 1 - Exp / Exp$\Longrightarrow$ 1 - Exp / 2 $\Longrightarrow$ 1 - 4 / 2

And here is some useful notation:

• $\Longrightarrow$ means derives in one step
• $\stackrel{+}\Longrightarrow$ means derives in one or more steps
• $\stackrel{*}\Longrightarrow$ means derives in zero or more steps

So, given the above example, we could write: Exp $\stackrel{+}\Longrightarrow$ 1 - Exp / Exp.

A more formal definition of what it means for a CFG $G$ to define a language may be stated as follows:

Leftmost and Rightmost DerivationsL

There are several kinds of derivations that are important. A derivation is a leftmost derivation if it is always the leftmost nonterminal that is chosen to be replaced. It is a rightmost derivation if it is always the rightmost one.

Parse TreesL

Another way to derive things using a context-free grammar is to construct a parse tree (also called a derivation tree) as follows:

• Start with the start nonterminal.
• Repeat:
  • choose a leaf nonterminal $X$
  • choose a production $X \longrightarrow \alpha$
  • the symbols in $\alpha$ become the children of $X$ in the tree
  until there are no more leaf nonterminals left.

The derived string is formed by reading the leaf nodes from left to right.

Here is the example expression grammar given above:

Exp $\longrightarrow$ intliteral  | Exp minus Exp  | Exp divide Exp  | lparen Exp rparen

and, using that grammar, here's a parse tree for the string 1 - 4 / 2:

---

Self-Study #2L Below is the CFG for very simple if-statements used earlier.

Stmt $\;\longrightarrow\;$ if lparen BExp rparen Stmt
Stmt $\;\longrightarrow\;$ if lparen BExp rparen Stmt else Stmt
Stmt $\;\longrightarrow\;$ id assign BExp semicolon
BExp $\;\longrightarrow\;$ true
BExp $\;\longrightarrow\;$ false
BExp $\;\longrightarrow\;$ BExp or BExp
BExp $\;\longrightarrow\;$ BExp and BExp
BExp $\;\longrightarrow\;$ not BExp
BExp $\;\longrightarrow\;$ lparen BExp rparen

Question 1: Give a derivation for the string: if (! true ) x = false; Is your derivation leftmost, rightmost, or neither?

Question 2: Give a parse tree for the same string.

solution