JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY HYDERABAD
JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY HYDERABAD B.Tech III FINITE AUTOMATA AND COMPILER DESIGN Previous Question Paper (January/February - 2023 - R18)
Note: i) Question paper consists of Part A, Part B. ii) Part A is compulsory, which carries 25 marks. In Part A, Answer all questions. iii) In Part B, Answer any one question from each unit. Each question carries 10 marks and may have a, b as sub questions.
Part A
Define a Context Free Grammar.
Answer
A Context Free Grammar (CFG) is a formal grammar defined by a 4-tuple G = (V, Σ, R, S), where V is a finite set of variables (non-terminals), Σ is a finite set of terminals disjoint from V, R 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 from V. It is used to generate the strings of a context-free language by recursively applying production rules.
Define Token, Pattern and Lexeme.
Answer
A token is a category or classification of lexical units, such as an identifier, keyword, or operator, which is represented as a pair consisting of a token name and an optional attribute value. A pattern is the set of rules or the regular expression that describes the form that the lexemes of a particular token may take. A lexeme is the actual sequence of characters in the source program that matches the pattern for a token.
Define ‘Handle’ in shift reduce parser.
Answer
Sign in to view the complete answer paper.
List out the rules for computing FIRST SET.
Answer
Sign in to view the complete answer paper.
What is the difference between type conversion and type checking?
Answer
Sign in to view the complete answer paper.
Define Regular Grammar.
Answer
Sign in to view the complete answer paper.
How to define the Leader in a Basic Block?
Answer
Sign in to view the complete answer paper.
What is dynamic storage allocation?
Answer
Sign in to view the complete answer paper.
What do you mean by machine dependent code generation?
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
Remove left recursion from the above CFG.
Answer
Sign in to view the complete answer paper.
Compute FIRST and FOLLOW set for the non-terminals of the resulting grammar.
Answer
Sign in to view the complete answer paper.
Show that the resulting grammar is LL(1).
Answer
Sign in to view the complete answer paper.
Design FA for the following Regular Expression over Σ{0, 1}
a) 01(1+0)*10
b) 11(0+1)*101(0+1)*{0 1}
Answer
Sign in to view the complete answer paper.
What is LR parser? Compare and contrast the different types of LR parsers.
Answer
Sign in to view the complete answer paper.
How are ambiguities resolved in YACC?
Answer
Sign in to view the complete answer paper.
What are L-attributed definitions? Explain with an example.
Answer
Sign in to view the complete answer paper.
Explain in detail about Chomsky hierarchy of grammars.
Answer
Sign in to view the complete answer paper.
Distinguish static and dynamic Type checking.
Answer
Sign in to view the complete answer paper.
Explain the machine dependent and machine independent code optimization? What are their advantages? How to represent the dummy blocks with no statements indicated in global dataflow analysis?
Answer
Sign in to view the complete answer paper.
Give the block diagram of organization of code optimizer. What are the advantages of the organization of code optimizer?
Answer
Sign in to view the complete answer paper.
Explain about Generic code generation algorithm.
Answer
Sign in to view the complete answer paper.
Define a Directed Acyclic Graph. Construct a DAG and write the sequence of instructions for the expression 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 following fragment using the above attribute grammar: for i= 1 to n step m+k do s:= s+i.
Answer
Sign in to view the complete answer paper.