JNTU III B.Tech Supplimentary Examinations, Aug/Sep 2008
(Computer Science & Engineering)
1. (a) Write a procedure that combines two NFAs in to a single NFA. The operations to be performed are those of concatenation, union and closure.
(b) Write a procedure that detects all extraneous states in a DFA.
2. (a) Eliminate ambiguity if any from the following grammar for boolean expressions.
bexpr ! bexpr or bterm|bterm
bterm ! bterm and bfactor|bfactor
bfactor ! nst factor|(bexpr)|true|false.
where or, and, not (, ), true, false are terminals in the grammar.
(b) Write a recursion discent parser for the above grammar.
3. Construct LALR parse table for the following grammer
S ! L = R
S ! R
L ! _R
L ! id
R ! L
4. (a) What is type expression? Write type expression for the following types.
i. A two dimensional array of integers (i.e. an array of arrays) whose rows are indexed from 0 to 9 and whose columns are indexed from -10 to 10.
ii. Functions whose domains are functions from integers to pointers to integers and whose ranges are records consisting of an integer and a character.
(b) What is type system. Discuss static and dynamic checking of types.
5. (a) What are the advantages and disadvantages of static storage allocation strategy.
(b) What are the advantages and disadvantages of heap storage allocation strategy?
6. (a) Translate the expression -(a+b)*(c+d)+(a+b+c) into quadruple, triple and indirect triple.
(b) Explain in detail the optimization tecnique “Strength Reduction”.
7. (a) Write an algorithm to compute reaching definition informatory for a flow graph.
(b) Explain the working of the above algorithm using a suitable example.
8. (a) How are constants defined in an assembly program? Explain with an example.
(b) What is meant by Assembler directives? Explain the functions of the following