Compiler Construction Lecture Notes

Why study compilers?

You may never write a commercial compiler, but that's not why we study compilers. We study compiler construction for the following reasons:

• Writing a compiler gives a student experience with large-scale applications development. Your compiler program may be the largest program you write as a student. Experience working with really big data structures and complex interactions between algorithms will help you out on your next big programming project.
• Compiler writing is one of the shining triumphs of CS theory. It demonstrates the value of theory over the impulse to just "hack up" a solution.
• Compiler writing is a basic element of programming language research. Many language researchers write compilers for the languages they design.
• Many applications have similar properties to one or more phases of a compiler, and compiler expertise and tools can help an application programmer working on other projects besides compilers.

Compilers - a brief overview

Purpose: translate a program in some language (the source language) into a lower-level language (the target language).

Phases:

Lexical Analysis:

Converts a sequence of characters into words, or tokens

Syntax Analysis:

Converts a sequence of tokens into a parse tree

Semantic Analysis:

Manipulates parse tree to verify symbol and type information

Intermediate Code Generation:

Converts parse tree into a sequence of intermediate code instructions

Optimization:

Manipulates intermediate code to produce a more efficient program

Final Code Generation:

Translates intermediate code into final (machine/assembly) code

Example of the Compilation Process

Consider the example from Figure 1.10 on p. 13 of the book in detail.

position = initial + rate * 60

30 or so characters, from a single line of source code, are first transformed by lexical analysis into a sequence of 7 tokens. Those tokens are then used to build a tree of height 4 during syntax analysis. Semantic analysis may transform the tree into one of height 5, that includes a type conversion necessary for real addition on an integer operand. Intermediate code generation uses a simple traversal algorithm to linearize the tree back into a sequence of machine-independent three-address-code instructions.

t1 = inttoreal(60)
t2 = id3 * t1
t3 = id2 + t2
id1 = t3

Optimization of the intermediate code allows the four instructions to be reduced to two machine-independent instructions. Final code generation might implement these two instructions using 5 machine instructions, in which the actual registers and addressing modes of the CPU are utilized.

MOVF	id3, R2
MULF	#60.0, R2
MOVF	id2, R1
ADDF	R2, R1
MOVF	R1, id1

Overview of Lexical Analysis

Lexical Analyzer a.k.a. scanner

• Convert from a sequence of characters into a (shorter) sequence of tokens
• Identify and categorize specific character sequences into tokens
• Skip comments & whitespace
• Handle lexical errors (illegal characters, malformed tokens)
• Efficiency is crucial; scanner may perform elaborate input buffering
• Tokens are specified as regular expressions, e.g. IDENTIFIER=[a-zA-Z][a-zA-Z0-9]*
• Lexical Analyzers are implemented by DFAs.

The term "token" usually refers to an object (or struct) containing complete information about a single lexical entity, but it is often also used to refer the category ("class" if you prefer) of that entity. The term "lexeme" denotes the actual string of characters that comprise a particular occurrence ("instance" if you like) of a token.

Regular Expressions

The notation we use to precisely capture all the variations that a given category of token may take are called "regular expressions" (or, less formally, "patterns". The word "pattern" is really vague and there are lots of other notations for patterns besides regular expressions). Regular expressions are a shorthand notation for sets of strings. In order to even talk about "strings" you have to first define an alphabet, the set of characters which can appear.

1. Epsilon is a regular expression denoting the set containing the empty string
2. Any letter in the alphabet is also a regular expression denoting the set containing a one-letter string consisting of that letter.
3. For regular expressions r and s,
            r | s
   is a regular expression denoting the union of r and s
4. For regular expressions r and s,
            r s
   is a regular expression denoting the set of strings consisting of a member of r followed by a member of s
5. For regular expression r,
            r*
   is a regular expression denoting the set of strings consisting of zero or more occurrences of r.
6. You can parenthesize a regular expression to specify operator precedence (otherwise, alternation is like plus, concatenation is like times, and closure is like exponentiation)

Although these operators are sufficient to describe all regular languages, in practice everybody uses extensions:

• For regular expression r,
           r+
  is a regular expression denoting the set of strings consisting of one or more occurrences of r. Equivalent to rr*
• For regular expression r,
           r?
  is a regular expression denoting the set of strings consisting of zero or one occurrence of r. Equivalent to r|epsilon
• The notation [abc] is short for a|b|c. [a-z] is short for a|b|...|z

Finite Automata

A finite automaton is an abstract, mathematical machine, also known as a finite state machine, with the following components:

1. A set of states S
2. A set of input symbols E (the alphabet)
3. A transition function move(state, symbol) : new state(s)
4. A start state S0
5. A set of final states F

For a deterministic finite automaton (DFA), the function move(state, symbol) goes to at most one state, and symbol is never epsilon.

Finite automata correspond in a 1:1 relationship to transition diagrams; from any transition diagram one can write down the formal automaton in terms of items #1-#5 above, and vice versa. To draw the transition diagram for a finite automaton:

• draw a circle for each state s in S; put a label inside the circles to identify each state by number or name
• draw an arrow between S_i and S_j, labeled with x whenever the transition says to move(S_i, x) : S_j
• draw a "wedgie" into the start state S0 to identify it
• draw a second circle inside each of the final states in F

DFA Implementation

The nice part about DFA's is that they are efficiently implemented on computers. What DFA does the following code correspond to? What is the corresponding regular expression? You can speed this code fragment up even further if you are willing to use goto's or write it in assembler.

state := S0
for(;;)
   switch (state) {
   case 0: 
      switch (input) {
         'a': state = 1; input = getchar(); break;
         'b': input = getchar(); break;
	 default: printf("dfa error\n"); exit(1);
         }
   case 1: 
      switch (input) {
         EOF: printf("accept\n"); exit(0);
	 default: printf("dfa error\n"); exit(1);
         }
      }

Nondeterministic Finite Automata (NFA's)

Notation convenience motivates more flexible machines in which function move() can go to more than one state on a given input symbol, and some states can move to other states even without consuming an input symbol.

Fortunately, one can prove that for any NFA, there is an equivalent DFA. They are just a notational convenience. So, finite automata help us get from a set of regular expressions to a computer program that recognizes them efficiently.

Regular expressions can be converted automatically to NFA's

Each rule in the definition of regular expressions has a corresponding NFA; NFA's are composed using epsilon transitions. This is cited in the text as "Thompson's construction" (Algorithm 3.3). We will work examples such as (a|b)*abb in class and during lab.

1. For epsilon, draw two states with a single epsilon transition.
2. For any letter in the alphabet, draw two states with a single transition labeled with that letter.
3. For regular expressions r and s, draw r | s by adding a new start state with epsilon transitions to the start states of r and s, and a new final state with epsilon transitions from each final state in r and s.
4. For regular expressions r and s, draw rs by adding epsilon transitions from the final states of r to the start state of s.
5. For regular expression r, draw r* by adding new start and final states, and epsilon transitions (a) from the start state to the final state, (b) from the final state back to the start state, (c) from the new start to the old start and from the old final states to the new final state.
6. For parenthesed regular expression (r) you can use the NFA for r.

NFA's can be converted automatically to DFA's

In: NFA N
OUt: DFA D
Method: Construct transition table Dtran (a.k.a. the "move function"). Each DFA state is a set of NFA states. Dtran simulates in parallel all possible moves N can make on a given string.

Operations to keep track of sets of NFA states:

e_closure(s)

set of states reachable from state s via epsilon

e_closure(T)

set of states reachable from any state in set T via epsilon

move(T,a)

set of states to which there is an NFA transition from states in T on symbol a

Algorithm:

Dstates := {e_closure(start_state)}
while T := unmarked_member(Dstates) do {
	mark(T)
	for each input symbol a do {
		U := e_closure(move(T,a))
		if not member(Dstates, U) then
			insert(Dstates, U)
		Dtran[T,a] := U
	}
}

lex(1) and flex(1)

These programs generally take a lexical specification given in a .l file and create a corresponding C language lexical analyzer in a file named lex.yy.c. The lexical analyzer is then linked with the rest of your compiler.

The C code generated by lex has the following public interface. Note the use of global variables instead of parameters, and the use of the prefix yy to distinguish scanner names from your program names. This prefix is also used in the YACC parser generator.

FILE *yyin;	/* set this variable prior to calling yylex() */
int yylex();	/* call this function once for each token */
char yytext[];	/* yylex() writes the token's lexeme to this array */

The .l file format consists of a mixture of lex syntax and C code fragments. The percent sign (%) is used to signify lex elements. The whole file is divided into three sections separated by %%:

   header
%%
   body
%%
   helper functions

The header consists of C code fragments enclosed in %{ and %} as well as macro definitions consisting of a name and a regular expression denoted by that name. lex macros are invoked explicitly by enclosing the macro name in curly braces. Following are some example lex macros.

letter		[a-zA-Z]
digit		[0-9]
ident		{letter}({letter}|{digit})*

The body consists of of a sequence of regular expressions for different token categories and other lexical entities. Each regular expression can have a C code fragment enclosed in curly braces that executes when that regular expression is matched. For most of the regular expressions this code fragment (also called a semantic action consists of returning an integer that identifies the token category to the rest of the compiler, particularly for use by the parser to check syntax. Some typical regular expressions and semantic actions might include:

" "		{ /* no-op, discard whitespace */ }
{ident}		{ return IDENTIFIER; }
"*"		{ return ASTERISK; }

You also need regular expressions for lexical errors such as unterminated character constants, or illegal characters.

The helper functions in a lex file typically compute lexical attributes, such as the actual integer or string values denoted by literals.

Lex extended regular expressions

Lex further extends the regular expressions with several helpful operators. Lex's regular expressions include:

c

normal characters mean themselves

\c

backslash escapes remove the meaning from most operator characters. Inside character sets and quotes, backslash performs C-style escapes.

"s"

Double quotes mean to match the C string given as itself. This is particularly useful for multi-byte operators and may be more readable than using backslash multiple times.

[s]

This character set operator matches any one character among those in s.

[^s]

A negated-set matches any one character not among those in s.

.

The dot operator matches any one character except newline: [^\n]

r*

match r 0 or more times.

r+

match r 1 or more times.

r?

match r 0 or 1 time.

r{m,n}

match r between m and n times.

r₁r₂

concatenation. match r₁ followed by r₂

r₁|r₂

alternation. match r₁ or r₂

(r)

parentheses specify precedence but do not match anything

r₁/r₂

lookahead. match r₁ when r₂ follows, without consuming r₂

^r

match r only when it occurs at the beginning of a line

r$

match r only when it occurs at the end of a line

Lexical Attributes and Token Objects

Besides the token's category, the rest of the compiler may several pieces of information about a token in order to perform semantic analysis, code generation, and error handling. These are stored in an object instance of class Token, or in C, a struct. The fields are generally something like:

struct token {
   int category;
   char *text;
   int linenumber;
   int column;
   char *filename;
   union literal value;
}

The union literal will hold computed values of integers, real numbers, and strings.

Lexical Analysis and the Symbol Table

In many compilers, the symbol table and memory management components of the compiler interact with several phases of compilation, starting with lexical analysis.

• Efficient storage is necessary to handle large input files.
• There is a colossal amount of duplication in lexical data: variable names, strings and other literal values duplicate frequently
• What token type to use may depend on previous declarations.

A hash table or other efficient data structure can avoid this duplication. The software engineering design pattern to use is called the "flyweight". Example: Figure 3.18, p. 109. Use "install_id()" instead of "strdup()" to avoid duplication in the lexical data.

Syntax Analysis

Parsing is the act of performing syntax analysis to verify an input program's compliance with the source language. A by-product of this process is typically a tree that represents the structure of the program.

Context Free Grammars

A context free grammar G has:

• A set of terminal symbols, T
• A set of nonterminal symbols, N
• A start symbol, s, which is a member of N
• A set of production rules of the form A -> w, where A is a nonterminal and w is a string of terminal and nonterminal symbols.

   

  A context free grammar can be used to generate strings in the corresponding language as follows:

  let X = the start symbol s
  while there is some nonterminal Y in X do
     apply any one production rule using Y, e.g. Y -> w
  

  When X consists only of terminal symbols, it is a string of the language denoted by the grammar. Each iteration of the loop is a derivation step. If an iteration has several nonterminals to choose from at some point, the rules of derviation would allow any of these to be applied. In practice, parsing algorithms tend to always choose the leftmost nonterminal, or the rightmost nonterminal, resulting in strings that are leftmost derivations or rightmost derivations.

  Grammar Ambiguity

  The grammar

  E -> E + E
  E -> E * E
  E -> ( E )
  E -> ident
  

  allows two different derivations for strings such as "x + y * z". The grammar is ambiguous, but the semantics of the language dictate a particular operator precedence that should be used. One way to eliminate such ambiguity is to rewrite the grammar. For example, we can force the precedence we want by adding some nonterminals and production rules.

  E -> E + T
  E -> T
  T -> T * F
  T -> F
  F -> ( F )
  F -> ident
  

  Recursive Descent Parsing

  Perhaps the simplest parsing method, for a large subset of context free grammars, is called recursive descent. It is simple because the algorithm closely follows the production rules of nonterminal symbols.
  • Write 1 procedure per nonterminal rule
  • Within each procedure, a) match terminals at appropriate positions, and b) call procedures for non-terminals.
  • Pitfalls: left recursion is FATAL; must distinguish between several production rules, or potentially, one has to try all of them via backtracking.

  Recursive Descent Parsing Example #1

  The grammar

  S -> A B C
  A -> a A
  A -> epsilon
  B -> b
  C -> c
  

  maps to code like

  procedure S()
    if A() & B() & C() then succeed
  end
  
  procedure A()
    if currtoken == a then # use production 2
       currtoken = scan()
       return A()
    else
       succeed # production rule 3, match epsilon
  end
  
  procedure B()
     if currtoken == b then
        currtoken = scan()
        succeed
     else fail
  end
  
  procedure C()
     if currtoken == c then
        currtoken = scan()
        succeed
     else fail
  end
  
  
  

  Removing Left Recursion

  E -> E + T | T
  T -> T * F | F
  F -> ( E ) | ident
  

  We can remove the left recursion by introducing new nonterminals and new production rules.

  E  -> T E'
  E' -> + T E' | epsilon
  T  -> F T'
  T' -> * F T' | epsilon
  F  -> ( E ) | ident
  

  Getting rid of such immediate left recursion is not enough, one must get rid of indirect left recursion, where two or more nonterminals are mutually left-recursive. One can rewrite any CFG to remove left recursion (Algorithm 4.1).

  for i := 1 to n do
     for j := 1 to i-1 do begin
        replace each Ai -> Aj gamma with productions
        Ai -> delta1gamma | delta2gamma
        end
     eliminate immediate left recursion
  

  Backtracking?

  Current token could begin more than one of your possible production rules? Try all of them, remember and reset state for each try.

  S -> cAd
  A -> ab
  A -> a
  

  Left factoring can often solve such problems

  S -> cAd
  A -> a A'
  A'-> b
  A'-> (epsilon)
  

  One can also perform left factoring (Algorithm 4.2) to reduce or eliminate the lookahead or backtracking needed to tell which production rule to use. If the end result has no lookahead or backtracking needed, the resulting CFG can be solved by a "predictive parser" and coded easily in a conventional language. If backtracking is needed, a recursive descent parser takes more work to implement, but is still feasible. As a more concrete example:

  S -> if E then S
  S -> if E then S1 else S2
  

  can be factored to:

  S -> if E then S S'
  S'-> else S2 | epsilon
  

  Some More Parsing Theory

  Automatic techniques for constructing parsers start with computing some basic functions for symbols in the grammar. These functions are useful in understanding both recursive descent and bottom-up LR parsers.

  First(a)

  First(a) is the set of terminals that begin strings derived from a, which can include epsilon.
  1. First(X) starts with the empty set.
  2. if X is a terminal, First(X) is {X}.
  3. if X -> epsilon is a production, add epsilon to First(X).
  4. if X is a non-terminal and X -> Y₁ Y₂ ... Y_k is a production, add First(Y₁) to First(X).

  5. for (i = 1; if Yi can derive epsilon; i++)
             add First(Yi+1) to First(X)
     

  Follow(A)

  Follow(A) for nonterminal A is the set of terminals that can appear immediately to the right of A in some sentential form S -> aAxB... To compute Follow, apply these rules to all nonterminals in the grammar:
  1. Add $ to Follow(S)
  2. if A -> aBb then add First(b) - epsilon to Follow(B)
  3. if A -> aB or A -> aBb where epsilon is in First(b), then add Follow(A) to Follow(B).

  Bottom Up Parsing

  Bottom up parsers start from the sequence of terminal symbols and work their way back up to the start symbol by repeatedly replacing grammar rules' right hand sides by the corresponding non-terminal. This is the reverse of the derivation process, and is called "reduction".

  Example. For the grammar

  (1)	S->aABe
  (2)	A->Abc
  (3)	A->b
  (4)	B->d
  

  the string "abbcde" can be parsed bottom-up by the following reduction steps:

  abbcde
  aAbcde
  aAde
  aABe
  S
  

  Definition: a handle is a substring that
  1. matches a right hand side of a production rule in the grammar and
  2. whose reduction to the nonterminal on the left hand side of that grammar rule is a step along the reverse of a rightmost derivation.

  Shift Reduce Parsing

  A shift-reduce parser performs its parsing using the following structure

  Stack					Input
  $						w$
  

  At each step, the parser performs one of the following actions.
  1. Shift one symbol from the input onto the parse stack
  2. Reduce one handle on the top of the parse stack. The symbols from the right hand side of a grammar rule are popped of the stack, and the nonterminal symbol is pushed on the stack in their place.
  3. Accept is the operation performed when the start symbol is alone on the parse stack and the input is empty.
  4. Error actions occur when no successful parse is possible.

  LR Parsers

  LR denotes a class of bottom up parsers that is capable of handling virtually all programming language constructs. LR is efficient; it runs in linear time with no backtracking needed. The class of languages handled by LR is a proper superset of the class of languages handled by top down "predictive parsers". LR parsing detects an error as soon as it is possible to do so. Generally building an LR parser is too big and complicated a job to do by hand, we use tools to generate LR parsers.

  The LR parsing algorithm is given below. See Figure 4.29 for a schematic.

  ip = first symbol of input
  repeat {
     s = state on top of parse stack
     a = *ip
     case action[s,a] of {
        SHIFT s': { push(a); push(s') }
        REDUCE A->beta: {
           pop 2*|beta| symbols; s' = new state on top
           push A
           push goto(s', A)
           }
        ACCEPT: return 0 /* success */
        ERROR: { error("syntax error", s, a); halt }
        }
     }
  

  Conflicts in Shift-Reduce Parsing

  "Conflicts" occur when an ambiguity in the grammar creates a situation where the parser does not know which step to perform at a given point during parsing. There are two kinds of conflicts that occur.

  shift-reduce

  a shift reduce conflict occurs when the grammar indicates that different successful parses might occur with either a shift or a reduce at a given point during parsing. The vast majority of situations where this conflict occurs can be correctly resolved by shifting.

  reduce-reduce

  a reduce reduce conflict occurs when the parser has two or more handles at the same time on the top of the stack. Whatever choice the parser makes is just as likely to be wrong as not. In this case it is usually best to rewrite the grammar to eliminate the conflict, possibly by factoring.

  Example shift reduce conflict:

  S->if E then S
  S->if E then S else S
  

  In many languages two nested "if" statements produce a situation where an "else" clause could legally belong to either "if". The usual rule (to shift) attaches the else to the nearest (i.e. inner) if statement. Example reduce reduce conflict:

  (1)	S -> id LP plist RP
  (2)	S -> E GETS E
  (3)	plist -> plist, p
  (4)	plist -> p
  (5)	p -> id
  (6)	E -> id LP elist RP
  (7)	E -> id
  (8)	elist -> elist, E
  (9)	elist -> E
  

  By the point the stack holds ...id LP id
  the parser will not know which rule to use to reduce the id: (5) or (7).

  Constructing SLR Parsing Tables:

  Definition: An LR(0) item of a grammar G is a production of G with a dot at some position of the RHS.

  Example: The production A->aAb gives the items:

  A->.aAb A->a.Ab A->aA.b A->aAb.

  Note: A production A-> e generates only one item:

  A->.

  Intuition: an item A->a. b denotes:

  1. a - we have already seen a string derivable from a
  2. b - we hope to see a string derivable from b

  Functions on Sets of Items

  Closure: if I is a set of items for a grammar G, then closure(I) is the set of items constructed as follows:

  1. Every item in I is in closure(I).
  2. If A->aBb is in closure(I) and B->g is a production, then add B-> .g to closure(I).

  These two rules are applied repeatedly until no new items can be added.

  Intuition: If A->a.Bb e closure(I) then we home to see a string derivable from B in the input. So if B-> g is a production, we should hope to see a string derivable from g. Hence, B->.g e closure(I).