ASSESSMENT TEST – II

ACADEMIC YEAR 2025-2026 (EVEN SEMESTER) – APR / MAY 2026

Second Year / Fourth Semester
DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING
CS24403 –AUTOMATA THEORY AND COMPILER DESIGN (Regulations 2024)
ANSWER KEY
SET B

Q. No. Answer ALL Questions CO PO BL

PART – A (7 × 2 = 14 Marks)

1 What are the functions of preprocessors? CO3 PO2 2

A preprocessor processes source code before the main compilation. Its functions are:
1. Macro processing — expands macros defined with #define.
2. File inclusion — inserts content of header files via #include.
3. Rational preprocessor — extends older language features (e.g., adds structs to older C).
4. Language extension — supports conditional compilation (#ifdef, #ifndef, #endif).
5. Stripping comments — removes all comments from the source.

2 Define a symbol table CO3 PO1 2

A symbol table is a data structure maintained by the compiler to store information about every
identifier (variable, function, class, etc.) in the source program.
It stores: identifier name, data type, scope, memory location, size, and parameter info for
functions.
Operations: insert (when declared), lookup (when referenced), update (when type info is
added).
Used across all phases — from lexical analysis to code generation.

3 What is an ambiguous grammar? CO3 PO2 2

A CFG is ambiguous if there exists at least one string in the language that has more than one
parse tree (equivalently, more than one leftmost or rightmost derivation).

Example: E → E+E | E*E | id is ambiguous — the string id+id*id has two parse trees
depending on whether + or * is applied first.
 Ambiguity is a property of the grammar, not the language. It can be eliminated by rewriting the
grammar to enforce precedence and associativity.

4 What is a predictive parser? CO4 PO2 2

A predictive parser is a top-down parser that determines which production to apply by looking
at the current input token (lookahead) without backtracking.
• It works on LL(1) grammars — no left recursion, no ambiguity, no common prefixes.
• Uses a parsing table (rows = non-terminals, columns = terminals) built from FIRST and
FOLLOW sets.
• Maintains a stack and replaces top non-terminal based on table entry for current input.
• Also called LL(1) parser or non-recursive predictive parser.

5 What are the notations used to represent an intermediate languages? CO4 PO1 1

Intermediate code is represented using:

1. Three-address code (TAC) — each instruction has at most 3 operands: x = y op z
2. Syntax trees / DAGs — tree or directed acyclic graph representing expressions
3. Postfix notation — operators follow operands (reverse Polish notation)
4. Quadruples — 4-field tuples: (operator, arg1, arg2, result)
5. Triples — 3-field: (operator, arg1, arg2); result is implicit by statement number
6. Indirect triples — a list of pointers to triples, allowing reordering

6 Give the ways of representing three address statements. CO4 PO2 2

Three-address statements are represented in three ways:

1. Quadruples — 4 fields: (op, arg1, arg2, result)
Example for a = b + c * d:
(*, c, d, t1) (+, b, t1, t2) (=, t2, _, a)
2. Triples — 3 fields: (op, arg1, arg2); result referenced by index
(0)(*, c, d) (1)(+, b, (0)) (2)(=, a, (1))
3. Indirect triples — a separate statement list of pointers into a triples table; enables easy
reordering for optimisation without renumbering.

7 Draw a annotated parse tree diagram for the input string 3*5+4$. CO4 PO2 2

Grammar assumed: E→E+T | T, T→T*F | F, F→digit

The string is 3*5+4. Parse tree with synthesised attribute .val:
 PART – B (2 × 13 = 26 Marks)

Illustrate the compiler internal representation of the changes in the

source program, as translation progresses by considering the
8a CO3 PO2 2
translation of the statement A:=B+C*50.

The compiler transforms the statement through each phase. Here's the progression:
1. Source program (input):
A := B + C * 50

2. Lexical analysis → Token stream:

<id,A> <:=> <id,B> <+> <id,C> <*> <num,50>

3. Syntax analysis → Parse tree:

assign → id(A) := expr → expr(B) + expr → expr(C) * factor(50)

4. Semantic analysis → Annotated tree:

Type checking: if C is int and 50 is int → C*50 is int; B+result is int; A = int ✓

5. Intermediate code generation → Three-address code:

t1 = inttoreal(50) (if type promotion needed)
t2 = C * t1
t3 = B + t2
A = t3

6. Code optimization:
t1 = C * 50
A = B + t1
(temp folded, constant not converted if same type)

7. Target code (assembly-like):

MOV R2, C
MUL R2, 50
 MOV R1, B
ADD R1, R2
MOV A, R1
For full marks, draw the parse/syntax tree diagram for A := B + C * 50 showing operator
precedence (*, then +, then :=).

OR

Implement LALR parsing for the Grammar S-> AA

A->aA A->d
8 b and give the LALR parsing table. CO3 PO2 3

Step 1 — Augment grammar:

(0) S' → S (1) S → AA (2) A → aA (3) A → d

Step 2 — LR(1) items → merge same core for LALR:

States after closure and GOTO (merged):

State Items

I₀ S'→·S, S→·AA, A→·aA, A→·d

I₁ S'→S·

I₂ S→A·A, A→·aA, A→·d

I₃ A→a·A, A→·aA, A→·d

I₄ A→d·

I₅ S→AA·

I₆ A→aA·

LALR Parsing Table:

State a d $ S A

0 s3 s4 1 2

1 acc
 2 s3 s4 5

3 s3 s4 6

4 r3 r3 r3

5 r1

6 r2 r2 r2

s = shift, r = reduce (by rule number), acc = accept. LALR merges states with same LR(0) core
— here I₃ and the second A→·aA,A→·d state are merged. No conflicts → grammar is
LALR(1).

What is syntax directed translation? How it is used for translation of

expressions?
9a CO4 PO1 2

Syntax Directed Translation (SDT) is a method that associates semantic rules or actions with
grammar productions to perform translation during parsing.
Two types:
• S-attributed SDT — uses only synthesised attributes (computed bottom-up from children to
parent). Compatible with LR parsing.
• L-attributed SDT — uses both synthesised and inherited attributes (passed top-down).
Compatible with LL parsing.

Syntax Directed Definition (SDD) for expression translation:

Production Semantic rule

E → E₁ + T [Link] = E₁.val + [Link]

E→T [Link] = [Link]

T → T₁ * F [Link] = T₁.val * [Link]

T→F [Link] = [Link]

F→(E) [Link] = [Link]

F → digit [Link] = [Link]

Three-address code generation SDD:

Production Translation action

 E → E₁ + T [Link] = newtemp(); emit([Link] '=' E₁.place '+' [Link])

T → T₁ * F [Link] = newtemp(); emit([Link] '=' T₁.place '*' [Link])

F → id [Link] = [Link]

For 13 marks: explain S-attributed vs L-attributed, write the full SDD table, show an example
evaluation tree (e.g. for a+b*c), and show the generated 3-address code.

OR

For the given Grammar S->(L)

S->a
L->L,S
L->S. CO4 PO1 3
Construct predictive parsing table for the grammar.
9b

Step 1 — Eliminate left recursion from L→L,S|S:

L → S L'
L' → ,S L' | ε

Revised grammar:
S → (L) | a
L → S L'
L' → ,SL' | ε

Step 2 — FIRST sets:

FIRST(S) = { (, a }
FIRST(L) = FIRST(S) = { (, a }
FIRST(L') = { , , ε }

Step 3 — FOLLOW sets:

FOLLOW(S) = { $, ,, ) }
FOLLOW(L) = { ) }
FOLLOW(L') = FOLLOW(L) = { ) }

Step 4 — Predictive Parsing Table M[A, a]:

Non-term ( ) a , $

S S→(L) S→a

L L→SL' L→SL'
 L' L'→ε L'→,SL' L'→ε

Blank entries = error. L'→ε is placed in FOLLOW(L') = {)}. The grammar is LL(1) after left-
recursion elimination — no cell has more than one entry.

PART – C (1 × 10 = 10 Marks)

State about FIRST AND FOLLOW and

10 a E->E+T E->T CO3 PO1 3
T->T*F

Step 1 — Eliminate left recursion:

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

Step 2 — FIRST sets:

FIRST(F) = { (, id }
FIRST(T') = { *, ε }
FIRST(T) = FIRST(F) = { (, id }
FIRST(E') = { +, ε }
FIRST(E) = FIRST(T) = { (, id }

Step 3 — FOLLOW sets:

FOLLOW(E) = { $, ) } ($ from start; ) from F→(E))

FOLLOW(T) = FIRST(E')\{ε} ∪ FOLLOW(E') = { +, $, ) }

FOLLOW(E') = FOLLOW(E) = { $, ) }

FOLLOW(F) = FIRST(T')\{ε} ∪ FOLLOW(T') = { *, +, $, ) }

FOLLOW(T') = FOLLOW(T) = { +, $, ) }

Step 4 — Predictive Parsing Table:

Non-term id + * ( ) $
E E→TE' E→TE'
E' E'→+TE' E'→ε E'→ε
T T→FT' T→FT'
T' T'→ε T'→*FT' T'→ε T'→ε
F F→id F→(E)
 This is a standard result — memorise it. ε-productions go into FOLLOW sets. No cell conflict
confirms this is LL(1) after transformation.

COURSE OUTCOMES:
Upon successful completion of this course, students will be able to:
CO1: Construct automata theory using Finite Automata and Regular Expressions
CO2: Design context free grammar, Pushdown Automata and Turing Machine
CO3: Utilize the knowledge of patterns and tokens for developing a Lexical and Syntax
analyzer.
CO4: Understand semantics rules (SDT) Schemes to map syntactic structures to semantic
actions.
CO5: Implement code generation and apply code optimization techniques

COURSE COORDINATOR FACULTY INCHARGE HOD