• 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

For each nonterminal $A$:
• Find the longest non-empty prefix $\alpha$ that is common to 2 or more production right-hand sides.
• Replace the productions:

  $A$

  $\longrightarrow$

  $\alpha$ $\beta_1$ | $\ldots$ | $\alpha$ $\beta_m$ | y1 | .. | yn

  with:

  $A$	$\longrightarrow$	$\alpha$ $A'$   |   $y_1$   |   $\ldots$   |   $y_n$
  $A'$	$\longrightarrow$	$\beta_1$ |   $\ldots$   |   $\beta_m$

  Repeat this process until no nonterminal has two productions with a common prefix.

Note that this transformation (like the one for removing immediate left recursion) has the disadvantage of making the grammar much harder to understand. However, it is necessary if you need an LL(1) grammar.

Here's an example that demonstrates both left-factoring and immediate left-recursion removal:

• The original grammar is:

  $Exp$

  $\longrightarrow$

  ( $Exp$ ) $\;|\;$ $Exp$ $Exp$ $\;|\;$ (  )

• After removing immediate left-recursion, the grammar becomes:

  $Exp$	$\longrightarrow$	( $Exp$ ) $Exp'$ $\;|\;$ (  ) $Exp'$
  $Exp'$	$\longrightarrow$	$Exp$ $Exp'$ $\;|\;$ $\varepsilon$

• After left-factoring, this new grammar becomes:

  $Exp$	$\longrightarrow$	( $Exp''$
  $Exp''$	$\longrightarrow$	$Exp$ ) $Exp'$ $\;|\;$ ) $Exp'$
  $Exp'$	$\longrightarrow$	$Exp$ $Exp'$ $\;|\;$ $\varepsilon$

solution

---

TEST YOURSELF #2

Using the same grammar: exp ::= ( exp ) | exp exp | ( ), do left factoring first, then remove immediate left recursion.

---

FIRST and FOLLOW Sets

Recall: A predictive parser can only be built for an LL(1) grammar. A grammar is not LL(1) if it is:

• Left recursive, or
• not left factored.
However, grammars that are not left recursive and are left factored may still not be LL(1). As mentioned earlier, to see if a grammar is LL(1), we try building the parse table for the predictive parser. If any element in the table contains more than one grammar rule right-hand side, then the grammar is not LL(1).

To build the table, we must must compute FIRST and FOLLOW sets for the grammar.

FIRST Sets

Ultimately, we want to define FIRST sets for the right-hand sides of each of the grammar's productions. To do that, we define FIRST sets for arbitrary sequences of terminals and/or nonterminals, or $\varepsilon$ (since that's what can be on the right-hand side of a grammar production). The idea is that for sequence $\alpha$, FIRST($\alpha$) is the set of terminals that begin the strings derivable from $\alpha$, and also, if $\alpha$ can derive $\varepsilon$, then $\varepsilon$ is in FIRST($\alpha$). Using derivation notation: $$\mathrm{FIRST}(\alpha) = \left\{ \; t \; \middle| \; \left( t \; \in \Sigma \wedge \alpha \stackrel{*}\Longrightarrow t \beta \right) \vee \left( t = \varepsilon \wedge \alpha \stackrel{*}\Longrightarrow \varepsilon \right) \right\} $$ To define FIRST($\alpha$) for arbitrary $\alpha$, we start by defining FIRST(X), for a single symbol X (a terminal, a nonterminal, or $\varepsilon$):

1. X $\in \Sigma$ (e.g. X is a terminal): FIRST(X) = {X}
2. X $= \varepsilon$: FIRST(X) = {$\varepsilon$}
3. X $\in N$ (e.g. X is a nonterminal): we must look at all grammar productions with X on the left, i.e., productions of the form:
   X $\longrightarrow$ Y₁ Y₂ Y₃ ... Y_k
   where each Y_k is a single terminal or nonterminal (or there is just one Y, and it is $\varepsilon$). For each such production, we perform the following actions:
   • Put FIRST(Y₁) - {$\varepsilon$} into FIRST(X).
   • If $\varepsilon$ is in FIRST(Y₁), then put FIRST(Y₂) - {epsilon} into FIRST(X).
   • If epsilon is in FIRST(Y₂), then put FIRST(Y₃) - {$\varepsilon$} into FIRST(X).
   • etc...
   • If $\varepsilon$ is in FIRST(Y_i) for 1 $\leq$ i $\leq$ k (all production right-hand sides)) then put $\varepsilon$ into FIRST(X).

For example, consider computing FIRST sets for each of the nonterminals in the following grammar:

Exp	$\longrightarrow$	Term Exp'
Exp'	$\longrightarrow$	minus Term Exp' | $\varepsilon$
Term	$\longrightarrow$	Factor Term'
Term'	$\longrightarrow$	divide Factor Term' | $\varepsilon$
Factor	$\longrightarrow$	intlit | lparens Exp rparens

Here are the FIRST sets (starting with nonterminal factor and working up, since we need to know FIRST(factor) to compute FIRST(term), and we need to know FIRST(term) to compute FIRST(exp)):

Once we have computed FIRST(X) for each terminal and nonterminal X, we can compute FIRST($\alpha$) for every production's right-hand-side $\alpha$. In general, $\alpha$ will be of the form:

X₁ X₂ ... X_n
where each X is a single terminal or nonterminal, or there is just one X and it is $\varepsilon$. The rules for computing FIRST($\alpha$) are essentially the same as the rules for computing the first set of a nonterminal:
1. Put FIRST(X₁) - {$\varepsilon$} into FIRST($\alpha$)
2. If $\varepsilon$ is in FIRST(X₁) put FIRST(X₂) into FIRST($\alpha$).
3. etc...
4. If $\varepsilon$ is in the FIRST set for every X_k, put $\varepsilon$ into FIRST($\alpha$).

For the example grammar above, here are the FIRST sets for each production right-hand side:

Why do we care about the FIRST($\alpha$) sets? During parsing, suppose that there are two productions:

Production 1:	$A$	$\longrightarrow$	$\alpha$
Production 2:	$A$	$\longrightarrow$	$\beta$

Consider the situation when the top-of-stack symbol is A and the current token is a. If a $\in$ FIRST($\alpha$), choose production 1: pop, push $\alpha$. If, on the other hand, a $\in$ FIRST($\beta$), choose production 2 : pop, push $\beta$. We haven't yet given the rules for using FIRST and FOLLOW sets to determine whether a grammar is LL(1); however, you might be able to guess based on this discussion, that if a is in both FIRST($\alpha$) and FIRST($\beta$), the grammar is not LL(1).

FOLLOW Sets

FOLLOW sets are only defined for single nonterminals. The definition is as follows:

For a nonterminal $A$, FOLLOW($A$) is the set of terminals that can appear immediately to the right of A in some partial derivation; i.e., terminal t is in FOLLOW(A) if $ S \stackrel{+}\Longrightarrow\ldots A \; \mathrm{t} \ldots $ where t is a terminal. If $A$ can be the rightmost symbol in a derivation, then EOF is in FOLLOW($A$).
It is worth noting that $\varepsilon$ is never in a FOLLOW set.

Using notation: $$\mathrm{FOLLOW}(A) = \left\{ \; \mathrm{t} \; \middle| \; \left( \mathrm{t} \; \in \Sigma \wedge S \stackrel{+}\Longrightarrow \alpha \; A \; \mathrm{t} \; \beta \right) \vee \left( \mathrm{t} = \mathrm{EOF} \wedge S \stackrel{*}\Longrightarrow \alpha A \right) \right\} $$

Here are some pictures illustrating the conditions under which symbols a, c, and EOF are in the FOLLOW set of nonterminal A:

Figure 1

Figure 2

Figure 2

How to compute FOLLOW(A) for each nonterminal A:
• If A is the start nonterminal, put EOF in FOLLOW(A) (like S in Fig. 3).
• Now find the productions with A on the right-hand-side:
  • For each production $X$ $\longrightarrow$ $\alpha$ $A$ $\beta$, put FIRST($\beta$) - {$\varepsilon$} in FOLLOW($A$) -- see Fig. 1.
  • If epsilon is in FIRST($\beta$) then put FOLLOW($X$) into FOLLOW(A) -- see Fig. 2.
  • For each production $X$ $\longrightarrow$ $\alpha$ $A$, put FOLLOW(X) into FOLLOW(A) -- see Fig. 3, and Fig. 4 below:

    Figure 4

It is worth noting that:

• To compute FIRST(A) you must look for A on a production's left-hand side.
• To compute FOLLOW(A) you must look for A on a production's right-hand side.
• FIRST and FOLLOW sets are always sets of terminals (plus, perhaps, $\varepsilon$ for FIRST sets, and EOF for follow sets). Nonterminals are never in a FIRST or a FOLLOW set; $\varepsilon$ is never in a FOLLOW set.

Here's an example of FOLLOW sets (and the FIRST sets we need to compute them). In this example, nonterminals are upper-case letters, and terminals are lower-case letters.

$S$	$\longrightarrow$	$B$ c $\;|\;$ $D$ $B$
$B$	$\longrightarrow$	a b $\;|\;$ c $S$
$D$	$\longrightarrow$	d $\;|\;$ $\varepsilon$

$\alpha$		FIRST($\alpha$)		FOLLOW($\alpha$)
$D$		{d, $\varepsilon$}		{a, c}
$B$		{a, c}		{c, EOF}
$S$		{a, c, d}		{EOF, c}	Note that FOLLOW($S$) always includes EOF

Now let's consider why we care about FOLLOW sets:

• Suppose, during parsing, we have some $X$ at the top-of-stack, and a is the current token.
• We need to replace $X$ on the stack with the right-hand side of a production $X \longrightarrow \alpha$. What if $X$ has an additional production $X \longrightarrow \beta$. Which one should we use?
• We've already said that if a is in FIRST($\alpha$), but not in FIRST($\beta$), then we want to choose $X \longrightarrow \alpha$.
• But what if a is not in FIRST($\alpha$) or FIRST($\beta$)? If $\alpha$ or $\beta$ can derive $\varepsilon$, and a is in FOLLOW($X$), then we still have hope that the input will be accepted: If $\alpha$ can derive $\varepsilon$ (i.e., $\varepsilon \in$ FIRST($\alpha$), then we want to choose $X \longrightarrow \alpha$ (and similarly if $\beta$ can derive $\varepsilon$). The idea is that since $\alpha$ can derive $\varepsilon$, it will eventually be popped from the stack, and if we're lucky, the next symbol down (the one that was under the $X$) will be a.

---

TEST YOURSELF #3

Here are five grammar productions for (simplified) method headers:

1. methodHeader -> VOID ID LPAREN paramList RPAREN

2. paramList    -> epsilon 
3. paramList    -> nonEmptyParamList

4. nonEmptyParamList -> ID ID
5. nonEmptyParamList -> ID ID COMMA nonEmptyParamList

Question 1: Compute the FIRST and FOLLOW sets for the three nonterminals, and the FIRST sets for each production right-hand side.

Question 2: Draw a picture to illustrate what the predictive parser will do, given the input sequence of tokens: "VOID ID LPAREN RPAREN EOF". Include an explanation of how the FIRST and FOLLOW sets are used when there is a nonterminal on the top-of-stack that has more than one production.

solution

How to Build Parse Tables

Recall that the form of the parse table is:

Table entry[$X$,a] is either empty (if having $X$ on top of stack and having a as the current token means a syntax error) or contains the right-hand side of a production whose left-hand-side nonterminal is $X$ -- that right-hand side is what should be pushed.

To build the table, we fill in the rows one at a time for each nonterminal $X$ as follows:

for each production $X \longrightarrow \alpha$:
for each terminal t in FIRST($\alpha$):
put $\alpha$ in Table[$X$,t]

if $\epsilon \in$ FIRST($\alpha$) then:
for each terminal t in FOLLOW($X$):
put $\alpha$ in Table[$X$,t]

The grammar is not LL(1) iff there is more than one entry for any cell in the table.

Let's try building a parse table for the following grammar:

$S$	$\longrightarrow$	$B$ c $\;|\;$ $D$ $B$
$B$	$\longrightarrow$	a b $\;|\;$ c $S$
$D$	$\longrightarrow$	d $\;|\;$ $\varepsilon$

First we calculate the FIRST and FOLLOW sets:

$\alpha$		FIRST($\alpha$)		FOLLOW($\alpha$)
$D$		{d, $\varepsilon$}		{a, c}
$B$		{a, c}		{c, EOF}
$S$		{a, c, d}		{EOF, c}
$B$ c		{a, c}		-
$D$ $B$		{d, a, c}		-
a b		{a}		-
c $S$		{c}		-
d		{d}		-
$\varepsilon$		{$\varepsilon$}		-

Then we use those sets to start filling in the parse table:

Here's how we filled in this much of the table:

1. First, we considered the production S -> B c. FIRST(Bc) = { a, c }, so we put the production's right-hand side (B c) in Table[S, a] and in Table[S, c]. FIRST(Bc) does not include epsilon, so we're done with that production.
2. Next, we considered the production S -> D B . FIRST(DB) = { d, a, c }, so we put the production's right-hand side (D B) in Table[S, d], Table[S, a], and Table[S, c].
3. Next, we considered the production D -> epsilon. FIRST(epsilon) = { epsilon }, so we must look at FOLLOW(D). FOLLOW(D) = { a, c }, so we put the production's right-hand side (epsilon) in Table[D, a] and Table[D, c}.

Finish filling in the parse table given above.

solution

How to Code a Predictive Parser

Now, suppose we actually want to code a predictive parser for a grammar that is LL(1). The simplest idea is to use a table-driven parser with an explicit stack. Here's pseudo-code for a table-driven predictive parser:

   Stack.push(EOF);
   Stack.push(start-nonterminal);
   currToken = scan();

   while (! Stack.empty()) {
     topOfStack = Stack.pop();
     if (isNonTerm(topOfStack)) {
       // top of stack symbol is a nonterminal
       p = table[topOfStack, currToken];
       if (p is empty) report syntax error and quit
       else {
         // p is a production's right-hand side
	 push p, one symbol at a time, from right to left
       }
     }
     else {
       // top of stack symbol is a terminal
       if (topOfStack == currToken) currToken = scan();
       else report syntax error and quit
     }
   }

Here is a CFG (with rule numbers):

S -> epsilon               (1)
  |  X Y Z                 (2)

X -> epsilon               (3)
  |  X S                   (4)

Y -> epsilon               (5)
  |  a Y b                 (6)

Z -> c Z                   (7)
  |  d                     (8)

Question 1(a): Compute the First and Follow Sets for each nonterminal.

Question 1(b): Draw the Parse Table.

solution

Contents

• LR Parsing Overview
• Basic LR Parsing Algorithm
• Example
• Parse Tables
• Conflicts

LR Parsing Overview

There are several different kinds of bottom-up parsing. We will discuss an approach called LR parsing, which includes SLR, LALR, and LR parsers. LR means that the input is scanned left-to-right, and that a rightmost derivation, in reverse, is constructed. SLR means "simple" LR, and LALR means "look-ahead" LR.

Every SLR(1) grammar is also LALR(1), and every LALR(1) grammar is also LR(1), so SLR is the most limited of the three, and LR is the most general. In practice, it is pretty easy to write an LALR(1) grammar for most programming languages (i.e., the "power" of an LR parser isn't usually needed). A disadvantage of LR parsers is that their tables can be very large. Therefore, parser generators like Yacc and Java Cup produce LALR(1) parsers.

Let's start by considering the advantages and disadvantages of the LR parsing family:

Advantages

• Almost all programming languages have LR grammars.
• LR parsers take time and space linear in the size of the input (with a constant factor determined by the grammar).
• LR is strictly more powerful than LL (for example, every LL(1) grammar is also both LALR(1) and LR(1), but not vice versa).
• LR grammars are more "natural" than LL grammars (e.g., the grammars for expression languages get mangled when we remove the left recursion to make them LL(1), but that isn't necessary for an LALR(1) or an LR(1) grammar).

• Although an LR grammar is usually easier to understand than the corresponding LL grammar, the parser itself is harder to understand and to write (thus, LR parsers are built using parser generators, rather than being written by hand).
• When we use a parser generator, if the grammar that we provide is not LALR(1), it can be difficult to figure out how to fix that.
• Error repair may be more difficult using LR parsing than using LL.
• Table sizes may be larger (about a factor of 2) than those used for LL parsing.

Recall that top-down parsers use a stack. The contents of the stack represent a prediction of what the rest of the input should look like. The symbols on the stack, from top to bottom, should "match" the remaining input, from first to last token. For example, earlier, we looked at the example grammar

and parsed the input string ([]). At one point during the parse, after the first parenthesis has been consumed, the stack contains

    [ S ] ) EOF

Bottom-up parsers also use a stack, but in this case, the stack represents a summary of the input already seen, rather than a prediction about input yet to be seen. For now, we will pretend that the stack symbols are terminals and nonterminals (as they are for predictive parsers). This isn't quite true, but it makes our introduction to bottom-up parsing easier to understand.

A bottom-up parser is also called a "shift-reduce" parser because it performs two kind of operations, shift operations and reduce operations. A shift operation simply shifts the next input token from the input to the top of the stack. A reduce operation is only possible when the top N symbols on the stack match the right-hand side of a production in the grammar. A reduce operation pops those symbols off the stack and pushes the non-terminal on the left-hand side of the production.

One way to think about LR parsing is that the parse tree for a given input is built, starting at the leaves and working up towards the root. More precisely, a reverse rightmost derivation is constructed.

Recall that a derivation (using a given grammar) is performed as follows:

1. start with the start symbol (i.e., the current string is the start symbol)
2. repeat:
   • choose a nonterminal X in the current string
   • choose a grammar rule X $\longrightarrow$ $\alpha$
   • replace X in the current string with $\alpha$
   until there are no more nonterminals in the current string

A rightmost derivation is one in which the rightmost nonterminal is always the one chosen.

In this example, the nonterminal that is chosen at each step is in red, and each derivation step is numbered. The corresponding bottom-up parse is shown below by showing the parse tree with its edges numbered to show the order in which the tree was built (e.g., the first step was to add the nonterminal F as the parent of the leftmost parse-tree leaf "id", and the last step was to combine the three subtrees representing "id", "+", and "id * id" as the children of a new root node E).

Note that both the rightmost derivation and the bottom-up parse have 8 steps. Step 1 of the derivation corresponds to step 8 of the parse; step 2 of the derivation corresponds to step 7 of the parse; etc. Each step of building the parse tree (adding a new nonterminal as the parent of some existing subtrees) is called a reduction (that's where the "reduce" part of "shift-reduce" parsing comes from).

Basic LR Parsing AlgorithmL

All LR parsers use the same basic algorithm:

Based on:
• the top-of-stack symbol and
• the current input symbol (token) and
• the entry in one of the parse tables (indexed by the top-of-stack and current-input symbols)
the parser performs one of the following actions:
1. shift: push the current input symbol onto the stack, and go on to the next input symbol (i.e., call the scanner again)
2. reduce: a grammar rule's right-hand side is on the top of the stack! pop it off and push the grammar rule's left-hand-side nonterminal
3. accept: accept the input (parsing has finished successfully)
4. reject: the input is not syntactically correct

The difference between SLR, LALR, and LR parsers is in the tables that they use. Those tables use different techniques to determine when to do a reduce step, and, if there is more than one grammar rule with the same right-hand side, which left-hand-side nonterminal to push.

Example

Here are the steps the parser would perform using the grammar of arithmetic expressions with + and * given above, if the input is

id + id * id

Stack		Input		Action
		id + id * id		shift (id)
id		+ id * id		reduce by $F$ $\longrightarrow$ id
$F$		+ id * id		reduce by $T$ $\longrightarrow$ $F$
$T$		+ id * id		reduce by $E$ $\longrightarrow$ $T$
$E$		+ id * id		shift(+)
$E$ +		id * id		shift(id)
$E$ + id		* id		reduce by $F$ $\longrightarrow$ id
$E$ + $F$		* id		reduce by $T$ $\longrightarrow$ $F$
$E$ + $T$		* id		shift(*)
$E$ + $T$ *		id		shift(id)
$E$ + $T$ * id				reduce by $F$ $\longrightarrow$ id
$E$ + $T$ * $F$				reduce by $T$ $\longrightarrow$ $T$ * $F$
$E$ + $T$				reduce by $E$ $\longrightarrow$ $E$ + $T$
$E$				accept

(NOTE: the top of stack is to the right; the reverse rightmost derivation is formed by concatenating the stack with the remaining input at each reduction step)

Parse Tables

As mentioned above, the symbols pushed onto the parser's stack are not actually terminals and nonterminals. Instead, they are states, that correspond to a finite-state machine that represents the parsing process (more on this soon).

All LR Parsers use two tables: the action table and the goto table. The action table is indexed by the top-of-stack symbol and the current token, and it tells which of the four actions to perform: shift, reduce, accept, or reject. The goto table is used during a reduce action as explained below.

Above we said that a shift action means to push the current token onto the stack. In fact, we actually push a state symbol onto the stack. Each "shift" action in the action table includes the state to be pushed.

Above, we also said that when we reduce using the grammar rule A → alpha, we pop alpha off of the stack and then push A. In fact, if alpha contains N symbols, we pop N states off of the stack. We then use the goto table to know what to push: the goto table is indexed by state symbol t and nonterminal A, where t is the state symbol that is on top of the stack after popping N times.

Here's pseudo code for the parser's main loop:

push initial state s0
a = scan()
do forever
    t = top-of-stack (state) symbol
    switch action[t, a] {
       case shift s:
           push(s)
           a = scan()
       case reduce by A → alpha:
           for i = 1 to length(alpha) do pop() end
	   t = top-of-stack symbol
           push(goto[t, A])
       case accept:
           return( SUCCESS )
       case error:
           call the error handler
           return( FAILURE )
    }
end do

Remember, all LR parsers use this same basic algorithm. As mentioned above, for all LR parsers, the states that are pushed onto the stack represent the states in an underlying finite-state machine. Each state represents "where we might be" in a parse; each "place we might be" is represented (within the state) by an item. What's different for the different LR parsers is:

• the definition of an item
• the number of states in the underlying finite-state machine
• the amount of information in a state

• Topic Introduction
• Top-Down SDT
• Example: Counting Parentheses
• Self-Study #1
• Handling Non-LL(1) Grammars
• Self-Study #2
• Bottom-Up SDT
• Summary

• Introduction
• Overview
  • Scoping
  • Test Yourself #1
  • Test Yourself #2
  • Symbol Table Implementations
    • Method 1: List of Hashtables
    • Test Yourself #3
    • Method 2: Hashtable of Lists
    • Test Yourself #4

Symbol Table Introduction

The parser ensures that the input program is syntactically correct, but there are other kinds of correctness that it cannot (or usually does not) enforce. For example:

• A variable should not be declared more than once in the same scope.
• A variable should not be used before being declared.
• The type of the left-hand side of an assignment should match the type of the right-hand side.
• Methods should be called with the right number and types of arguments.

The next phase of the compiler after the parser, sometimes called the static semantic analyzer is in charge of checking for these kinds of errors. The checks can be done in two phases, each of which involves traversing the abstract-syntax tree created by the parser:

1. For each scope in the program: Process the declarations, adding new entries to the symbol table and reporting any variables that are multiply declared; process the statements, finding uses of undeclared variables, and updating the "ID" nodes of the abstract-syntax tree to point to the appropriate symbol-table entry.
2. Process all of the statements in the program again, using the symbol-table information to determine the type of each expression, and finding type errors.

Symbol Table Overview

The purpose of the symbol table is to keep track of names declared in the program. This includes names of classes, fields, methods, and variables. Each symbol table entry associates a set of attributes with one name; for example:

• which kind of name it is
• what is its type
• what is its nesting level
• where will it be found at runtime.

Scoping

A language's scoping rules tell you when you're allowed to reuse a name, and how to match uses of a name to the corresponding declaration. In most languages, the same name can be declared multiple times under certain circumstances. In C++ you can use the same name in more than one declaration if the declarations involve different kinds of names. For example, you can use the same name for a class, a field of the class, and a local variable of a member function (this is not recommended, but it is legal):

class Test{
        private:
        int Test;
        void func() {
                double Test;  // Could have been declared int
        }
};

In C++ functions (and Java methods), you can also use the same name more than once in a scope as long as the number and/or types of parameters are unique (this is called overloading).

In C and C++, but not in Java, you can declare variables with the same name in different blocks. A block is a piece of code inside curly braces; for example, in an if or a loop. The following is a legal C or C++ function, but not a legal Java method:

void f(int k) {
   int x = 0;       /* x is declared here */

   while (...) {
      int x = 1;   /* another x is declared here */
      ...
      if (...) {
        float x = 5.5;  /* and yet another x is declared here! */
        ...
      }
   }
}

In the example given above, the outermost scope includes just the name "f", and function f itself has three scopes:

1. The outer scope for f includes parameter k, and the variable x that is initialized to 0.
2. The next scope is for the body of the while loop, and includes the variable x that is initialized to 1.
3. The innermost scope is for the body of the if, and includes the variable x that is initialized to 5.5.

Question 1: Consider the names declared in the following code. For each, determine whether it is legal according to the rules used in Java.

class animal {
  // methods
  void attack(int animal) {
     for (int animal=0; animal<10; animal++) {
         int attack;
     }
  }

  int attack(int x) {
     for (int attack=0; attack<10; attack++) {
        int animal;
     }
  }

  void animal() { }

  // fields
  double attack;
  int attack;
  int animal;
}

Question 2: Consider the following C++ code. For each use of a name, determine which declaration it corresponds to (or whether it is a use of an undeclared name).

int k=10, x=20;

void foo(int k) {
    int a = x;
    int x = k;
    int b = x;
    while (...) {
        int x;
	if (x == k) {
	   int k, y;
	   k = y = x;
	}
	if (x == k) {
	   int x = y;
	}
    }
}

solution

Not all languages use static scoping. Lisp, APL, Perl (depending on how a variable is declared), and Snobol use what is called dynamic scoping. A use of a variable that has no corresponding declaration in the same function corresponds to the declaration in the most-recently-called still active function. For example, consider the following code:

void main() {
  f1();
  f2();
}

void f1() {
  int x = 10;
  g();
}

void f2() {
  String x = "hello";
  f3();
  g();
}

void f3() {
  double x = 30.5;
}

void g() {
  print(x);
}