Uttar Pradesh Technical University (UPTU) 2007 M.C.A Compiler Design--404(1) - Question Paper

(Following Paper ID and Roll No. to be filled in your Answer Book)

Roll No.

M. C. A.

(SEM. IV) EXAMINATION, 2006-07 COMPILER DESIGN

[Total Marks : 100

Note : Attempt all questions

1 Attempt any two of the following parts

10

(a)    What do you understand by single pass and multi pass compiler. Discuss their merits and demerits also.

(b)    Describe the languages denoted by the    10 following regular expressions :

0(011) * o

C(e | 0) | * )*

(0|1)*0(0|1)(0|1) a 10* 10* 10 *

(c)    Following are the sequence of auxiliary    10 definitions :

Aq =a/b Ai = A₀A₀ A₂ = Aj Aj

followed by the pattern A_n

(1)    Describe the set of strings denoted by the pattern (as a function of n)

(2)    If we substitute out all auxiliary definitions in the pattern, how long is the regular expression ?

(3)    If you convert the regular expression from (ii) into on NFA how many states are there ?

2 Attempt any two of the following :

(a)    What do you understand by Boot strapping ? 10 Explain with the help of example.

(b)    Formulate a context free grammar for the 10 language of parenthesized logical expressions consisting of the logical variable b and the

logical operations    | (not) V(or),

a (and) (if then) and o- (if and only if) the priority of the amgmented set of logical operators is given from highest to lowest priority as :

| Highest

A

V

-

<- Lowest

Give a derivation and its associated syntax tree for each of the following sentences :

(2)    | b b v b

(3)    ( \bvb)*+ \(bAb)

(c) Given the grammer :

<number>:: = <integer> | <real number>

<integer>:: = <digit> | <integer> <digit>

<real number>:: = <integer> <integer> |

<integer> <integer> E <scale> factor> | <integer> E <scale factor>

<scale factor> :: <integer> | <sign> <integer> <sign>:: = + | -

<digit> : : = 0 | 1 | 2 | 3....... | 9

where <number> is the starting symbol of the grammer, give left most and right most canonical derivation for the following sentences :

(1) 100

(2)    6E-3

(3)    87.25E+7

3 Attempt any two of the following parts :

(a)    Discuss basic parsing techniques.    10

(b)    Consider the fragment of grammer as    10 Stat if cond then sub stat else stat

| if cond then stat Sub stat if cond then substat else stat show that this grammer fragment is still ambiguous if stat, substat, and cond are given productions that allow them to derive terminal strings.

(c) To generate a small NFA from a regular 10 expression, it is useful to identity, character strings in the syntax analysis of a regular expression. We might therefore wish to inteduce the non terminal S(not the start symbol) standing for "string" as follows :

EE + E\EE\E*\(E)\a\b\E\s S-as\bs\E

(1)    Give ambiguity resolving rules that will cause all maximal length strings of two or more consecutive a's and b's to be parsed as an

(2)    Construct the LALR parser for the grammer with your ambiguity rules.

Attempt any four of the following :

(a)    Discuss the role of syntax directed translation 10 scheme.

(b)    Discuss the role of data flow analysis.

(c)    Discuss important data structures which are 10 used in implementing symbol table.

(d)    What do you understand by left recursion and 10 left factoring ? How these are eliminated ? Explain with the help of example.

(e)    Discus the principal sources of optimization. 10

(f)    Write down algorithm for code generation for three address code.

-1475]    4    [2890]

Attachment: uttar-pradesh-technical-university--uptu--2007-m-c-a--53413-1.pdf

Earning:   Approval pending.