Bottom Up Parsing Questions and Answers

Q: Consider the following statements about merging states in LALR construction.1. It can introduce a reduce-reduce conflict.2. It never introduces a shift-reduce conflict.3. It always reduces the number of states below the SLR count.

Correct answer: 1 and 2 onlyStatements 1 and 2 are correct: merging states with the same core unions their lookahead sets, which can put two reductions in competition on one lookahead, but it cannot affect the shift actions. Statement 3 misstates the comparison - LALR has exactly as many states as SLR, both being built on the LR(0) automaton. The saving is against canonical LR(1), not against SLR.

Q: Arrange these stages of a single reduce action in the order they occur.1. the goto table is consulted for the exposed state and left side2. the action table reports a reduction by a chosen production3. the left side and its new state are pushed onto the stack4. the right side symbols are popped from the parsing stack

Correct answer: 2 - 4 - 1 - 3The order is fixed by what each step needs from the last. The action table, indexed by the state on top and the lookahead, says which production to reduce by; the right side symbols and their states are then popped, exposing the state beneath; the goto table is consulted with that exposed state and the left side; and the left side with its new state is pushed. The input pointer never moves.

21.

Arrange the steps of constructing an SLR parsing table in the order performed.
1. compute the FOLLOW sets of the nonterminals
2. augment the grammar with a new start production
3. fill the action and goto tables from the items and FOLLOW sets
4. construct the canonical collection of LR(0) item sets

A.2 - 4 - 1 - 3
B.3 - 1 - 4 - 2
C.4 - 2 - 1 - 3
D.2 - 1 - 4 - 3

Answer: A

Augmentation comes first so the item sets include the accepting configuration. The collection is then built, FOLLOW computed, and the two tables filled from those ingredients. Every step is mechanical, which is why the whole process can be automated.

Discuss in Forum

22.

In the SLR construction, a reduction by A goes to alpha is entered for lookahead a when

A.a is the end of input marker and nothing else
B.a belongs to FOLLOW(A)
C.a belongs to FIRST(alpha) for that production
D.a is any terminal at all appearing in the grammar

Answer: B

SLR uses FOLLOW as its lookahead approximation. It is easy to compute but coarse, since not every terminal that can follow A in some context can follow it in this one. Canonical LR carries a lookahead specific to the state and avoids the problem.

Discuss in Forum

23.

SLR parsing can report a conflict where canonical LR does not because

A.SLR merges states that canonical LR keeps separate
B.SLR omits to augment the grammar before it builds any of the tables
C.FOLLOW is a coarser approximation than the context specific lookahead
D.SLR uses more lookahead tokens than canonical LR does

Answer: C

The FOLLOW set gathers every context in which A can appear, whereas canonical LR carries a lookahead specific to the state. The extra precision resolves conflicts that SLR cannot. The price is a much larger collection of item sets to construct and store.

Discuss in Forum

24.

An LR(1) item differs from an LR(0) item by carrying

A.a count of how many times the production has been used
B.the number of the state in which the item appears
C.the FOLLOW set of every nonterminal in the grammar
D.a lookahead terminal valid for that particular context

Answer: D

Correct answer: a lookahead terminal valid for that particular context

An LR(0) item records only how far through a production the parser has got. The LR(1) item adds a terminal that may legitimately follow in this context, which lets the parser distinguish situations that the LR(0) automaton merges - and that extra discrimination is exactly what resolves the conflicts SLR cannot.

Discuss in Forum

25.

The core of an LR(1) state is

A.the set of its LR(0) items with the lookaheads discarded
B.the single item from which the state was first generated
C.the union of the lookaheads of all its items taken together
D.the production that will be reduced in that state

Answer: A

LALR merges states whose cores agree, uniting their lookahead sets. This gives the SLR state count with lookaheads better than FOLLOW but not quite as precise as canonical LR. That middle position is exactly why the construction is so widely used.

Discuss in Forum

26.

LALR parsing is constructed by

A.removing states from the canonical collection at random
B.merging canonical LR(1) states that share the same core
C.discarding the lookaheads from canonical LR(1) items entirely
D.adding lookaheads to the SLR table after it has been built

Answer: B

The merge cuts the table to the size of the SLR table while retaining most of the precision of canonical LR. It is the construction that Yacc and Bison implement. That choice has shaped how language grammars have been written for decades.

Discuss in Forum

27.

Consider the following statements about merging states in LALR construction.
1. It can introduce a reduce-reduce conflict.
2. It never introduces a shift-reduce conflict.
3. It always reduces the number of states below the SLR count.

A.1 only
B.All of them
C.1 and 2 only
D.3 only

Answer: C

Correct answer: 1 and 2 only

Statements 1 and 2 are correct: merging states with the same core unions their lookahead sets, which can put two reductions in competition on one lookahead, but it cannot affect the shift actions. Statement 3 misstates the comparison - LALR has exactly as many states as SLR, both being built on the LR(0) automaton. The saving is against canonical LR(1), not against SLR.

Discuss in Forum

28.

Assertion (A): Merging LALR states can never introduce a shift-reduce conflict.
Reason (R): The shift actions of two states with the same core are identical, so merging changes only the reduction lookaheads.

A.Both A and R are true, but R is not the correct explanation of A
B.A is true but R is false
C.A is false but R is true
D.Both A and R are true, and R is the correct explanation of A

Answer: D

Correct answer: Both A and R are true, and R is the correct explanation of A

Both are true and the reason gives the mechanism. Two states with the same core have identical items apart from their lookaheads, so their shift actions - which depend only on the symbol after the dot - are already the same. Merging can therefore only union the reduction lookaheads, and any new conflict must be reduce-reduce.

Discuss in Forum

29.

Arrange these stages of a single reduce action in the order they occur.
1. the goto table is consulted for the exposed state and left side
2. the action table reports a reduction by a chosen production
3. the left side and its new state are pushed onto the stack
4. the right side symbols are popped from the parsing stack

A.2 - 4 - 1 - 3
B.3 - 1 - 4 - 2
C.4 - 2 - 1 - 3
D.2 - 1 - 4 - 3

Answer: A

Correct answer: 2 - 4 - 1 - 3

The order is fixed by what each step needs from the last. The action table, indexed by the state on top and the lookahead, says which production to reduce by; the right side symbols and their states are then popped, exposing the state beneath; the goto table is consulted with that exposed state and the left side; and the left side with its new state is pushed. The input pointer never moves.

Discuss in Forum

30.

An LR(0) parser decides to reduce

A.after examining two tokens of lookahead in the input
B.whenever a complete item is present, without consulting the lookahead
C.only when the lookahead falls in the FOLLOW set of the left side
D.only when the lookahead matches the item's attached terminal

Answer: B

Ignoring the lookahead makes LR(0) conflict on almost every real grammar. The construction matters chiefly as the foundation on which SLR and the later methods build. Understanding it makes the later constructions much easier to follow.

Discuss in Forum

Loading…

Topics

Other Subjects

Tags: Bottom Up Parsing Questions and Answers || Bottom Up Parsing MCQ Questions and Answers || Bottom Up Parsing GK Questions and Answers || Bottom Up Parsing GK MCQ Questions || Bottom Up Parsing Multiple Choice Questions and Answers || Bottom Up Parsing GK || GK on Bottom Up Parsing || Compiler Design Questions and Answers || Compiler Design MCQ Questions and Answers || Compiler Design GK Questions and Answers || GK on Compiler Design

Bottom Up Parsing Questions and Answers

Topics

Other Subjects

About Us

Stay informed about all important Dates & Notifications