JNTU
JNTU B.Tech III AUTOMATA AND COMPILER DESIGN Previous Question Paper (May/June - 2019 - R15)
Note: This question paper contains two parts A and B. Part A is compulsory which carries 25 marks. Answer all questions in Part A. Part B consists of 5 Units. Answer any one full question from each unit. Each question carries 10 marks and may have a, b, c as sub questions.
Part A
Define the term lexical analyzer.
Answer
A lexical analyzer, or scanner, is the first phase of a compiler that reads the input source program character by character and groups them into meaningful sequences called lexemes, which are then converted into tokens for the syntax analyzer.
Construct NFA corresponding the regular expression a(a+b)*ab .
Answer
The NFA for the regular expression a(a+b)*ab is constructed as follows:
- Start state 0 transitions to state 1 on input 'a'.
- State 1 transitions to itself on 'a' or 'b' (representing (a+b)*).
- State 1 transitions to state 2 on input 'a'.
- State 2 transitions to state 3 on input 'b'.
- State 3 is the final accepting state.
What do you mean by Handle pruning?
Answer
Sign in to view the complete answer paper.
Write the procedure to find CLOSURE of an LR(0) item.
Answer
Sign in to view the complete answer paper.
Define context sensitive grammar? What language does the grammar S →aSa | bSb | c generate?
Answer
Sign in to view the complete answer paper.
Define type 3 grammar.
Answer
Sign in to view the complete answer paper.
What do you mean by dead code?
Answer
Sign in to view the complete answer paper.
What are the rules to determine the leaders of basic blocks? What are the primary structure preserving transformations on basic blocks?
Answer
Sign in to view the complete answer paper.
Mention the applications of DAGs.
Answer
Sign in to view the complete answer paper.
What do you mean by machine dependant code generation?
Answer
Sign in to view the complete answer paper.
Part B
Construct DFA equivalent to the NFA { { P, Q, R, S }, {0, 1 }, , P, {P, Q} } , where the transition function given by table.
Answer
Sign in to view the complete answer paper.
Construct an LL(1) parsing Table for the grammar: E → E+T | T; T → T*F | F; F → (E) | id
Answer
Sign in to view the complete answer paper.
Consider the grammar: lexp → atom | list; atom → number | identifier; list → ( lexp_seq ); lexp_seq → lexp_seq lexp | lexp. Answer: a) Remove left recursion, b) Construct FIRST and FOLLOW set, c) Construct LL(1) parsing table.
Answer
Sign in to view the complete answer paper.
Construct SLR parser for the grammar: E → (L) | a; L → L, E | E. Check the behavior of parser with an example string.
Answer
Sign in to view the complete answer paper.
Consider the grammar: E → (L) | a; L → L, E | E. Construct LR(1) items and LR(1) parsing table.
Answer
Sign in to view the complete answer paper.
Give syntax Directed Translation definition for type checking of an expression.
Answer
Sign in to view the complete answer paper.
What is phase structure grammar? Explain Chomsky classification of grammar with examples.
Answer
Sign in to view the complete answer paper.
Define phrase structure grammar and explain Chomsky classification in detail.
Answer
Sign in to view the complete answer paper.
Explain in detail about peephole optimization.
Answer
Sign in to view the complete answer paper.
Differentiate between static scope and dynamic scope. Explain the implementation of static scoping.
Answer
Sign in to view the complete answer paper.
What is code optimization? Differentiate between machine dependent and machine independent code optimization.
Answer
Sign in to view the complete answer paper.
Construct the DAG for the following basic block and apply common sub-expression and dead code elimination: a = b + c; b = b – d; c = c + d; e = b + c. Assume a, b are live and c, e are non-live on exit.
Answer
Sign in to view the complete answer paper.
What is DAG? Why is it used? Construct DAG for: Z = X – Y + X * Y * U – V/W + X + V
Answer
Sign in to view the complete answer paper.
Consider the sequence of three address instructions provided. If we have ONE register available, which variables would you put into a register assuming memory operations are twice as slow?
Answer
Sign in to view the complete answer paper.