Sample Paper

FINAL-TERM EXAMINATION
Spring/Fall 2023
CS606 – Compiler Construction

Time: 90 min
Marks: 60
Section A: Objective Part

[40 sample MCQs each of Mark (01) –

You need to attempt any 33 questions from these]

Question No: 1 (Marks: 01) - Please choose the correct option.

The basic purpose of a compiler is to convert a/an _____________ language code into a low-level
machine code.
1. high-level
2. medium-level
3. low-level
4. bottom-level

Question No: 2 (Marks: 01) - Please choose the correct option.

An interpreter translates code line by line, while a/an _____________ translates all code at
once.
1. linker
2. loader
3. compiler
4. debugger

Question No: 3 (Marks: 01) - Please choose the correct option.

A two-pass compiler consists of a front-end and a/an ____________.

1. forward-end
2. next-end
3. middle-end
 4. back-end

Question No: 4 (Marks: 01) - Please choose the correct option.

A three-pass compiler consists of a front-end, a/an ____________ and a back-end.

1. forward-end
2. next-end
3. middle-end
4. back-end

Question No: 5 (Marks: 01) - Please choose the correct option.

What is the output of a scanner?

1. IR
2. Binary
3. Tokens
4. Parse Tree

Question No: 6 (Marks: 01) - Please choose the correct option.

The following statement contains ____________ tokens.

int x = 10 ;
1. three
2. four
3. five
4. six

Question No: 7 (Marks: 01) - Please choose the correct option.

Which of the following phase of the compiler is called Lexical Analyzer?

1. Scanner
2. Parser
3. Optimizer
4. Scheduler
Question No: 8 (Marks: 01) - Please choose the correct option.

Which part of a compiler can detect "missing semicolon" in source code?

1. Scanner
2. Parser
3. Register
4. Scheduler

Question No: 9 (Marks: 01) - Please choose the correct option.

In a compiler, a parser takes tokens as input and generates ____________ as output.

1. source code
2. machine code
3. binary code
4. IR code

Question No: 10 (Marks: 01) - Please choose the correct option.

What is the meaning of following regular expression?

R | S
1. Either R or S
2. Both R and S
3. Only R, not S
4. Not R, only S

Question No: 11 (Marks: 01) - Please choose the correct option.

The regular expression that allows all lower-case alphabets is ____________.

1. [a.z]
2. [a-z]
3. [a+z]
4. [a,z]

Question No: 12 (Marks: 01) - Please choose the correct option.

An FA can be encoded as a table, which is called a/an ____________ table.
1. truth
2. symbol
3. transition
4. hash

Question No: 13 (Marks: 01) - Please choose the correct option.

What does DFA stand for?

1. Deterministic Finite Array
2. Deterministic Finite Approach
3. Deterministic Finite Algorithm
4. Deterministic Finite Automaton

Question No: 14 (Marks: 01) - Please choose the correct option.

What is the purpose of the final states in a DFA?

1. To debug the execution of the automaton.
2. To sort the strings into different categories.
3. To assign a score to each string based on its length.
4. To determine whether a string is accepted or rejected.

Question No: 15 (Marks: 01) - Please choose the correct option.

If a grammar defines ________________________ is considered as an ambiguous grammar.

1. a unique parse tree for every string
2. a unique parse tree for different strings
3. multiple parse trees for the same string
4. multiple parse trees for different strings

Question No: 16 (Marks: 01) - Please choose the correct option.

The flex input file (i.e., specification file) consists of ____________ sections.
1. one
2. two
 3. three
4. four

Question No: 17 (Marks: 01) - Please choose the correct option.

How many tuple/s are there in a typical CFG (i.e., Context Free Grammar)?
1. one
2. two
3. three
4. four

Question No: 18 (Marks: 01) - Please choose the correct option.

In a parse tree, the interior nodes contain ____________.

1. root
2. terminals
3. non-terminals
4. leaves

Question No: 19 (Marks: 01) - Please choose the correct option.

In arithmetic, multiplication has ____________ priority over addition.

1. same
2. lower
3. higher
4. equal

Question No: 20 (Marks: 01) - Please choose the correct option.

The part of a compiler that can detect syntax errors is the ____________.
1. scanner
2. parser
3. register allocation
4. instruction scheduling
Question No: 21 (Marks: 01) - Please choose the correct option.

There are basically two parsing techniques: top-down and ____________.

1. bottom-up
2. bottom-down
3. bottom-next
4. bottom-previous

Question No: 22 (Marks: 01) - Please choose the correct option.

If A → abc, then FIRST (A) = ?

1. $
2. a
3. b
4. c

Question No: 23 (Marks: 01) - Please choose the correct option.

If A → abc, then FOLLOW (A) = ?

1. $
2. a
3. b
4. c

Question No: 24 (Marks: 01) - Please choose the correct option.

A non-recursive predictive parser can be generated by using a/an ____________ and a table.
1. array
2. queue
3. stack
4. tree

Question No: 25 (Marks: 01) - Please choose the correct option.

Bottom-Up parser is also called a/an ____________ parser.

 1. LL(1)
2. Predictive
3. Top-Down
4. Shift-Reduce

Question No: 26 (Marks: 01) - Please choose the correct option.

Left-recursive grammars CAN NOT be handled by ____________ parser.

1. Top-Up
2. Top-Down
3. Bottom-Up
4. Bottom-Down

Question No: 27 (Marks: 01) - Please choose the correct option.

In Bottom-up parser, only ____________ kinds of actions are allowed.

1. two
2. three
3. four
4. five

Question No: 28 (Marks: 01) - Please choose the correct option.

In a parser, a "lookahead" refers to the technique of examining the _______________ symbol(s)

in the input.
1. first
2. previous
3. next
4. last

Question No: 29 (Marks: 01) - Please choose the correct option.

In the context of bottom-up parser, a handle is represented as a pair i.e., _______________.

1. <A → β, k>
2. <k → A, β>
 3. <β → k, A>
4. <A → k, β>

Question No: 30 (Marks: 01) - Please choose the correct option.

Right-most derivation is performed in ____________ parser.

1. LL(1)
2. LR(1)
3. RL(1)
4. RR(1)

Question No: 31 (Marks: 01) - Please choose the correct option.

In bottom-up parser, ____________ table is used to determine the next action to take in the
parsing process, based on the current state and lookahead symbol.
1. RR(1)
2. RL(1)
3. LR(1)
4. LL(1)

Question No: 32 (Marks: 01) - Please choose the correct option.

In bottom-up parsing, the parser stores the DFA state in the ____________ along with the
symbol.
1. tree
2. queue
3. stack
4. table

Question No: 33 (Marks: 01) - Please choose the correct option.

A collection of sets of LR(1) items, where each set represents a single state in the LR(1) parser, is
called a/an ____________.
1. Handle
2. Upper Frontier
 3. Closure Procedure
4. Canonical Collection

Question No: 34 (Marks: 01) - Please choose the correct option.

In LR(1) parsing, the Goto table is basically a ____________ array.

1. one-dimensional
2. two-dimensional
3. three-dimensional
4. four-dimensional

Question No: 35 (Marks: 01) - Please choose the correct option.

An LR parsing table can be constructed by using canonical sets and a/an ____________ function.
1. first
2. goto
3. follow
4. continue

Question No: 36 (Marks: 01) - Please choose the correct option.

What does YACC stand for?

1. Yet Another Compiler Creator
2. Yet Another Compiler Compiler
3. Yet Another Compiler Computer
4. Yet Another Compiler Configuration

Question No: 37 (Marks: 01) - Please choose the correct option.

What is the input to YACC?

1. A binary file
2. A source code file
3. An executable file
4. A specification file
Question No: 38 (Marks: 01) - Please choose the correct option.

The input to the code generation module of a compiler is a/an ____________ code.
1. binary
2. source
3. machine
4. intermediate

Question No: 39 (Marks: 01) - Please choose the correct option.

Register allocation is an important method in ____________ phase of a compiler.

1. Start-end
2. Front-end
3. Middle-end
4. Back-end

Question No: 40 (Marks: 01) - Please choose the correct option.

The general register allocation problem is ____________.

1. P
2. NP
3. NP-hard
4. NP-complete
 Section B: Subjective Part

[06 Short questions of 3 Marks each –

You need to attempt any 04 questions from these]
Question No: 41 (Marks: 03)

List down the three main components of a three-pass compiler.

Question No: 42 (Marks: 03)

Convert the following FA (i.e., Finite Automaton) into a corresponding transition table.

FA:

Transition Table:
a b
0 ? ?
1 ? ?
2 ? ?

Question No: 43 (Marks: 03)

You are required to count "total number of tokens" for the following statements.

Statement No. of tokens

int a ; ?
x = y + z ; ?
cout << "Hello World" ; ?

Question No: 44 (Marks: 03)

A typical CFG (i.e., Context Free Grammar) has four tuples; one is given below, you are required
to list down the remaining three tuples.

1. S (i.e., Start Symbol)

2. ?
3. ?
4. ?

Question No: 45 (Marks: 03)

Consider the following grammar written for a signed binary number.

Number → Sign Bit

Sign → + | –
Bit → 0 | 1

Now, derive the string "–1" by using left most derivation.

Question No: 46 (Marks: 03)

In the context of IR Taxonomy, list down the three main organization categories.
 [04 Descriptive questions of 5 Marks each –
You need to attempt any 03 questions from these]

Question No: 47 (Marks: 05)

Draw a transition graph for an FA (i.e., Finite Automaton) that accepts all binary strings in which
last two bits are 1. i.e., RE = (0|1)*11 and Σ = {0, 1}

Question No: 48 (Marks: 05)

Pseudo code of a subset construction algorithm is given below. You are required to provide the
missing parts (dotted lines represent the missing code).

1. s0’ = ….…….…….
2. S’ = {s0’} (unmarked)
3. while (there is some unmarked state T in S’)
4. mark ….…….…….
5. for all a in Σ do
6. U = ε-closure(….…….…….);
7. if U not already in S’
8. add U as an unmarked state to S’
9. ….…….……. = U;
10. end for
11. end while
12. for each DFA state S
13. if S contains an NFA final state
14. mark S as ….…….…….
15. end algorithm

Note: No need to write complete code again, just write the missing parts in the following format;
1. ….…….…….….…….…….
4. ….…….…….….…….…….
6. ….…….…….….…….…….
9. ….…….…….….…….…….
14. ….…….…….….…….…….

Question No: 49 (Marks: 05)

Consider the following grammar.

S → E E
 E → e E
| f

Now, derive the following sentence by using Shift-Reduce parsing technique.

e f f

You are required to provide solution in the following format.

# Word Stack Handle Action

1 e > none Shift
2
3
4
5
6
7
8 $ S > none Accept

Question No: 50 (Marks: 05)

DAG (i.e., Directed Acyclic Graph) plays a vital role in the context of code optimization. You are
required to draw a DAG which should represent the following basic blocks.

t1 := a + b
t2 := c - d
t3 := t1 x t2
t4 := t1 – t3