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 Regular Examinations, November 2007

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) What is Finite Automaton? Give an example.
(b) Find the number of tokens presented in the following ‘FORTRAN’ statements:
i. DO 100 I = 1.625


ii. IF ( MIN .EQ. MAX ) GOTO 1000
(c) Find the Regular Expression for the DFA as shown in figure 1c. [2+2+12]

Figure 1c
2. (a) Construct a Context Free Grammar(CFG) for possible sequences of if and else
in‘C’
(b) Find the moves of the above grammar to derive the if - else sequence of the
string: iieie. [10+6]
3. Consider the following augmented grammar:
S ! A
A ! BA|2
B ! aB|b
(a) Construct the LR(1) parser.
(b) Find the moves made by the LR(1) parser on the input string: a a b b.[10+6]
4. (a) Compare Inherited attributes and Synthesized attributes with an example.
(b) Construct triples of an expression: a * - (b + c). [8+8]
5. Explain Linear bounded automaton with an Example? [16]
6. (a) Write a notes on the static storage allocation strategy with example and dis-
cuss its limitations?
1 of 2
Code No: R05311201 Set No. 1
(b) Discuss about the stack allocation strategy of runtime environment with an
example? [8+8]
7. Write explain about Organization for an Optimizing Compiler? [16]
8. Write differences between single pass and two pass translation? [16]
⋆ ⋆ ⋆ ⋆ ⋆

III B.Tech I Semester Regular Examinations, November 2007

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) Define Alphabets, Strings, and Languages. Give two examples of each.
(b) Consider the line number 4 of the following ‘C’ program:
int main() /* Line 1 */
{ /* Line 2 */
int i, n; /* Line 3 */
fro(i=0, i<n, i++); /* Line 4 */
} /* Line 5 */
What is the compiler’s response about this line while creating the object mod-
ule? Explain. [9+7]
2. Write a Context Free Grammar(CFG) for the while statement in ‘C’ language. [16]
3. Consider the following augmented grammar:
S ! E
E ! E + T|T
T ! a |(E)
(a) Construct the DFA whose states are the canonical collection of LR(0) items.
(b) Construct the SLR(1) parse table. [8+8]
4. (a) Construct triples of the expressions: a[i] := b and a := b[i]
(b) Generate the three-address code for the following ‘C’ program fragment:
for( i = 1; i <= 20; i++) if( a < b) x = y + z; [8+8]
5. (a) Write a short notes on context sensitive language with suitable example.
(b) Write about Linear Bounded Automata. [8+8]
6. Write and Explain about Symbol Table Organization? [16]
7. Explain the following:
(a) Dominators
(b) Algorithm for Constructing the Natural Loops
(c) Reducible Flow Graphs. [4 × 4]
8. Explain the concept of label tree for code generation. [16]
⋆ ⋆ ⋆ ⋆ ⋆

III B.Tech I Semester Regular Examinations, November 2007

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) What is left factoring? Explain with a suitable example.
(b) What is the language, L generated by the following grammar, G:
G = ({S}, {a, b}, {S ! aSb |ab }, S)
(c) Identify the language, L generated by the following grammar, G:
G = ({S,A,B}, {a, b}, {S ! Aa,A ! a |B ,B ! bB | b }, S). [6+5+5]
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. Translate the executable statements of the following ‘C’ program into a three-
address code by assuming each element of an array ‘a’ takes 4 bytes. [16]
void main()
{
int i = 1, a[10];
while(i++ < = 10)a[i] = 0;
}
5. (a) Distinguish static and dynamic Type checking?
(b) Explain about on Polymorphic functions? [8+8]
6. Write and Explain about algorithm for construction of equivalence trees? [16]
7. (a) Define the following:
i. Basic Block
ii. Local Optimization
iii. Global Optimization.
1 of 2
Code No: R05311201 Set No. 3
(b) Explain about Algebraic Transformations?
(c) “Copy propagation Leads to Dead code” - Justify the statement. [6+6+4]
8. Write and explain an algorithm for building a DAG from a basic Block . [16]
⋆ ⋆ ⋆ ⋆ ⋆

III B.Tech I Semester Regular Examinations, November 2007

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) Define Alphabets, Strings, and Languages. Give two examples of each.
(b) Consider the line number 4 of the following ‘C’ program:
int main() /* Line 1 */
{ /* Line 2 */
int i, n; /* Line 3 */
fro(i=0, i<n, i++); /* Line 4 */
} /* Line 5 */
What is the compiler’s response about this line while creating the object mod-
ule? Explain. [9+7]
2. Construct the predictive parse table for the following grammar:
S ! iEtSS′ |a
S′ ! eS |2
E ! b. [16]
3. Consider the grammar: S ! (S) |a
Construct the DFA for SLR(1), CLR(1), and LALR(1) parsers and find the number
of states in each of the parser. [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. (a) what is type Checker? How does it work?
(b) Write short notes on Dynamic and Static type checking? [8+8]
6. Write and Explain about Runtime storage administration? [16]
7. (a) Explain Briefly about the Global Optimization?
(b) Distinguish machine dependent and machine independent optimization.[8+8]
8. Explain all the data structures used for designing the macro pre-processor? [16]
⋆ ⋆ ⋆ ⋆ ⋆