West Bengal Institute of Technology (WBIT) 2008-7th Sem B.Tech Computer Science and Engineering Computer Science -Language Processor - Question Paper
C8/B.TECH(C8B)/8BM-7/C8-701 /0S/(0) 3
ENGINEERING & MANAGEMENT EXAMINATIONS, DECEMBER - 2008
LANGUAGE PROCESSOR SEMESTER - 7
y
Time : 3 Hours ] [ Full Marks : 70
GROUP - A (Multiple Cboice Type Questions)
1. Choose the correct alternatives for the following : 10x1 = 10
i) Which data structure is mainly used during shift-reduce parsing ?
a) Stack b) Queue
c) Array d) Pointer. ! -
U) If all productions in a grammar G - ( V, T, S, P ) are of the form A -* xB or A -* x A, B 6 V and x e T*. then it Is called
a) contex-sensitive grammar b) non-linear grammar
. c) right-linear graihmar d) left-linear grammar. L-
HI) The edges in a flow graph whose heads dominate their tails are called
a) Back edges b) Front edges
c) Flow edges d) None of these. -
lv) The regular expression 0* ( 10* )* denotes the same set as
a) (1 *0)* 1 * b) 0 + (0 + 10')*
c) ( 0 + 1 )'* 10 ( 0 + 1 ) * d) none of these. -
v) If Jt is a terminal, then FIRST (x) is
a) e b) {x}
lyres! (a/ian vl) The role of preprocessor is
a) produce output data
b) produce output to compilers
c) produce input to compilers
d) none of these.
vii) Which of the following is not true about dynamic type checking ?
a) 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.
viii) A dangling reference is a
a) pointer pointing to storage which is still in use
l ,
b) pointer pointing to storage which Is freed
c) pointer.pointing to nothing
d) pointer pointing to uninitialized storage.
ix) Which of the following is not k loop optimization ?
a) Loop unrolling
b) Loop jamming
c) Loop heading i
d) Induction variable elimination.
x) If a grammar is LALR (1) then it is necessarily
a) LL ( 1 ) h) SLR ( 1 )
c) LR ( 1 ) d) None of these.
GROUP-B (Short Answer Type Questions )
Answer any three of the following. 3x5 = 15
2. 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 is generated by this grammar ? 2 + 2+1
3. Consider the following left-linear grammar :
S Sab | Aa A Abb | bb Find out an equivalent right-linear grammar.
4. Translate the arithmetic expression a* - ( b + c ) into
a) Syntax tree
b) Three-address code
c) Postfix notation. 2 + 2+1
5. Give the NFA for the following Regular Expression. Then find a DFA for the same language.
(a | b) * abb ' / 2 + 3
6. What is a handle ?
Consider the grammar E-*E + E|E*E|id
Find the handles of the right sentential forms of reduction for the string id + id * id.
1+4
C8/B.T*CH(CB)/8K>l-7/C8-701/0/(0aj 6 i
GROUP-C (Long Answer Type Questions)
Answer any three of the following questions. 3 x 15 = 45
7. Explain the following terms with examples : 3x5
a) Quadruples
b) Triples
c) Indirected triples
ex : a : = -b * ( c + d|b )-( e * f)
8. Design a I?L(1) parsing table for the following grammar :
S-aAcd|BcAe
A -* b | c B Gf | d C -*fe
With the help of the parsing table show how the string "fefcbe" Is parsed. 10 + 5
9. a) Consider the following Grammar :
1) E -> TE
2) E -> + TE | e
3) T-> FT
4) T -> * FT | e
1 ' ' /
5) F -> (E) | id
i) Obtain the FIRST and FOLLOW sets for the above grammar.
ii) Construct a Predictive Parsing table for the above grammar.
b) Explain the predictive Parser's action by describing the moves it would make on an Input id + Id * id$. 10 + 5
10. a) What is Peephole optimization ?
b) What is an activation record ? When and why are those records used ? List different fields of an activation record and state the purpose of those fields.
C) Construct the DAG for the following basic block :
d : = b * c
e : = a + b
b : = b * c
a : = e - d 3 + (2 + 2 + 4) + 4
11. a) What do you understand by terminal table and literal table ?
b) Consider some interblock code optimization without any data-flow analysis by treating each extended bask; block as if it is a basic block. Give algorithms to do the fdllowing optimization 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.
I) Common sub-expression elimination
II) Constant folding
Iii) Copy propagatibn (3 + 3) + (3 + 3 + 3)
12. Write short notes on any three of the following : 3x5
a) Cross compiler
b) Code optimization
c) Left factoring
d) Context free grammar
e) Inherited attributes.
END
|
Attachment: |
| Earning: Approval pending. |
