Compiler Course Final Exam Solutions

Group A

Question 1a: CLR(1) Parsing Table Construction

Grammar:

S → Aa | bAc | dc | bda
A → d

Augmented Grammar:

S' → S
S → Aa | bAc | dc | bda
A → d

CLR(1) Items and States:

I₀:

• S' → •S, $
• S → •Aa, $
• S → •bAc, $
• S → •dc, $
• S → •bda, $

I₁: (on S)

• S' → S•, $

I₂: (on A from I₀)

• S → A•a, $

I₃: (on b from I₀)

• S → b•Ac, $
• S → b•da, $
• A → •d, c
• A → •d, a

I₄: (on d from I₀)

• S → d•c, $
• A → d•, c (from I₃)
• A → d•, a (from I₃)

I₅: (on a from I₂)

• S → Aa•, $

I₆: (on A from I₃)

• S → bA•c, $

I₇: (on d from I₃)

• A → d•, c
• A → d•, a
• S → bd•a, $

I₈: (on c from I₄)

• S → dc•, $

I₉: (on c from I₆)

• S → bAc•, $

I₁₀: (on a from I₇)

• S → bda•, $

CLR(1) Parsing Table:

Production Rules:

• r1: S → Aa
• r2: S → bAc
• r3: S → dc
• r4: S → bda
• r5: A → d

Question 1b: LL(1) Grammar Check

Grammar:

A → Q
Q → St | Rr
S → sS | ε
R → qR | ε

Step-by-step analysis:

First Sets:

• FIRST(S) = {s, ε}
• FIRST(R) = {q, ε}
• FIRST(Q) = {s, ε, q, ε} = {s, q, ε}
• FIRST(A) = {s, q, ε}

Follow Sets:

• FOLLOW(A) = {$}
• FOLLOW(Q) = {$}
• FOLLOW(S) = {t}
• FOLLOW(R) = {r}

LL(1) Conditions Check:

For Q → St | Rr:

• FIRST(St) = {s, t} (since ε ∈ FIRST(S))
• FIRST(Rr) = {q, r} (since ε ∈ FIRST(R))
• FIRST(St) ∩ FIRST(Rr) = {s, t} ∩ {q, r} = ∅ ✓

For S → sS | ε:

• FIRST(sS) = {s}
• FIRST(ε) = {ε}
• FIRST(sS) ∩ FIRST(ε) = {s} ∩ {ε} = ∅ ✓
• FIRST(sS) ∩ FOLLOW(S) = {s} ∩ {t} = ∅ ✓

For R → qR | ε:

• FIRST(qR) = {q}
• FIRST(ε) = {ε}
• FIRST(qR) ∩ FIRST(ε) = {q} ∩ {ε} = ∅ ✓
• FIRST(qR) ∩ FOLLOW(R) = {q} ∩ {r} = ∅ ✓

String "qqqr5" generation:

1. A → Q
2. Q → Rr
3. R → qR
4. R → qR
5. R → qR
6. R → ε

Conclusion: Yes, the grammar is LL(1) and "qqqr5" can be generated.

Question 2a: CFG Analysis

Grammar:

X → X + Y | Y
Y → Y d F | F
F → (X) | id

First and Follow Functions:

First Sets:

• FIRST(F) = {(, id}
• FIRST(Y) = {(, id}
• FIRST(X) = {(, id}

Follow Sets:

• FOLLOW(X) = {$, )}
• FOLLOW(Y) = {+, d, $, )}
• FOLLOW(F) = {+, d, $, )}

LL(1) Grammar Check:

For X → X + Y | Y:

• FIRST(X + Y) = {(, id}
• FIRST(Y) = {(, id}
• FIRST(X + Y) ∩ FIRST(Y) = {(, id} ≠ ∅ ✗

Conclusion: This grammar is NOT LL(1) due to left recursion in X → X + Y | Y.

Question 2b: Predictive Parser

Grammar:

E → T E'
E' → + T E' | ε
T → F T'
T' → * F T' | ε
F → (E) | id

Sequence of moves for "id+id*id":

Group B

Question 3a: Synthesized Attributes

Grammar with Semantic Rules:

PRODUCTION | SEMANTIC RULES
1) D → T L | L.in = T.type
2) T → int | T.type = integer
3) T → float | T.type = float
4) L → L₁, id | L₁.in = L.in; addType(id.lexeme, L.in)
5) L → id | addType(id.lexeme, L.in)

Parse Tree for "float id1, id2, id3":

         D
       /   \
      T     L
   (float)  |
          L , id3
         /     |
        L , id2
       /    |
      id1

Dependency Graph:

• T.type flows to L.in
• L.in flows to addType calls for each identifier
• Left-to-right evaluation ensures proper type propagation

Question 3b: Parse Tree vs Syntax Tree vs DAG

Differences:

• Parse Tree: Shows complete derivation with all grammar symbols
• Syntax Tree: Abstract representation, removes unnecessary nodes
• DAG: Directed Acyclic Graph, shares common subexpressions

Question 3c: Left Factoring Algorithm

Algorithm:

1. Identify productions with common prefixes
2. Factor out the common prefix
3. Create new non-terminal for the remaining parts
4. Repeat until no common prefixes exist

Question 4a: Dynamic Storage Allocation

Strategies:

1. Stack Allocation: LIFO, automatic cleanup
2. Heap Allocation: Dynamic, manual management
3. Static Allocation: Fixed at compile time

Question 4b: SDD for Simple Desk Calculator

Grammar with SDD:

E → E + T | E.val = E.val + T.val
E → T     | E.val = T.val
T → T * F | T.val = T.val * F.val
T → F     | T.val = F.val
F → (E)   | F.val = E.val
F → digit | F.val = digit.lexval

Parse Tree for "3*5 + 4n":

        E (19)
       / | \
      E  +  T (4)
     /|\    |
    T * F   F
    |   |   |
    F   5   4
    |
    3

Question 4c: DAG for Basic Block

Basic Block:

a = b + c
b = b - d
c = c + d
d = b + c

DAG Representation:

• Nodes represent operations and variables
• Edges show data dependencies
• Common subexpressions are shared

Question 5a: C Code Analysis

Code:

void productionInt(int a[], int b[])
{
    int prod=0, i=1;
    do {
        prod = prod * a[i]*b[i];
        i++;
    } while(i<=20);
    printf("product=%d", prod);
}

i) Three Address Code:

t1 = 0
t2 = 1
L1: t3 = t2 * 4
    t4 = a[t3]
    t5 = t2 * 4
    t6 = b[t5]
    t7 = t1 * t4
    t8 = t7 * t6
    t1 = t8
    t9 = t2 + 1
    t2 = t9
    if t2 <= 20 goto L1
    print t1

ii) Basic Blocks:

• Block 1: Initialization
• Block 2: Loop body
• Block 3: Loop condition

iii) Flow Graph:

Entry → Block1 → Block2 → Block3
                    ↑        ↓
                    ←────────┘

Question 5b: Basic Block and Flow Graph

Basic Block: Sequence of consecutive statements with:

• One entry point (first statement)
• One exit point (last statement)
• No branching except at the end

Flow Graph: Directed graph showing control flow between basic blocks.

Question 5c: Fill in the Blanks

i) Data type grammar use: synthesized attributes ii) Symbol table is generated in: semantic analysis phase iii) Operator precedence parser is: shift-reduce parser iv) Recursive descent parser can parse: LL(1) grammar

Question 5d: Expression Translation

Expression: a + b * c / e + f * g

i) Quadruple:

(*, b, c, t1)
(/, t1, e, t2)
(+, a, t2, t3)
(*, f, g, t4)
(+, t3, t4, t5)

ii) Triple:

(*, b, c)
(/, (0), e)
(+, a, (1))
(*, f, g)
(+, (2), (3))

iii) Indirect Triple:

Instruction List: [0, 1, 2, 3, 4]
Triple:
(*, b, c)
(/, (0), e)
(+, a, (1))
(*, f, g)
(+, (2), (3))

Question 5e: Peephole Optimization

Definition: Local optimization technique that examines small sequences of instructions and replaces them with shorter or faster sequences.

Characteristics:

• Works on small windows of code
• Performs local improvements
• Can be applied multiple times
• Common optimizations: redundant instruction elimination, strength reduction

Example:

Before: MOV R1, R2
        MOV R2, R1
After:  MOV R1, R2

Question 5f: Code Generator Tasks

Primary Tasks:

1. Instruction Selection: Choose appropriate machine instructions
2. Register Allocation: Assign variables to registers efficiently
3. Instruction Scheduling: Order instructions for optimal performance