AS PER JNTU SYLLABUS ALL 8 UNITS IMPORTANT QUESTIONS
UNIT I
1. (a) Explain, in detail, lexical analyzer generator.
(b) Describe the lexical errors and various error recovery strategies with suitable
examples.
2. (a) Consider the following fragment of ‘C’ code:
float i, j;
i = i * 70 + j + 2;
.Write the output at all phases of the compiler for the above ‘C’ code.
Explain the input buffer scheme for scanning the source program. How the use of
sentinels can improve its performance? Describe in detail.
(b) Write short notes on: input buffering.
3.(a) Write a regular expressions and NFA for the following patterns. Use auxiliary
definitions where convenient?
i. The set of words having a, e, i, o, u appearing in that order, although not
having necessarily consecutively.
ii. Comments in C.
(b) Differentiate Interpreter & Compiler?
**4.Describe various phases of a compiler? Differentiate a phase and pass? Compare
multipass and single pass compiler?
***5. Explain with one example how LEX program perform lexical analysis for the follow-
ing patterns in `C': identifier, comments, numerical constants, arithmetic operators.
6.(a) Construct an NFA for regular expression R= (aa/b)*ab convert it into an
equivalent DFA
(b) Write a LEX program for identifying the keywords and identifiers from the
file?
*7.(a) Explain the different phases of a compiler, showing the output of each phase,
using the example of the following statement:
position : = initial + rate * 60
(b) Compare compiler and interpreter with suitable diagrams.
**8.(a) Explain the different phases of a compiler, showing the output of each phase
using the example for the statement:
x=(a+b) * (c+d)
(b) Write short notes on bootstrapping process.
9.State the steps to convert a regular expression to NFA. Explain with an example
(a) Construct an NFA for regular expression R= (aa/b)*ab convert it into an
equivalent DFA
(b) Write a LEX program for identifying the keywords and identifiers from the
file?
10.(a) Explain the bootstrapping process with suitable diagrams.
(b) Explain how input buffering helps lexical analyzer in compilation process
11.Explain the input buffer scheme for scanning the source program. How the use of
sentinels can improve its performance? Describe in detail.
12.a) What is LEX? Explain, in detail, different sections of LEX program.
(b) Write regular expressions for the following patterns. Use auxiliary definitions
wherever convenient.
13.i. the set of words having a,e,i,o,u appearing in that order, although not
necessarily consecutively.
ii. comments in C.
14.(a) What is regular expression? Write regular expressions for the following pat-terns: identifiers and float constants.
(b) Define lexeme, token and pattern. Identify the lexemes, that make up thetokens in the following program segment. Indicate corresponding token andpattern. [6+10]
void swap(int i, int j)
{
int t;
t=i;
i=j;
j=t;
}
15. (a) Consider the following fragment of `C' code:
oat i, j;
i = i * 70 + j + 2;
Write the output at all phases of the compiler for the above `C' code.
(b) Write short notes on: input buffering.
Unit2
.1. (a) Construct recursive descent parser for the following grammar.
E -> T E’
E’ -> +T E’|e
T -> F T’
T’ -> *FT’|e
F -> (E)|id
(b) Eliminate ambiguities in the following grammar.
S -> iEtS| iEtSeS| a
E -> b| c | d
**2. (a) What are the difficulties in top down parsing? Explain in detail.
(b) Consider the following grammar
S -> (L) |a
L -> L, S |S
Construct leftmost derivations and parse trees for the following sentences:
i. (a,(a,a))
ii. (a,((a,a),(a,a))).
3.(a) Construct predictive parse table for the following grammar.
E -> E + T/T
T -> T *F/F
F -> F /a/b
(b) What are the limitations of recursive descent parser
(a) What are the common conicts that can be encountered in shift - reduce
parser.
(b) Construct SLR parsing table for the following grammar.
R -> R’/ ‘R /RR /R* /(R) /a /b
4.(a) Convert the following grammar into LL(1) grammar
b) construct LL(1) parse table for the above grammer
S→ ABC A →a A| C B → b C → c
5. (a) What is the string generated by the grammar A -> (A)A
(b) Explain the basic method of LL(1) parsing and hence explain how very simple
grammar generates strings of balanced parentheses.
6.a) Give the rules for computation of FIRST(X) and FOLLOW(X). Construct
FIRST and FOLLOW sets for the following grammar.
E -> T E’
E’ -> +T E’|e
T -> F T’
T’ -> *FT’|e
F -> (E)|id
(b) Write an algorithm for construction of predictive parsing table.
1.Construct SLR parsing table for the following grammar.
S -> AS/b
A -> SA/a
7.Construct SLR parsing table for following grammar:
E -> E + T/T
T -> T * F/F
F -> (E)/id.
8.(a) What is CFG? Explain in detail.
(b) Write short notes on following terms:
i. Parse tree.
ii. LL(k) grammar.
9.(a) Write the algorithm for predictive parsing.
(b) Explain error recovery in predictive parsing.
. Construct LL(1) parse table for the following grammar.
b exp r -> b exp r or bterm / bterm
bterm -> bterm and bfactor / bfactor
b factor -> not bfactor ->(b exp r) /true /false
where or, and, not, (,), true, false are terminals in the grammar.
10.a) \Top down parsing is also considered as LMD derivation". Justify the given
statement.
(b) Verify whether string \id+(id+id)" is accepted by following grammar or not
by using predictive parsing:
E -> TE’
E’ -> +TE’/ e
T -> FT’
T’ -> *FT’/ e
F -> (E)/id.
11.(a) What are the merits & demerits of recursive descent parsing.
(b) Explain predictive parsing in detail.
12.(a) Explain recursive descent parsing in detail.
(b) State the rules to compute FIRST(X) & FOLLOW(X).
13. (a) What is left recursion? Remove left recursion from following grammar:
S -> Aa/b
A -> Ac/Sd/ e
(b) Check for LL(1) for following grammar:
prog -> begin d semi X end
X -> d semi X/sY
Y -> semi s Y/2.
14.(a) Consider the following grammar.
S -> 0A/1B/0/1
A -> 0S/1B/1
B ->. 0A/1S
Construct leftmost derivations and parse trees for the following sentences
i. 0101
ii. 1100101
(b) Consider the following grammar
E -> T + E/T
T -> V*T/V
V -> id
Write down the procedures for the non-terminals of the grammar to make a
recursive descent parser.
15.(a) Explain the following top-down parsing methods with Example?
(b) Recursive - Decent parsing
c) Predictive Parser
16.a) Draw the syntax tree for the following expression a : = b * - c + b * - c
(b) Write the postfix notation and three address code for the following expression
i. ( - ( a + b ) * ( c + d ) + ( a + b + c ) )
17.(a) What is recursive descent parser? Construct recursive descent parser for the
following grammar.
E -> E + T|T
T -> TF|F
F -> F_|a|b
(b) What is ambiguous grammar? Eliminate ambiguities for the grammar:
E -> E + E|E*E|(E)|id.
18.Construct the SLR(1) parse table for the following grammar:
S -> xAy |xBy| xAz
A -> aS |q
B -> q.
19.. (a) What is an LL(1) parse table? Explain.
(b) Build an LL(1) parse table for the following production grammar:
S -> CC
C -> cC| d.
20.construct predictaive parsing table for given
E -> T E’
E’ -> +T E’|e
T -> F T’
T’ -> *FT’|e
F -> (E)|id
Unit3
**1. (a) Define LR(k) parser. Draw and explain model of LR parser.
(b) Write LR parsing algorithm.
2. (a) Explain the stack implementation of shift reduce parsing method with an
example.
(b) Define handle. Give suitable example.
3. Construct Canonical LR parsing table for the following grammar
S -> CC
C -> cC/d
4. Define precedence functions. Construct precedence table and directed graph rep-
resenting precedence functions for operators +, *, id, $. [
5. (a) What are the actions of shift-reduce parsers?
(b) Construct SLR parsing table for the following grammer.
6.Construct LALR parsing table for the following grammar.
A′ -> A
A -> (A)
A -> a
7.(a) Construct LALR parsing table for the following grammar
S - > CC
C - > cC/d
(b) What do you mean by left most derivation. Explain with an example
**8.Give the algorithm to generate the canonical collection of LR(0) items
9.(a) What is an SLR Grammar?
(b) Construct LALR(1) Parse table from the following grammar
S-> Aa/bAc/dc/bda:.
*10..What is an ambiguous grammar? With an example illustrate how we can not
uniquely parse a given sentence for an ambigious grammar
*11.a) What is an LR(0) item? Write an LR(0) item for the production A !2.
(b) Construct LR(0) parser for the following grammar:
S0 -> cA|ccB
A -> cA|a
B -> ccB|b.
10. Construct a DFA whose states are the canonical collection of LR(1) items for the
following augmented grammer:
S ->A
A->BA|e
B -> aB |b
**11.C onstruct LALR Parsing table for the following grammar
S -> Aa|bAc|Bc|bBa
A ->d
B -> d
12.Construct LALR parsing table for the following grammar
S -> A S|b
A -> S A|a
13.a) Consider following grammar:
S ->1S0/0S1/10
Is this grammar SLR(1) or not.
(b) Distinguish between CLR & LALR parsing
14.(a) Find the precedence functions for following grammar:
E -> E + E/E * E/(E)/id
(b) What is the significance of look ahead symbol in parsing process
(a) Explain error recovery in LR parsing.
(b) Remove ambiguity from following grammar:
R -> R'/'R / RR/R*/(R)/a/b.
15.(a) Find the precedence functions for following grammar:
E -> E + E->E * E/(E)/id
(b) Explain error recovery in LR parsing
16.Construct SLR parsing table for following grammar:
E -> E + T/T
T -> T * F/F
F -> (E)/id.
17.(a) Construct LALR parsing table for the following grammar:
S -> Aa/bAc/dc/bda
A -> d
18.Show the moves of this parser on input bda.
(b) Consider following grammar:
S -> 1S0/0S1/10
Is this grammar SLR(1) or not.
19.Give the algorithm to generate the canonical collection of LR(0) items.
20. (a) What is next use information explain in detail.
(b) Write about target code forms. Explain how the target code can be generated
from the given three address code.
21.(a) What is meant by a parser generator? Illustrate with examples using YACC
(b) Mention the error recovery strategies of parser.
22. (a) Write a short notes on token speci_cation.
(b) Draw a NFA for a */ b *.
(c) Convert the above (b) to DFA.
23.Explain shift-reduce parsing. Illustrate with examples.
24.(a) Explain LALR parsing, justify how it is efficient over SLR parsing
(b) Find the moves made by the LR(1) parser on the input string: aabb
25.a) What is an operator grammar? Give an example.
(b) Write an operator precedence parsing algorithm
26.Consider the grammar: S -> (S) |a
Construct the DFA for SLR(1), CLR(1), and LALR(1) parsers and find the number of states in each of the parser.
27.Construct the LR(1) parse table for the following augmented grammar:
S’-> S
S -> BB
B->bB |c. [16]
28.(a) Explain canonical LR parsing.
(b) Explain briefly, precedence functions. construct the precedence graph using
the following prededence table. [8+8]
+ * ( ) id $
f 2 3 0 4 4 0
g 1 3 5 0 5 0
Unit 4
**1. (a) Write a note on the specification of a simple type checker.
(b) What is a type expression? Explain the equivalence of type expressions with
an appropriate examples.
**2.(a) Draw syntax tree for the arithmetic expressions
A*(b + c) − d/2
Also write the given expression in postfix notation.
(b) Write the quadruple, triple, indirect triple for the following expression
(x + y)*(y + z) + (x + y + z)
3. (a) Describe the overloading of functions and operators with suitable examples.
(b) Write a note on polymorphic functions.
4. Write type expressions for the following types.
(a) An array of pointers to reals, where array index ranages from 1 to 100.
(b) A two dimensional array of integers (i.e. an array of array) whose rows are
indexed from 0 to 9 and whose columns are indexed from -10 to 10.
(c) Functions whose domains are functions from integers to pointers to integers
and whose ranges are records consisting of an integer and a character
5.(a) Write the quadruples, triples and indirect triples for the expression
i. ( a + b ) *(c + d ) *( a + b + c )
ii. a * ( b + c )
1
S→ AS | b
A → SA | a
(b) Write a top-down translation scheme to produce quadruples for Boolean Ex-
Pression
6.a) Why are quadruples preferred over triples in an optimizing compiler. Explain
(b) Give the triple representation of an array operation x : = y [ i ]
(c) Give the syntax directed definition of if else statement.
7. (a) Write the three-address code for the following code.
fact(x)
f int f=1;
for (i=2, i >=x, i++)
f
f=f*i;
return f;
(b) Write an algorithm for identifying leaders and partition the code into basic
8. (a) Translate the following code segment into quadruples.
While A C and B D
if A=1 then C = C+1
else while A = D do A = A+2 from the given three address code
(b) Explain the different statements allowed in TAC with examples.
9.a) Write a note on the specification of a simple type checker.
(b) What is a type expression? Explain the equivalence of type expressions with
an appropriate examples.
10.a) Write the quadruple, triple, indirect triple for the statement a := b* − c + b* − c.
(b) Explain the role of intermediate code generator in compilation process.
11.a) What is back patching?
(b) Explain back patching with reference to the three address code generated for
the expression p > q andq < t.
12.(a) Write a short note on type equivalence.
(b) Write a short note on type checking
13.(a) Write a short note on abstract syntax tree.
(b) Compare and contrast the quadruples, triples & indirect triples
14. (a) Write a short note on L-attributed grammars.
(b) It is required to compute the total number of reductions performed to parse
a given input. Using synthesized attributes only write the semantic rules to
find E.red, the number of reductions performed while reducing on input to E.
E -> E * T/T
T -> F - T/F
F ->2/4
Also draw annotated tree for 4-2-4*2.
*15.a) Consider following grammar:
E -> num.num/literal/num/E%E/E+E/ E`/'E/ E*E/ E[E]
Construct semantic rules to find type of expression.
(b) Give an algorithm to test the equivalence of C types
16.(a) Write about type checking. Consider following C declarations:
typedef struct
f
int a, b;
gCELL,*PCELL;
CELL foo[100];
PCELL bar(x,y)
int x;
CELL y f..g
Write type expressions for the types of foo and bar.
(b) Write a short note on type checking.
17.(a) Compare and contrast the quadruples, triples & indirect triples.
(b) Write the translation schemes for addressing array elements for following grammar:
S -> L := E
E -> E + E/(E)/L
L -> Elist]/id
Elist -> Elist,E
Elist -> id [ E
18.(a) Consider following expression grammar:
S -> E
E -> E + E/E * E/(E)/I
I -> Idigit/digit
Digit -> 0=1=2=::::=9
Write semantic rules to evaluate expression on decimal numbers that it de-
rives. Use `val' attribute for storing the values & constant parse tree for
2*(21+1)+10. Find S.val.
(b) What is the significance of syntax- directed definition
19.Consider following grammar,
E -> E + E/E * E/literal/num/id/EmodE/E[E]/ *E/float
Write semantic rules to compute type of expression
20.a) Distinguish between synthesized & inherited attributes.
(b) Write a short note on abstract syntax tree
21.(a) Write an algorithm for elimination of induction variable.
(b) Write a C program to compute sum of digits of a number and convert it into
three address code. And generate ow graph.
22.a) What is the main purpose of semantic analysis?
(b) Write about three address code? Give examples
23.a) Write a short note on type equivalence.
(b) Write a short note on type checking
24.(a) Write an algorithm for partitioning a sequence of three-address statements
into basic blocks.
(b) Apply the algorithm for the following three-address code :
i. t1:= 4_i
ii. t2:= a[t1]
iii. t3:= 4_I
iv. t4:= b[t3]
v. t5:= t2*t4
vi. t6:= prod +t5
vii. prod:= t6
viii. t7:= i+1
ix. i:= t7
x. if i<=20 goto (1). [8+8]
25.(a) Consider following grammar & identify the type of subexpression. Use type
error as a type expression in error condition.
E -> literal/num/id/EmodE/E[E]/ * E
(b) Write about type checking. Consider following C declarations:
typedef struct
f
int a, b;
gCELL,*PCELL;
CELL foo[100];
PCELL bar(x,y)
int x;
CELL y f..g
Write type expressions for the types of foo and bar.
(26.a) What is dependency graph? What is its significance?
(b) Translate the expression (a+b)*(c+d)+(a+b+c) into.
i. Quadruples.
ii. Triples.
iii. Indirect triples.
iv. Syntax
27.a) Compare and contrast the quadruples, triples & indirect triples.
(b) What is the significance of syntax- directed definition
tree.
28.a) Construct operator precedence parse table for the below grammar.
S- > iEts/iEtSeS/a
E- > b/c/d:
b) Eliminate Ambiguity for above grammar
29.(a) Construct an abstract syntax tree for the following expression:
if a = b then a := c + d else b := c - d
(b) Generate three-address code for the following Boolean expression:
P < Q OR R < S AND T < U .
30.a) Translate the following code segment into Quadruples.
While A < C and B < D
if A=1 then C:= C+1
else while A <= D do A:= A+2
(b) Explain the different statements allowed in TAC with examples
31.(a) Write the quadruples, triples and indirect triples for the expression
i. ( a + b ) *(c + d ) ( a + b + c )
ii. a * ( b + c )
(b) Write a top-down translation scheme to produce quadruples for Boolean Ex-
pression.
32.Generate the code for the following C statements using its equivalent three address
code.
(a) a = b + 1
(b) x = y+3
(c) y = a/b
(d) a = b+c.
33.Write short notes on the following:
(a) S-attributed definitions.
(b) L-attributed definitions.
(c) Dependency graph.
34.(a) Write a note on the specification of a simple type checker.
(b) What is a type expression? Explain the equivalence of type expressions with
an appropriate examples.
35.Generate the three-address code for the following ?C? program fragment: [16]
while(a > b)
{
if (c < d) x = y + z;
else x = y - z;
}
36.(a) What is a Syntax Directed Translation Scheme? Explain with an example.
(b) Design an abstract syntax tree for the expression: a = (a[i+1] = 2) + a[j].
37.What is Type Expression? Write type Expressions for the following type
i. A Two dimensional array integers (i.e. an array of arrays) whose rows are
indexed from 0 to 9 and whose columns are indexed from -10 to 10.
(b) What is Type System? Discuss static and dynamic Checking of types?
38.(a) Write the three-address code for the following code.
begin
PROD: = 0;
I: =1;
do
begin
PROD:=PROD + A[I]∗B[I];
I:=I+1;
End
while I<=20
end
Unit 5
**1. (a) What is an ordered and unordered symbol table? What is the function of
symbol table in the compilation process? Explain.
(b) What are the various attributes of a Symbol Table? [10+6]
**2.(a) Compare three different storage allocation strategies.
(b) Consider the following array declaration in ‘c’;
float a[100][100];
Assume that the main memory in byte addressable and that the array is stored
starting from the memory address 100. What is the address of a[40][50]
**3.a) what is an ordered and unordered symbol table what is function of symbol of table in compilation of process?
b)what are various of symbols of table?
4.(a) Explain the hash table with temporary and permanent storage.
(b) Reusing the storage space for names.
5.Explain symbol table organization using hash tables? Construct hash based struc-
ture for symbol table for the variable in the following program.
int main()
f
int a1, a2, c1, c2;
char b1;
float d1, d2;
|-
|{
6. What is a symbol table? Explain the need for symbol table organization and the
data structures used for implementing a symbol table.
7.a) Describe the method to obtain faster access to nonlocals.
(b) Describe the facilities provided by languages for dynamic allocation of storage
of data.
8.(a) Discuss various object code forms.
(b) Explain the register allocation by graph coloring
9.(a) Compare and contrast various storage allocation strategies.
(b) Consider following pseudo program and find the result if the arguments are
passed by call-by- value, call by reference & call by value result.
begin int a
proc p(b); int b
begin b=b+1; print(b,a) end
a=1
p(a)
print(a)
end.
Explain how storage allocation is done for arrays, strings and records?
10.(a) What is the use of Symbol table in compilation process? List out various
attributes stored in the symbol table.
(b) Explain different schemes of storing name attribute in symbol table.
**11.Explain symbol table organization using hash tables? With an example show the
symbol table organization for block structured language.
**12.Explain DAG and its use. Write the procedure to construct the DAG for a state-
ment. [
.**13. What are the various operations performed on the symbol table? Explain each of
them in detail.
**14.(a) What is an activation record? Explain how it is related with runtime storage
organization?
(b) Write and explain about heap allocation strategy?
15.a) Explain the Dynamic storage allocation facilities provided by C language?
(b) What is dangling reference in storage allocation? Explain with an example
Unit 6
1. Explain different principal sources of optimization technique with suitable exam-
ples. [16]
2.Apply loop optimization and code motion for the following program code. begin
for i := 1 to n do
for j:=1 to n do
c[i, j] :=0;
for i := 1 to n do
for j:=1 to n do
1 of 2
for k :=1 to n do
c[i, j] :=c[i , j] +a[i ,k] *b [k ,j]
end
3. (a) What is DAG? Construct the DAG for the following basic block
D := B_C
E :=A+B
B := B+C
A := E-D
(b) What are the legal evaluation orders and names for the values at the nodes
for the DAG of problem (a).
i. Assuming A, B and C are alive at the end of the basic block?
ii. Assuming only A is live at the end?
4. (a) What is loop invariant operation? Write an algorithm for detecting loop in-
variant computations.
(b) Consider the following program fragment code:
int p=1, k=0, n;
while(k<n)
{
p=2*p;
k=k+1;
} Apply the invariant operation elimination on the above program segment
*6.Explain machine dependent code optimization with example
7.Write the importance of global code optimization. Explain redundant sub expres-
sion elimination technique across di_erent blocks with example
**8.Explain with example the various techniques in loop optimization
**9.Explain different principal sources of optimization technique with suitable exam-
ples.
10.. Describe, in detail, about the concept of DAG for register allocation with an ap-propriate example.
11. Explain DAG and its use. Write the procedure to construct the DAG for a state-
ment. [16]
12.a) What is code optimization? What are its advantages?
(b) Explain briefly about folding.
(c) What are the problems in optimizing compiler design?
13 a) Give the applications of DAG.
(b) Generate code for the following C statements:
i. x=++f(a)
ii. *p++=*q++.
14.a) Write the code sequences for indexed and pointer assignments.
(b) Discuss DAG representation of basic block
15. (a) Discuss loop optimization techniques.
(b) What are reducible flow graphs? Explain with examples
15. (a) Write an algorithm to implement the elimination of redundant subexpressions
in constructing a DAG?
(b) Construct the DAG for the following code:
A[I]:=B
*P := C
D:=A[J]
E:= *P
*P:=A[I]
Assume that
i. P can point anywhere,
ii. P points to only B or D.
Do not forget to show the implied order constraints. [8+8]
16 (a) Generate code for the following C statements. Assume all variables are static
and three registers are available:
i. x=a[i]+1
ii. a[i]=b[c[i]]
(b) Give the applications of DAG.
17.(a) Write the procedure for constructing the DAG.
(b) For the following basic block construct DAG.
d = b * c;
e = a * b;
b = b + c;
c = b * c;
18.(a) Explain DAG and its use.
(b) For the following statements draw the DAG.
t8 = d + e
t6 = a + b
t5 = t6 - c
t4 = t5 * t8
t3 = t4 - e
t2 = t6 + t4
t1 = t2 * t3
19.a) Explain peephole optimization with example.
(b) Explain the procedure for constructing DAG with example. Write the appli-
cations of DAG.
20.(a) What is code optimization? What are its advantages?
(b) Explain briefly about folding.
(c) What are the problems in optimizing compiler design
21.(a) What is DAG? Construct the DAG for the following basic block
D := B∗C
E :=A+B
B := B+C
A := E-D
(b) What are the legal evaluation orders and names for the values at the nodes
for the DAG of problem (a).
i. Assuming A, B and C are alive at the end of the basic block?
ii. Assuming only A is live at the end?
22.(a) Write an algorithm for generating code from a labeled tree.
(b) Construct a DAG for the following program code:
x=y*z
w=p+y
y=y*z
p=w-x
Unit 7
1. Describe, how redundant expression elimination can be done in loop optimization
technique, during global optimization. [16]
2. Consider the following program which counts the primes form 2 to n using the sieve
method on a suitably large array
begin
read n
for i : = 2 to n do
a[i] : = true / * initialize */
count: = 0;
for i : 2 to n ** .5 do
if a [i] then /* i is a prime */
begin
count := count +1
for j : = 2 * i to n by i do
a[j] : =false
/ * j is divisible by i */
end ;
print count
end
(a) Propagate out copy statements wherever possible.
(b) Is loop jumping possible? If so, do it.
(c) Eliminate the induction variables wherever possible
3. (a) What is an Induction variable? Explain with an example.
(b) Discuss how induction variables can be detected and how transformation can
be applied.
4. Describe, how redundant expression elimination can be done in loop optimization
technique, during global optimization.
5.Explain about global data flow analysis. List data flow equations for reaching definitionin structure
blocks and apply it on the above derived three-address code
6. Consider the following program which counts the primes form 2 to n using the Sieve
method on a suitably large array
begin
read n
for i : = 2 to n do
a[i] : = true / * initialize */
count: = 0;
for i : 2 to n ** .5 do
if a [i] then /* i is a prime */
begin
count := count +1
for j : = 2 * i to n by i do
a[j] : =false
/ * j is divisible by i */
end ;
print count
end
(a) Translate the above program into three address statements assuming a is al-
located static storage.
(b) Construct a flow graph from the three address statements and indicate the
back edges and their natural loops
7.Explain the following in detail:
(a) Copy Propagation
(b) Live variables analysis
8.(a) What is a data flows Equation? Explain with an example
(b) Explain how data flows Equations are setup and how they are solved
9.For the flow graph as shown in figure 1 compute:
(a) Live variables at the end of each block
(b) Is any constant folding possible? If so, do it
(c) Are there any common sub expressions? If so, eliminate them
(d) ud and du chains
10.(a) Explain live variable analysis with example.
(b) Explain redundant sub expression elimination with example
11. Consider following code:
begin
read n;
for i=1 to n do
a[i]=true;
count=0;
1
for i=2 to n**5 do
if a[i] then
begin
count=count+1;
for j=2* i to n by i do
a[j]=false
end
print count
end
Generate three address code and draw flow graph. What optimizations can be
performed? Generate an optimized code
13.(a) Write and explain live variable analysis algorithm.
(b) Explain the use of algebraic transformations with an example
14.(a) Generate the flow-graphs for the following expressions:
S-> id: = E |S; S| if E then S else S | do S while E
E-> id + id |id
(b) Mention data-flow equations for reaching definitions for the above expressions
15.(a) Give an algorithm to compute.
i. Available expressions.
ii. Live variables for the language with pointers.
(b) Prove that \depth of a reducible flow graph is never less than the number of
times interval analysis must be performed to produce a single node."
16.a) Write the procedure to detect induction variable with example.
(b) With example explain dead code elimination.
17.Explain data flow analysis. Compute in and out for the following figure
18.a) Explain reducible and non-reducible flow graphs with an example.
(b) Explain natural loops and inner loops of a flow graph with an example
19.(a) What is an Induction variable? Explain with an example.
(b) Discuss how induction variables can be detected and how transformation can
be applied.
20.Explain the following:
(a) Common sub-expression elimination
(b) Dead-code elimination
(c) Renaming of temporary variables
(d) Interchange of two independent adjacent statements
21.a) What is global data flow analysis?
(b) Write briefly about various loop optimization techniques
Unit 8
**1.a) Explain the concept of object code forms.
(b) Generate optimal machine code for the following C program. [6+10]
main()
{
int i, a[10];
while (i<=10) a[i] =0
}
2. (a) Write an algorithm for generating code from a labeled tree.
(b) Construct a DAG for the following program code:
x=y*z
w=p+y
y=y*z
p=w-x .
3. (a) Explain the different issues in the design of a code generator.
(b) Generate code for the following C statements:
i. x= f(a) + f(a) + f(a)
ii. x= f(a) /g(b,c)
iii. x= f(f(a))
iv. x= ++f(a)
4.(a) Write about global register allocation strategy for loops.
(b) Explain code generation from DAG. For the following instructions construct
DAG.
t1:=a / b
t2:=a/b
t3:=e - t2
t4:=t1 -t3
t5:=e+t2
t6:=t4 * t5.
}
*5.(a) What are the various problems that arise in generating good code? Briefly
explain them
(b) “Good Code generation requires an intimate knowledge of target machine”.
Justify the statement with an appropriate example
6(a) Explain the different issues in the design of a code generator.
(b) Generate code for the following C statements:
Figure 1:
i. x= f(a) + f(a) + f(a)
ii. x= f(a) /g(b,c)
iii. x= f(f(a))
iv. x= ++f(a) [8+8]
7.a) Write about the issues in the design of code generator.
(b) Write about target code forms. Explain how the instruction forms effect the
computation time.
8.a) Describe, how addressing modes can be used for reducing the memory access
time
(b) Generate the code sequence using Code generation algorithm for the following
expression [8+8]
W:=(A-B)+(A-C)+(A-C)
Combine CD question
1. Define the following terms.
(a) Reaching definition.
(b) Live variables.
(c) Flow graphs.
(d) Global optimization. [16]
2. Write the procedure for identifying the basic blocks with example. For the same
example draw domination tree. [16]
3. Explain activation tree and draw activation tree for any sorting method. [16]
4. What is a basic block? With an example explain the procedure to identifying basic
blocks in a given program. [16]
5. Explain the terms.
(a) Activation record.
(b) Activation trees.
(c) Block structure.
(d) Non block structured languages.
6. Describe the procedure to compute in and out values using data flow equations for
reaching definition in structured programs
7. Explain activation trees and draw activation tree for quick sort program
8. (a) What is next use information explain in detail.
(b) Write about target code forms. Explain how the target code can be generated
.
9. Explain code-improving transformation techniques with suitable examples. [16]
10. Write short notes on following terms:
(a) Derivation.
(b) Ambiguity.
(c) Parse tree.
(d) LL(k) grammar.
11.Write a short note on following terms:
(a) NFA
(b) Regular expressions
(c) Transition diagram
(d) Token.
12.Consider following:
program main(input, output);
procedure p(x,y,z);
begin
y:=y+1;
z:=z+x;
end
begin
a:=2;
b:=3;
p(a+b,a,a);
print a;
end
what will be the output, if:
(a) call by value.
(b) call by reference.
(c) copy restore linkage.
(d) call by name.
are used
13.(a) Give an algorithm to compute reaching definitions interprocedurally.
(b) Give an algorithm for eliminating global common subexpression
14.Write short notes on following:
(a) Activation record.
(b) Dynamic scope.
(c) Call by copy restore.
(d) Access links.
15.Write short notes on following terms:
(a) dominators.
(b) natural loops.
(c) inner loops.
(d) preheaders.
16.(a) Consider the following declaration grammar & write the translation scheme
for identifying the type of the identifier:
P -> D;E
D -> D;D/id : T
T -> char/int/ *T/array[num]ofT
Find the type of each entry.
.(b) Generate code for the following C statements. Assume all the variables are
Static,automatic and three registers are available:
i. x=a+b*c
ii . x=a/(b+c)-d*(e+f)
(a) x=a+b*c (b) x=a/(b+c)-d*(e+f) (c) a[i][j]=b[i][k]*c[k][j] (d) a[i]+=b[j] [16]
17.(a) Generate code for following c program:
main()
f int i;
int a[10];
while(i < = 10)
a[i]=0;
g
(b) Explain the register allocation by graph coloring
18. (a) How will you generate the intermediate code for the flow of control statements?
Explain with examples.
(b) Translate the following assignment into intermediate code
A[I,J]: = B[I,J] + C[A[K,L]]+ D[I+J]
19.(a) Define the following:
i. Basic Block
ii. Local Optimization
iii. Global Optimization Explain about Generic code generation algorithm.
b) Explain about Algebraic Transformations?
211. Explain the following concepts:
(a) Next-use information
(b) Register descriptors
(c) Address descriptors.
(d) Register interference [4+4+4+4]
22. (a) What is loop invariant operation? Write an algorithm for detecting loop in-
variant computations.
(b) Consider the following program fragment code:
int p=1, k=0, n;
while(k<n)
f
p=2*p;
k=k+1;
Apply the invariant operation elimination on the above program segment
23. State and explain different machine dependent code optimization techniques.
24.(a) Write a S - attributed grammar to connect the fopllowing grammar with prefix
rotator
L -> E
E -> E+T | E-T | T
T -> T*F | T/F | F
F -> P " F | P
P -> (E)
P -> id.
(b) Construct triples of an expression: a * −(b + c).
Prepared by Kiran Kumar Varaka Asso Professor,MRIT
Click Here To Download All 8 Units Important Questions
UNIT I
1. (a) Explain, in detail, lexical analyzer generator.
(b) Describe the lexical errors and various error recovery strategies with suitable
examples.
2. (a) Consider the following fragment of ‘C’ code:
float i, j;
i = i * 70 + j + 2;
.Write the output at all phases of the compiler for the above ‘C’ code.
Explain the input buffer scheme for scanning the source program. How the use of
sentinels can improve its performance? Describe in detail.
(b) Write short notes on: input buffering.
3.(a) Write a regular expressions and NFA for the following patterns. Use auxiliary
definitions where convenient?
i. The set of words having a, e, i, o, u appearing in that order, although not
having necessarily consecutively.
ii. Comments in C.
(b) Differentiate Interpreter & Compiler?
**4.Describe various phases of a compiler? Differentiate a phase and pass? Compare
multipass and single pass compiler?
***5. Explain with one example how LEX program perform lexical analysis for the follow-
ing patterns in `C': identifier, comments, numerical constants, arithmetic operators.
6.(a) Construct an NFA for regular expression R= (aa/b)*ab convert it into an
equivalent DFA
(b) Write a LEX program for identifying the keywords and identifiers from the
file?
*7.(a) Explain the different phases of a compiler, showing the output of each phase,
using the example of the following statement:
position : = initial + rate * 60
(b) Compare compiler and interpreter with suitable diagrams.
**8.(a) Explain the different phases of a compiler, showing the output of each phase
using the example for the statement:
x=(a+b) * (c+d)
(b) Write short notes on bootstrapping process.
9.State the steps to convert a regular expression to NFA. Explain with an example
(a) Construct an NFA for regular expression R= (aa/b)*ab convert it into an
equivalent DFA
(b) Write a LEX program for identifying the keywords and identifiers from the
file?
10.(a) Explain the bootstrapping process with suitable diagrams.
(b) Explain how input buffering helps lexical analyzer in compilation process
11.Explain the input buffer scheme for scanning the source program. How the use of
sentinels can improve its performance? Describe in detail.
12.a) What is LEX? Explain, in detail, different sections of LEX program.
(b) Write regular expressions for the following patterns. Use auxiliary definitions
wherever convenient.
13.i. the set of words having a,e,i,o,u appearing in that order, although not
necessarily consecutively.
ii. comments in C.
14.(a) What is regular expression? Write regular expressions for the following pat-terns: identifiers and float constants.
(b) Define lexeme, token and pattern. Identify the lexemes, that make up thetokens in the following program segment. Indicate corresponding token andpattern. [6+10]
void swap(int i, int j)
{
int t;
t=i;
i=j;
j=t;
}
15. (a) Consider the following fragment of `C' code:
oat i, j;
i = i * 70 + j + 2;
Write the output at all phases of the compiler for the above `C' code.
(b) Write short notes on: input buffering.
Unit2
.1. (a) Construct recursive descent parser for the following grammar.
E -> T E’
E’ -> +T E’|e
T -> F T’
T’ -> *FT’|e
F -> (E)|id
(b) Eliminate ambiguities in the following grammar.
S -> iEtS| iEtSeS| a
E -> b| c | d
**2. (a) What are the difficulties in top down parsing? Explain in detail.
(b) Consider the following grammar
S -> (L) |a
L -> L, S |S
Construct leftmost derivations and parse trees for the following sentences:
i. (a,(a,a))
ii. (a,((a,a),(a,a))).
3.(a) Construct predictive parse table for the following grammar.
E -> E + T/T
T -> T *F/F
F -> F /a/b
(b) What are the limitations of recursive descent parser
(a) What are the common conicts that can be encountered in shift - reduce
parser.
(b) Construct SLR parsing table for the following grammar.
R -> R’/ ‘R /RR /R* /(R) /a /b
4.(a) Convert the following grammar into LL(1) grammar
b) construct LL(1) parse table for the above grammer
S→ ABC A →a A| C B → b C → c
5. (a) What is the string generated by the grammar A -> (A)A
(b) Explain the basic method of LL(1) parsing and hence explain how very simple
grammar generates strings of balanced parentheses.
6.a) Give the rules for computation of FIRST(X) and FOLLOW(X). Construct
FIRST and FOLLOW sets for the following grammar.
E -> T E’
E’ -> +T E’|e
T -> F T’
T’ -> *FT’|e
F -> (E)|id
(b) Write an algorithm for construction of predictive parsing table.
1.Construct SLR parsing table for the following grammar.
S -> AS/b
A -> SA/a
7.Construct SLR parsing table for following grammar:
E -> E + T/T
T -> T * F/F
F -> (E)/id.
8.(a) What is CFG? Explain in detail.
(b) Write short notes on following terms:
i. Parse tree.
ii. LL(k) grammar.
9.(a) Write the algorithm for predictive parsing.
(b) Explain error recovery in predictive parsing.
. Construct LL(1) parse table for the following grammar.
b exp r -> b exp r or bterm / bterm
bterm -> bterm and bfactor / bfactor
b factor -> not bfactor ->(b exp r) /true /false
where or, and, not, (,), true, false are terminals in the grammar.
10.a) \Top down parsing is also considered as LMD derivation". Justify the given
statement.
(b) Verify whether string \id+(id+id)" is accepted by following grammar or not
by using predictive parsing:
E -> TE’
E’ -> +TE’/ e
T -> FT’
T’ -> *FT’/ e
F -> (E)/id.
11.(a) What are the merits & demerits of recursive descent parsing.
(b) Explain predictive parsing in detail.
12.(a) Explain recursive descent parsing in detail.
(b) State the rules to compute FIRST(X) & FOLLOW(X).
13. (a) What is left recursion? Remove left recursion from following grammar:
S -> Aa/b
A -> Ac/Sd/ e
(b) Check for LL(1) for following grammar:
prog -> begin d semi X end
X -> d semi X/sY
Y -> semi s Y/2.
14.(a) Consider the following grammar.
S -> 0A/1B/0/1
A -> 0S/1B/1
B ->. 0A/1S
Construct leftmost derivations and parse trees for the following sentences
i. 0101
ii. 1100101
(b) Consider the following grammar
E -> T + E/T
T -> V*T/V
V -> id
Write down the procedures for the non-terminals of the grammar to make a
recursive descent parser.
15.(a) Explain the following top-down parsing methods with Example?
(b) Recursive - Decent parsing
c) Predictive Parser
16.a) Draw the syntax tree for the following expression a : = b * - c + b * - c
(b) Write the postfix notation and three address code for the following expression
i. ( - ( a + b ) * ( c + d ) + ( a + b + c ) )
17.(a) What is recursive descent parser? Construct recursive descent parser for the
following grammar.
E -> E + T|T
T -> TF|F
F -> F_|a|b
(b) What is ambiguous grammar? Eliminate ambiguities for the grammar:
E -> E + E|E*E|(E)|id.
18.Construct the SLR(1) parse table for the following grammar:
S -> xAy |xBy| xAz
A -> aS |q
B -> q.
19.. (a) What is an LL(1) parse table? Explain.
(b) Build an LL(1) parse table for the following production grammar:
S -> CC
C -> cC| d.
20.construct predictaive parsing table for given
E -> T E’
E’ -> +T E’|e
T -> F T’
T’ -> *FT’|e
F -> (E)|id
Unit3
**1. (a) Define LR(k) parser. Draw and explain model of LR parser.
(b) Write LR parsing algorithm.
2. (a) Explain the stack implementation of shift reduce parsing method with an
example.
(b) Define handle. Give suitable example.
3. Construct Canonical LR parsing table for the following grammar
S -> CC
C -> cC/d
4. Define precedence functions. Construct precedence table and directed graph rep-
resenting precedence functions for operators +, *, id, $. [
5. (a) What are the actions of shift-reduce parsers?
(b) Construct SLR parsing table for the following grammer.
6.Construct LALR parsing table for the following grammar.
A′ -> A
A -> (A)
A -> a
7.(a) Construct LALR parsing table for the following grammar
S - > CC
C - > cC/d
(b) What do you mean by left most derivation. Explain with an example
**8.Give the algorithm to generate the canonical collection of LR(0) items
9.(a) What is an SLR Grammar?
(b) Construct LALR(1) Parse table from the following grammar
S-> Aa/bAc/dc/bda:.
*10..What is an ambiguous grammar? With an example illustrate how we can not
uniquely parse a given sentence for an ambigious grammar
*11.a) What is an LR(0) item? Write an LR(0) item for the production A !2.
(b) Construct LR(0) parser for the following grammar:
S0 -> cA|ccB
A -> cA|a
B -> ccB|b.
10. Construct a DFA whose states are the canonical collection of LR(1) items for the
following augmented grammer:
S ->A
A->BA|e
B -> aB |b
**11.C onstruct LALR Parsing table for the following grammar
S -> Aa|bAc|Bc|bBa
A ->d
B -> d
12.Construct LALR parsing table for the following grammar
S -> A S|b
A -> S A|a
13.a) Consider following grammar:
S ->1S0/0S1/10
Is this grammar SLR(1) or not.
(b) Distinguish between CLR & LALR parsing
14.(a) Find the precedence functions for following grammar:
E -> E + E/E * E/(E)/id
(b) What is the significance of look ahead symbol in parsing process
(a) Explain error recovery in LR parsing.
(b) Remove ambiguity from following grammar:
R -> R'/'R / RR/R*/(R)/a/b.
15.(a) Find the precedence functions for following grammar:
E -> E + E->E * E/(E)/id
(b) Explain error recovery in LR parsing
16.Construct SLR parsing table for following grammar:
E -> E + T/T
T -> T * F/F
F -> (E)/id.
17.(a) Construct LALR parsing table for the following grammar:
S -> Aa/bAc/dc/bda
A -> d
18.Show the moves of this parser on input bda.
(b) Consider following grammar:
S -> 1S0/0S1/10
Is this grammar SLR(1) or not.
19.Give the algorithm to generate the canonical collection of LR(0) items.
20. (a) What is next use information explain in detail.
(b) Write about target code forms. Explain how the target code can be generated
from the given three address code.
21.(a) What is meant by a parser generator? Illustrate with examples using YACC
(b) Mention the error recovery strategies of parser.
22. (a) Write a short notes on token speci_cation.
(b) Draw a NFA for a */ b *.
(c) Convert the above (b) to DFA.
23.Explain shift-reduce parsing. Illustrate with examples.
24.(a) Explain LALR parsing, justify how it is efficient over SLR parsing
(b) Find the moves made by the LR(1) parser on the input string: aabb
25.a) What is an operator grammar? Give an example.
(b) Write an operator precedence parsing algorithm
26.Consider the grammar: S -> (S) |a
Construct the DFA for SLR(1), CLR(1), and LALR(1) parsers and find the number of states in each of the parser.
27.Construct the LR(1) parse table for the following augmented grammar:
S’-> S
S -> BB
B->bB |c. [16]
28.(a) Explain canonical LR parsing.
(b) Explain briefly, precedence functions. construct the precedence graph using
the following prededence table. [8+8]
+ * ( ) id $
f 2 3 0 4 4 0
g 1 3 5 0 5 0
Unit 4
**1. (a) Write a note on the specification of a simple type checker.
(b) What is a type expression? Explain the equivalence of type expressions with
an appropriate examples.
**2.(a) Draw syntax tree for the arithmetic expressions
A*(b + c) − d/2
Also write the given expression in postfix notation.
(b) Write the quadruple, triple, indirect triple for the following expression
(x + y)*(y + z) + (x + y + z)
3. (a) Describe the overloading of functions and operators with suitable examples.
(b) Write a note on polymorphic functions.
4. Write type expressions for the following types.
(a) An array of pointers to reals, where array index ranages from 1 to 100.
(b) A two dimensional array of integers (i.e. an array of array) whose rows are
indexed from 0 to 9 and whose columns are indexed from -10 to 10.
(c) Functions whose domains are functions from integers to pointers to integers
and whose ranges are records consisting of an integer and a character
5.(a) Write the quadruples, triples and indirect triples for the expression
i. ( a + b ) *(c + d ) *( a + b + c )
ii. a * ( b + c )
1
S→ AS | b
A → SA | a
(b) Write a top-down translation scheme to produce quadruples for Boolean Ex-
Pression
6.a) Why are quadruples preferred over triples in an optimizing compiler. Explain
(b) Give the triple representation of an array operation x : = y [ i ]
(c) Give the syntax directed definition of if else statement.
7. (a) Write the three-address code for the following code.
fact(x)
f int f=1;
for (i=2, i >=x, i++)
f
f=f*i;
return f;
(b) Write an algorithm for identifying leaders and partition the code into basic
8. (a) Translate the following code segment into quadruples.
While A C and B D
if A=1 then C = C+1
else while A = D do A = A+2 from the given three address code
(b) Explain the different statements allowed in TAC with examples.
9.a) Write a note on the specification of a simple type checker.
(b) What is a type expression? Explain the equivalence of type expressions with
an appropriate examples.
10.a) Write the quadruple, triple, indirect triple for the statement a := b* − c + b* − c.
(b) Explain the role of intermediate code generator in compilation process.
11.a) What is back patching?
(b) Explain back patching with reference to the three address code generated for
the expression p > q andq < t.
12.(a) Write a short note on type equivalence.
(b) Write a short note on type checking
13.(a) Write a short note on abstract syntax tree.
(b) Compare and contrast the quadruples, triples & indirect triples
14. (a) Write a short note on L-attributed grammars.
(b) It is required to compute the total number of reductions performed to parse
a given input. Using synthesized attributes only write the semantic rules to
find E.red, the number of reductions performed while reducing on input to E.
E -> E * T/T
T -> F - T/F
F ->2/4
Also draw annotated tree for 4-2-4*2.
*15.a) Consider following grammar:
E -> num.num/literal/num/E%E/E+E/ E`/'E/ E*E/ E[E]
Construct semantic rules to find type of expression.
(b) Give an algorithm to test the equivalence of C types
16.(a) Write about type checking. Consider following C declarations:
typedef struct
f
int a, b;
gCELL,*PCELL;
CELL foo[100];
PCELL bar(x,y)
int x;
CELL y f..g
Write type expressions for the types of foo and bar.
(b) Write a short note on type checking.
17.(a) Compare and contrast the quadruples, triples & indirect triples.
(b) Write the translation schemes for addressing array elements for following grammar:
S -> L := E
E -> E + E/(E)/L
L -> Elist]/id
Elist -> Elist,E
Elist -> id [ E
18.(a) Consider following expression grammar:
S -> E
E -> E + E/E * E/(E)/I
I -> Idigit/digit
Digit -> 0=1=2=::::=9
Write semantic rules to evaluate expression on decimal numbers that it de-
rives. Use `val' attribute for storing the values & constant parse tree for
2*(21+1)+10. Find S.val.
(b) What is the significance of syntax- directed definition
19.Consider following grammar,
E -> E + E/E * E/literal/num/id/EmodE/E[E]/ *E/float
Write semantic rules to compute type of expression
20.a) Distinguish between synthesized & inherited attributes.
(b) Write a short note on abstract syntax tree
21.(a) Write an algorithm for elimination of induction variable.
(b) Write a C program to compute sum of digits of a number and convert it into
three address code. And generate ow graph.
22.a) What is the main purpose of semantic analysis?
(b) Write about three address code? Give examples
23.a) Write a short note on type equivalence.
(b) Write a short note on type checking
24.(a) Write an algorithm for partitioning a sequence of three-address statements
into basic blocks.
(b) Apply the algorithm for the following three-address code :
i. t1:= 4_i
ii. t2:= a[t1]
iii. t3:= 4_I
iv. t4:= b[t3]
v. t5:= t2*t4
vi. t6:= prod +t5
vii. prod:= t6
viii. t7:= i+1
ix. i:= t7
x. if i<=20 goto (1). [8+8]
25.(a) Consider following grammar & identify the type of subexpression. Use type
error as a type expression in error condition.
E -> literal/num/id/EmodE/E[E]/ * E
(b) Write about type checking. Consider following C declarations:
typedef struct
f
int a, b;
gCELL,*PCELL;
CELL foo[100];
PCELL bar(x,y)
int x;
CELL y f..g
Write type expressions for the types of foo and bar.
(26.a) What is dependency graph? What is its significance?
(b) Translate the expression (a+b)*(c+d)+(a+b+c) into.
i. Quadruples.
ii. Triples.
iii. Indirect triples.
iv. Syntax
27.a) Compare and contrast the quadruples, triples & indirect triples.
(b) What is the significance of syntax- directed definition
tree.
28.a) Construct operator precedence parse table for the below grammar.
S- > iEts/iEtSeS/a
E- > b/c/d:
b) Eliminate Ambiguity for above grammar
29.(a) Construct an abstract syntax tree for the following expression:
if a = b then a := c + d else b := c - d
(b) Generate three-address code for the following Boolean expression:
P < Q OR R < S AND T < U .
30.a) Translate the following code segment into Quadruples.
While A < C and B < D
if A=1 then C:= C+1
else while A <= D do A:= A+2
(b) Explain the different statements allowed in TAC with examples
31.(a) Write the quadruples, triples and indirect triples for the expression
i. ( a + b ) *(c + d ) ( a + b + c )
ii. a * ( b + c )
(b) Write a top-down translation scheme to produce quadruples for Boolean Ex-
pression.
32.Generate the code for the following C statements using its equivalent three address
code.
(a) a = b + 1
(b) x = y+3
(c) y = a/b
(d) a = b+c.
33.Write short notes on the following:
(a) S-attributed definitions.
(b) L-attributed definitions.
(c) Dependency graph.
34.(a) Write a note on the specification of a simple type checker.
(b) What is a type expression? Explain the equivalence of type expressions with
an appropriate examples.
35.Generate the three-address code for the following ?C? program fragment: [16]
while(a > b)
{
if (c < d) x = y + z;
else x = y - z;
}
36.(a) What is a Syntax Directed Translation Scheme? Explain with an example.
(b) Design an abstract syntax tree for the expression: a = (a[i+1] = 2) + a[j].
37.What is Type Expression? Write type Expressions for the following type
i. A Two dimensional array integers (i.e. an array of arrays) whose rows are
indexed from 0 to 9 and whose columns are indexed from -10 to 10.
(b) What is Type System? Discuss static and dynamic Checking of types?
38.(a) Write the three-address code for the following code.
begin
PROD: = 0;
I: =1;
do
begin
PROD:=PROD + A[I]∗B[I];
I:=I+1;
End
while I<=20
end
Unit 5
**1. (a) What is an ordered and unordered symbol table? What is the function of
symbol table in the compilation process? Explain.
(b) What are the various attributes of a Symbol Table? [10+6]
**2.(a) Compare three different storage allocation strategies.
(b) Consider the following array declaration in ‘c’;
float a[100][100];
Assume that the main memory in byte addressable and that the array is stored
starting from the memory address 100. What is the address of a[40][50]
**3.a) what is an ordered and unordered symbol table what is function of symbol of table in compilation of process?
b)what are various of symbols of table?
4.(a) Explain the hash table with temporary and permanent storage.
(b) Reusing the storage space for names.
5.Explain symbol table organization using hash tables? Construct hash based struc-
ture for symbol table for the variable in the following program.
int main()
f
int a1, a2, c1, c2;
char b1;
float d1, d2;
|-
|{
6. What is a symbol table? Explain the need for symbol table organization and the
data structures used for implementing a symbol table.
7.a) Describe the method to obtain faster access to nonlocals.
(b) Describe the facilities provided by languages for dynamic allocation of storage
of data.
8.(a) Discuss various object code forms.
(b) Explain the register allocation by graph coloring
9.(a) Compare and contrast various storage allocation strategies.
(b) Consider following pseudo program and find the result if the arguments are
passed by call-by- value, call by reference & call by value result.
begin int a
proc p(b); int b
begin b=b+1; print(b,a) end
a=1
p(a)
print(a)
end.
Explain how storage allocation is done for arrays, strings and records?
10.(a) What is the use of Symbol table in compilation process? List out various
attributes stored in the symbol table.
(b) Explain different schemes of storing name attribute in symbol table.
**11.Explain symbol table organization using hash tables? With an example show the
symbol table organization for block structured language.
**12.Explain DAG and its use. Write the procedure to construct the DAG for a state-
ment. [
.**13. What are the various operations performed on the symbol table? Explain each of
them in detail.
**14.(a) What is an activation record? Explain how it is related with runtime storage
organization?
(b) Write and explain about heap allocation strategy?
15.a) Explain the Dynamic storage allocation facilities provided by C language?
(b) What is dangling reference in storage allocation? Explain with an example
Unit 6
1. Explain different principal sources of optimization technique with suitable exam-
ples. [16]
2.Apply loop optimization and code motion for the following program code. begin
for i := 1 to n do
for j:=1 to n do
c[i, j] :=0;
for i := 1 to n do
for j:=1 to n do
1 of 2
for k :=1 to n do
c[i, j] :=c[i , j] +a[i ,k] *b [k ,j]
end
3. (a) What is DAG? Construct the DAG for the following basic block
D := B_C
E :=A+B
B := B+C
A := E-D
(b) What are the legal evaluation orders and names for the values at the nodes
for the DAG of problem (a).
i. Assuming A, B and C are alive at the end of the basic block?
ii. Assuming only A is live at the end?
4. (a) What is loop invariant operation? Write an algorithm for detecting loop in-
variant computations.
(b) Consider the following program fragment code:
int p=1, k=0, n;
while(k<n)
{
p=2*p;
k=k+1;
} Apply the invariant operation elimination on the above program segment
*6.Explain machine dependent code optimization with example
7.Write the importance of global code optimization. Explain redundant sub expres-
sion elimination technique across di_erent blocks with example
**8.Explain with example the various techniques in loop optimization
**9.Explain different principal sources of optimization technique with suitable exam-
ples.
10.. Describe, in detail, about the concept of DAG for register allocation with an ap-propriate example.
11. Explain DAG and its use. Write the procedure to construct the DAG for a state-
ment. [16]
12.a) What is code optimization? What are its advantages?
(b) Explain briefly about folding.
(c) What are the problems in optimizing compiler design?
13 a) Give the applications of DAG.
(b) Generate code for the following C statements:
i. x=++f(a)
ii. *p++=*q++.
14.a) Write the code sequences for indexed and pointer assignments.
(b) Discuss DAG representation of basic block
15. (a) Discuss loop optimization techniques.
(b) What are reducible flow graphs? Explain with examples
15. (a) Write an algorithm to implement the elimination of redundant subexpressions
in constructing a DAG?
(b) Construct the DAG for the following code:
A[I]:=B
*P := C
D:=A[J]
E:= *P
*P:=A[I]
Assume that
i. P can point anywhere,
ii. P points to only B or D.
Do not forget to show the implied order constraints. [8+8]
16 (a) Generate code for the following C statements. Assume all variables are static
and three registers are available:
i. x=a[i]+1
ii. a[i]=b[c[i]]
(b) Give the applications of DAG.
17.(a) Write the procedure for constructing the DAG.
(b) For the following basic block construct DAG.
d = b * c;
e = a * b;
b = b + c;
c = b * c;
18.(a) Explain DAG and its use.
(b) For the following statements draw the DAG.
t8 = d + e
t6 = a + b
t5 = t6 - c
t4 = t5 * t8
t3 = t4 - e
t2 = t6 + t4
t1 = t2 * t3
19.a) Explain peephole optimization with example.
(b) Explain the procedure for constructing DAG with example. Write the appli-
cations of DAG.
20.(a) What is code optimization? What are its advantages?
(b) Explain briefly about folding.
(c) What are the problems in optimizing compiler design
21.(a) What is DAG? Construct the DAG for the following basic block
D := B∗C
E :=A+B
B := B+C
A := E-D
(b) What are the legal evaluation orders and names for the values at the nodes
for the DAG of problem (a).
i. Assuming A, B and C are alive at the end of the basic block?
ii. Assuming only A is live at the end?
22.(a) Write an algorithm for generating code from a labeled tree.
(b) Construct a DAG for the following program code:
x=y*z
w=p+y
y=y*z
p=w-x
Unit 7
1. Describe, how redundant expression elimination can be done in loop optimization
technique, during global optimization. [16]
2. Consider the following program which counts the primes form 2 to n using the sieve
method on a suitably large array
begin
read n
for i : = 2 to n do
a[i] : = true / * initialize */
count: = 0;
for i : 2 to n ** .5 do
if a [i] then /* i is a prime */
begin
count := count +1
for j : = 2 * i to n by i do
a[j] : =false
/ * j is divisible by i */
end ;
print count
end
(a) Propagate out copy statements wherever possible.
(b) Is loop jumping possible? If so, do it.
(c) Eliminate the induction variables wherever possible
3. (a) What is an Induction variable? Explain with an example.
(b) Discuss how induction variables can be detected and how transformation can
be applied.
4. Describe, how redundant expression elimination can be done in loop optimization
technique, during global optimization.
5.Explain about global data flow analysis. List data flow equations for reaching definitionin structure
blocks and apply it on the above derived three-address code
6. Consider the following program which counts the primes form 2 to n using the Sieve
method on a suitably large array
begin
read n
for i : = 2 to n do
a[i] : = true / * initialize */
count: = 0;
for i : 2 to n ** .5 do
if a [i] then /* i is a prime */
begin
count := count +1
for j : = 2 * i to n by i do
a[j] : =false
/ * j is divisible by i */
end ;
print count
end
(a) Translate the above program into three address statements assuming a is al-
located static storage.
(b) Construct a flow graph from the three address statements and indicate the
back edges and their natural loops
7.Explain the following in detail:
(a) Copy Propagation
(b) Live variables analysis
8.(a) What is a data flows Equation? Explain with an example
(b) Explain how data flows Equations are setup and how they are solved
9.For the flow graph as shown in figure 1 compute:
(a) Live variables at the end of each block
(b) Is any constant folding possible? If so, do it
(c) Are there any common sub expressions? If so, eliminate them
(d) ud and du chains
10.(a) Explain live variable analysis with example.
(b) Explain redundant sub expression elimination with example
11. Consider following code:
begin
read n;
for i=1 to n do
a[i]=true;
count=0;
1
for i=2 to n**5 do
if a[i] then
begin
count=count+1;
for j=2* i to n by i do
a[j]=false
end
print count
end
Generate three address code and draw flow graph. What optimizations can be
performed? Generate an optimized code
13.(a) Write and explain live variable analysis algorithm.
(b) Explain the use of algebraic transformations with an example
14.(a) Generate the flow-graphs for the following expressions:
S-> id: = E |S; S| if E then S else S | do S while E
E-> id + id |id
(b) Mention data-flow equations for reaching definitions for the above expressions
15.(a) Give an algorithm to compute.
i. Available expressions.
ii. Live variables for the language with pointers.
(b) Prove that \depth of a reducible flow graph is never less than the number of
times interval analysis must be performed to produce a single node."
16.a) Write the procedure to detect induction variable with example.
(b) With example explain dead code elimination.
17.Explain data flow analysis. Compute in and out for the following figure
18.a) Explain reducible and non-reducible flow graphs with an example.
(b) Explain natural loops and inner loops of a flow graph with an example
19.(a) What is an Induction variable? Explain with an example.
(b) Discuss how induction variables can be detected and how transformation can
be applied.
20.Explain the following:
(a) Common sub-expression elimination
(b) Dead-code elimination
(c) Renaming of temporary variables
(d) Interchange of two independent adjacent statements
21.a) What is global data flow analysis?
(b) Write briefly about various loop optimization techniques
Unit 8
**1.a) Explain the concept of object code forms.
(b) Generate optimal machine code for the following C program. [6+10]
main()
{
int i, a[10];
while (i<=10) a[i] =0
}
2. (a) Write an algorithm for generating code from a labeled tree.
(b) Construct a DAG for the following program code:
x=y*z
w=p+y
y=y*z
p=w-x .
3. (a) Explain the different issues in the design of a code generator.
(b) Generate code for the following C statements:
i. x= f(a) + f(a) + f(a)
ii. x= f(a) /g(b,c)
iii. x= f(f(a))
iv. x= ++f(a)
4.(a) Write about global register allocation strategy for loops.
(b) Explain code generation from DAG. For the following instructions construct
DAG.
t1:=a / b
t2:=a/b
t3:=e - t2
t4:=t1 -t3
t5:=e+t2
t6:=t4 * t5.
}
*5.(a) What are the various problems that arise in generating good code? Briefly
explain them
(b) “Good Code generation requires an intimate knowledge of target machine”.
Justify the statement with an appropriate example
6(a) Explain the different issues in the design of a code generator.
(b) Generate code for the following C statements:
Figure 1:
i. x= f(a) + f(a) + f(a)
ii. x= f(a) /g(b,c)
iii. x= f(f(a))
iv. x= ++f(a) [8+8]
7.a) Write about the issues in the design of code generator.
(b) Write about target code forms. Explain how the instruction forms effect the
computation time.
8.a) Describe, how addressing modes can be used for reducing the memory access
time
(b) Generate the code sequence using Code generation algorithm for the following
expression [8+8]
W:=(A-B)+(A-C)+(A-C)
Combine CD question
1. Define the following terms.
(a) Reaching definition.
(b) Live variables.
(c) Flow graphs.
(d) Global optimization. [16]
2. Write the procedure for identifying the basic blocks with example. For the same
example draw domination tree. [16]
3. Explain activation tree and draw activation tree for any sorting method. [16]
4. What is a basic block? With an example explain the procedure to identifying basic
blocks in a given program. [16]
5. Explain the terms.
(a) Activation record.
(b) Activation trees.
(c) Block structure.
(d) Non block structured languages.
6. Describe the procedure to compute in and out values using data flow equations for
reaching definition in structured programs
7. Explain activation trees and draw activation tree for quick sort program
8. (a) What is next use information explain in detail.
(b) Write about target code forms. Explain how the target code can be generated
.
9. Explain code-improving transformation techniques with suitable examples. [16]
10. Write short notes on following terms:
(a) Derivation.
(b) Ambiguity.
(c) Parse tree.
(d) LL(k) grammar.
11.Write a short note on following terms:
(a) NFA
(b) Regular expressions
(c) Transition diagram
(d) Token.
12.Consider following:
program main(input, output);
procedure p(x,y,z);
begin
y:=y+1;
z:=z+x;
end
begin
a:=2;
b:=3;
p(a+b,a,a);
print a;
end
what will be the output, if:
(a) call by value.
(b) call by reference.
(c) copy restore linkage.
(d) call by name.
are used
13.(a) Give an algorithm to compute reaching definitions interprocedurally.
(b) Give an algorithm for eliminating global common subexpression
14.Write short notes on following:
(a) Activation record.
(b) Dynamic scope.
(c) Call by copy restore.
(d) Access links.
15.Write short notes on following terms:
(a) dominators.
(b) natural loops.
(c) inner loops.
(d) preheaders.
16.(a) Consider the following declaration grammar & write the translation scheme
for identifying the type of the identifier:
P -> D;E
D -> D;D/id : T
T -> char/int/ *T/array[num]ofT
Find the type of each entry.
.(b) Generate code for the following C statements. Assume all the variables are
Static,automatic and three registers are available:
i. x=a+b*c
ii . x=a/(b+c)-d*(e+f)
(a) x=a+b*c (b) x=a/(b+c)-d*(e+f) (c) a[i][j]=b[i][k]*c[k][j] (d) a[i]+=b[j] [16]
17.(a) Generate code for following c program:
main()
f int i;
int a[10];
while(i < = 10)
a[i]=0;
g
(b) Explain the register allocation by graph coloring
18. (a) How will you generate the intermediate code for the flow of control statements?
Explain with examples.
(b) Translate the following assignment into intermediate code
A[I,J]: = B[I,J] + C[A[K,L]]+ D[I+J]
19.(a) Define the following:
i. Basic Block
ii. Local Optimization
iii. Global Optimization Explain about Generic code generation algorithm.
b) Explain about Algebraic Transformations?
211. Explain the following concepts:
(a) Next-use information
(b) Register descriptors
(c) Address descriptors.
(d) Register interference [4+4+4+4]
22. (a) What is loop invariant operation? Write an algorithm for detecting loop in-
variant computations.
(b) Consider the following program fragment code:
int p=1, k=0, n;
while(k<n)
f
p=2*p;
k=k+1;
Apply the invariant operation elimination on the above program segment
23. State and explain different machine dependent code optimization techniques.
24.(a) Write a S - attributed grammar to connect the fopllowing grammar with prefix
rotator
L -> E
E -> E+T | E-T | T
T -> T*F | T/F | F
F -> P " F | P
P -> (E)
P -> id.
(b) Construct triples of an expression: a * −(b + c).
Prepared by Kiran Kumar Varaka Asso Professor,MRIT
Click Here To Download All 8 Units Important Questions
Post a Comment
Post a Comment