10

11

12

13

14

15

a)

b)
a)
b)

a)

b)

a)

b)

a)
b)

a)

03000CS304052001

Left factor the following grammar and then obtain LL(1) parsing table
E> T+E|T
T > float | float * T | (E)
What is the relevance of input buffering in lexical analysis?
Write Non-recursive predictive parsing algorithm.
Write regular expressions for the following languages:
i) All strings over the English alphabet that contain the five vowels in order.
ii) All strings of a’s and b’s that do not contain the subsequence abb.

PART C

Answer all questions, each carries 3 marks.

What is handle pruning? Indicate the handles in the reduction of the right
sentential form 5 5+ a * to the start symbol using the grammar below:
S->SS+|SS*la
What are viable prefixes? For the given grammar S > 0 5 110 1 write all the
viable prefixes for the string 00001111
Give the S-attributed SDD of a simple desk calculator and show annotated parse
tree for the expression (3+4)*(5+6).
Write a translation scheme for performing type checking of statements.

PART D

Answer any two full questions, each carries 9 marks.

Construct canonical collection of LR(1) items for the following grammar:
ऽ ~> ‏حم‎
‏م‎ < 408 | 0
Differentiate between S-attributed and L-attributed definitions with suitable
examples.
Write the SDD for a simple type declaration and draw the annotated parse tree
for the declaration float a, b, ௦.
Construct SLR parsing table for the grammar A > a| (A).
Using operator precedence relations, parse the string id + (id * id).
Construct DAG for the expression (a/10 + (b -10))*(a/10 + (b-10)). Also write
the sequence of instructions used for the DAG construction.

PART E

Answer any four full questions, each carries 10 marks.
Using necessary figure, illustrate how the caller and callee cooperate in

Page 2 of 3

(6)

(3)
(5)
(4)

(3)

(3)

(3)

(3)

(5)

(4)

(5)

(4)

(5)
(4)

(6)