JNTU
JNTU B.Tech III AUTOMATA AND COMPILER DESIGN Previous Question Paper (November/December - 2017 - 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 a context free grammar? Design a CFG that generates floating-point literal.
Answer
A Context-Free Grammar (CFG) is a 4-tuple G = (V, T, P, S) where V is a set of variables, T is a set of terminals, P is a set of productions of the form A → α (where A ∈ V and α ∈ (V ∪ T)*), and S is the start symbol. A CFG for a floating-point literal (e.g., 12.34) is:
Number → Digit Number | Digit
Float → Number . Number
Considering the following grammar, remove left recursion and left factor the grammar to be LL (1).
S → id = E | id (E)
E → id | num
Answer
To remove left recursion from L → L ; S | S, we introduce a new variable L':
L' → ; S L' | ε
S → id = E | id (E)
E → id | num
S' → = E | (E)
L → S L'
L' → ; S L' | ε
E → id | num
What is syntax directed definition? Give a suitable example?
Answer
Sign in to view the complete answer paper.
Find the canonical collection of sets of LR(1) items
A → BbBa
A → ε
B → ε
Answer
Sign in to view the complete answer paper.
What is the difference between type conversion and type checking? Explain with the help of a high level language?
Answer
Sign in to view the complete answer paper.
What is unit production in CFG? What is the procedure to eliminate Unit productions?
Answer
Sign in to view the complete answer paper.
Explain the principle sources of optimization. What are the patterns used for code optimization? What are the 3 areas of code optimization?
Answer
Sign in to view the complete answer paper.
What are the rules to determine the leaders of basic blocks? What is the use of algebraic transformation?
Answer
Sign in to view the complete answer paper.
What is a flow graph? Mention the applications of DAGs.
Answer
Sign in to view the complete answer paper.
Construct a DAG for the expression a = b * -c + b * -c.
Answer
Sign in to view the complete answer paper.
PART - B
Consider the following grammar: lexp → atom | list; atom → number | identifier; list → ( lexp_seq ); lexp_seq → lexp_seq lexp | lexp. Answer the following: Remove left recursion, Construct FIRST and FOLLOW set, Construct LL(1) parsing table, Show that it is LL(1), Show parsing action for input (a (b (2)) (c)).
Answer
Sign in to view the complete answer paper.
Construct an LL(1) parsing Table for the given grammar.
Answer
Sign in to view the complete answer paper.
Construct DFA equivalent to the NFA ({p, q, r, s}, {0,1}, δ, p, {s}) where the transition function δ is given in following table.
Answer
Sign in to view the complete answer paper.
Discuss the construction of LR parser. What are the various data structures used? Discuss construction of ACTION and GOTO table.
Answer
Sign in to view the complete answer paper.
Write syntax directed definition to implement a desk calculator with an LR parser and show the evaluation of expression ‘95*4 + 5’.
Answer
Sign in to view the complete answer paper.
Describe the syntax directed translation procedure for assignment statements with integers and mixed types.
Answer
Sign in to view the complete answer paper.
Construct LALR(1) parsers for the following grammar: S → L = R | R; L → * R | id; R → L.
Answer
Sign in to view the complete answer paper.
What is phase structure grammar? State and explain Chomsky classification of grammar with examples.
Answer
Sign in to view the complete answer paper.
For the given grammar, eliminate useless symbols, ε-production, unit production, and convert to CNF.
Answer
Sign in to view the complete answer paper.
What is phase structure grammar? What is Chomsky normal form of grammar? Explains the steps used to reduce a CFG to CNF.
Answer
Sign in to view the complete answer paper.
Convert the following grammar into Chomsky normal form: S → AAA | B; A → aA | B; B → ε.
Answer
Sign in to view the complete answer paper.
Give the block diagram of organization of code optimizer. What are the advantages?
Answer
Sign in to view the complete answer paper.
What is dynamic storage allocation? Why is not static allocation sufficient for everything?
Answer
Sign in to view the complete answer paper.
What is activation record? Discuss the structure and layout of a typical activation record.
Answer
Sign in to view the complete answer paper.
Explain machine dependent and independent code optimization. How to represent the dummy blocks with no statements indicated in global dataflow analysis?
Answer
Sign in to view the complete answer paper.
Define a DAG. Construct a DAG and write sequence of instructions for: a + a * ( b – c ) + ( b – c ) * d.
Answer
Sign in to view the complete answer paper.
Give the sequence of three-address code instructions corresponding to the fragment: for i= 1 to n step m+k do s:= s+i.
Answer
Sign in to view the complete answer paper.
Explain code generation process and steps for expression: (A + B) / C + D. Assume two machine registers are available.
Answer
Sign in to view the complete answer paper.
Explain the various issues in the design of code generation. Construct the DAG for the basic block: d:= b*c; e:= a+b; b:= b*c; a:= e-d.
Answer
Sign in to view the complete answer paper.