LPU GUIDE



Registration No.:__________________

PNR No:: 117181CSE52326

COURSE CODE : CSE415

COURSE TITLE : COMPILER DESIGN

Time Allowed: 01:30 hrs Max.Marks: 40

Read the following instructions carefully before attempting the question paper.

1. This question paper divided into two parts A and B.

2. Part A contains 5 questions of 2 marks each. All questions are compulsory.

3. Part B contains 3 questions of 10 marks each. In each question attempt either question (a) or (b), in case both (a) and (b) questions are attempted for any question then only the first attempted question will be evaluated.

4. Answer all questions in serial order.

5. Do not write or mark anything on the question paper except your registration number at the designated space.

PART A

Q1 a)Explain about Lexical errors? [ 2 Marks ]

Ans. A lexical error is any input that can be rejected by the lexer. This generally results from token recognition falling off the end of the rules you've defined.

b)Differentiate between front end and back end of compiler? [ 2 Marks ]

Front end: Lexical analysis, syntax anaylsis, semantic analysis

Back end: intermediate code generation, code optimization, target code generation

c)What is the role of lexical analyzer in compiler design? [ 2 Marks ]

Ans:

Lexical analysis is the first phase of a compiler. It takes the modified source code from language preprocessors that are written in the form of sentences. The lexical analyzer breaks these syntaxes into a series of tokens, by removing any whitespace or comments in the source code.

d)Define the problem of left recursion in context free grammars. [ 2 Marks ]

Ans. . In terms of context-free grammar, a nonterminal is left-recursive if the leftmost symbol in one of its productions is itself. The problem with left recursion, from a computational linguistics point of view, is that it leads to infinite recursion, 

e)What is handle pruning? Illustrate with example. [ 2 Marks ]

Ans: A rightmost derivation in reverse can be obtained by handle pruning. · i.e., start with a string of terminals w that is to parse. If w is a sentence of the grammar at hand, then w = γn, where γn is the nth right sentential form of some as yet unknown rightmost derivation.

PART B

Q2 a)Explain the working of each phase of the compiler by taking a suitable example. Clearly mention the inputs and outputs of each phase. [ 10 Marks ]

Ans:- The answer should carry explanation of all the phases along with an example explaning the input and output from each phase.

OR

b) (i)Count the total no of unique tokens in the following code:

#include

int main()

{

int a,b,c;

a=6

b=7;

c=a+b;

printf("total %d",c);

return 0;

}

Ans:- The no of tokens in this code are 36. Rest if you have any deviation we can discuss before the start of the evaluation. [ 5 Marks ]

(ii)Explain various compiler construction tools [ 5 Marks ]

Ans:- Parser generator ,scanner generator,syntax directed translation engine,code generator generators,dataflow analysis engines,compiler construction tool kits.

Q3 a)What is the difference between deterministic and non-deterministic grammar.What is left factoring and how it should be removed. Eliminate left factoring from following grammar:

S-> bSSaaS|bSSaSb|bSb|a [ 10 Marks ]

Ans:- a) In formal language theory, deterministic context-free languages (DCFL) are a proper subset of context-free languages. They are the context-free languages that can be accepted by a deterministic pushdown automaton. DCFLs are always unambiguous, meaning that they admit an unambiguous grammar, but any (non-empty) DCFL also admits ambiguous grammars.

Non deterministic In automata theory, a finite state machine is called a deterministic finite automaton (DFA), if

each of its transitions is uniquely determined by its source state and input symbol, and

reading an input symbol is required for each state transition.

A nondeterministic finite automaton (NFA), or nondeterministic finite state machine, does not need to obey these restrictions.

Left factoring :- Left Factoring is a grammar transformation technique. It consists in "factoring out" prefixes which are common to two or more productions.

For example, going from:

A -> α β | α γ

to:

A -> α A'

A' -> β | γ

S->bssaS’|bsb|a

S’->as|sb

s->bsS’’|a

S’’->saS’|b

S’->as|sb

Any deviation please discuss before the start of the evaluation.

OR

b) (i)Consider the following grammar and remove left factoring /left recursion.:

S -> ABC A -> Aa |d B -> Bb | e C -> Cc | f [ 5 Marks ]

A->dA’ A’->aA’|Ɛ B->eB’ B’->bB’| Ɛ C->fC’ C’->cC’| Ɛ

(ii)Consider the context-free grammar:

S --> (L) | a

L --> L , S | S

and the string ((a,a),a,(a)).

Give a leftmost derivation and rightmost derivation for the string. [ 5 Marks ]

[pic]

[pic]

Q4 a)For the following grammar construct the SLR(I) parsing table

N -> V=E

N -> E

E -> V

V -> x

V -> *E [ 10 Marks ]

[pic]

[pic]

[pic]

OR

b) (i)Construct Predictive Parsing table for following grammar and Check whether the given grammar is LL(1) or not?

S->1AB|Epsilon

A->1AC|0C

B->0S

C->1

[ 5 Marks ]

[pic]

(ii)For the following grammar construct LR(o) prasing table:

E->E+E

E->E*E

E->(E)

E->id

and input string is id+ id * id, accept it using the constructed parse table. [ 5 Marks ]

[pic]

-- End of Question Paper --

................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download