BE Computer Engineering (Pokhara University) Compiler Design (PU, CMP 422) Question Paper 2079 Nepal

(a) Phases of a Compiler

A compiler translates a source program into target code through the following phases (the analysis/front-end followed by the synthesis/back-end):

   Source program
        |
  +-----------------+
  | Lexical Analyzer|  (Scanner)  -> tokens
  +-----------------+
        |
  +-----------------+
  | Syntax Analyzer |  (Parser)   -> parse/syntax tree
  +-----------------+
        |
  +-----------------+
  | Semantic        |  -> type-checked tree
  | Analyzer        |
  +-----------------+
        |
  +-----------------+
  | Intermediate    |  -> three-address code
  | Code Generator  |
  +-----------------+
        |
  +-----------------+
  | Code Optimizer  |  -> optimized IR
  +-----------------+
        |
  +-----------------+
  | Code Generator  |  -> target (assembly/machine) code
  +-----------------+
        |
   Target program

The Symbol Table and Error Handler interact with all phases.

• Lexical Analysis: groups characters into tokens, removes whitespace/comments.
• Syntax Analysis: builds a parse tree using the grammar; reports syntax errors.
• Semantic Analysis: checks types, scope, declarations; inserts type conversions.
• Intermediate Code Generation: produces machine-independent code (three-address code).
• Code Optimization: improves the IR for speed/size.
• Code Generation: emits target machine code, allocating registers.

Trace of position = initial + rate * 60

Assume position, initial, rate are float.

1. Lexical Analyzer (tokens):

id1(position)  =  id2(initial)  +  id3(rate)  *  60

(symbol table: id1=position, id2=initial, id3=rate)

2. Syntax Analyzer (parse tree):

        =
      /   \
   id1     +
          /  \
       id2     *
              /  \
           id3    60

3. Semantic Analyzer: 60 (int) is converted to float via inttofloat:

        =
      /   \
   id1     +
          /  \
       id2     *
              /  \
           id3   inttofloat(60)

4. Intermediate Code (three-address code):

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

5. Code Optimizer:

t1 = id3 * 60.0
id1 = id2 + t1

6. Code Generator (target code, registers R1/R2):

LDF  R2, id3
MULF R2, R2, #60.0
LDF  R1, id2
ADDF R1, R1, R2
STF  id1, R1

(b) Compiler vs Interpreter

Two advantages of front-end / back-end division:

1. Retargetability: the same front-end can be reused with different back-ends to generate code for several target machines.
2. Reusability/portability: different source languages can share one back-end (and optimizer) by writing only a new front-end that produces the common intermediate representation; it also makes the compiler easier to maintain and to add optimizations.

(a) FIRST and FOLLOW sets

Grammar:

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

FIRST:

FOLLOW (start symbol gets $):

(b) LL(1) Predictive Parsing Table

Each production A -> alpha is placed under terminals in FIRST(alpha); if alpha derives epsilon, also under FOLLOW(A).

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

(c) Parsing id + id * id $

The string id + id * id is successfully parsed.

(a) Canonical LR(0) item sets and DFA

Grammar (augmented):

0. S' -> S
1. S  -> C C
2. C  -> c C
3. C  -> d

Item sets:

I0 = closure(S'->.S)

S' -> . S
S  -> . C C
C  -> . c C
C  -> . d

I1 = goto(I0,S): S' -> S .

I2 = goto(I0,C):

S -> C . C
C -> . c C
C -> . d

I3 = goto(I0,c):

C -> c . C
C -> . c C
C -> . d

I4 = goto(I0,d): C -> d .

I5 = goto(I2,C): S -> C C .

I6 = goto(I3,C): C -> c C .

(goto(I2,c)=I3, goto(I2,d)=I4, goto(I3,c)=I3, goto(I3,d)=I4.)

DFA of viable prefixes (transitions):

I0 --S--> I1
I0 --C--> I2     I0 --c--> I3     I0 --d--> I4
I2 --C--> I5     I2 --c--> I3     I2 --d--> I4
I3 --C--> I6     I3 --c--> I3     I3 --d--> I4

(b) SLR(1) Parsing Table

FOLLOW(S')={$}, FOLLOW(S)={$}, FOLLOW(C)={c, d, $}. Reduce by C->d (prod 3) in I4 and by C->cC (prod 2) in I6 on FOLLOW(C)={c,d,}; reduce by `S->CC` (prod 1) in I5 on ``.

(s = shift, rN = reduce by production N, acc = accept.) No conflicts -> grammar is SLR(1).

(c) Parsing cdd $

The input cdd is accepted.

(a) Basic block, flow graph, and partitioning

Basic block: a maximal sequence of consecutive three-address statements with a single entry (at the first statement) and a single exit (at the last), i.e. control enters only at the beginning and leaves only at the end with no internal branches or branch targets.

Flow graph (control flow graph): a directed graph whose nodes are the basic blocks and whose edges represent the possible flow of control between blocks.

Leaders (first statements of blocks): (1) the first statement; (2) any target of a goto; (3) any statement following a goto/conditional jump. Here leaders are: statement 1, statement 2 (target of goto 2), statement 3 (target of goto 3), statement 9 (follows the jump in 8).

Basic blocks:

B1: 1: i = 1
B2: 2: j = 1
B3: 3: t1 = 10 * i
    4: t2 = t1 + j
    5: t3 = 8 * t2
    6: a[t3] = 0.0
    7: j = j + 1
    8: if j <= 10 goto 3
B4: 9:  i = i + 1
    10: if i <= 10 goto 2

Control flow graph (edges):

B1 -> B2
B2 -> B3
B3 -> B3   (loop back, j <= 10)
B3 -> B4   (fall through, j > 10)
B4 -> B2   (loop back, i <= 10)
B4 -> exit (i > 10)

This represents the nested loop: the inner loop (B3) over j, nested inside the outer loop (B2..B4) over i.

(b) Three machine-independent optimizations

1. Common Subexpression Elimination: if an expression is computed more than once and its operands are unchanged, compute it once and reuse the result.

t1 = b * c        t1 = b * c
t2 = b * c   =>   x  = t1 + 1
x  = t1 + 1       y  = t1 + 2
y  = t2 + 2

2. Dead Code Elimination: remove statements whose computed value is never used.

x = a + b        (x never used later)
y = a - b   =>   y = a - b
... use y

The assignment to x is dead and is deleted.

3. Loop-Invariant Code Motion: move computations whose value does not change inside the loop out to a pre-header.

while (i < n) {          t = a * b;     // moved out
   x = a * b;     =>     while (i < n) {
   c[i] = x + i;            c[i] = t + i;
   i++;                     i++;
}                        }

This avoids recomputing a * b on every iteration.

(a) Regular expression for C identifiers

Let letter = [A-Za-z], digit = [0-9].

$$\text{id} \;=\; (\text{letter} \mid \_)\,(\text{letter} \mid \text{digit} \mid \_)^*$$

In POSIX/lex form: [A-Za-z_][A-Za-z0-9_]* — a letter or underscore, followed by zero or more letters, digits, or underscores.

(b) NFA (Thompson) and DFA (subset construction) for (a|b)*abb

Thompson NFA (states 0..10; epsilon = e):

0 -e-> 1, 0 -e-> 7
1 -e-> 2, 1 -e-> 4
2 -a-> 3 -e-> 6
4 -b-> 5 -e-> 6
6 -e-> 1, 6 -e-> 7
7 -a-> 8
8 -b-> 9
9 -b-> 10  (10 = accepting)

The sub-NFA on states 1..6 forms the (a|b)* loop; states 7..10 match abb.

Subset construction (DFA). Compute epsilon-closures.

• A = closure(0) = {0,1,2,4,7}
• B = move(A,a) closure = {1,2,3,4,6,7,8}
• C = move(A,b) closure = {1,2,4,5,6,7}
• move(B,a) = B; move(B,b) closure = {1,2,4,5,6,7,9} = D
• move(C,a) = B; move(C,b) = C
• move(D,a) = B; move(D,b) closure = {1,2,4,5,6,7,10} = E (accepting, contains 10)
• move(E,a) = B; move(E,b) = C

DFA transition table (start = A, accept = E):

This DFA accepts exactly the strings over {a,b} ending in abb.

(a) Ambiguity of E -> E + E | E * E | id

The grammar is ambiguous because the string id + id * id has two distinct leftmost derivations / parse trees:

Tree 1 ( + at root, i.e. id + (id * id) ):

        E
      / | \
     E  +  E
     |    / | \
    id   E  *  E
         |     |
        id    id

Tree 2 ( * at root, i.e. (id + id) * id ):

        E
      / | \
     E  *  E
   / | \   |
  E  +  E id
  |     |
 id    id

Since one string yields two different parse trees, the grammar is ambiguous.

(b) Remove left recursion and left factoring

Grammar:

A -> A c | A a d | b d | c

This is immediate left recursion of the form A -> A alpha1 | A alpha2 | beta1 | beta2 with:

• alpha1 = c, alpha2 = a d
• beta1 = b d, beta2 = c

Standard elimination A -> beta A', A' -> alpha A' | epsilon:

A  -> b d A' | c A'
A' -> c A' | a d A' | epsilon

Left factoring: the two A-alternatives b d A' and c A' begin with different terminals (b vs c), so no factoring is needed for A. The A'-alternatives c A' and a d A' also begin with different terminals (c vs a), so no factoring is required there either.

Final grammar (left-recursion-free, already left-factored):

A  -> b d A' | c A'
A' -> c A' | a d A' | epsilon

(a) Synthesized vs Inherited attributes

Example (synthesized): in E -> E1 + T { E.val = E1.val + T.val }, E.val is built from its children — synthesized.

Example (inherited): in a declaration D -> T L, the type is passed down: L.inh = T.type and then L -> id { addtype(id.entry, L.inh) }. Here L.inh is inherited from its sibling T.

(b) Syntax-Directed Definition for a desk calculator

Grammar with synthesized attribute val:

This S-attributed definition gives + lower precedence than * (because * appears at the deeper T level) and both are left-associative; ( E ) handles parentheses. Example: for input 2 + 3 * 4, it computes T = 3*4 = 12, then E = 2 + 12 = 14.

(a) Three-address code

Three-address code (TAC) is an intermediate representation in which each instruction has at most three addresses (operands) and one operator, of the general form x = y op z. Complex expressions are broken into a sequence of such instructions using temporary names, making it easy to optimize and to translate to machine code.

Common representations:

1. Quadruples — record (op, arg1, arg2, result); results are named explicitly.
2. Triples — (op, arg1, arg2); the result is referred to by the triple's position/index (no explicit temporaries).
3. Indirect triples — a list of pointers to triples, so triples can be reordered (e.g. during optimization) without changing references.

(b) TAC and quadruples for a = b * -c + b * -c

Three-address code:

t1 = - c        (unary minus)
t2 = b * t1
t3 = - c
t4 = b * t3
t5 = t2 + t4
a  = t5

Quadruple representation:

(With common-subexpression elimination the two -c/b*-c computations collapse to one, but the unoptimized form above is the direct translation.)

(a) Symbol table contents and nested scopes

Information stored for each identifier (name): the name (lexeme), its type, its scope/storage class, memory location/offset, size, and for procedures the number and types of parameters and the return type; for arrays/structures, dimension and field information.

Handling nested scopes (block structure): scopes are organized as a stack of tables (a chain of symbol tables), one per block/procedure.

• On entering a block, a new (child) symbol table is created and pushed; it links back to the enclosing scope's table.
• A declaration inserts the name into the current (innermost) table.
• A lookup searches the innermost table first; if not found, it follows the parent links outward to enclosing scopes (implementing the most-closely-nested rule).
• On exiting the block, its table is popped/closed, so its local names become invisible while outer names remain.

(b) Linear list vs hash table for a symbol table

Conclusion: a linear list is simple and space-efficient but slow (linear search), suitable only for small symbol tables. A hash table gives near-constant insertion and lookup on average and is the preferred structure for real compilers; performance degrades only when many collisions occur.

(a) Major issues in code generator design

1. Input/IR form: the form of the intermediate representation accepted (three-address code, trees, DAGs).
2. Target program / instruction set: properties of the target machine (RISC/CISC), available instructions and addressing modes.
3. Instruction selection: choosing the most efficient machine instructions that implement each IR operation (cost-effective patterns).
4. Register allocation and assignment: deciding which values reside in registers (limited number) and which in memory — strongly affects speed.
5. Evaluation order: choosing the order of computations to minimize register usage and temporaries.
6. Approach: keeping the generator simple, correct, and maintainable.

(b) DAG for a + a * (b - c) + (b - c) * d

Identify the repeated subexpression (b - c). A DAG (Directed Acyclic Graph) shares a single node for each common subexpression.

Nodes:

n1: b
n2: c
n3: -   (children n1, n2)        ; represents (b - c), shared
n4: a
n5: *   (children n4, n3)        ; a * (b - c)
n6: +   (children n4, n5)        ; a + a*(b-c)   (a is shared node n4)
n7: d
n8: *   (children n3, n7)        ; (b - c) * d   (reuses n3)
n9: +   (children n6, n8)        ; final result (root)

Drawn out, the single node n3 (b - c) has two parents (n5 and n8), and the single leaf n4 (a) is referenced by both n5 and n6.

How the DAG detects common subexpressions: while building the DAG, before creating a node for an operation we check whether a node with the same operator and the same (already existing) child nodes already exists; if so, we reuse it instead of creating a new one. Because b - c appears twice and maps to the same node n3, the DAG automatically exposes it as a common subexpression — it can then be computed once into a temporary, eliminating redundant evaluation.

(a) Classification of compiler errors

1. Lexical errors — detected by the scanner; ill-formed tokens. Example: an illegal character or a misspelled token, e.g. 123abc as an identifier, or an unterminated string.
2. Syntactic (syntax) errors — detected by the parser; the token sequence violates the grammar. Example: missing semicolon or unbalanced parentheses, e.g. a = (b + c; or int x y;.
3. Semantic errors — detected by the semantic analyzer; syntactically valid but meaningless. Example: type mismatch or use of an undeclared variable, e.g. adding an int to a string, or x = y; where y is not declared.

(b) Error-recovery strategies in syntax analysis

Panic-mode recovery: on detecting an error, the parser discards input tokens one at a time until it finds a token belonging to a designated set of synchronizing tokens (such as ;, }, or end), then resumes parsing from there.

• Advantages: simple, never loops infinitely.
• Drawback: may skip a considerable amount of input, possibly missing further errors.

Phrase-level recovery: on encountering an error, the parser performs a local correction on the remaining input — inserting, deleting, or replacing a small number of tokens (e.g. inserting a missing ; or )) so that parsing can continue.

• Advantages: can correct common minor mistakes precisely.
• Drawback: difficult to design correctly and may make a wrong correction that misleads later parsing.

Answer any TWO.

(a) Peephole optimization

Peephole optimization is a simple, local, machine-dependent technique applied to a short sliding window (the peephole) of a few consecutive target/intermediate instructions, replacing them with shorter or faster equivalent instructions. Typical transformations:

• Redundant load/store elimination: remove STORE a; LOAD a pairs.
• Algebraic simplification / strength reduction: x = x * 2 -> x = x + x or shift; remove x = x + 0.
• Constant folding: evaluate constant expressions at compile time.
• Unreachable / dead code elimination within the window.
• Flow-of-control optimization: replace a jump to a jump with a single jump. The pass is repeated until no further improvement is found.

(b) Loop optimization techniques

Loops dominate execution time, so optimizing them is highly profitable:

• Code motion (loop-invariant code motion): move computations whose value is unchanged across iterations to the loop pre-header.
• Strength reduction: replace an expensive operation by a cheaper one, e.g. replace a multiplication i*c updated each iteration by repeated addition.
• Induction-variable elimination: detect related induction variables and remove redundant ones.
• Loop unrolling: replicate the loop body to reduce test/branch overhead.
• Loop fusion/jamming: merge adjacent loops over the same range.

(c) Bootstrapping of a compiler

Bootstrapping is building a compiler for a language by writing (part of) it in the same language it compiles. A small initial compiler for a subset of the language is first written in an existing language (or assembly); this is then used to compile a fuller compiler written in the new language. Using the T-diagram notation, a compiler is described by source language, target language, and implementation language. A self-compiling compiler is improved in stages: compile the new compiler with the old one to produce the next version (this also allows porting the compiler to a new machine by retargeting the back-end and recompiling itself).