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→ABCDS \rightarrow ABCD
A→a∣εA \rightarrow a | \varepsilon
B→bB \rightarrow b
C→0∣εC \rightarrow 0 | \varepsilon
D→d∣εD \rightarrow d | \varepsilon
[10]
2.
How does a 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→AaAbS \rightarrow AaAb
A→BbBaA \rightarrow BbBa
A→εA \rightarrow \varepsilon
B→ε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→T+E…(1)E \rightarrow T + E \ldots (1)
E→T…(2)E \rightarrow T \ldots (2)
T→int∗T…(3)T \rightarrow int * T \ldots (3)
T→int…(4)T \rightarrow int \ldots (4)
T→(E)…(5)T \rightarrow (E) \ldots (5)
ACTIONGOTOSTATEint∗+()$ET1S5S4232ACC3S6R2R24S5S4735S8R4R4R46S5S4937S108S5S4119R1R110R5R5R511R3R3R3\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→aAbcD∣εS \rightarrow aAbcD | \varepsilon
A→SD∣εA \rightarrow SD | \varepsilon
C→SaC \rightarrow Sa
D→aBD∣εD \rightarrow aBD | \varepsilon
[5]