West Bengal Institute of Technology (WBIT) 2009-7th Sem B.Tech Computer Science and Engineering Computer Science -Language Processor - Question Paper
Name : ................................................................a...
Roll No. : ............<................................................... , i - "
Invigilators Signature :...............................................
CS/B.TECH (CSE)/SEM-7/CS-701/2009-10 2009
Time Allotted : 3 Hours Full Marks : 70
The figures in the margin indicate full marks.
Candidates are required to give their answers in their Own words
as far as practicable..
GROUP - A ( Multiple Choice Type Questions )
1. Choose the correct alternatives for the following :
10 x 1 = 10
i) The regular expression ( a | b) * abb denotes
a) all possible combinations of cCs and b's
b) set of all strings ending with abb
c) set of all strings starting with a and ending with abb
d) none of these.
ii) An inherited attributes is the one whose initial value at a parse tree node is defined in terms of
| ||||||||||||
|
t . |
ill) The intersection of a regular language and a context free language is
a) always a regular language
b) always a context free language
c) always a context sensitive language
d) none of these.
iv) If / is a set of valid items for a viable prefix y, then GOTO ( I, X) is a set of items that are valid for the viable prefix :
a) y X b) y
c) prefix of y d) none of these.
v) Shift-reduce parsers are
a) top-down parsers
b) bottom-up parsers
c) may be top-down or bottom-up parsers
d) none of these.
vi) In a programming language, an identifier is permitted to be a letter followed by any number of letters or digits. If L and D denote the set of letters and digits respectively, which of the following expressions defines an identifier ?
a) (LUD)+ b) L.(LUD)*
c) ( L.D ) * d) L. ( L.D ) * .
vii) The following productions of a regular grammar generates a language L.
S-> aS | bS | a | b
The regular egression for L is
a) a + b b) (a + b)*
c) ( a + b ) ( a + b ) * d) ( aa + bb ) a * .
vlli) Which of the following is not a loop optimization ?
a) Induction variable elimination
b) Loop jamming
c) Loop unrolling
d) Loop heading.
ix) Which of the following is not true about dynamic type checking ?
0 It increases the cost of execution
b) Type checking is done during the execution
c) All the type errors are detected
d) None of these.
x) An annotated parse tree is a parse tree
a) with values of only some attributes shown at parse tree nodes
b) with attribute values shown at the parse tree node
c) without attribute values shown at the parse tree nodes
d) with grammar symbols shown at the parse tree nodes.
GROUP -B ( Short Answer Type Questions )
Answer any three of the following. 3x5= 15
2. Convert the non-deterministic FA below to its equivalent DFA.
3. Consider the following lexically nested C code :
int a, b ;
int foo() {int a, c ;}
int bar() {int a, d ;/* HERE * / }
a) How can symbol tables represent the state of each scope at the point marked HERE ? Draw a diagram.
b) What symbols are visible/not visible at point HERE ?
3 + 2
4. Consider the context-free grammar
S -> SS + | SS* | a
a) Show how the string aa + a * can be generated by this grammar.
b) Construct a parse tree for this string.
c) What language does this grammar generate ? Justify your answer. 2+1+2
5. a) How does Lexical Analyzer help In the process of
compilation ? Explain It with an example.
b) Consider the following conditional statement:
If (x> 3 ) then y = 5 else y = 10 ;
From the above statement how many tokens are possible and what are that ? 3 + 2
6. What is look ahead operator ? Give an example. With the help of the look ahead concept show how identifiers can be distinguished from keywords. 1 + 1+3
GROUP- C ( Long Answer Type Questions )
Answer any three of the following. 3 x 15 = 45
Explain the different phases of a compiler, showing the output of each phase, using the example of the following statement:
7. a)
position : = Initial + rate * 60
Compare compiler and interpreter. 10 + 5
b)
8. a) b)
Construct SLR parsing table for the following grammar :
S -> AS | b
A SA | a
What is an operator grammar ? Give an example.
/
12 + 3
9. a) Translate the following expression :
a=b*-c+b*-c
into
1) Quadruples
ii) Triples
iii) Indirect Triples.
b) What are the differences among Quadruples, Triples and Indirect Triples ?
c) Generate machine code for the following instruction :
v = a+ [b*c)-d.
(3+3+3J+3+3
10. sO Construct the DAG for the following basic block :
d
e
b
a
= b * c = a + b = b * c = e - d
b) What is peephole optimization ?
c) Consider some interblock code optimization without any data flow analysis by treating each extended basic block as if it is a basic block. Give algorithms to do the following optimizations within an extended basic block. In each case, indicate what effect on other extended basic blocks a change within one extended basic block can have.
0 Common sub-expression elimination
ii) Constant folding
ill) Copy propagation. 4 + 3 + 8
a) Loop optimization
b) Dependency graph
c) Input buffering
d) YACC
e) Symbol Table
f) L-attributed definitions
g) LEX.
77301 7
|
Attachment: |
| Earning: Approval pending. |
