Page |1

PYQ
GROUP C
8. For the following augmented grammar
E’— >E
E—>E+T | T
T—>T*F | F
F—>id | (E)
construct the LR (0) automaton.
9. a. Consider the following three address code block.
(1) prod=0
(2) i=1
(3) t1=4*i
(4) t2=a[t1]
(5) t3=4*i
(6) t4= b[t3]
(7) t5=t2*t4
(8) t6=prod+t5
(9) prod=t6
(10) t7=i+1
(11) i=t7
(12) if i <= 20 goto (3)
i) Write down the rules to find out the leaders from a three address code block.
ii) Construct the flow graph for the following three address code block.
b. Find the number of tokens in the following c code snippets
i. printf(“the value of x is=%d”,x);
ii. void main()
{
 Page |2

int a, b,
a=10,b=20;
}
c. Explain code motion with proper example.

10. a. Draw the DAG of the following expression:

A*(B+C)+ C*(D+E)+ A+(B+C)

b. Is it possible to parse a string generated from an ambiguous grammar using LL(1)

parsing. Justify.
c. Explain Quadraples, Triples and Indirect Triples with proper example.
[3+3+4]
OR
a. Construct the DAG for the expression
((x+y)-((x+y)*(x-y)))+((x+y)*(x-y))

b. Can all ambiguous grammar be solved by LR(0) grammar. Explain.

c. How procedure call is implemented by three address code. [3+3+4]

GROUP B
2. Explain Syntax Directed Definition (SDD) with a proper example. Define
Synthesized attribute.[3+2]
3. Explain the various phases of the compiler with a neat diagram and explain each
stage with a suitable example. [5]
4.Explain the induction variable and reduction in strength with proper examples.
[5]
5. Consider the following grammars.
i. S—>SS | aSb | bSa | ε;
ii. S—>aSbS | bSaS | ε.
Which one is ambiguous and which one is unambiguous. Justify.
[5]
 Page |3

6. Build the operator relation table for the following operator grammar.
E → E+E | E*E |E-E| id
OR
Construct the LL(1) parsing table of the following grammar.
S—>iEtSS’ | a
S’—>eS | ε
E—>b [5]
7. Consider the following grammar
S—>aSa | bSb | A
A—>aBb
B—>aB | bB | ε. Find out FIRST and FOLLOW sets.

Group-A
1. Perform left factoring in the following grammar: A → aAB / aBc / aAc
2. Define Dead code elimination.
3. What is the importance of semantic analysis?
4. Explain the importance of look-ahead in the lexical analysis phase.
5. Discuss the need of the symbol table.
6. Discuss the four possible actions a shift-reduce parser can take
7. Write down the properties of an operator grammar.
8. Differentiate between Top-Down and Bottom-Up parsing?
9. State the use of Lex.
10. What is the use of YACC.
11. Define L attributed definition.
12. Define “Handle” pruning.
13. Differentiate between S-attribute and inherited-attribute.
14. State the advantages of DAG.
 Page |4

College Sample
Introduction and lexical analysis:
1. Explain various phases of compiler with a diagram.
2. State token, pattern and lexeme with example. Differentiate among them.
3. State the output of lexical analyzer.
4. Which type of finite automata is used in lexical analysis phase.
5. What is look ahead in context of lexical analysis. Explain the importance of look
ahead.
6. What is symbol table? Explain. State the importance of symbol table.
7. Write down the number of tokens in the following code snippet

a. printf("i=%d, &i=%x", i, &i);

b. int main()
{
int a = 10, b = 20;
printf("sum is:%d",a+b);
return 0;
}
8. Is the following C statement lexically correct?
9. printf("i=%d, &i=%x", i, &i)
Syntax Analysis:
10. What is syntax analysis? Explain.
11. What is left recursion? Explain with proper example. What is indirect left
recursion? Explain with proper example.
12. How to eliminate direct and indirect left recursion? Explain with proper example.
13. Find out the left factor of the following grammar
S → iEtS|iEtSeS|a, E → b
14. For the given grammars eliminate left recursion.
a. G: E-->E+T/T
T-->T*F/F
F-->(E)/id

b. S → a|^|(T)

T → T, S|S

c. A->BC

B->CA|b
 Page |5

C->AA|a

d. E->E+T|E, T->T*F|F, F->(E)|id

15. Construct the FIRST and FOLLOW sets of the following grammars.

a. G: E-->E+T/T
T-->T*F/F
F-->(E)/id

b. S—>iEtSS’ | a
S’—>eS | ε
E—>b

c. E -> TR
R -> +T R| #
T -> F Y
Y -> *F Y | #
F -> (E) | i

d. S→[SX] |a
X→ε|+SY |Yb
Y→ ε | - S X c
16. What are the top-down parsing and bottom up pursing? Explain. State LL(1)
parsing table.

17. Construct the LL(1) parsing table of the problems given in 14.a, 14.b and 14.c.

18. For the grammar stated in 14.c, parse i+i*i using LL(1) parsing method.
19. What are the disadvantages of LL(1) parsing method. Explain.
20. What is handle? What is handle pruning? Explain with proper example.
21. For the given grammar, create the LR(0) parsing table and parse the terminal
string abab.

a. S—> AA | AB
A—> aA | b
B—> bB | b
22. For the given grammar, create the LR(0) parsing table and parse the terminal
string abab.
23. What are the advantages of LR(0) parser over LL(1) parser? Explain.
24. Explain handle pruning with proper example.
25. What are the possible actions in LR(0) parser? Explain. What are the
disadvantages of LR(0) parser? Explain.
 Page |6

26. Explain shift-reduce and reduce-reduce conflict in connection with LR(0)

parsing with proper example.

Code Generation and Code Optimization

1. What is DAG? Explain.
2. Draw the DAG of the following code snippet and expressions.
a. p := (-r * q) + (-r * s)
b.
a=bxc
d=b
e=dxc
b=e
f=b+c
g=f+d
c. B10:
d. S1 = 4 x I
e. S2 = addr(A) – 4
f. S3 = S2[S1]
g. S4 = 4 x I
h. S5 = addr(B) – 4
i. S6 = S5[S4]
j. S7 = S3 x S6
k. S8 = PROD + S7
l. PROD = S8
m. S9 = I + 1
n. I = S9
o. If I <= 20 goto L10
3. Explain Three address code. Explain. how if else, procedure call, conditional and
unconditional jump and array indexing are implemented in three address code.
4. Explain quadraples, triples and indirect triples with proper examples.
5. Also write the three-address code of the above problems.
6. Explain Basic block with proper example?
 Page |7

7. Why is code optimization required?

8. Distinguish between Machine-Dependent and Machine-Independent
optimization.
9. Consider the following code snippet

void quicksort(int m, int n)

{
int i,j;
if(n<=m) return;
i=m-1; j=n; v=a[n];
while(1) {
do i=i+1; while (a[i]<v);
do j=j-1; while (a[j]>v);
if(i>=j) break;
x=a[i]; a[i]=a[j]; a[j]=x;
}
x=a[i]; a[i]=a[n]; a[n]=x;
quicksort(m,j); quicksort(i+1,n);
}

For the above code, write down the three address code. After that draw the flow
graph of the corresponding three address code.
10. For the expression X= (((A/B)+B)*(C+(D*E))) – (A+B+C), write the
quadruples, triples and indirect triples representations and also compare these
representations.
11. For the expression (x + y)*(y + 2) + (x + y + z), write the quadruples, triples and
indirect triples representations and also compare these representations.

12. Explain Global common subexpression, copy propagation, dead code

elimination, induction variables and reduction in strength with the help of the
flow graph in question no. 3.
13. Explain peephole optimization with proper example. Explain eliminating
redundant loads and stores, eliminating unreachable code, dead code elimination,
flow of control optimization and algebraic simplification and reduction in
strength with proper example.
14. Construct the flow graph for the following three address code
 Page |8

15. Write the three address code of the following code fragment 3
while(a > b) {
if(c< d)
x = y + z;
else
x = y - z;
}

Extra Question
16.Draw the syntax tree and the DAG of the following expression: 1+2
(x + y) x (x + y + z)
17. Build the operator relation table for the following operator grammar
E → E+E | E*E | id
18. For the following Grammar G: compute leftmost and rightmost derivations of the
string aaabbabbba
G: S → aB / bA
S → aS / bAA / a
B → bS / aBB / b
19. For the given grammar
E → BB
B → cB|d,
create the SLR(1) parsing table and show the parsing of the string ccdd$.