Friday, April 20, 2018

KTU B.Tech S6 Model Questions Compiler Design CS

Model Question Paper

Sixth Semester B.Tech Degree Examination

13.601 : COMPILER DESIGN(FR)

Time: 3 hours Max.Marks:100

PART A
(Answer all questions)

1. Symbol table is necessary for compiler construction. Justify your statement with example.
2. For ∑={a,b}, build a Finite Automata that accepts only those words that do not end with ba.
3. Explain ambiguity in grammars. Consider the grammar

S→aSbS/bSaS/ε
Show that the grammar is ambiguous by constructing two different leftmost derivations for the sentence
abab.
4. Explain the pros and cons of operator precedence parsing.
5. Write the syntax directed translation for “do-while” statement in C.

(5*4=20 marks)

PART B

(Answer any one full question from each module)

MODULE I

6. a) Explain the output for each phase of compiler for the following character streams.
i) T1=T2*3+2*6.3+2*T2, where T1 and T2 are integers
ii) if (a
b) Consider the grammar
S → (L) | a
L → L, S | S
i)What are the terminals, non-terminals and start symbol in the given grammar?
ii)Find parse tree for the following sentences:
i) (a,a)
ii) (a, ((a,a),(a,a))) (4)
c) Explain the concept of compiler writing tools. (4)


OR

7. a) List any four issues in compilation. (4)
b) Consider the context free grammar
S→ SS+|SS*|a
And the strings i) aa+a*
ii)aa+aa+

I) Give the leftmost derivation of the strings
II) Give the rightmost derivation of the strings
III) Give a parse tree for the strings
IV) Is the grammar ambiguous or not? Justify your answer. (8)
c) Explain the front end of a compiler with a neat diagram. Show the output of different phases in front
end for the following input: a[index]=b*2.0 (8)

MODULE II

8. a) Consider a language that consists of a single email address. An email id is a USERNAME followed by
@ character followed by a HOSTNAME. A USERNAME is the combination of one or more alphanumeric
characters and a HOSTNAME is composed of two or more DOMAINS separated by the character dot (.). A
DOMAIN is a sequence of one or more characters.
i) Draw a DFA for this language.
ii) Write a regular expression to recognize the language.
iii) Recast your language as a CFG using the non terminal EMAIL as the start symbol. (12)
b) Write an algorithm for finding the ɛ-closure of all states of a ɛ-NFA. (8)

OR

9. a) Draw a Finite Automata for a language which consists of the following lexemes:
<,<=, ==, >, >=, != ,( , ), +,-,*,/,=,semicolon, identifier and digits. Comments, which begins in /* and end
with a */ and blanks should be ignored by the scanner. (12)
b) Write the algorithm to minimize the number of states in a DFA. Apply this algorithm to
minimize the states of the following DFA: (8)
State Inputs

A B
Start A B C
B B D
C B C
D B E
Accept E B C

MODULE III
10. a)Construct a predictive parsing table for the following grammar.

S→iCtS|iCtSeS|a
C→b

Check whether the grammar is LL(1) or not. Justify your answer. (12)
b) State the error recovery methods in operator precedence parser. (8)

OR
11. a) Construct SLR parsing table for the following grammar

E→E+T|T
T→T*F|F
F→(E)|id (10)
b) Construct the operator precedence parse table for the following grammar and show its action for the
input string ccbab. (10)

S→Aab
A→cA/cb
MODULE IV

12. a)Explain the syntax directed translation scheme for array references (12)
b)Write the three address code for the following statements (8)
while(a
{
if(c
{
x=y+z;
}
else
{
x=y-z;
}
}

OR

13. a) Write quadruples, triples and indirect triples for the expression
-(a+b)*(c+d)-(a+b+c) (8)
b) Explain the concept of backpatching and write the syntax directed translation scheme for Boolean
expressions with and without back patching
(12)
Load disqus comments

0 comments

Follow us on Facebook
Powered by: KTU Online