CSC376 · TU past paper

Compiler Design and Construction 2075 question paper

The complete TU 2075 exam paper for Compiler Design and Construction (CSC376), all 10 questions with solved model answers written to the mark scheme.

Past Papers2081.1 2081 2080 2078 2076 2075

Tap a question to open its answer.

16 marksBasic concepts related to Compiler such asHideAnswer
Difference between compiler and interpreter. "Symbol table is necessary component of compiler". Justify this statement with examples.[6]
--- Basis Compiler Interpreter --------- Translation Translates the entire source program at once into machine code Translates and executes the source program line by line Speed Faster execution after compilation Slower execution due to ...
26 marksNumericalFinite Automata relevant to compiler constHideAnswer
List out the major tasks carried out in Lexical Analysis Phase. Convert the following NFA to DFA.[6]
Part 1: Conceptual question - list major tasks of the lexical analysis phase. Part 2: "Convert the following NFA to DFA." - Missing data: The actual NFA (state transition diagram or table) is not present in the question text provided. No...
36 marksNumericalTop-down parsingHideAnswer
Differentiate between recursive descent and non-recursive predictive parsing method. Find first and follow of all the non-terminals in the following grammar.E→TA;A→+TA∣ε;T→FB;B→∗FB∣ε;F→(E)∣idE \rightarrow TA; A \rightarrow +TA|\varepsilon; T \rightarrow FB; B \rightarrow *FB|\varepsilon; F \rightarrow (E)|idE→TA;A→+TA∣ε;T→FB;B→∗FB∣ε;F→(E)∣id[6]
Grammar: $E \rightarrow TA$ $A \rightarrow +TA \mid \varepsilon$ $T \rightarrow FB$ $B \rightarrow FB \mid \varepsilon$ $F \rightarrow (E) \mid \text{id}$ Non-terminals: $E, A, T, B, F$ . Terminals: $+, , (, ), \text{id}$ . --- B...
Grammar: $$E \rightarrow TA$$ $$A \rightarrow +TA \mid \varepsilon$$ $$T \rightarrow FB$$ $$B \rightarrow FB \mid \varepsilon$$ $$F \rightarrow (E) \mid \text{id}$$ Non-terminals: $E, A, T, B, F$. Terminals: $+, , (, ), \text{id}$. --- B...
46 marksNumericalLR parsingHideAnswer
Construct SLR parse table for the following grammarS→ES \rightarrow ES→EE→E+T∣TE \rightarrow E+T|TE→E+T∣TT→T∗F∣FT \rightarrow T*F|FT→T∗F∣FF→idF \rightarrow idF→id[6]
Grammar: - $S \rightarrow E$ - $E \rightarrow E + T \mid T$ - $T \rightarrow T F \mid F$ - $F \rightarrow id$ Terminals: $\{+, , id\}$ , plus endmarker $\$$ Non-terminals: $\{S, E, T, F\}$ $
Grammar: - $S \rightarrow E$ - $E \rightarrow E + T \mid T$ - $T \rightarrow T F \mid F$ - $F \rightarrow id$ Terminals: ${+, , id}$, plus endmarker $$$ $$ Non-terminals: ${S, E, T, F}$ $
56 marksNumericalAnnotated Parse TreeHideAnswer
Syntax Directed Definition and Annotated Parse Tree
A Syntax-Directed Definition (SDD) is a context-free grammar in which each grammar symbol is associated with a set of attributes, and each production is associated with a set of semantic rules for computing the values of those attributes...
66 marksType Checking and ConversionHideAnswer
Differentiate between static and dynamic type checking. How can we carry out type checking for the following expression using syntax-directed definition?

$S \rightarrow id = E$

$S \rightarrow \text{if } E \text{ then } S1$

$S \rightarrow \text{while } E \text{ do } S1$

$S \rightarrow S1; S2$

[6]
Differentiate between static and dynamic type checking. How can we carry out type checking for the following expression using syntax-directed definition?

$S \rightarrow id = E$

$S \rightarrow \text{if } E \text{ then } S1$

$S \rightarrow \text{while } E \text{ do } S1$

$S \rightarrow S1; S2$

[6]
--- Type checking is the process of verifying that each operation in a program receives the correct number and type of operands. Feature Static Type Checking Dynamic Type Checking --------- When performed At compile time At run time Spee...

76 marksNumericalThree-address codeAnswer

Define three address codes. write three address codes for S = do m = n + p while a <= b [6]

Three Address Code

Definition (Step 1 - Extract)

Given data (from the question):

Statement to translate: S = do m = n + p while a <= b
Structure: a do ... while loop with body m = n + p and condition a <= b.

No numeric matrices or values are involved; this is a compiler-design (intermediate code generation) problem.

Step 2 - Solve

Definition of Three Address Code

Three Address Code (TAC) is an intermediate code representation in which each instruction contains at most three addresses -- normally two operands and one result. The general form is:

$x = y \; op \; z$

where:

$x, y, z$ are names, constants, or compiler-generated temporaries,
$op$ is an operator (arithmetic, logical, relational, etc.).

It is called three address code because each statement references at most three "addresses." Complex expressions are broken into a sequence of such simple instructions using temporaries. TAC can be implemented using quadruples, triples, or indirect triples.

Common statement forms:

Assignment: x = y op z, x = op y, x = y
Unconditional jump: goto L
Conditional jump: if x relop y goto L
Labels: L:

Translating: `S = do m = n + p while a <= b`

This is a do-while loop:

Body: m = n + p (executed at least once)
Condition: a <= b (checked after each iteration; if true, repeat)

The body executes first, then the condition is tested. If the condition holds, control loops back to the beginning of the body.

Generated Three Address Code

Line	Instruction	Meaning
1	`L1:`	Start of loop body (control always enters here first)
2	`t1 = n + p`	Evaluate `n + p` into temporary `t1`
3	`m = t1`	Assign result to `m`
4	`if a <= b goto L1`	Test condition; if true, repeat the body
5	`L2:`	Exit point of the loop

In pure sequential form:

L1:  t1 = n + p
     m  = t1
     if a <= b goto L1
L2:  ...

Explanation

L1: marks the beginning of the body. Since it is a do-while, the body must run at least once, so control enters L1 unconditionally.
t1 = n + p uses a new temporary t1 = newtemp() to store the arithmetic result (three-address form: one operator, two operands, one result).
m = t1 completes the assignment m = n + p.
if a <= b goto L1 evaluates the relational condition. If true, jump back to L1 and repeat; if false, fall through.
L2: is the loop-exit label, where execution continues after the loop.

Quadruple Representation (optional supporting form)

#	op	arg1	arg2	result
(1)	+	n	p	t1
(2)	=	t1	-	m
(3)	if<=	a	b	L1

This confirms each instruction uses at most three addresses.

Three Address Code

Definition (Step 1 - Extract)

Given data (from the question):

Statement to translate: S = do m = n + p while a <= b
Structure: a do ... while loop with body m = n + p and condition a <= b.

No numeric matrices or values are involved; this is a compiler-design (intermediate code generation) problem.

Step 2 - Solve

Definition of Three Address Code

Three Address Code (TAC) is an intermediate code representation in which each instruction contains at most three addresses -- normally two operands and one result. The general form is:

$$x = y ; op ; z$$

where:

$x, y, z$ are names, constants, or compiler-generated temporaries,
$op$ is an operator (arithmetic, logical, relational, etc.).

Common statement forms:

Assignment: x = y op z, x = op y, x = y
Unconditional jump: goto L
Conditional jump: if x relop y goto L
Labels: L:

Translating: `S = do m = n + p while a <= b`

This is a do-while loop:

Body: m = n + p (executed at least once)
Condition: a <= b (checked after each iteration; if true, repeat)

The body executes first, then the condition is tested. If the condition holds, control loops back to the beginning of the body.

Generated Three Address Code

Line	Instruction	Meaning
1	`L1:`	Start of loop body (control always enters here first)
2	`t1 = n + p`	Evaluate `n + p` into temporary `t1`
3	`m = t1`	Assign result to `m`
4	`if a <= b goto L1`	Test condition; if true, repeat the body
5	`L2:`	Exit point of the loop

In pure sequential form:

L1:  t1 = n + p
     m  = t1
     if a <= b goto L1
L2:  ...

Explanation

L1: marks the beginning of the body. Since it is a do-while, the body must run at least once, so control enters L1 unconditionally.
t1 = n + p uses a new temporary t1 = newtemp() to store the arithmetic result (three-address form: one operator, two operands, one result).
m = t1 completes the assignment m = n + p.
if a <= b goto L1 evaluates the relational condition. If true, jump back to L1 and repeat; if false, fall through.
L2: is the loop-exit label, where execution continues after the loop.

Quadruple Representation (optional supporting form)

#	op	arg1	arg2	result
(1)	+	n	p	t1
(2)	=	t1	-	m
(3)	if<=	a	b	L1

This confirms each instruction uses at most three addresses.

86 marksCode OptimizationHideAnswer
Define code optimization. Discuss about any three code optimization techniques with example.[6]
Code optimization is the process of improving the intermediate code so that the output program runs faster and takes less memory space. It removes unnecessary lines of code and rearranges the sequence of statements to speed up program ex...
96 marksRun-time storage managementHideAnswer
What is activation record? Discuss the different activities performed by caller and callee during procedure call and return.[6]
An activation record is a block of memory used for managing information needed by a single execution of a procedure. It is also called a stack frame. Each time a procedure is called, a new activation record is pushed onto the runtime sta...
106 marksCode GeneratorHideAnswer
Discuss about the different factors affecting target code generation.[6]
Target code generation is the final phase of compilation that translates optimized intermediate code into target machine code. Several important factors influence this process. --- The input to the code generator is the optimized interme...

Keep going

Important questions + predictions

Full syllabus Flashcards and practice

Other papers

2081.1 paper 2081 paper 2080 paper 2078 paper 2076 paper

Compiler Design and Construction 2075 question paper

Three Address Code

Definition (Step 1 - Extract)

Step 2 - Solve

Definition of Three Address Code

Translating: S = do m = n + p while a <= b

Generated Three Address Code

Explanation

Quadruple Representation (optional supporting form)

Three Address Code

Definition (Step 1 - Extract)

Step 2 - Solve

Definition of Three Address Code

Translating: S = do m = n + p while a <= b

Generated Three Address Code

Explanation

Quadruple Representation (optional supporting form)

Three Address Code

Definition (Step 1 - Extract)

Step 2 - Solve

Definition of Three Address Code

Translating: S = do m = n + p while a <= b

Generated Three Address Code

Explanation

Quadruple Representation (optional supporting form)

Translating: `S = do m = n + p while a <= b`

Translating: `S = do m = n + p while a <= b`

Translating: `S = do m = n + p while a <= b`