JNTU
JNTU B.Tech III AUTOMATA AND COMPILER DESIGN Previous Question Paper (May - 2018 - 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 Token, Pattern and Lexeme.
Answer
A Token is a category of lexical units (e.g., identifier, keyword). A Pattern is the set of rules describing the form that the lexemes of a token may take. A Lexeme is the actual sequence of characters in the source program that matches the pattern for a token.
What is Context free grammar?
Answer
A Context-Free Grammar (CFG) is a formal grammar defined by a 4-tuple (V, T, P, S), where V is a finite set of variables, T is a finite set of terminals, P is a finite set of production rules of the form A -> α (where A is a variable and α is a string of variables and terminals), and S is the start symbol.
What are the actions performed by Shift reduce parser?
Answer
Sign in to view the complete answer paper.
List out the rules for FIRST and Follow.
Answer
Sign in to view the complete answer paper.
What is type checking?
Answer
Sign in to view the complete answer paper.
Draw the model of Chomsky hierarchy of grammars.
Answer
Sign in to view the complete answer paper.
Define Flow Graph.
Answer
Sign in to view the complete answer paper.
What is dynamic storage allocation?
Answer
Sign in to view the complete answer paper.
Define Code generation.
Answer
Sign in to view the complete answer paper.
List out the issues in the design of a code generation.
Answer
Sign in to view the complete answer paper.
Part B
Construct Finite Automata for the regular Expression 1(01+10)*00.
Answer
Sign in to view the complete answer paper.
Show that L={a2n|n>0} is Regular.
Answer
Sign in to view the complete answer paper.
Define Derivation tree. Explain about LMD and RMD.
Answer
Sign in to view the complete answer paper.
Construct a derivation tree for the string abcd from the grammar: S→aAB, A→bC, B→d, C→cd.
Answer
Sign in to view the complete answer paper.
Construct a LALR Parser for the Grammar: S→CC, C→cC | d.
Answer
Sign in to view the complete answer paper.
Construct a annotated parse tree for the expression 3*5+4/n.
Answer
Sign in to view the complete answer paper.
Construct SLR Parsing table for the grammar S→L=R | R, L→*R | id, R→L.
Answer
Sign in to view the complete answer paper.
Construct an annotated parse tree for 9-5+2.
Answer
Sign in to view the complete answer paper.
Explain in brief about Type checking and Type Conversion.
Answer
Sign in to view the complete answer paper.
Explain about the procedure for checking polymorphic functions.
Answer
Sign in to view the complete answer paper.
Explain in detail about Polymorphism.
Answer
Sign in to view the complete answer paper.
Explain in brief about Chomsky hierarchy of grammars.
Answer
Sign in to view the complete answer paper.
Differentiate between Static and Dynamic Storage allocation Strategies.
Answer
Sign in to view the complete answer paper.
Explain in brief about Heap Storage allocation strategy.
Answer
Sign in to view the complete answer paper.
List out and explain about the criteria required for Code improving Transformations.
Answer
Sign in to view the complete answer paper.
Define Basic block? Explain in brief about optimization of basic blocks.
Answer
Sign in to view the complete answer paper.
Explain in detail the procedure that eliminates global common sub expression.
Answer
Sign in to view the complete answer paper.
What is an Induction variable? Explain it with an example.
Answer
Sign in to view the complete answer paper.
Explain reducible and non reducible flow graphs with examples.
Answer
Sign in to view the complete answer paper.
Explain in detail about the garbage collection via Reference Counting.
Answer
Sign in to view the complete answer paper.