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

(a) Role of the Lexical Analyzer [6]

The lexical analyzer (scanner) is the first phase of a compiler. It reads the source program as a stream of characters and groups them into meaningful sequences called lexemes, producing a stream of tokens that is passed to the parser.

Main functions:

• Read input characters and produce tokens.
• Strip out whitespace and comments.
• Correlate error messages with line numbers.
• Expand macros / interact with the symbol table (entering identifiers).

Key terms:

(b) (a|b)*abb — NFA → DFA → Minimized DFA [8]

Thompson NFA (described): The construction yields a start state with an $\varepsilon$-loop subautomaton for (a|b)* followed by a linear path consuming a, b, b. Conceptually a 11-state NFA with $\varepsilon$-transitions.

Subset construction. Using start = $\varepsilon$-closure of the initial state, the relevant DFA states are:

• $A$ = start set (loop)
• $B$ = states reachable after a (still in loop, plus first a of abb)
• $C$ = after seeing prefix ab
• $D$ = after seeing abb (accepting)

DFA transition table:

Start state = $A$; accepting state = $D$.

Minimization. Initial partition: non-accepting $\{A,B,C\}$ and accepting $\{D\}$. Checking transitions, $A$, $B$, $C$ all reach distinct behaviour with respect to reaching $D$ (only $C$ goes to $D$ on b), so they remain distinguishable. The DFA above is already minimal with 4 states $\{A,B,C,D\}$ — this is the classic minimal DFA recognizing strings over $\{a,b\}$ ending in abb.

Augmented grammar adds E' -> E. Productions: E->E+T | T, T->T*F | F, F->(E) | id.

(a) Canonical Collection of LR(0) Items [8]

• I0: E'->.E, E->.E+T, E->.T, T->.T*F, T->.F, F->.(E), F->.id
• I1 = goto(I0,E): E'->E., E->E.+T
• I2 = goto(I0,T): E->T., T->T.*F
• I3 = goto(I0,F): T->F.
• I4 = goto(I0,(): F->(.E), E->.E+T, E->.T, T->.T*F, T->.F, F->.(E), F->.id
• I5 = goto(I0,id): F->id.
• I6 = goto(I1,+): E->E+.T, T->.T*F, T->.F, F->.(E), F->.id
• I7 = goto(I2,*): T->T*.F, F->.(E), F->.id
• I8 = goto(I4,E): F->(E.), E->E.+T
• I9 = goto(I6,T): E->E+T., T->T.*F
• I10 = goto(I7,F): T->T*F.
• I11 = goto(I8,)): F->(E).

(b) SLR(1) Parsing Table & Parse of id * id + id [8]

FOLLOW sets: FOLLOW(E)={+,),$}, FOLLOW(T)={+,*,),$}, FOLLOW(F)={+,*,),$}.

ACTION / GOTO (s=shift, r=reduce by numbered production: 1 E->E+T, 2 E->T, 3 T->T*F, 4 T->F, 5 F->(E), 6 F->id):

Parse of id * id + id $:

The string is accepted.

(a) Machine-dependent vs Machine-independent Optimization [4]

(b) Basic Blocks, CFG and Optimization [8]

Basic block: The code is straight-line with no jumps, so it forms a single basic block B1 (statements 1–8). The CFG is one node B1 with entry → B1 → exit.

Step 1 – Common Sub-expression Elimination. 4 * i is computed in lines 1, 3, 7. Compute once into t1; reuse it:

t1 = 4 * i
t2 = a[t1]
t4 = b[t1]      ; was b[t3], t3 = t1
t5 = t2 + t4
c  = t5
d  = t1         ; was t6 = 4*i = t1

Step 2 – Copy/Dead Code Elimination. t3, t6 are dead (no longer used); c = t5 and d = t1 are kept since c,d are live results. t5 used only once — could be folded but is a result:

t1 = 4 * i
t2 = a[t1]
t4 = b[t1]
c  = t2 + t4
d  = t1

Step 3 – Constant Folding. No constant-only expressions remain to fold here (4 * i has variable i). If i were a known constant, 4*i would be folded; otherwise no change.

Final optimized code:

t1 = 4 * i
t2 = a[t1]
t4 = b[t1]
c  = t2 + t4
d  = t1

Three redundant 4 * i computations are reduced to one; dead temporaries t3, t6 removed.

(a) Synthesized vs Inherited Attributes [5]

• Synthesized attribute: value computed from the attributes of the node's children (and itself). Flows bottom-up. Example: in E -> E1 + T { E.val = E1.val + T.val }, E.val is synthesized.
• Inherited attribute: value computed from attributes of the node's parent and/or siblings. Flows top-down / left-to-right. Example: in a declaration D -> T L, the type flows down via L.in = T.type.

S-attributed definition: an SDD that uses only synthesized attributes. It can always be evaluated bottom-up during LR parsing.

L-attributed definition: an SDD where each inherited attribute of a symbol on the RHS depends only on (i) inherited attributes of the head, and (ii) attributes of symbols to its left. Every S-attributed definition is also L-attributed. L-attributed SDDs can be evaluated in a single left-to-right (e.g., LL / predictive) pass.

(b) SDD generating 3AC for a = b * -c + b * -c [5]

Using attributes E.addr (place holding the value) and E.code, with newtemp() and gen():

t1 = minus c     ; unary minus on c
t2 = b * t1
t3 = minus c
t4 = b * t3
t5 = t2 + t4
a  = t5

Annotated parse tree (described): The tree for a = E has E -> E1 + E2, each Ei -> b * (-c). Bottom-up, each -c synthesizes t1/t3; each b * (-c) synthesizes t2/t4; the + node synthesizes t5; finally the assignment node emits a = t5. Each node's addr attribute holds the temporary name shown above, and code accumulates the generated instructions.

Phases of a Compiler [6]

Block diagram (described): Source program → Lexical Analyzer → Syntax Analyzer → Semantic Analyzer → Intermediate Code Generator → Code Optimizer → Code Generator → Target program. The Symbol Table and Error Handler interact with all phases.

Phases:

1. Lexical Analysis – converts characters to tokens.
2. Syntax Analysis – builds a parse/syntax tree, checks grammar.
3. Semantic Analysis – type checking, scope checking; annotates the tree.
4. Intermediate Code Generation – produces machine-independent code (e.g., 3AC).
5. Code Optimization – improves the intermediate code.
6. Code Generation – emits target machine code.

Output for position = initial + rate * 60

1. Lexical Analyzer (tokens): <id,1> <=> <id,2> <+> <id,3> <*> <num,60> (symbol table: 1=position, 2=initial, 3=rate)

2. Syntax tree:

      =
     / \
 position  +
          /   \
      initial   *
               / \
            rate   60

3. Semantic Analyzer: type check; 60 (int) is converted to float → inttofloat(60).

4. Intermediate code (3AC):

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

5. Optimized code:

t1 = id3 * 60.0
id1 = id2 + t1

6. Target code (assembly):

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

FIRST, FOLLOW and LL(1) Table [6]

Grammar: S->aBDh, B->cC, C->bC | ε, D->EF, E->g | ε, F->f | ε.

FIRST sets:

• FIRST(C) = { b, ε }
• FIRST(B) = { c }
• FIRST(E) = { g, ε }
• FIRST(F) = { f, ε }
• FIRST(D) = FIRST(E) ∪ (FIRST(F) since E→ε) ∪ {ε if both nullable} = { g, f, ε }
• FIRST(S) = { a }

FOLLOW sets:

• FOLLOW(S) = { $ }
• FOLLOW(B): in S->aBDh, follows B = FIRST(Dh) = FIRST(D) (minus ε) ∪ {h} = { g, f, h }
• FOLLOW(C) = FOLLOW(B) = { g, f, h }
• FOLLOW(D): in S->aBDh, FOLLOW(D) = { h }
• FOLLOW(E): in D->EF, FOLLOW(E) = FIRST(F) (minus ε) ∪ FOLLOW(D) = { f, h }
• FOLLOW(F) = FOLLOW(D) = { h }

LL(1) Parsing Table (rows = non-terminals, columns = terminals):

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

Left Recursion [5]

Left recursion occurs when a non-terminal A derives a string beginning with itself, e.g. A -> A α. Problem for top-down parsers: a recursive-descent / predictive parser would call A to expand A again without consuming any input, causing infinite recursion / non-termination.

Eliminating left recursion in A

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

Here α-alternatives (left-recursive) = {c, ad}, β-alternatives (non-left-recursive) = {bd, ε}. Using the rule A -> βA' and A' -> αA' | ε:

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

(A -> A' arises because β includes ε.)

Left factoring S

S -> i E t S | i E t S e S | a

The two alternatives share the common prefix i E t S. Factor it:

S  -> i E t S S' | a
S' -> e S | ε

This removes the common prefix so a predictive parser can decide between alternatives by one token of lookahead (the classic dangling-else resolution: S' -> ε for no else).

Symbol Table Data Structures [5]

A symbol table stores information (name, type, scope, offset, etc.) about identifiers. Common implementations:

• Linear/unordered list: array or linked list of entries.
• Ordered list / sorted array: allows binary search.
• Binary search tree (BST): keeps entries ordered.
• Hash table: key (name) hashed to a bucket; most widely used.

Linear List vs Hash Table

Linear lists are simple and space-efficient but slow for large programs; hash tables give near-constant lookup/insertion and are the standard choice.

Scope in Block-Structured Languages

A block-structured language uses nested scopes. The symbol table is organized as a stack of scopes (chained/nested tables): entering a block pushes a new table; on lookup, the most recent (innermost) scope is searched first, then enclosing scopes (the most-closely-nested rule); leaving a block pops/closes its table so its local names become inaccessible. This naturally implements name hiding by inner declarations.

Representations of Three-Address Code [6]

For a = b * -c + b * -c, the 3AC is:

(0) t1 = minus c
(1) t2 = b * t1
(2) t3 = minus c
(3) t4 = b * t3
(4) t5 = t2 + t4
(5) a  = t5

Quadruples — (op, arg1, arg2, result)

Triples — (op, arg1, arg2); results referenced by position (i)

Indirect Triples — a list of pointers into a triple table

Comparison

• Quadruples: explicit result field → temporaries can be moved/renamed easily; best for optimization and code reorganization, but uses more space.
• Triples: save space (no result field, refer by index), but reordering is hard because positions are referenced directly.
• Indirect triples: keep triples' space saving while allowing reordering (just permute the pointer list) — good compromise for optimizers.

(a) Major Issues in Code Generator Design [3]

1. Input to the code generator – form of the intermediate representation (3AC, trees) and assumption that semantic/type checking is done.
2. Target program / instruction set – choice of target (absolute, relocatable, assembly) and its addressing modes.
3. Instruction selection – choosing efficient machine instructions for IR operations.
4. Register allocation and assignment – deciding which values reside in registers (NP-hard in general).
5. Evaluation order – ordering computations to minimize register usage/spills.

(b) Target Code Generation [3]

For t = a-b, u = a-c, v = t+u, d = v+u with 2 registers R0, R1, using getReg() with register/address descriptors:

MOV  a, R0        ; R0 = a
SUB  b, R0        ; R0 = a - b  (t)
MOV  a, R1        ; R1 = a
SUB  c, R1        ; R1 = a - c  (u)
ADD  R1, R0       ; R0 = t + u  (v)
ADD  R1, R0       ; R0 = v + u  (d)
MOV  R0, d        ; store d

Register/address descriptors: after the first two lines R0 holds t, R1 holds u. v = t+u reuses R0 (t is dead after this) and R0 now holds v; d = v+u adds R1(u) into R0 → d in R0; finally d is stored to memory. Only the live final value d is spilled, minimizing memory traffic.

Ambiguity of E -> E + E | E * E | ( E ) | id [5]

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

Derivation 1 (treats + as topmost — correct precedence): E ⇒ E + E ⇒ id + E ⇒ id + E * E ⇒ id + id * E ⇒ id + id * id Tree: root +, right child is id * id. Means id + (id * id).

Derivation 2 (treats * as topmost — wrong precedence): E ⇒ E * E ⇒ E + E * E ⇒ id + E * E ⇒ id + id * E ⇒ id + id * id Tree: root *, left child is id + id. Means (id + id) * id.

Since two different leftmost derivations / parse trees exist for the same string, the grammar is ambiguous.

Removing Ambiguity

Use precedence (give * higher precedence than +) and associativity (make both left-associative) by introducing levels:

E -> E + T | T      ; + lowest precedence, left associative
T -> T * F | F      ; * higher precedence, left associative
F -> ( E ) | id     ; highest (parentheses / atoms)

This unambiguous grammar forces * to bind tighter than +, so id + id * id parses uniquely as id + (id * id). (Alternatively, a parser generator like YACC can be given explicit %left '+' / %left '*' precedence declarations.)

Loop Optimizations [5]

(a) Loop-Invariant Code Motion

Move computations whose operands do not change inside the loop to outside (before) the loop.

// before
for (i=0; i<n; i++)  x = y + z;  a[i] = x * i;
// after  (y+z is invariant)
x = y + z;
for (i=0; i<n; i++)  a[i] = x * i;

(b) Strength Reduction

Replace an expensive operation with an equivalent cheaper one (e.g., multiplication by repeated addition).

// before: t = 4 * i  computed each iteration
for (i=0; i<n; i++)  t = 4 * i; ...
// after: replace multiply with add
t = 0;                 // = 4*i for i=0
for (i=0; i<n; i++) { ...; t = t + 4; }

(c) Induction Variable Elimination

When several variables move in lockstep (induction variables), keep one and eliminate the others, rewriting tests in terms of the retained variable.

// i and t = 4*i are both induction variables
// before
for (i=0; i<n; i++)  a[4*i] = 0;
// after eliminate i, drive loop by t
for (t=0; t<4*n; t=t+4)  a[t] = 0;

Here the original counter i is eliminated and the loop runs directly on the derived induction variable t.

Comparison of Parsers [5]

Hierarchy of power: LL(1) ⊂ SLR(1) ⊂ LALR(1) ⊂ LR(1). Every SLR(1) grammar is LALR(1), and every LALR(1) is LR(1).

Why LALR(1) is most used (YACC/Bison)

• It accepts almost all practical programming-language grammars (much more powerful than SLR/LL(1)).
• Its table has the same small number of states as SLR, far smaller than canonical LR(1), so it is memory-efficient.
• It is obtained by merging LR(1) item sets with identical cores, giving precise lookahead at low cost.
• The only drawback (occasional reduce-reduce conflicts from merging, and possibly one extra reduction before reporting an error) is rare in practice.

Thus LALR(1) offers the best trade-off between grammar power and table size, which is why YACC/Bison use it.