### SET 1

Question 1

**Which one of the following is True at any valid state in shift-reduce parsing?**

A : Viable prefixes appear only at the bottom of the stack and not inside

B : Viable prefixes appear only at the top of the stack and not inside

C : The stack contains only a set of viable prefixes

D : The stack never contains viable prefixes

Answer Discuss it!

.

Correct answer is :B

Question 2

**Match the following:**

A : P - 2, Q-3, R -1, S- 4

B : P - 2, Q-1, R -4, S- 3

C : P - 2, Q-4, R -1, S- 3

D : P - 2, Q-3, R -4, S- 1

Answer Discuss it!

.

Correct answer is :C

Solution :

Lemical Analyzer uses DFA to recognize the longest possible input sequence that makes up a token. Parser takes input in the form of tokens and usually builds a data structure in the form of parse tree. Here parse tree can be termed as a Production tree as parser uses production of the grammar to check whether generated tokens form a meaningful compression).

Register allocation can be reduced to K-colouring problem where K is the number of registers available on the target architecture.

P

Question 3

**Among simple LR (SLR), canonical LR, and look-ahead LR (LALR), which of the following pairs identify the method that is very easy to implement and the method that is the most powerful, in that order?**

A : SLR, LALR

B : Canonical LR, LALR

C : SLR, canonical LR

D : LALR, canonical LR

Answer Discuss it!

.

Correct answer is :C

Solution :

In SLR method, we work with LR(0) items where as in CLR(1) we work with LR(1) items. LR(1) item is comprised of two parts-the LR(0) item and a look ahead associated with the item. If we work with LR(1) items instead of using LR(0) items, then every state of the parser corresponds to a set of LR(1) items. When the parser looks ahead in the input buffer to decide whether the reduction is to be done or not the information about the terminals is available in the state of the parser itself which is n

Question 4

**Consider the following grammar G **

S -> F | H

S -> p | c

S -> d | c

where S, F, and H are non-terminal symbols, p, d, and c are terminal symbols. Which of the following statements(s) is/are correct?

S1.LL(1) can parse all strings that are generated using grammar G

S2: LR(1) can parse all strings that are generate using grammar G

A : Only S1

B : Only S2

C : Both S1 and S2

D : Neither S1 nor S2

Answer Discuss it!

.

Correct answer is :D

Question 1

.

Correct answer is :B

Question 2

.

Correct answer is :C

Solution :

Lemical Analyzer uses DFA to recognize the longest possible input sequence that makes up a token. Parser takes input in the form of tokens and usually builds a data structure in the form of parse tree. Here parse tree can be termed as a Production tree as parser uses production of the grammar to check whether generated tokens form a meaningful compression).

Register allocation can be reduced to K-colouring problem where K is the number of registers available on the target architecture.

P

Question 3

.

Correct answer is :C

Solution :

In SLR method, we work with LR(0) items where as in CLR(1) we work with LR(1) items. LR(1) item is comprised of two parts-the LR(0) item and a look ahead associated with the item. If we work with LR(1) items instead of using LR(0) items, then every state of the parser corresponds to a set of LR(1) items. When the parser looks ahead in the input buffer to decide whether the reduction is to be done or not the information about the terminals is available in the state of the parser itself which is n

Question 4

S -> F | H

S -> p | c

S -> d | c

where S, F, and H are non-terminal symbols, p, d, and c are terminal symbols. Which of the following statements(s) is/are correct?

S1.LL(1) can parse all strings that are generated using grammar G

S2: LR(1) can parse all strings that are generate using grammar G

.

Correct answer is :D