### SET 6

Question 1

**The grammar A → AA | (A) | e is not suitable for predictive-parsing because the grammar is**

A : ambiguous

B : left-recursive

C : right-recursive

D : an operator-grammar

Answer Discuss it!

.

Correct answer is :B

Question 2

**Consider the grammar **

E → E + n | E × n | n

For a sentence n + n × n, the handles in the right-sentential form of the reduction are

A : n, E + n and E + n × n

B : n, E + n and E + E × n

C : n, n + n and n + n × n

D : n, E + n and E × n

Answer Discuss it!

.

Correct answer is :D

Solution :

E -> E + n {Applying E -> E + n }

-> E + E * n {Applying E -> E * n }

-> E + n * n {Applying E -> n }

-> n + n * n {Applying E -> n }

Question 3

**Consider the grammar **

S → (S) | a

Let the number of states in SLR(1), LR(1) and LALR(1) parsers for the grammar be n1, n2 and n3 respectively. The following relationship holds good

A : n1 < n2 < n3

B : n1 = n3 < n2

C : n1 = n3 = n2

D : n1 >= n3 >= n2

Answer Discuss it!

.

Correct answer is :B

Question 4

**Consider line number 3 of the following C- program. **

int main ( ) { /* Line 1 */

int I, N; /* Line 2 */

fro (I = 0, I < N, I++); /* Line 3 */

}

Identify the compiler's response about this line while creating the object-module

A : No compilation error

B : Only a lexical error

C : Only syntactic errors

D : Both lexical and syntactic errors

Answer Discuss it!

.

Correct answer is :C

Solution :

Note that there is 'fro' instead of 'for'. This is not a lexical error as lexical analysis typically involves Tokenization.

Question 5

**Consider the following expression grammar. The semantic rules for expression calculation are stated next to each grammar production. **

E → number E.val = number. val

| E '+' E E(1).val = E(2).val + E(3).val

| E '×' E E(1).val = E(2).val × E(3).val

The above grammar and the semantic rules are fed to a yacc tool (which is an LALR (1) parser generator) for parsing and evaluating arithmetic expressions. Which one of the following is true about the action of yacc for the given grammar?

A : It detects recursion and eliminates recursion

B : It detects reduce-reduce conflict, and resolves

C : It detects shift-reduce conflict, and resolves the conflict in favor of a shift over a reduce action

D : It detects shift-reduce conflict, and resolves the conflict in favor of a reduce over a shift action

Answer Discuss it!

.

Correct answer is :C

Question 6

**Consider the following expression grammar. The semantic rules for expression calculation are stated next to each grammar production. **

E → number E.val = number. val

| E '+' E E(1).val = E(2).val + E(3).val

| E '×' E E(1).val = E(2).val × E(3).val

Assume the conflicts in Part (a) of this question are resolved and an LALR(1) parser is generated for parsing arithmetic expressions as per the given grammar. Consider an expression 3 × 2 + 1. What precedence and associativity properties does the generated parser realize?

A : Equal precedence and left associativity; expression is evaluated to 7

B : Equal precedence and right associativity; expression is evaluated to 9

C : Precedence of '×' is higher than that of '+', and both operators are left associative; expression is

D : Precedence of '+' is higher than that of '×', and both operators are left associative; expression is

Answer Discuss it!

.

Correct answer is :A

Question 7

**Consider the following grammar. **

S -> S * E

S -> E

E -> F + E

E -> F

F -> id

Consider the following LR(0) items corresponding to the grammar above.

(i) S -> S * .E

(ii) S -> F. + E

(iii) S -> F + .E

Given the items above, which two of them will appear in the same set in the canonical sets-of-items for the grammar?

A : i and ii

B : ii and iii

C : i and iii

D : None of the above

Answer Discuss it!

.

Correct answer is :C

Question 8

**Consider the following statements about the context free grammar**

G = {S -> SS, S ->ab, S -> ba, S -> ∈ }

I. G is ambiguous

II. G produces all strings with equal number of a’s and b’s

III. G can be accepted by a deterministic PDA.

Which combination below expresses all the true statements about G?

A : I only

B : I and III only

C : II and III only

D : I,II and III

Answer Discuss it!

.

Correct answer is :B

Solution :

II is not right because the grammer cannot produce aabb

Question 9

**Consider these two functions and two statements S1 and S2 about them
**

int work1(int *a, int i, int j)

{

int x = a[i+2];

a[j] = x+1;

return a[i+2] – 3;

}

int work2(int *a, int i, int j)

{

int t1 = i+2;

int t2 = a[t1];

a[j] = t2+1;

return t2 – 3;

}

S1: The transformation form work1 to work2 is valid, i.e., for any program state and input arguments, work2 will compute the same output and have the same effect on program state as work1 S2: All the transformations applied to work1 to get work2 will always improve the performance (i.e reduce CPU time) of work2 compared to work1

A : S1 is false and S2 is false

B : S1 is false and S2 is true

C : S1 is true and S2 is false

D : S1 is true and S2 is true

Answer Discuss it!

.

Correct answer is :C

Question 10

**Consider the following grammar: **

S → FR

R → S | ∅

F → id

In the predictive parser table, M, of the grammar the entries M[S, id] and M[R, $] respectively.

A : {S → FR} and {R → ε }

B : {S → FR} and { }

C : {S → FR} and {R → *S}

D : {F → id} and {R → ε}

Answer Discuss it!

.

Correct answer is :A

Question 11

**Consider the following translation scheme.**

S → ER

R → *E{print("*");}R | ε

E → F + E {print("*");} | F

F ? (S) | id {print(id.value);}

Here id is a token that represents an integer and id.value represents the corresponding integer value. For an input '2 * 3 + 4', this translation scheme prints

A : 2 * 3 + 4

B : 2 * +3 4

C : 2 3 * 4 +

D : 2 3 4+*

Answer Discuss it!

.

Correct answer is :D

Question 12

**In the correct grammar of above question, what is the length of the derivation (number of steps starring from S) to generate the string l**^{a}b^{m} with l ≠ m?

A : max(l,m) + 2

B : l + m + 2

C : l + m + 3

D : max(l, m) + 3

Answer Discuss it!

.

Correct answer is :A

Question 1

.

Correct answer is :B

Question 2

E → E + n | E × n | n

For a sentence n + n × n, the handles in the right-sentential form of the reduction are

.

Correct answer is :D

Solution :

E -> E + n {Applying E -> E + n }

-> E + E * n {Applying E -> E * n }

-> E + n * n {Applying E -> n }

-> n + n * n {Applying E -> n }

Question 3

S → (S) | a

Let the number of states in SLR(1), LR(1) and LALR(1) parsers for the grammar be n1, n2 and n3 respectively. The following relationship holds good

.

Correct answer is :B

Question 4

int main ( ) { /* Line 1 */

int I, N; /* Line 2 */

fro (I = 0, I < N, I++); /* Line 3 */

}

Identify the compiler's response about this line while creating the object-module

.

Correct answer is :C

Solution :

Note that there is 'fro' instead of 'for'. This is not a lexical error as lexical analysis typically involves Tokenization.

Question 5

E → number E.val = number. val

| E '+' E E(1).val = E(2).val + E(3).val

| E '×' E E(1).val = E(2).val × E(3).val

The above grammar and the semantic rules are fed to a yacc tool (which is an LALR (1) parser generator) for parsing and evaluating arithmetic expressions. Which one of the following is true about the action of yacc for the given grammar?

.

Correct answer is :C

Question 6

E → number E.val = number. val

| E '+' E E(1).val = E(2).val + E(3).val

| E '×' E E(1).val = E(2).val × E(3).val

Assume the conflicts in Part (a) of this question are resolved and an LALR(1) parser is generated for parsing arithmetic expressions as per the given grammar. Consider an expression 3 × 2 + 1. What precedence and associativity properties does the generated parser realize?

.

Correct answer is :A

Question 7

S -> S * E

S -> E

E -> F + E

E -> F

F -> id

Consider the following LR(0) items corresponding to the grammar above.

(i) S -> S * .E

(ii) S -> F. + E

(iii) S -> F + .E

Given the items above, which two of them will appear in the same set in the canonical sets-of-items for the grammar?

.

Correct answer is :C

Question 8

G = {S -> SS, S ->ab, S -> ba, S -> ∈ }

I. G is ambiguous

II. G produces all strings with equal number of a’s and b’s

III. G can be accepted by a deterministic PDA.

Which combination below expresses all the true statements about G?

.

Correct answer is :B

Solution :

II is not right because the grammer cannot produce aabb

Question 9

int work1(int *a, int i, int j)

{

int x = a[i+2];

a[j] = x+1;

return a[i+2] – 3;

}

int work2(int *a, int i, int j)

{

int t1 = i+2;

int t2 = a[t1];

a[j] = t2+1;

return t2 – 3;

}

S1: The transformation form work1 to work2 is valid, i.e., for any program state and input arguments, work2 will compute the same output and have the same effect on program state as work1 S2: All the transformations applied to work1 to get work2 will always improve the performance (i.e reduce CPU time) of work2 compared to work1

.

Correct answer is :C

Question 10

S → FR

R → S | ∅

F → id

In the predictive parser table, M, of the grammar the entries M[S, id] and M[R, $] respectively.

.

Correct answer is :A

Question 11

S → ER

R → *E{print("*");}R | ε

E → F + E {print("*");} | F

F ? (S) | id {print(id.value);}

Here id is a token that represents an integer and id.value represents the corresponding integer value. For an input '2 * 3 + 4', this translation scheme prints

.

Correct answer is :D

Question 12

^{a}b

^{m}with l ≠ m?

.

Correct answer is :A