Compiler Design

Important Questions

Unit-1
1. Explain the various errors that occur in compilation process or explain the syntax phase
and lexical phase and tell the errors that come in these phases.
2. Explain in detail the process of compilation. Illustrate the output of each phase of
compilation of the input a = (b + c)*(b + c)* 2
3. Convert NFA to equivalent DFA and minimize number of states in DFA.(Any NFA
given)
4. Construct the minimized DFA for the regular expression. ( Any RE given)
5. Explain lexical analyzer generator and explain the different parts of the program.
6. What is an ambiguous grammar? Check whether given grammar is ambiguous or not. If
ambiguous then convert it into unambiguous grammar: E→E+E|E*E|id (any grammar given)
7. Construct the following grammar after removing left recursion (any grammar given)

S -> Aa | b | ε
A -> Ac | SAd | ε
8. Write short note on Lex and YACC.
 Unit-2
1. What is top-down parsing? What are the problems in top-down parsing? Explain each
with suitable example. State any two differences between top-down and bottom-up
parsing.
2. Consider the following grammar: S→B|SabS, B→bB| ε Compute First and follow of
all non-terminals (any grammar can be given)
3. Construct LL(1) parsing table for the following grammar and check if the given
grammar is LL(1) or not. (any grammar can be given)

S → aB | aC | Sd | Se
B → bBc | f
C→g
4. Parse the input strings (a,(a, a)) and ,(a, a) using shift reduce parser (any grammar can
be given)and List down the conflicts during shift-reduce parsing
S → (L) | a
L → L, S | S
5. Questions based on LR, SLR, CLR, and LALR parsers (construction of parsing tables
and parsing the given string) (VERY IMPORTANT)
 Unit-3
1. Define the syntax directed definition (SDD) with suitable and simple example. Mention
the difference between inherited and synthesized attributes.

2. Consider the following grammar and give the syntax directed definition to construct
parse tree for the input expression 4*7+3*9. E -> E+T | T T -> T*F | F F -> num.
Construct an annotated parse tree according to your syntax directed definition.

3. Illustrate the role of syntax directed translation in compiler design. Also explain how
semantic actions are attached to the production with example.

4. What is postfix notations? translate (C+D)*(E+Y) into postfix using syntax directed
translation scheme(STDS)

5. Give various types of three address statements used for different programming language
constructs such as assignment, jump, procedure calls, array statements etc.

6. Write three address code for the following statement(any statement can be given)
while(a>b)
{
if(c<d)
x=y+z;
else
x=y-z;
}
7. What is the difference between parse tree and abstract syntax tree?
8. Explain the concepts of quadruples and triples in the context of syntax directed
translation. Discuss how they represent intermediate code and support optimization.
9. Write Quadruple, Triple, and three address code for the expression (a/b)*(a+b) - (a*b)/d
(any expression can be given)
 Unit-4
1. Explain the role of a hash table in implementing a symbol table.
2. Define Symbol table? Explain about data structures used for symbol table.
3. Analyse the role of symbol tables in different phases of compilation. How does symbol
table interact with lexical, syntax, and semantic analysers?
4. What are Static and Dynamic Scope Rules? Briefly explain access to non-local names
in static scope. How are the activation records used in implementation of recursive calls
of a procedure/function?
5. Describe a simple stack allocation scheme for managing memory during program
execution. Explain how it is used for storing local variables and managing function
calls. Also explain heap allocation strategies of the runtime environment with an
example.
6. What is mean by Activation record? Draw the format of Activation Record in stack
allocation and explain each field in it. Explain how it is related with runtime storage
organization?
7. Define semantic errors in a compiler. Explain different types of semantic errors with
examples and how a compiler detects them during semantic analysis.
8. Give a classification of various errors and discuss each class of errors with examples.
Explain the various types of compile-time errors in phases of compiler.
9. Explain the function of error handling phase of a compiler. What is phrase level error
recovery?
10. Explain lexical, syntax, semantic phase errors in detail.
 Unit-5
1. Explain the role of a code generator in a compiler. Discuss its responsibilities and how
it translates intermediate code into the target code. Construct target code for the
following expression: x: = (a+b)*c+d/(a+b)
2. Explain the major design issues in code generation. How do these issues impact the
performance of a compiler?
3. Define a directed acyclic graph. Compute the number of nodes in Directed Acyclic
Graph (DAG) for the following C code segment executed in the sequence: a = b + c; e
= a + 1; d = b + c; f = d + 1; g = e + f; (AKTU 2023-24)
4. Explain in the DAG representation of the basic block with example. How the DAG is
used in common sub-expression elimination? Discuss in details. What are the
advantages of DAG?
5. Explain in the DAG representation of the basic block with example. Construct the flow
graph for the following code segment:
fact(n)
{
int f=1;
for(i=2; i≤n; i++)
f=f*i;
return f;
}
6. Explain what constitutes a loop in a flow graph and how will do you do loop
optimizations in code optimization of a compiler.
7. Define induction variable?

8. Explain the need of data flow analysis in code optimization. Explain the concept of
global data-flow analysis.

9. Discuss the following terms: