Reduce-Reduce Conflict and SLR Parsing Table

Part 1: Reduce-Reduce Conflict Example

A reduce-reduce conflict occurs when, in a single LR state, two or more complete items (items with the dot at the far right) call for reduction by different productions, and a lookahead symbol is in the FOLLOW set of more than one of the corresponding left-hand nonterminals. The parser cannot decide which production to reduce by.

Example Grammar:

S -> A
S -> B
A -> c
B -> c

After reading c, the state contains both complete items:

A -> c .
B -> c .

Since both $A$ and $B$ can appear in the same context (via S -> A and S -> B), the FOLLOW sets of $A$ and $B$ overlap (both contain $). On lookahead $, the parser cannot decide whether to reduce A -> c or B -> c. This is a reduce-reduce conflict.

Part 2: SLR Parsing Table

Given Grammar (augmented and numbered):

$$ \begin{aligned} (0)\ & E' \rightarrow E \ (1)\ & E \rightarrow (L) \ (2)\ & E \rightarrow a \ (3)\ & L \rightarrow L, E \ (4)\ & L \rightarrow E \end{aligned} $$

FIRST and FOLLOW Sets

$$\text{FIRST}(E) = \text{FIRST}(L) = {\ (\ ,\ a\ }$$

• $$\text{FOLLOW}(E') = { $ }$$
• $$\text{FOLLOW}(E) = { $,\ ),\ ,\ }$$ (from $E'\to E$: $; from L -> L,E: ,; and E inherits from L -> E where L is followed by ) and ,)
• $\text{FOLLOW}(L) = { ),\ ,\ }$ (from E -> (L): ); from L -> L,E: ,)

Canonical LR(0) Item Sets

I0: E'->.E, E->.(L), E->.a → on E→I1, on ( →I2, on a→I3

I1: E'->E.

I2: E->(.L), L->.L,E, L->.E, E->.(L), E->.a → on L→I4, on E→I5, on ( →I2, on a→I3

I3: E->a.

I4: E->(L.), L->L.,E → on ) →I6, on , →I7

I5: L->E.

I6: E->(L).

I7: L->L,.E, E->.(L), E->.a → on E→I8, on ( →I2, on a→I3

I8: L->L,E.

SLR Parsing Table

Notes:

• Reductions by production (2) E->a and (1) E->(L) appear on FOLLOW(E) = { ), , , $ }.
• Reductions by production (4) L->E and (3) L->L,E appear on FOLLOW(L) = { ), , }.

The table has no multiply-defined entries, so the grammar is SLR(1).

Intermediate Code, DAG vs Syntax Tree, and Quadruple/Triple Representation

Given Data (Extracted)

• Task 1: Significances of intermediate code (conceptual)
• Task 2: Differentiate DAG vs Syntax tree (conceptual)
• Task 3: Expression to represent using quadruple and triple: $$A = B + C - D * E + G$$

Operator precedence assumption: * binds tighter than +/-; + and - are left-associative and equal precedence, evaluated left to right. So the expression parses as: $$A = ((B + C) - (D * E)) + G$$

1. Significances of Intermediate Code (3 marks)

Intermediate code (IC) is a machine-independent representation produced between the analysis (front end) and synthesis (back end) phases of a compiler.

2. Difference Between DAG and Syntax Tree (3 marks)

Example: A + A * B

Syntax Tree (A duplicated):

      +
     / \
    A   *
       / \
      A   B

DAG (A shared):

      +
     / \
    |   *
     \ / \
      A   B

3. Quadruples and Triples for A = B + C - D * E + G (4 marks)

Three-Address Code

$$ \begin{aligned} t_1 &= B + C \ t_2 &= D * E \ t_3 &= t_1 - t_2 \ t_4 &= t_3 + G \ A &= t_4 \end{aligned} $$

Quadruple Representation: (op, arg1, arg2, result)

Triple Representation: (op, arg1, arg2) (result implied by position)

Quadruple vs Triple

Backpatching and RE to DFA Conversion

Part 1: Backpatching (5 marks)

Concept

Backpatching is a technique used during single-pass code generation for handling forward jumps whose target addresses are not yet known when the jump instruction is generated.

When we emit a conditional or unconditional jump, the destination label may still be undefined. Instead of making a second pass, we:

1. Generate the jump with the target field left blank.
2. Keep the instruction number in a list.
3. When the target address becomes known, we go back and fill in all instructions in that list. This "going back to fill in" is backpatching.

Data Structures and Helper Functions

• truelist: jumps taken when a boolean is true.
• falselist: jumps taken when a boolean is false.
• nextlist: unconditional jumps to the statement following the current one.

Example: if (a < b) then x = 1 else x = 2

Code is emitted with blank targets:

Backpatching actions:

• then-part begins at 102 → backpatch(truelist,102) gives 100: if a<b goto 102
• else-part begins at 104 → backpatch(falselist,104) gives 101: goto 104
• exit is 105 → backpatch(nextlist,105) gives 103: goto 105

Final patched code:

100: if a < b goto 102
101: goto 104
102: x = 1
103: goto 105
104: x = 2
105: ...

Backpatching therefore lets the compiler resolve forward addresses in a single pass.

Part 2: Convert a(a + b)a# to DFA (Direct / Syntax-Tree Method)

Step 1: Number the leaves

The augmented expression is $a \cdot (a+b) \cdot a \cdot #$. Numbering symbol positions:

$$a_1 \cdot (a_2 + b_3) \cdot a_4 \cdot #_5$$

Step 2: Syntax tree

              . (root)
             / \
            .    #(5)
           / \
          .    a(4)
         / \
      a(1)   +
            / \
         a(2) b(3)

Step 3: nullable / firstpos / lastpos

No leaf is nullable, so every node here is non-nullable.

Step 4: followpos

Rule for concatenation $c_1 \cdot c_2$: for each $i \in lastpos(c_1)$, $followpos(i) \mathrel{+}= firstpos(c_2)$.

followpos table:

Step 5: Construct the DFA

• Start state $A = firstpos(\text{root}) = {1}$.
• The accepting states are those containing position 5 (the #).

From $A={1}$ (position 1 is a):

• on a: union of followpos of positions in $A$ with symbol a = followpos(1) = {2,3} → state $B={2,3}$.
• on b: none.

From $B={2,3}$ (2 is a, 3 is b):

• on a: followpos(2) = {4} → state $C={4}$.
• on b: followpos(3) = {4} → state $C={4}$.

From $C={4}$ (position 4 is a):

• on a: followpos(4) = {5} → state $D={5}$.
• on b: none.

From $D={5}$ (position 5 is #, contains #, so $D$ is the accepting state):

• followpos(5) = ∅ → no outgoing transitions.

DFA Transition Table

DFA Diagram

        a          a / b          a
 →(A) ------> (B) --------> (C) -------> ((D))

Accepting state: $D={5}$. The DFA accepts strings matching $a(a,|,b)a$, i.e. exactly aaa and aba, before the endmarker #.

Phases of a Compiler

A compiler operates in phases, where each phase takes a program in one representation and produces output in another representation. There are two major phases of compilation:

1. Analysis Phase (Front End)

In the analysis part, an intermediate representation is created from the given source program. It consists of the following phases:

i) Lexical Analysis (Scanning)

• The source program is read left-to-right and grouped into tokens.
• Tokens are sequences of characters with a collective meaning (e.g., constants, operators, reserved words).
• Input: Source program
• Output: Stream of tokens

ii) Syntax Analysis (Parsing)

• The tokens produced by the lexical analyzer are grouped into grammatical phrases using the grammar of the programming language.
• A parse tree or syntax tree is produced to show the hierarchical structure of the token stream.
• Input: Stream of tokens
• Output: Parse tree / Syntax tree

iii) Semantic Analysis

• Checks whether the parse tree follows the rules of the language (e.g., type checking, scope resolution).
• Ensures that the program is semantically correct.
• Input: Parse tree
• Output: Annotated parse tree

iv) Intermediate Code Generation

• An intermediate representation (e.g., three-address code) of the source program is generated.
• This code is easy to produce and easy to translate into target code.
• Input: Annotated parse tree
• Output: Intermediate code

2. Synthesis Phase (Back End)

In the synthesis part, the equivalent target program is created from the intermediate representation. It consists of the following phases:

i) Code Optimization

• Improves the intermediate code so that the output program runs faster and takes less space.
• Removes unnecessary lines of code and rearranges statements to speed up execution.
• Example:

t2 = id3 * 3.0;
id1 = id2 + t2;

ii) Code Generation

• The final phase that translates the optimized intermediate code into target machine code (or assembly code).
• Memory locations are assigned to variables and intermediate results.
• Input: Optimized intermediate code
• Output: Target machine code

Supporting Component: Symbol Table

Throughout all phases, the symbol table is used. It is a data structure that holds information about source-program constructs (identifiers), such as:

• Type
• Position in storage
• Other relevant information

The analysis phase collects information into the symbol table, and the synthesis phase uses it to generate target code.

Summary Diagram

Source Program
      |
  Lexical Analysis       |
      |                  |  Analysis
  Syntax Analysis        |  Phase
      |                  |  (Front End)
  Semantic Analysis      |
      |
  Intermediate Code Gen  |
      |                  |
  Code Optimization      |  Synthesis
      |                  |  Phase
  Code Generation        |  (Back End)
      |
  Target Program

LR(1) Item Sets for S → AA, A → aA | b

Given Data

Grammar:

• $S \rightarrow AA$
• $A \rightarrow aA \mid b$

Definition of Core Item

The core of an LR(1) item $[A \rightarrow \alpha.\beta, a]$ is its first component $A \rightarrow \alpha.\beta$, i.e., the underlying LR(0) item with the look-ahead removed. Two LR(1) item sets have the same core if their sets of LR(0) items (ignoring look-aheads) are identical.

Step 1: Augmented Grammar

$$S' \rightarrow S,\quad S \rightarrow AA,\quad A \rightarrow aA,\quad A \rightarrow b$$

Step 2: FIRST Sets

$$\text{FIRST}(S) = {a,b},\qquad \text{FIRST}(A) = {a,b}$$

Step 3: Canonical Collection

I₀ = Closure([S' → .S, $]):

[S' → .S,  $]
[S  → .AA, $]
[A  → .aA, a/b]
[A  → .b,  a/b]

I₁ = GOTO(I₀, S):

[S' → S., $]      (accept)

I₂ = GOTO(I₀, A):

[S → A.A, $]
[A → .aA, $]
[A → .b,  $]

I₃ = GOTO(I₀, a):

[A → a.A, a/b]
[A → .aA, a/b]
[A → .b,  a/b]

I₄ = GOTO(I₀, b):

[A → b., a/b]     (reduce A → b)

I₅ = GOTO(I₂, A):

[S → AA., $]      (reduce S → AA)

I₆ = GOTO(I₂, a):

[A → a.A, $]
[A → .aA, $]
[A → .b,  $]

I₇ = GOTO(I₂, b):

[A → b., $]       (reduce A → b)

I₈ = GOTO(I₃, A):

[A → aA., a/b]    (reduce A → aA)

• GOTO(I₃, a) = I₃ (same items, self-loop)
• GOTO(I₃, b) = I₄

I₉ = GOTO(I₆, A):

[A → aA., $]      (reduce A → aA)

• GOTO(I₆, a) = I₆ (self-loop)
• GOTO(I₆, b) = I₇

Summary of Transitions

Total: 10 canonical LR(1) item sets (I₀ through I₉).

Note: Unlike LALR, states I₄/I₇ and I₈/I₉ have the same core but different look-aheads, so they remain distinct in the canonical LR(1) collection.

STEP 1 - EXTRACT: Given Data

Part 1: Conceptual question about representing recursion in an activation tree. No numeric data.

Part 2: "Generate the three-address code for the following instruction."

Critical issue: The actual instruction/expression to be translated into three-address code is NOT provided in the question text. The statement ends with "the following instruction:" but no instruction, expression, or code fragment follows.

Therefore, the specific expression required for Part 2 is missing or unreadable, and three-address code cannot be generated for an expression that was not given. An expression such as a = b * c + b * d can only be treated as an illustration, not as the question's data.

I will fully answer Part 1 (conceptual, no data needed) and, for Part 2, explain the method and demonstrate it on a clearly-labelled illustrative example (marked as assumed, since the actual instruction is missing).

STEP 2 - SOLVE

Part 1: Representing Recursion in an Activation Tree

An activation tree shows the flow of control among procedure activations during a program's execution.

Properties:

• Each node = one activation (one call) of a procedure.
• The root = the activation of main.
• Node for P is the parent of node for Q if control flows from P into Q (i.e., P calls Q).
• Left-to-right ordering reflects the temporal order in which activations begin.

Recursion representation: When a procedure calls itself, the activation tree contains several distinct nodes bearing the same procedure name, arranged as a chain (or subtree) descending from the calling node. Each recursive call is a separate activation with its own activation record (own parameters, locals, return address) pushed onto the control stack.

Example: fact(n) computing $n!$

$$ \text{fact}(4) \rightarrow \text{fact}(3) \rightarrow \text{fact}(2) \rightarrow \text{fact}(1) $$

        fact(4)
           |
        fact(3)
           |
        fact(2)
           |
        fact(1)

• Each node is a distinct activation even though the procedure name repeats.
• At any moment, the runtime stack holds exactly the activation records lying on the path from the root to the currently active node.
• On return, fact(1)'s record is popped, control resumes in fact(2), and so on.

Thus recursion = repeated nodes of the same procedure along a root-to-leaf path, each with its own activation record on the stack.

Part 2: Three-Address Code Generation

Missing data: The question says "Generate the three-address code for the following instruction:" but no instruction/expression was supplied in the given text. I cannot produce the intended answer without it. Below I state the method and demonstrate it on an assumed illustrative expression (clearly marked as not from the question).

Method (syntax-directed translation):

• $E \rightarrow id$: E.place = id
• $E \rightarrow E_1 * E_2$: emit t = E1.place * E2.place
• $E \rightarrow E_1 + E_2$: emit t = E1.place + E2.place
• $S \rightarrow id = E$: emit id = E.place

Assumed example (illustrative only): $a = b * c + b * d$

$$ \begin{aligned} t_1 &= b * c \ t_2 &= b * d \ t_3 &= t_1 + t_2 \ a &= t_3 \end{aligned} $$

Quadruple form $(op, arg_1, arg_2, result)$:

Caveat: If the actual exam instruction differs (e.g., x = (a + b) * (c + d) or a control statement), the code must be regenerated from that expression. The above b*c+b*d result is not verifiable because the source instruction was absent from the given question.

Type Expression and Properties of LL(1) Grammar

Part 1: Type Expression (2 marks)

Definition

The type of a language construct is denoted by a type expression. A type expression is either a basic type or is formed by applying an operator called a type constructor to other type expressions. The sets of basic types and constructors depend on the language being type-checked.

Type Constructors Include:

1. Basic Types

   • Primitive types such as int, float, char, bool, etc.
   • A special basic type error is used to signal type errors.

2. Arrays

   • If T is a type expression, then array(I, T) is a type expression denoting an array with elements of type T and index set I.
   • Example: array(0...99, int)

3. Products

   • If T1 and T2 are type expressions, then their Cartesian product T1 x T2 is a type expression.
   • Example: int x int

4. Pointers

   • If T is a type expression, then pointer(T) is a type expression denoting the type "pointer to an object of type T".

5. Functions

   • A function maps a domain type to a range type, expressed as T1 -> T2.

Part 2: Properties of LL(1) Grammar (3 marks)

Definition of LL(1) Grammar

LL(1) grammar is a class of context-free grammar that can be parsed by a non-recursive predictive (top-down) parser using a single lookahead symbol without backtracking. The name LL(1) stands for:

• L - Left to right scanning of input
• L - Leftmost derivation
• 1 - One lookahead symbol

Properties of LL(1) Grammar

A grammar G is said to be LL(1) if and only if the following conditions hold:

1. No Left Recursion

   • The grammar must not contain any left-recursive productions.
   • Example: A production of the form A -> Aα is not allowed in LL(1) grammar.

2. No Ambiguity

   • The grammar must be unambiguous. An ambiguous grammar cannot be LL(1) because it would lead to multiple entries in the parsing table for the same (non-terminal, terminal) pair.

3. Left Factoring

   • For any non-terminal A with two or more productions, the productions must not have a common prefix. If they do, left factoring must be applied.
   • That is, for any two productions A -> α | β, FIRST(α) ∩ FIRST(β) = ∅.

4. FIRST and FOLLOW Condition

   • For each non-terminal A with productions A -> α | β:
     • FIRST(α) ∩ FIRST(β) = ∅
     • If α =>* ε, then FIRST(β) ∩ FOLLOW(A) = ∅
   • This ensures that the parsing table has at most one production per cell M[A, a].

5. Deterministic Parsing Table

   • The LL(1) parsing table M[A, a] must have at most one entry for every non-terminal A and terminal a. Multiple entries indicate grammar conflicts and disqualify the grammar from being LL(1).

6. Single Lookahead is Sufficient

   • Only one input symbol of lookahead is needed at each step to determine the correct production to apply, making parsing efficient and backtrack-free.

Summary: A type expression represents the type of a language construct using basic types and constructors like arrays, products, and functions. LL(1) grammar must be non-left-recursive, unambiguous, left-factored, and must produce a conflict-free parsing table using only one lookahead symbol.