AUTOMATA AND COMPILER DESIGN jntu university previous year question paper foe 3rd year first semester Supplimentary Examinations for IT and CSSE departments

AUTOMATA AND COMPILER DESIGN jntu university previous year question paper foe 3rd year first semester Supplimentary Examinations for IT and CSSE departments

AUTOMATA AND COMPILER DESIGN jntu university previous year question paper foe 3rd year first semester Supplimentary Examinations for IT and CSSE departments

III B.Tech I Semester Supplimentary Examinations, February 2008

AUTOMATA AND COMPILER DESIGN

( Common to Information Technology and Computer Science & Systems

Engineering)

Time: 3 hours Max Marks: 80

Answer any FIVE Questions

All Questions carry equal marks

⋆ ⋆ ⋆ ⋆ ⋆

1. (a) Design a DFA that accepts the language over the alphabet, = {0, 1, 2}
where the decimal equivalent of the language is divisible by 3.
(b) Compare compiler and an interpreter with the help of suitable examples. [8+8]
2. (a) Test whether the following grammar is LL(1) or not.
S ! AaAb |BbBa


A ! 2
B !2
(b) Construct the predictive parse table for the following grammar:
S ! A
A ! aB|Ad
B ! bBC|f
C ! g. [8+8]
3. (a) What is LR parser? Compare and contrast the different types of LR parsers.
(b) Construct the CLR parse table for the following augmented grammar:
A′ ! A
A ! (A) |a [8+8]
4. (a) Compare Inherited attributes and Synthesized attributes with an example.
(b) Construct triples of an expression: a * - (b + c). [8+8]
5. (a) List out various typical semantic errors .Explain the procedure to rectify them?
(b) What is Static Checking? List out some examples of static checks? [8+8]
6. (a) Write a notes on the static storage allocation strategy with example and dis-
cuss its limitations?
(b) Discuss about the stack allocation strategy of runtime environment with an
example? [8+8]
7. Write about the following Algorithms
(a) Detection of Loop Invariant Computation
(b) Code Motion. [8+8]
8. Explain about Generic code generation algorithm? [16]

III B.Tech I Semester Supplimentary Examinations, February 2008

AUTOMATA AND COMPILER DESIGN

( Common to Information Technology and Computer Science & Systems

Engineering)

Time: 3 hours Max Marks: 80

Answer any FIVE Questions

All Questions carry equal marks

⋆ ⋆ ⋆ ⋆ ⋆

1. (a) Obtain the Kleen Closure and Positive Closure of the language {ba, bb}, where
the alphabet = {a, b}.
(b) Give a finite state diagram that accepts all the floating-point numbers. [6+10]
2. (a) What is the time complexity of a parser to parse a string of ‘n’ tokens?
(b) Consider the Grammar: G = ({S, A}, {a, b}, {S ! aAa |bAb| |A, A ! SS}, S)
Find the leftmost derivation, rightmost derivation, and parse tree for the
string: baabbb. [6+10]
3. Construct the collection of non-empty sets of LR(0) items for the following aug-
mented grammar:
S ! E1
E1 ! T3E1 |T1
E2 ! T3E2 |T2
T1 ! a$ |(E2$
T2 ! a) |(E2)
T3 ! a+|(E2+.
[16]
4. Let synthesized attribute, Val give the value of the binary number generated by S
in the following grammar. For example, on input 101.101, S.Val = 5.625.
S ! L • L |L
L ! LB|B
B ! 0 |1
Write synthesized attribute values corresponding to each of the productions to
determine the S.Val. [16]
5. Explain the following:
(a) Type checking of Expressions
(b) Translation scheme for checking the type of statements. [8+8]
6. (a) Explain the concept of implicit deallocation of memory.
(b) Give an example of creating dangling references and explain how garbage is
created. [8+8]
7. Explain about Data-Flow analysis of structured flow graphs. [16]
1 of 2
Code No: R05311201 Set No. 2
8. What are legal evolution orders and names for the values at the nodes for the DAG
for following?
d := b + c
e := a + b
b := b * c
a := e - d. [16]
⋆ ⋆ ⋆ ⋆ ⋆


AUTOMATA AND COMPILER DESIGN
( Common to Information Technology and Computer Science & Systems
Engineering)
Time: 3 hours Max Marks: 80
Answer any FIVE Questions
All Questions carry equal marks
⋆ ⋆ ⋆ ⋆ ⋆
1. (a) Explain Regular Expressions with suitable examples.
(b) Design a DFA that accepts the language over = {a, b} of all strings that
contain the sub-string either aa or bb. [6+10]
2. (a) Write a procedure to combine two NFA?s into a single NFA. The operations
to be performed are those of concatenation, union and closure.
(b) Obtain the Non-deterministic Finite Automaton (NFA) corresponds to the
Grammar,
G = ({S, X, Y}, {a, b}, P, S), where P is defined as follows:
P ! aS |bS| bX
X ! bY |b
Y ! aY |bY| a |b. [8+8]
3. (a) What is meant by a parser generator? Illustrate with examples using YACC.
(b) How are ambiguities resolved in YACC? [10+6]
4. Generate the three-address code for the following ?C? program fragment: [16]
while(a > b)
{
if (c < d) x = y + z;
else x = y - z;
}
5. (a) What is Type Expression? Write type Expressions for the following type
i. A Two dimensional array integers (i.e. an array of arrays) whose rows are
indexed from 0 to 9 and whose columns are indexed from -10 to 10.
(b) What is Type System? Discuss static and dynamic Checking of types? [8+8]
6. (a) Write a notes on the static storage allocation strategy with example and dis-
cuss its limitations?
(b) Discuss about the stack allocation strategy of runtime environment with an
example? [8+8]
7. Explain the following
(a) Copy Propagation
(b) Dead-Code Elimination
1 of 2
Code No: R05311201 Set No. 3
(c) Code Motion
(d) Reduction in Strength. [4×4]
8. Construct DAG for the following basic block:
d: = b+c
e: = a+b
b: =b*c
a: = e-d. [16]

III B.Tech I Semester Supplimentary Examinations, February 2008

AUTOMATA AND COMPILER DESIGN

( Common to Information Technology and Computer Science & Systems

Engineering)

Time: 3 hours Max Marks: 80

Answer any FIVE Questions

All Questions carry equal marks

⋆ ⋆ ⋆ ⋆ ⋆

1. (a) Design a DFA that accepts the language over the alphabet, = {0, 1, 2}
where the decimal equivalent of the language is divisible by 3.
(b) Compare compiler and an interpreter with the help of suitable examples. [8+8]
2. Write a Context Free Grammar(CFG) for the while statement in ‘C’ language. [16]
3. (a) What is meant by a parser generator? Illustrate with examples using YACC.
(b) How are ambiguities resolved in YACC? [10+6]
4. (a) What are L-attributed definitions? Explain with an example.
(b) Draw the syntax tree for the following Boolean expression:
(P < Q AND R < S) OR (T < U AND R <Q). [8+8]
5. (a) Distinguish static and dynamic Type checking ?
(b) Discuss in detail about semantic analysis phase? [8+8]
6. (a) Explain how scope information is represented in the symbol table for block
structured language?
(b) Write and explain about activation record? [10+6]
7. Explain in detail the procedure that eliminating global common sub expression?
[16]
8. Write and explain about object code forms? [16]