rtmnuonline.

com

B.E. (Computer Science & Engineering) Seventh Semester (C.B.S.)

Language Processor
P. Pages : 4 NRJ/KW/17/4627
Time : Three Hours *0935* Max. Marks : 80
_____________________________________________________________________
Notes : 1. All questions carry marks as indicated.
2. Solve Question 1 OR Questions No. 2.
3. Solve Question 3 OR Questions No. 4.
4. Solve Question 5 OR Questions No. 6.
5. Solve Question 7 OR Questions No. 8.
6. Solve Question 9 OR Questions No. 10.
7. Solve Question 11 OR Questions No. 12.

1. a) Explain various phases of compiler in brief. For the given expression, 8

a  bc  d e
give output of each phase of compiler including symbol table and memory representation.

b) Explain role of Regular Expressions and Finite Automata in Lexical Analyzer. Construct 5
Finite Automata to identify REAL numbers.

OR

2. a) Write a short note on. 5

i) Cross compiler.

ii) Bootstrapping.

Also, provide suitable example.

b) Construct optimized DFA for the regular expression 0  1 011 . Also mention algorithm 8
for minimizing number of states of DFA.

3. a) Design LL(1) parser for the given grammar. 8

S  UVW
U  S | a S b | d
V  a V |
W  c W |
Also, give parsing Actions for the input string "dcac" .

b) Construct LR 0 Parser for the following grammar. 6

S  c A | cc B
A  cA |a
B  cc B | b
check validity of string "ccccb".

OR

NRJ/KW/17/4627 1 P.T.O

www.rtmnuonline.com
rtmnuonline.com

4. a) Determine whether given grammar is ambiguous or not. 4

S  iSeS | is | a
If yes, remove ambiguity and rewrite.

b) Determine whether given grammar is LR(1) or not. 10

S  a IJh
I  I bSe | c
J  K L K r |
K  d |
L  p |

5. a) List out various ways to represent Three Address code. 6

Write the given expression in the form of 3-Addr. Code and also represent the same with
Listed representation methods.

om
a  b  c  b  c

e.c
lin
b) Generate 3-Address code for the given program Fragment. 7

on
While A  B or C  D do

nu
if D  20 and not B  C then

rtm
A  AB w.
ww
else
D  D 1
X YZ
Write the translation scheme for 'WHILE' Loop.

OR
om

6. a) Draw Annotated Parse Tree For the given expression and also generate 3-Address code. 5
e.c
lin

P  Q AND R  S OR NOTT  U AND R  Q

on
nu

b) For the following array reference, construct three address code (TAC). 8
rtm
w.

Ci, j, k  a b i , j , k   a  i, j 
ww

Dimensions : c  10 x 20 x 30
a , b  10 x 20

Assume , bpw = 4.

7. a) Explain various data structures required for implementation of symbol Table. 6

b) Explain different error recovery techniques for predictive parsing with suitable example. 7

OR

NRJ/KW/17/4627 2

www.rtmnuonline.com
rtmnuonline.com

8. a) Explain the activation record structure in detail by considering suitable example. 6

b) Implement phrase Level error recovery routines For LR Parsing by considering given 7
grammar.

E  E  E | E  E | E | id

9. a) For the code below apply following code transformations: Constant Folding, constant 6
Propagation, copy propagation, dead-code elimination and strength reduction.
t1  t1  t1
L0 : t2  0
t 3  t1  8  1
t 4  t3  t 2
t5  t 4  4
t6  t3  t 4
t8  t 6
if  t 8  0  goto L1
L1 : goto L 0
L2 : t1  1
t 9  16
t10  t1  2
goto L1

b) Perform Live variable computation for the given flow graph. 8

1 p=q+r
2 s=p+q B1
3 u=s*v
B2 B3
4 v=r+u 5 q=s*u
B4
6
q=v+r

OR
10. a) Construct Dominator set and Dominator tree for the given flow graph. 6
1

5 6

9 10

Also, identify back-edges and Loop for the flow graph.

NRJ/KW/17/4627 3 P.T.O

www.rtmnuonline.com
rtmnuonline.com

b) Compute reaching Definitions for the given flow graph. 8

1 i=m_ 1
2 j=n B1
3 a = u1

4 i=i+1 B2
5 j = j _1
B3
6 a = u2

7 i=a+j B4

8 EXIT

11. a) Implement simple code generation algorithm for the given 3-Addr. code. 6
t ab
u  a c
v tu
d  vu
Also, Find out total number of registers required for executing the code.

b) Construct DAG for the given expression. Explain the need of Heuristic code generation 7
algorithm and also perform the same on constructed DAG.
X  a  b  e  c  d

OR

12. a) List out various issues to be considered for code generation phase. Explain each in brief. 6

b) Generate Target code for the given expression by considering optimal code generation 7
algorithm.
a  b * c  d /e  f  .

**********

NRJ/KW/17/4627 4

www.rtmnuonline.com