### SET 5

Question 1

**Which one of the following is a top-down parser?**

A : Recursive descent parser.

B : Operator precedence parser.

C : An LR(k) parser.

D : An LALR(k) parser.

Answer Discuss it!

.

Correct answer is :A

Solution :

Recursive Descent parsing is LL(1) parsing which is top down parsing.

Question 2

**Which of the following is TRUE about formulae in Conjunctive Normal Form?**

A : For any formula, there is a truth assignment for which at least half the clauses evaluate to true.

B : For any formula, there is a truth assignment for which all the clauses evaluate to true

C : There is a formula such that for each truth assignment, at most one-fourth of the clauses evaluate t

D : None of the above

Answer Discuss it!

.

Correct answer is :B

Question 3

**Consider the following two statements: **

P: Every regular grammar is LL(1)

Q: Every regular set has a LR(1) grammar

Which of the following is TRUE?

A : Both P and Q are true

B : P is true and Q is false

C : P is false and Q is true

D : Both P and Q are false

Answer Discuss it!

.

Correct answer is :C

Solution :

A regular grammar can also be ambiguous also

For example, consider the following grammar,

S -> aA/a

A -> aA/Ε

In above grammar, string 'a' has two leftmost
derivations.

(1) S -> aA

S->a (using A->?)

(2) S -> a

And LL(1) parses only unambiguous grammar,

so statement P is False.

Statement Q is true is for every regular set, we can have a regular

grammar which is unambiguous so it can be parse by LR parser.

Question 4

**In a simplified computer the instructions are:**

The computer has only to registers, and OP is either ADD or SUB. Consider the following basic block:

t1=a+b

t2=c+d

t3=e-t2

t4=t1-t3

Assume that all operands are initially in memory. The final value of the computation should be in memory. What is the minimum number of MOV instructions in the code generated for this basic block?

A : 2

B : 3

C : 5

D : 6

Answer Discuss it!

.

Correct answer is :B

Question 5

**Consider the CFG with {S, A,B} as the non-terminal alphabet, {a,b}as the terminal alphabet, S as the start symbol and the following set of production rules:**

Which of the following strings is generated by the grammar?

A : aaaabb

B : aabbbb

C : aabbab

D : abbbba

Answer Discuss it!

.

Correct answer is :C

Solution :

The grammar accepts strings with equal number of a's and b's. Option C is the only option which has equal a's and b's.

Question 6

**For the correct answer strings to above question, how many derivation trees are there?**

A : 1

B : 2

C : 3

D : 4

Answer Discuss it!

.

Correct answer is :B

Question 7

**Which of the following describes a handle (as applicable to LR-parsing) appropriately?**

A : It is the position in a sentential form where the next shift or reduce operation will occur

B : It is non-terminal whose production will be used for reduction in the next step

C : It is a production that may be used for reduction in a future step along with a position in the sent

D : It is the production p that will be used for reduction in the next step along with a position in the sentential form where the right hand side of the production may be found

Answer Discuss it!

.

Correct answer is :D

Question 8

**Some code optimizations are carried out on the intermediate code because**

A : they enhance the portability of the compiler to other target processors

B : program analysis is more accurate on intermediate code than on machine code

C : the information from dataflow analysis cannot otherwise be used for optimization

D : the information from the front end cannot otherwise be used for optimization

Answer Discuss it!

.

Correct answer is :A

Question 9

**Which of the following statements are true?**

I. Every left-recursive grammar can be converted to a right-recursive grammar and vice-versa

II. All ε productions can be removed from any context-free grammar by suitable transformations

III. The language generated by a context-free grammar all of whose productions are of the form X --> w or X --> wY (where, w is a string of terminals and Y is a non-terminal), is always regular

IV. The derivation trees of strings generated by a context-free grammar
in Chomsky Normal Form are always binary trees

A : I,II,III and IV

B : II,III and IV only

C : I,III and IV only

D : I,II and IV only

Answer Discuss it!

.

Correct answer is :C

Question 10

**An LALR(1) parser for a grammar G can have shift-reduce (S-R) conflicts if and only if**

A : the SLR(1) parser for G has S-R conflicts

B : the LR(1) parser for G has S-R conflicts

C : the LR(0) parser for G has S-R conflicts

D : the LALR(1) parser for G has reduce-reduce conflicts

Answer Discuss it!

.

Correct answer is :B

Question 1

.

Correct answer is :A

Solution :

Recursive Descent parsing is LL(1) parsing which is top down parsing.

Question 2

.

Correct answer is :B

Question 3

P: Every regular grammar is LL(1)

Q: Every regular set has a LR(1) grammar

Which of the following is TRUE?

.

Correct answer is :C

Solution :

A regular grammar can also be ambiguous also

For example, consider the following grammar,

S -> aA/a

A -> aA/Ε

In above grammar, string 'a' has two leftmost derivations.

(1) S -> aA

S->a (using A->?)

(2) S -> a

And LL(1) parses only unambiguous grammar,

so statement P is False.

Statement Q is true is for every regular set, we can have a regular

grammar which is unambiguous so it can be parse by LR parser.

Question 4

The computer has only to registers, and OP is either ADD or SUB. Consider the following basic block:

t1=a+b

t2=c+d

t3=e-t2

t4=t1-t3

Assume that all operands are initially in memory. The final value of the computation should be in memory. What is the minimum number of MOV instructions in the code generated for this basic block?

.

Correct answer is :B

Question 5

Which of the following strings is generated by the grammar?

.

Correct answer is :C

Solution :

The grammar accepts strings with equal number of a's and b's. Option C is the only option which has equal a's and b's.

Question 6

.

Correct answer is :B

Question 7

.

Correct answer is :D

Question 8

.

Correct answer is :A

Question 9

I. Every left-recursive grammar can be converted to a right-recursive grammar and vice-versa

II. All ε productions can be removed from any context-free grammar by suitable transformations

III. The language generated by a context-free grammar all of whose productions are of the form X --> w or X --> wY (where, w is a string of terminals and Y is a non-terminal), is always regular

IV. The derivation trees of strings generated by a context-free grammar in Chomsky Normal Form are always binary trees

.

Correct answer is :C

Question 10

.

Correct answer is :B