CDC 2080

Section A

Attempt any two questions.

1. Differentiate between one-pass and multi-pass compiler. Construct the LL(1) parsing table for the following grammar.

   S → ABCD

   A → a | ε

   B → b

   C → 0 | ε

   D → d | ε

2. How does Lexical Analyzer recognize a token? Give an example to make it clear. Convert the regular expression a(a+b)(b+c)*a# to DFA.

3. Construct the LR(1) parsing table for the following grammar.

   S → AaAb

   A → BbBa

   A → ε

   B → ε

Section B

Attempt any eight questions.

1. Why code optimization is needed? Describe any two techniques for loop optimization.

2. What is three-address code? How high level code is converted to three address code? Illustrate with an example.

3. What is activation tree? Define type checking system with examples.

4. What are the advantages of intermediate code? What types of information are provided by symbol table?

5. What is annotated parse tree? Define S-attributed grammar with an example.

6. Describe about syntax directed translation with an example.

7. Given the following grammar with SLR parsing table, test whether the string “int * (int + int)” will be accepted or rejected.

   E -> T + E……….(1)

   E -> T……….(2)

   T -> int*T……….(3)

   T -> int……….(4)

   T -> (E)……….(5)

   STATE	ACTION						GOTO
   	int	*	+	(	)	$	E	T
   1	S5			S4			2	3
   2						ACC
   3			S6		R2	R2
   4	S5			S4			7	3
   5		S8	R4		R4	R4
   6	S5			S4			9	3
   7					S10
   8	S5			S4				11
   9					R1	R1
   10			R5		R5	R5
   11			R3		R3	R3

8. How do you recognize basic block? Discuss about the factors that affect code generator.

9. Find the FIRST and FOLLOW of all the non terminals in following grammar.

   S → aAbCD | ε

   A → SD | ε

   C → Sa

   D → aBD | ε