Compiler Design and Construction

Factors affecting target code generation

The code generator takes the intermediate representation (and symbol table) as input and produces target code. The code must be correct and of high quality, and the generator itself should be efficient. The main design issues are as follows.

1. Input to the code generator: the intermediate representation (postfix, three address code, syntax trees, DAGs) with the symbol table information. The input is assumed to be free of errors, with type conversions already inserted.

2. Target program: the output may be absolute machine code (fast, fixed memory locations), relocatable machine code (separate compilation and linking, but with extra overhead), or assembly code (easier to generate and debug, but needs an assembler).

3. Memory management: names in the intermediate code must be mapped to run-time addresses using the symbol table; labels are converted to instruction addresses, and static or stack allocation is handled.

4. Instruction selection: the instruction set of the target machine decides the quality of the code. A statement can be translated in many ways, so the generator must choose efficient instructions (for example INC a instead of LD R0,a; ADD R0,#1; ST a,R0), considering the instruction speed and addressing modes.

5. Register allocation: register operations are faster than memory operations, so choosing which values to keep in registers (allocation) and which register to use (assignment) is important. The problem is made harder by instruction constraints, such as registers reserved for some operations.

6. Evaluation order: the order in which computations are performed affects the number of registers and temporaries needed. Finding the best order is NP-complete, so heuristics are used.

7. Approach to code generation: the generator should be correct, maintainable, testable and flexible.

Difference between compiler and interpreter

Symbol table is a necessary component of a compiler

The symbol table is a data structure (usually a hash table) that stores information about every identifier in the source program: its name, type, scope, size, memory address/offset, and for procedures the number and types of parameters and the return type. It is built mainly during lexical and syntax analysis and consulted by almost every later phase, so a compiler cannot work properly without it.

Justification with the statement int a; float b; a = b + 2.5;

• Lexical/syntax analysis enter a and b into the table with their types, and detect redeclaration of the same name in the same scope.
• Semantic analysis looks up a and b to find their types. It sees that b + 2.5 is float and that it is assigned to an int, so a type-conversion or a type-mismatch error is generated. An undeclared identifier is also detected only because the lookup fails.
• Intermediate and code generation use the stored address/offset of a and b to generate instructions such as t1 = b + 2.5; a = t1, and the stored sizes to allocate storage.
• Scope handling: in a nested block { int a; ... } the inner a hides the outer a. Separate tables or a stack of tables per scope resolve each use to the correct declaration.
• Optimization uses attributes such as whether a variable is constant or used.

Without the symbol table the compiler could not do type checking, scope resolution, storage allocation or consistent code generation, so it is an essential component.

Recursive descent vs non-recursive predictive parsing

FIRST and FOLLOW

Grammar:

• $E \to TA$
• $A \to +TA \mid \varepsilon$
• $T \to FB$
• $B \to *FB \mid \varepsilon$
• $F \to (E) \mid id$

FIRST sets:

• $FIRST(F) = \{ (, id \}$
• $FIRST(T) = FIRST(F) = \{ (, id \}$
• $FIRST(E) = FIRST(T) = \{ (, id \}$
• $FIRST(A) = \{ +, \varepsilon \}$
• $FIRST(B) = \{ *, \varepsilon \}$

FOLLOW sets:

• $FOLLOW(E)$: $E$ is the start symbol, so $USD \in FOLLOW(E)$, and $E$ is followed by $)$ in $F \to (E)$. So $FOLLOW(E) = \{ USD, ) \}$.
• $FOLLOW(A)$: from $E \to TA$, $FOLLOW(A) \supseteq FOLLOW(E)$, and from $A \to +TA$ it adds nothing new. So $FOLLOW(A) = \{ USD, ) \}$.
• $FOLLOW(T)$: from $E \to TA$ it gets $FIRST(A) \setminus \{\varepsilon\} = \{+\}$, and since $A$ is nullable also $FOLLOW(E)$ and $FOLLOW(A)$. So $FOLLOW(T) = \{ +, USD, ) \}$.
• $FOLLOW(B)$: from $T \to FB$, $FOLLOW(B) = FOLLOW(T) = \{ +, USD, ) \}$.
• $FOLLOW(F)$: from $T \to FB$ it gets $\{*\}$, and since $B$ is nullable also $FOLLOW(T)$. So $FOLLOW(F) = \{ *, +, USD, ) \}$.

SLR parse table

Number the productions (the grammar is already augmented by the start production $S \to E$, and we add $S' \to S$):

1. $S \to E$
2. $E \to E+T$
3. $E \to T$
4. $T \to T*F$
5. $T \to F$
6. $F \to id$

Canonical LR(0) collection

• $I_0$: $S' \to .S$, $S \to .E$, $E \to .E+T$, $E \to .T$, $T \to .T*F$, $T \to .F$, $F \to .id$
• $I_1 = goto(I_0,S)$: $S' \to S.$
• $I_2 = goto(I_0,E)$: $S \to E.$, $E \to E.+T$
• $I_3 = goto(I_0,T)$: $E \to T.$, $T \to T.*F$
• $I_4 = goto(I_0,F)$: $T \to F.$
• $I_5 = goto(I_0,id)$: $F \to id.$
• $I_6 = goto(I_2,+)$: $E \to E+.T$, $T \to .T*F$, $T \to .F$, $F \to .id$
• $I_7 = goto(I_3,*)$: $T \to T*.F$, $F \to .id$
• $I_8 = goto(I_6,T)$: $E \to E+T.$, $T \to T.*F$
• $I_9 = goto(I_7,F)$: $T \to T*F.$

Other transitions: $goto(I_6,F) = I_4$, $goto(I_6,id) = I_5$, $goto(I_7,id) = I_5$, $goto(I_8,*) = I_7$.

FOLLOW sets

• $FOLLOW(S) = \{USD\}$
• $FOLLOW(E) = \{USD, +\}$
• $FOLLOW(T) = \{USD, +, *\}$
• $FOLLOW(F) = \{USD, +, *\}$

SLR table (s = shift, r = reduce, acc = accept)

The reduce entries are placed only under the terminals in the FOLLOW set of the left-hand side. There are no multiply-defined entries, so the grammar is SLR(1).

Static vs dynamic type checking

Type checking using a syntax-directed definition

Each expression $E$ has a synthesized attribute E.type. Each statement $S$ has the attribute S.type, which is void if the statement is type correct and type_error otherwise. The function lookup(id.entry) returns the type of the identifier from the symbol table.

Explanation:

• In the assignment, the type of the identifier on the left must match the type of the expression on the right.
• The condition of if and while must be of type boolean; the statement then takes the type of its body, so an error inside the body propagates upward.
• A sequence of statements is correct only if both statements are correct.

For example, while x do y = 5 with x declared as int gives E.type = int, which is not boolean, so S.type = type_error.

Three address code

Three address code is an intermediate representation in which each instruction has at most three addresses (two operands and one result) and at most one operator on the right-hand side, of the general form

$x = y \ op \ z$

Complex expressions are broken into a sequence of such simple instructions using compiler-generated temporaries, and control flow is expressed with labels and jumps (goto, if ... goto). It is easy to optimize and to translate into target code. It is implemented as quadruples, triples or indirect triples.

Three address code for do m = n - p while a <= b

The body is executed first, then the condition is tested, and control returns to the start of the body while the condition is true.

L1:  t1 = n - p
     m  = t1
     if a <= b goto L1
L2:  ...

The code at L2 is the next statement after the loop. When a <= b is false the jump is not taken and control falls through to it.

Code optimization

Code optimization is the compiler phase (or set of transformations) that improves the intermediate or target code so that the program runs faster and/or uses less memory, without changing its meaning (output). Optimizations must be safe, must preserve the semantics, and should be worth the effort.

Three techniques

1. Constant folding (and propagation): expressions whose operands are constants are evaluated at compile time.

Before:  x = 2 * 3.14;  y = x + 1;
After:   x = 6.28;      y = 7.28;   (after propagating x)

2. Common subexpression elimination: if an expression has already been computed and its operands have not changed, reuse the earlier value instead of recomputing.

Before:  t1 = b * c        After:  t1 = b * c
         t2 = a + t1               t2 = a + t1
         t3 = b * c                t4 = t1 + d
         t4 = t3 + d

3. Dead code elimination: removal of code that is never executed or whose result is never used.

Before:  x = y + z;  x = 5;  print(x);
After:   x = 5;  print(x);       (first assignment is dead)

Other techniques include strength reduction (replace x*2 by x+x or x<<1), loop-invariant code motion, induction variable elimination, copy propagation and peephole optimization.

Activation record

When a procedure is called, the run-time system creates an activation record (stack frame) on the run-time stack to hold the information needed for that single execution (activation) of the procedure. It is removed when the procedure returns. The typical fields are:

Calling sequence and return sequence

Work is divided between the caller and the callee.

Caller (at call time)

1. Evaluates the actual parameters and places them (in the callee's frame or in registers).
2. Stores the return address and the old stack top pointer (control link) in the callee's frame.
3. Increments the stack pointer to create the new activation record, and jumps to the callee's code.

Callee (on entry)

1. Saves the registers and other machine status.
2. Initializes its local data and sets the frame pointer.
3. Begins executing its body.

Callee (on return)

1. Places the return value in the returned-value field (or a register).
2. Restores the registers and the stack top pointer, removing its own frame.
3. Branches to the return address.

Caller (after return)

1. Retrieves the returned value from the callee's frame (or register).
2. Continues execution with the next instruction, using the restored environment.

This division allows the number of arguments to be variable, since the caller knows what it passed while the callee knows how much local space it needs.

Phases of a compiler

A compiler translates a source program into target code in a number of phases. Each phase takes the output of the previous phase, while the symbol table manager and the error handler interact with all phases.

              Source program
                    |
          +---------v---------+
          |  Lexical analyzer |  -> tokens
          +---------+---------+
                    |
          +---------v---------+
          |   Syntax analyzer |  -> parse tree
          +---------+---------+
                    |                       +----------------+
          +---------v---------+             |  Symbol table  |
          | Semantic analyzer |  <--------> |    manager     |
          +---------+---------+             +----------------+
                    |                       +----------------+
          +---------v---------+  <--------> |  Error handler |
          | Intermediate code |             +----------------+
          |     generator     |
          +---------+---------+
                    |
          +---------v---------+
          | Code optimizer    |
          +---------+---------+
                    |
          +---------v---------+
          | Code generator    |
          +---------+---------+
                    |
              Target program

1. Lexical analysis (scanning): reads the characters of the source program, removes white space and comments, and groups characters into tokens (identifiers, keywords, operators, constants). For a = b + 10 the tokens are id(a), =, id(b), +, num(10).

2. Syntax analysis (parsing): checks whether the sequence of tokens follows the grammar of the language and builds a parse (syntax) tree. Syntax errors such as a missing ; are reported here.

3. Semantic analysis: uses the syntax tree and the symbol table to check the meaning: type checking, type conversion, declaration before use, and scope rules.

4. Intermediate code generation: produces a machine-independent representation, for example three address code: t1 = b + 10; a = t1.

5. Code optimization: improves the intermediate code to make it faster or smaller, for example by constant folding, removing common subexpressions and dead code, and loop optimizations.

6. Code generation: translates the optimized intermediate code to the target machine code or assembly, choosing instructions, allocating registers and memory.

Symbol table management keeps the attributes of identifiers (type, scope, address). Error handling detects, reports and recovers from errors in each phase. The first three phases are often called the analysis (front end) part, and the remaining ones the synthesis (back end) part.

DFA for $(\varepsilon + 0)^*10$ using the syntax tree method

Since $(\varepsilon + 0)^* = 0^*$, the language is $0^*10$. We follow the direct method anyway.

Step 1: Augment and number the leaves

The augmented expression is $(\varepsilon + 0)^* \cdot 1 \cdot 0 \cdot \#$. The leaves are numbered: $0$ is position 1, $1$ is position 2, $0$ is position 3 and $\#$ is position 4. The $\varepsilon$ leaf has no position.

Step 2: nullable, firstpos, lastpos

• $(\varepsilon+0)$: nullable, firstpos $=\{1\}$, lastpos $=\{1\}$.
• $(\varepsilon+0)^*$: nullable, firstpos $=\{1\}$, lastpos $=\{1\}$.
• Whole concatenation: since the star part is nullable, firstpos(root) $=\{1\} \cup \{2\} = \{1,2\}$.

Step 3: followpos

Step 4: Construct the DFA states

• Start state $A = firstpos(root) = \{1,2\}$.
• $A$ on 0: positions labelled 0 in $A$ is $\{1\}$, followpos $=\{1,2\} = A$.
• $A$ on 1: position $\{2\}$, followpos $=\{3\} = B$.
• $B$ on 0: position $\{3\}$, followpos $=\{4\} = C$.
• $B$ on 1: none. $C$ has no outgoing transitions.
• $C$ contains position 4 ($\#$), so it is the accepting state.

Transition table

(A missing transition goes to the dead state.) The DFA has three states: $A \xrightarrow{0} A$, $A \xrightarrow{1} B$, $B \xrightarrow{0} C$, with $C$ final. It accepts exactly the strings $0^*10$, for example $10$, $0010$. No two states are equivalent, so the DFA is already minimal.

Shift reduce parsing

Shift reduce parsing is a bottom-up parsing technique that constructs the parse tree from the leaves toward the root, reducing the input string to the start symbol. It uses a stack and an input buffer, with the following actions:

• Shift: move the next input symbol onto the top of the stack.
• Reduce: if the top of the stack is a handle (the right side of a production), replace it by the left-hand side non-terminal.
• Accept: the stack holds only the start symbol and the input is empty ($).
• Error: call the error recovery routine.

Parsing of $(x+x)*a$

Taking the grammar $E \to E+E \mid E*E \mid (E) \mid x \mid a$, with $*$ binding tighter than $+$ (the parenthesis forces the sum first):

The string is successfully parsed.

SLR parsing table

Productions:

1. $S \to aAa$
2. $S \to bAb$
3. $S \to ba$

The non-terminal $A$ has no productions in the given grammar, so it never derives a string. The only string actually generated by the grammar is $ba$, but the table is still built by the standard procedure. Augment with $S' \to S$.

Canonical LR(0) collection

• $I_0$: $S' \to .S$, $S \to .aAa$, $S \to .bAb$, $S \to .ba$
• $I_1 = goto(I_0,S)$: $S' \to S.$
• $I_2 = goto(I_0,a)$: $S \to a.Aa$
• $I_3 = goto(I_0,b)$: $S \to b.Ab$, $S \to b.a$
• $I_4 = goto(I_2,A)$: $S \to aA.a$
• $I_5 = goto(I_4,a)$: $S \to aAa.$
• $I_6 = goto(I_3,A)$: $S \to bA.b$
• $I_7 = goto(I_3,a)$: $S \to ba.$
• $I_8 = goto(I_6,b)$: $S \to bAb.$

$FOLLOW(S) = \{USD\}$, so all reductions are placed under $USD$.

SLR table

There are no conflicts, so the grammar is SLR(1). States 2, 4 and 6 can never be reached in a parse because there is no way to reduce to $A$, so only the string $ba$ is accepted (shift $b$, shift $a$ to state 7, reduce by $S \to ba$ on $USD$, goto state 1, accept).

Type checking using a syntax-directed definition

Each expression $E$ has a synthesized attribute E.type, whose value is a type expression such as integer, real, boolean, array(s,t), pointer(t) or type_error. The function lookup(id.entry) returns the type stored in the symbol table.

Explanation:

• For an identifier, the type is taken from the symbol table.
• For an arithmetic operator, two integers give an integer; if either operand is real (the other being numeric) the result is real, with the integer operand converted. Anything else is an error.
• For a relational operator, both operands must have the same basic type and the result is boolean.
• For array indexing, the index must be an integer and the indexed expression must be an array; the result is the element type $t$.
• For the dereference operator $\uparrow$, the operand must be a pointer to type $t$, and the result is $t$.

Intermediate code representation

Intermediate code is a machine-independent form of the program generated between the front end and the back end. It makes the compiler portable and allows optimization. The main representations are listed below, using the example $a = b * -c + b * -c$.

1. Syntax tree: a condensed parse tree in which the operators are the interior nodes and the operands are the children.

        =
       / \
      a   +
         / \
        *   *
       / \ / \
      b uminus b uminus
          |        |
          c        c

A DAG is similar, but identical sub-expressions are represented by a single shared node (here b * uminus c appears once), which avoids recomputation.

2. Postfix notation: the operator follows its operands, so no parentheses are needed: a b c uminus * b c uminus * + =.

3. Three address code: instructions of the form $x = y\ op\ z$ using temporaries:

t1 = uminus c
t2 = b * t1
t3 = uminus c
t4 = b * t3
t5 = t2 + t4
a  = t5

It is stored as one of three forms.

Quadruples have four fields (op, arg1, arg2, result):

Triples have three fields (op, arg1, arg2), and a result is referred to by the index of the instruction that computed it:

Indirect triples keep a separate list of pointers to triples, so statements can be reordered during optimization without changing the references.

Quadruples are easy to optimize (temporaries are explicit) but use more space; triples save space but moving statements is hard.

Purpose of code optimization

Code optimization transforms the intermediate code so that the final program runs faster and/or takes less memory, without changing its meaning. Since programs spend most of their time in loops, loop optimization gives the greatest improvement.

Loop optimization techniques

1. Code motion (loop-invariant code motion): a computation whose value does not change inside the loop is moved outside it, so it is done once.

Before:                          After:
while (i <= limit - 2) {         t = limit - 2;
    ...                          while (i <= t) {
}                                    ...
                                 }

2. Induction variable elimination: variables that change by a fixed amount each iteration (such as $i$ and $j = 4i$) are related; redundant ones are removed.

Before:                      After:
for (i = 0; i < n; i++)      for (j = 0; j < 4*n; j += 4)
    a[4*i] = 0;                  a[j] = 0;

3. Strength reduction: replace an expensive operation in the loop by a cheaper one, for example multiplication by repeated addition.

Before: for (i=1;i<=n;i++) x = i * 5;
After:  t = 0; for (i=1;i<=n;i++) { t = t + 5; x = t; }

4. Loop unrolling: the body is replicated several times to reduce the number of iterations and the loop-control overhead.

Before: for (i=0;i<100;i++) a[i]=0;
After:  for (i=0;i<100;i+=2) { a[i]=0; a[i+1]=0; }

5. Loop jamming (fusion): two loops with the same limits are merged into one loop.

Before: for(i=0;i<n;i++) a[i]=0;  for(i=0;i<n;i++) b[i]=1;
After:  for(i=0;i<n;i++) { a[i]=0; b[i]=1; }

6. Loop invariant/dead code removal and loop fission (splitting) are other variants.

Importance of the error handler

Programmers make errors, so a compiler must not simply stop at the first error. The error handler is the component of the compiler that detects errors, reports them, and recovers so that compilation continues and further errors can be found. Its importance:

• It reports errors clearly with the line number and a meaningful message, helping the programmer to correct the program.
• It recovers from each error so that the rest of the program can be checked in a single run.
• It prevents the compiler from crashing or looping on erroneous input, and avoids producing misleading cascaded errors.
• It adds little overhead to the processing of correct programs.

Handling errors in the different phases

Recovery strategies in brief

• Panic mode: discard input symbols until a synchronizing token is seen. It is simple and cannot loop forever.
• Phrase-level: perform a local correction (e.g. replace a comma by a semicolon).
• Error productions: extend the grammar with productions for common errors.
• Global correction: find the minimum changes that make the program correct (expensive, mostly theoretical).

Tasks performed in lexical analysis

The lexical analyzer (scanner) is the first phase of the compiler. Its tasks are:

1. Read the source characters and group them into lexemes, producing a stream of tokens (identifier, keyword, operator, constant, punctuation) for the parser.
2. Remove white space (blank, tab, newline) and comments.
3. Correlate error messages with the source line numbers.
4. Enter identifiers into the symbol table, and expand macros if the language needs it.
5. Report lexical errors such as illegal characters or malformed numbers.

Token specification is done with regular expressions, and recognition is done with finite automata.

DFA

A deterministic finite automaton is a 5-tuple $(Q, \Sigma, \delta, q_0, F)$ where $Q$ is a finite set of states, $\Sigma$ the input alphabet, $\delta: Q \times \Sigma \to Q$ the transition function (exactly one next state for each state and symbol), $q_0 \in Q$ the start state and $F \subseteq Q$ the set of accepting states.

DFA for $(a+b)^*a(a+b)$

The language is the set of strings over $\{a,b\}$ whose second-last symbol is $a$.

NFA: $q_0 \xrightarrow{a,b} q_0$, $q_0 \xrightarrow{a} q_1$, $q_1 \xrightarrow{a,b} q_2$, with $q_2$ final.

Subset construction:

Working: $B$ on $a$ gives $\{q_0,q_1\} \cup \{q_2\} = \{q_0,q_1,q_2\} = C$; $B$ on $b$ gives $\{q_0\} \cup \{q_2\} = D$; $C$ on $a$ gives $\{q_0,q_1,q_2\}$; $C$ on $b$ gives $\{q_0,q_2\}$; $D$ on $a$ gives $\{q_0,q_1\}$; $D$ on $b$ gives $\{q_0\}$.

The states remember the last two symbols read, so all four are distinguishable and the DFA is minimal. Check: $ab$ goes $A \to B \to D$ (accepted), $ba$ goes $A \to A \to B$ (rejected).

Difference between LR(0) and LR(1)

Canonical LR(1) table for $S \to AA$, $A \to aA \mid b$

Augment: $S' \to S$. Productions: 1 $S \to AA$, 2 $A \to aA$, 3 $A \to b$.

Item sets

• $I_0$: $S' \to .S, USD$; $S \to .AA, USD$; $A \to .aA, a/b$; $A \to .b, a/b$
• $I_1 = goto(I_0,S)$: $S' \to S., USD$
• $I_2 = goto(I_0,A)$: $S \to A.A, USD$; $A \to .aA, USD$; $A \to .b, USD$
• $I_3 = goto(I_0,a)$: $A \to a.A, a/b$; $A \to .aA, a/b$; $A \to .b, a/b$
• $I_4 = goto(I_0,b)$: $A \to b., a/b$
• $I_5 = goto(I_2,A)$: $S \to AA., USD$
• $I_6 = goto(I_2,a)$: $A \to a.A, USD$; $A \to .aA, USD$; $A \to .b, USD$
• $I_7 = goto(I_2,b)$: $A \to b., USD$
• $I_8 = goto(I_3,A)$: $A \to aA., a/b$
• $I_9 = goto(I_6,A)$: $A \to aA., USD$

Also $goto(I_3,a) = I_3$, $goto(I_3,b) = I_4$, $goto(I_6,a) = I_6$, $goto(I_6,b) = I_7$.

Parsing table

The table has no conflicts, so the grammar is LR(1). (Merging states with equal cores, $I_3/I_6$, $I_4/I_7$, $I_8/I_9$, would give the 7-state LALR table.)

Type checking

Type checking is the semantic-analysis task of verifying that every operator and function is applied to operands of the correct types according to the language's type system, so that type-related errors are found before the program is run.

Type system

A type system consists of the type expressions (basic types such as int, float, boolean, char, and constructed types such as arrays, records, pointers and functions), together with the rules for assigning types to the constructs of the language. A compiler assigns a type expression to every identifier and sub-expression, and a type checker implements the rules.

Kinds of checking

• Static checking is done at compile time (C, Java). It finds errors early with no run-time cost.
• Dynamic checking is done at run time (Python, JavaScript). It is more flexible but adds overhead, and errors appear late.

Type conversion and coercion

If the operand types differ, the type checker may insert an implicit conversion (coercion), for example int to float in 2 + 3.5, or report a type error when no conversion is allowed, as when a string is added to an int in a strictly typed language. An explicit conversion is called a cast.

Example of rules

• For $E \to E_1 + E_2$: if both operands are int the type is int; if one is float and the other int or float, the type is float; otherwise it is type_error.
• For an assignment $id = E$: the type of id and of E must be compatible.
• For an array reference $E_1[E_2]$: $E_1$ must be an array and $E_2$ an int.
• For a function call: the number and types of the actual arguments must match the formal parameters.

Example of a type error: int x; x = "abc"; is rejected at compile time because a string cannot be assigned to an int.

Implementation

Type checking is implemented with a syntax-directed definition in which every expression has a synthesized attribute type, with symbol table lookups giving the types of identifiers. Type equivalence is decided by structural or name equivalence.

The primary goal is to prevent type-related errors, such as invalid operations, wrong function arguments and incompatible assignments, before the program runs, which makes programs safer and more reliable.

Difference between compiler and interpreter

Some systems, such as Java, use both: the source is compiled to bytecode, which is then interpreted (or JIT-compiled) by a virtual machine.

Symbol table entries

The symbol table is a data structure used by the compiler to store information about the names (identifiers) used in the source program. It is created during lexical and syntax analysis and used in all later phases. Each entry typically contains the following information.

Example: for float x[10]; declared inside function main, the entry is (x, array variable, array(10,float), local to main, offset 0, size 40 bytes).

The compiler performs two main operations: insert a name at the declaration, and lookup when the name is used. A hash table is generally used so that both are fast.

Left recursive grammar

A grammar is left recursive if there is a non-terminal $A$ such that $A \Rightarrow^+ A\alpha$ for some string $\alpha$. If the recursion appears directly in a production, $A \to A\alpha$, it is immediate left recursion. Top-down parsers (recursive descent, LL(1)) can loop forever on such grammars, so left recursion must be removed.

Removal rule

$A \to A\alpha_1 \mid A\alpha_2 \mid \beta_1 \mid \beta_2 \quad\Longrightarrow\quad A \to \beta_1 A' \mid \beta_2 A',\qquad A' \to \alpha_1 A' \mid \alpha_2 A' \mid \varepsilon$

Given grammar

• $S \to SB \mid Ca$
• $B \to Bb \mid c$
• $C \to aB \mid a$

For $S$: $\alpha = B$, $\beta = Ca$:

• $S \to CaS'$
• $S' \to BS' \mid \varepsilon$

For $B$: $\alpha = b$, $\beta = c$:

• $B \to cB'$
• $B' \to bB' \mid \varepsilon$

For $C$: $C \to aB \mid a$ has no left recursion (and does not derive a string starting with $C$), so it is unchanged.

Resulting grammar

• $S \to CaS'$
• $S' \to BS' \mid \varepsilon$
• $B \to cB'$
• $B' \to bB' \mid \varepsilon$
• $C \to aB \mid a$

It generates the same language and has no left recursion. (A left factoring of $C$ gives $C \to aC'$, $C' \to B \mid \varepsilon$ if an LL(1) grammar is needed.)

Disadvantages of shift reduce parsing

• It is hard to write by hand; the parser is usually generated by tools (Yacc/Bison).
• Conflicts arise: a shift/reduce conflict (the parser cannot decide whether to shift or to reduce) and a reduce/reduce conflict (more than one production can be reduced). Ambiguous grammars, such as the one in this question, give conflicts that must be resolved with precedence and associativity rules.
• Not every context-free grammar can be handled; the handle must be found correctly on the stack.
• Error reporting and recovery are difficult because the parser has lost the context of what it was building.
• The parsing tables (for LR parsers) are large.

Shift reduce parsing of $(x-x)-(x/x)$

Grammar: $E \to E-E \mid E/E \mid (E) \mid x$, where $/$ has higher precedence than $-$ and $-$ is left associative. Conflicts are resolved by these rules, and the parenthesized subexpressions are handled first.

The string is accepted.

Attribute grammar

An attribute grammar is a context-free grammar in which each grammar symbol has a set of attributes (values such as type, value or code), and each production is associated with semantic rules that define how the attribute values are computed. It is a formal way to describe the semantics of a language and is the basis of syntax-directed translation. The attributes are of two kinds.

Synthesized attribute: the value of an attribute at a node is computed from the attributes of its children (and possibly of the node itself). Information flows bottom-up. A grammar with only synthesized attributes is called S-attributed.

Example (desk calculator):

For input 3*5+4, the synthesized attribute val flows from the leaves up, giving E.val = 19.

Inherited attribute: the value of an attribute at a node is computed from the attributes of its parent and/or siblings. Information flows top-down or sideways.

Example (declaration int a, b, c):

Here type of $T$ is synthesized, while in of $L$ is inherited from its left sibling $T$ and passes down the list so that every identifier gets the type integer.

Three address code

Three address code is an intermediate representation in which every instruction has at most three addresses, and at most one operator on the right side, of the form

$x = y \ op \ z$

where $x, y, z$ are names, constants or compiler-generated temporaries. Complex expressions are broken into a sequence of such simple instructions. It is easy to optimize and to convert into target code, and is stored as quadruples, triples or indirect triples.

Expression: $a = -b * (c + d) / e$

With unary minus having the highest precedence, then * and / left to right (so the expression is $((-b) * (c+d)) / e$), the three address code is:

t1 = uminus b
t2 = c + d
t3 = t1 * t2
t4 = t3 / e
a  = t4

Quadruples

Runtime storage management decides where the data of a running program lives. The target program's run-time memory is divided into a code area, a static area, a stack and a heap. Three allocation strategies are used.

1. Static allocation

• Storage is fixed at compile time, and the size and address of every name are known before execution.
• It is used for global variables, constants and static variables.
• It does not allow recursion, because each procedure has only one activation record, and it does not allow dynamically sized data.
• Advantage: it is fast and has no run-time overhead.

2. Stack allocation

• Storage is organised as a stack of activation records. A record is pushed when a procedure is called and popped when it returns.
• Local variables, parameters, the return address and the saved registers live in the record.
• It supports recursion and reuses memory automatically. Local values are lost after the return.
• It cannot hold data that must outlive the call that created it.

3. Heap allocation

• Memory is allocated and freed at run time in any order (malloc/free, new/delete).
• It is used for dynamic data structures such as linked lists and trees, and for data that must outlive the procedure that created it.
• It needs a free-space manager, which can cause fragmentation, and it needs garbage collection or explicit deallocation to reclaim storage. It is slower than the stack.

Advantages of code optimization

• The program runs faster, because redundant and expensive operations are removed or replaced.
• The program uses less memory (smaller code and fewer temporaries).
• It consumes less power, which matters on embedded and mobile devices.
• It lets programmers write clear, high-level code, because the compiler removes the inefficiency.
• It reduces the cost of loops and function calls, which are where programs spend most of their time.
• The program becomes more portable, since the optimizer can produce efficient code for each target machine.
• It does not change the meaning of the program. Only the efficiency changes.

Dead-code elimination

Dead code is code that can never be executed, or code that computes a value that is never used afterwards. Dead-code elimination removes such statements. This makes the program smaller and faster without changing its output.

There are two kinds:

1. Unreachable code: statements after a return or goto, or inside a branch whose condition is always false.
2. Dead (useless) assignments: a variable is assigned but not live afterwards, meaning its value is never used before it is redefined.

Example:

int f(int a) {
    int x = a * 5;     // x never used: dead store
    int debug = 0;
    if (debug) {       // condition always false
        print(a);      // unreachable
    }
    return a + 1;
}

After the optimization:

int f(int a) {
    return a + 1;
}

Dead code often appears after other optimizations such as constant propagation and copy propagation, so the compiler usually runs dead-code elimination repeatedly.

The code generator takes the intermediate representation (IR) and the symbol table as input and produces the target program. The output must be correct and of high quality, meaning it must run efficiently and use little memory. Generating optimal code is undecidable in general, so heuristics are used. The main design issues are listed below.

1. Input to the code generator The input is the IR (three-address code, quadruples, DAG, postfix) together with symbol-table information. The IR is assumed to be free of syntactic and semantic errors, with types already checked and conversions inserted. The level of the IR (high or low) affects the quality of the generated code.

2. Target program The output may be absolute machine code, relocatable machine code or assembly language.

• Absolute code can be executed immediately, but it is placed at a fixed memory location.
• Relocatable code allows separate compilation and linking, but it needs a linker and loader.
• Assembly code makes generation and debugging easier, but it needs an extra assembly step.

The target instruction set (RISC or CISC, addressing modes) also shapes the generated code.

3. Instruction selection Each IR statement must be mapped to target instructions. The choice depends on the uniformity and completeness of the instruction set, the instruction speeds and machine idioms. For example, a = a + 1 can use INC a instead of LD, ADD, ST. A naive statement-by-statement translation gives redundant loads and stores.

4. Register allocation and assignment Registers are much faster than memory but there are few of them. Deciding which values stay in registers is register allocation. Deciding which register holds a value is register assignment. Finding the optimal assignment is NP-complete. Some machines also require register pairs, for example for multiplication and division.

5. Evaluation order The order in which computations are performed affects the number of registers and instructions needed. Some orders need fewer temporaries than others. Choosing the best order is also NP-complete, so a simple order is usually used.

6. Memory management Names in the IR must be mapped to run-time addresses. Static, stack and heap storage determine how a name is addressed (absolute, frame offset, pointer), and labels in three-address code must be turned into instruction addresses.

7. Approach to code generation The generator should be correct, easy to implement, test and maintain. Correctness is the most important property.

Difference between one-pass and multi-pass compiler

A pass is one complete traversal of the source program or its intermediate form.

LL(1) parsing table

Grammar:

$S \to ABCD,\quad A \to a \mid \varepsilon,\quad B \to b,\quad C \to 0 \mid \varepsilon,\quad D \to d \mid \varepsilon$

FIRST sets:

• $FIRST(A)=\{a,\varepsilon\}$
• $FIRST(B)=\{b\}$
• $FIRST(C)=\{0,\varepsilon\}$
• $FIRST(D)=\{d,\varepsilon\}$
• $FIRST(S)=\{a,b\}$, since $A$ is nullable and $B$ is not.

FOLLOW sets:

• $FOLLOW(S)=\{USD\}$
• $FOLLOW(A)=FIRST(B)=\{b\}$
• $FOLLOW(B)=\{0,d,USD\}$, from $FIRST(C)$, then $FIRST(D)$, then $FOLLOW(S)$ because both are nullable.
• $FOLLOW(C)=\{d,USD\}$
• $FOLLOW(D)=FOLLOW(S)=\{USD\}$

Table entries. Entry $M[X,t]$ takes $X\to\alpha$ for every $t\in FIRST(\alpha)$. If $\alpha$ is nullable, it also takes $X\to\alpha$ for every $t\in FOLLOW(X)$.

No cell contains more than one production, so the grammar is LL(1).

How a lexical analyzer recognizes a token

Each token class is described by a regular expression, for example:

• identifier: $letter\,(letter\mid digit)^*$
• number: $digit^+$
• relational operator: <, <=, ==, >, >=

The specification is converted into a finite automaton (regular expression, then NFA, then DFA). The lexer then works as follows:

1. It starts in the initial state at the first unread character (lexemeBegin).
2. It moves a forward pointer through the input and follows the DFA transition for each character.
3. It remembers the last accepting state seen (longest-match rule). When no transition is possible, it stops.
4. It retracts the forward pointer to the last accepting position. The characters between lexemeBegin and forward form the lexeme.
5. It returns the token (token name, attribute value), for example by looking up the identifier in the symbol table or checking the keyword table. Whitespace and comments are skipped.

Example: for the input count1 = 25; and the identifier DFA

start --letter--> (S1) --letter/digit--> (S1)

• c takes the DFA from the start state to S1, which is accepting.
• o, u, n, t, 1 keep it in S1.
• The space has no transition, so the lexeme count1 is accepted.
• The token returned is <id, pointer to the symbol-table entry for count1>.
• Then = gives <assign_op>, 25 gives <num, 25> and ; gives <semicolon>.

Regular expression to DFA: $a(a+b)(b+c)^*a\#$

The direct method (followpos) is used. Number the positions:

$a_1\,(a_2+b_3)\,(b_4+c_5)^*\,a_6\,\#_7$

Nullable and firstpos: $(b_4+c_5)^*$ is nullable and the others are not. So $firstpos(root)=\{1\}$.

followpos:

Subset construction. Start with $A=\{1\}$.

• $A$ on $a$: positions with symbol $a$ are 1, so the state is $followpos(1)=\{2,3\}=B$.
• $B$ on $a$: position 2, giving $\{4,5,6\}=C$. $B$ on $b$: position 3, giving $\{4,5,6\}=C$.
• $C$ on $a$: position 6, giving $\{7\}=D$. $C$ on $b$: position 4, giving $\{4,5,6\}=C$. $C$ on $c$: position 5, giving $C$.
• $D$ has no outgoing transitions. It contains $\#$, so it is the accepting state.

The DFA accepts strings of the form $a\,(a|b)\,(b|c)^*\,a$.