Questions
Syllabus
Qns. By Syllabus

Semester

Subject

Year

Tribhuwan University

Institute of Science and Technology

2080

Bachelor Level / Third Year / Sixth Semester / Science

B.Sc in Computer Science and Information Technology (CSC376)

(Compiler Design and Construction)

Full Marks: 60

Pass Marks: 24

Time: 3 Hours

Candidates are required to give their answers in their own words as for as practicable.

The figures in the margin indicate full marks.

Section A

Long Answers Questions

Attempt any TWO questions.
[2*10=20]
1.
Differentiate between one-pass and multi-pass compiler. Construct the LL(1) parsing table for the following grammar.

$S \rightarrow ABCD$

$A \rightarrow a | \varepsilon$

$B \rightarrow b$

$C \rightarrow 0 | \varepsilon$

$D \rightarrow d | \varepsilon$
[10]
2.
How does Lexical Analyzer recognize a token? Give an example to make it clear. Convert the regular expression $a(a+b)(b+c)^*\, a\#$ to DFA.[10]
3.
Construct the LR(1) parsing table for the following grammar.

$S \rightarrow AaAb$

$A \rightarrow BbBa$

$A \rightarrow \varepsilon$

$B \rightarrow \varepsilon$
[10]
Section B

Short Answers Questions

Attempt any Eight questions.
[8*5=40]
4.
Why code optimization is needed? Describe any two techniques for loop optimization. [5]
5.
What is three-address code? How high level code is converted to three address code? Illustrate with an example. [5]
6.
What is activation tree? Define type checking system with examples. [5]
7.
What are the advantages of intermediate code? What types of information are provided by symbol table? [5]
8.
What is annotated parse tree? Define S-attributed grammar with an example. [5]
9.
Describe about syntax directed translation with an example. [5]
10.
Given the following grammar with SLR parsing table, test whether the string "int * (int + int)" will be accepted or rejected.

$E \rightarrow T + E \ldots (1)$

$E \rightarrow T \ldots (2)$

$T \rightarrow int * T \ldots (3)$

$T \rightarrow int \ldots (4)$

$T \rightarrow (E) \ldots (5)$

$\[\begin{array}{|c|c|c|c|c|c|c||c|c|}\hline & \text{ACTION} & & & & & & \text{GOTO} & \\ \hline \text{STATE} & \text{int} & * & + & ( & ) & \$ & E & T \\ \hline 1 & S5 & & & S4 & & & 2 & 3 \\ \hline 2 & & & & & & \text{ACC} & & \\ \hline 3 & & S6 & & & R2 & R2 & & \\ \hline 4 & S5 & & & S4 & & & 7 & 3 \\ \hline 5 & & S8 & R4 & & R4 & R4 & & \\ \hline 6 & S5 & & & S4 & & & 9 & 3 \\ \hline 7 & & & & & S10 & & & \\ \hline 8 & S5 & & & S4 & & & & 11 \\ \hline 9 & & & & & R1 & R1 & & \\ \hline 10 & & & R5 & & R5 & R5 & & \\ \hline 11 & & & R3 & & R3 & R3 & & \\ \hline \end{array}\]$
[5]
11.
How do you recognize basic block? Discuss about the factors that affect code generator. [5]
12.
Find the FIRST and FOLLOW of all the non terminals in following grammar.

$S \rightarrow aAbcD | \varepsilon$

$A \rightarrow SD | \varepsilon$

$C \rightarrow Sa$

$D \rightarrow aBD | \varepsilon$
[5]