### SET 3

Question 1

**The lexical analysis for a modern computer language such as Java needs the power of which one of the following machine models in a necessary and sufficient sense?**

A : Finite state automata

B : Deterministic pushdown automata

C : Non-Deterministic pushdown automata

D : Turing machine

Answer Discuss it!

.

Correct answer is :A

Solution :

Lexical Analysis is implemented by finite automata

Question 2

**In a compiler, keywords of a language are recognized during**

A : parsing of the program

B : the code generation

C : the lexical analysis of the program

D : dataflow analysis

Answer Discuss it!

.

Correct answer is :C

Solution :

Any identifier is also a token so it is recognized in lexical Analysis

Question 3

**For the grammar below, a partial LL(1) parsing table is also presented along with the grammar. Entries that need to be filled are indicated as E1, E2, and E3. ε is the empty string, $ indicates end of input, and, | separates alternate right hand sides of productions.**

A : B :

C : D :

Answer Discuss it!

.

Correct answer is :A

Solution :

First (A) = First (S) = First (aAbB) U First (bAaB) U First (ε)

={a} U {b} U {ε} = {ε , a,b}

First (B)= First (S) = {ε,a,b}

Follow (A) = First (bB) = First (aB) = {a,b}

Follow (B) = Follow (S)= {$} U Follow (A) ={ $,a,b}

Question 4

**For the grammar below, a partial LL(1) parsing table is also presented along with the grammar. Entries that need to be filled are indicated as E1, E2, and E3. ε is the empty string, $ indicates end of input, and, | separates alternate right hand sides of productions.**

The appropriate entries for E1, E2, and E3 are

A : E1: S->aAbB, A->S

E2: S->bAaB, B->S

E3: B->S

B : E1: S->aAbB, S->ε

E2: S->bAaB, S->ε

E3: S->ε

C : E1: S->aAbB, S->ε

E2: S->bAaB, S->ε

E3: B->S

D : E1: A->S, S->ε

E2: B->S, S->ε

E3 : B ->S

Answer Discuss it!

.

Correct answer is :C

Question 5

**What is the maximum number of reduce moves that can be taken by a bottom-up parser for a grammar with no epsilon- and unit-production (i.e., of type A -> ∈and A->a) to parse a string with n tokens?**

A : n/2

B : n-1

C : 2n-1

D : 2^{n}

Answer Discuss it!

.

Correct answer is :B

Solution :

Say string is pqrs and we want to parse it and the grammar is

A->pB

B->qC

C->rs

Derivation is like pB->pqC->pqrs so total 3 steps for length 4 string

Question 6

**Consider the following two sets of LR(1) items of an LR(1) grammar**

Which of the following statements related to merging of the two sets in the corresponding LALR parser is/are FALSE?

1. Cannot be merged since look aheads are different

2. Can be merged but will result in S–R conflict

3. Can be merged but will result in R–R conflict

4. Cannot be merged since goto on c will lead to two different sets

A : 1 only

B : 2 only

C : 1 and 4 only

D : 1,2,3 and 4

Answer Discuss it!

.

Correct answer is :D

Solution :

1. Merging of two states depends on core part (production rule with dot operator), not on look aheads.

2. The two states are not containing Reduce item ,So after merging, the merged state can not contain any S-R conflict

3. As there is no Reduce item in any of the state, so can’t have R-R conflict.

4.Merging of stats does not depend on further goto on any terminal. So all statements are false.

Question 7

**The following code segment is executed on a processor which allows only register operands in its instructions. Each instruction can have almost two source operands and one destination operand. Assume that all variables are dead after this code segment **

c =a+ b;

d= c * a;

e= c+ a;

x= c *c;

if (x >a )

{

y = a * a;

}

else {

d =d * d;

e= e * e;

}

Suppose the instruction set architecture of the processor has only two registers. The only allowed compiler optimization is code motion, which moves statements from one place to another while preserving correctness. What is the minimum number of spills to memory in the compiled code?

A : 0

B : 1

C : 2

D : 3

Answer Discuss it!

.

Correct answer is :B

Question 8

**The following code segment is executed on a processor which allows only register operands in its instructions. Each instruction can have almost two source operands and one destination operand. Assume that all variables are dead after this code segment **

c =a+ b;

d= c * a;

e= c+ a;

x= c *c;

if (x >a )

{

y = a * a;

}

else {

d =d * d;

e= e * e;

}

What is the minimum number of registers needed in the instruction set architecture of the processor to compile this code segment without any spill to memory? Do not apply any optimization other than optimizing register allocation

A : 3

B : 4

C : 5

D : 6

Answer Discuss it!

.

Correct answer is :B

Question 1

.

Correct answer is :A

Solution :

Lexical Analysis is implemented by finite automata

Question 2

.

Correct answer is :C

Solution :

Any identifier is also a token so it is recognized in lexical Analysis

Question 3

.

Correct answer is :A

Solution :

First (A) = First (S) = First (aAbB) U First (bAaB) U First (ε)

={a} U {b} U {ε} = {ε , a,b}

First (B)= First (S) = {ε,a,b}

Follow (A) = First (bB) = First (aB) = {a,b}

Follow (B) = Follow (S)= {$} U Follow (A) ={ $,a,b}

Question 4

The appropriate entries for E1, E2, and E3 are

.

Correct answer is :C

Question 5

.

Correct answer is :B

Solution :

Say string is pqrs and we want to parse it and the grammar is

A->pB

B->qC

C->rs

Derivation is like pB->pqC->pqrs so total 3 steps for length 4 string

Question 6

Which of the following statements related to merging of the two sets in the corresponding LALR parser is/are FALSE?

1. Cannot be merged since look aheads are different

2. Can be merged but will result in S–R conflict

3. Can be merged but will result in R–R conflict

4. Cannot be merged since goto on c will lead to two different sets

.

Correct answer is :D

Solution :

1. Merging of two states depends on core part (production rule with dot operator), not on look aheads.

2. The two states are not containing Reduce item ,So after merging, the merged state can not contain any S-R conflict

3. As there is no Reduce item in any of the state, so can’t have R-R conflict.

4.Merging of stats does not depend on further goto on any terminal. So all statements are false.

Question 7

c =a+ b;

d= c * a;

e= c+ a;

x= c *c;

if (x >a )

{

y = a * a;

}

else {

d =d * d;

e= e * e;

}

Suppose the instruction set architecture of the processor has only two registers. The only allowed compiler optimization is code motion, which moves statements from one place to another while preserving correctness. What is the minimum number of spills to memory in the compiled code?

.

Correct answer is :B

Question 8

c =a+ b;

d= c * a;

e= c+ a;

x= c *c;

if (x >a )

{

y = a * a;

}

else {

d =d * d;

e= e * e;

}

What is the minimum number of registers needed in the instruction set architecture of the processor to compile this code segment without any spill to memory? Do not apply any optimization other than optimizing register allocation

.

Correct answer is :B