The GOTO function on a set of items and a grammar symbol produces
Answer: C
Advancing the dot models having pushed that symbol, and closure then adds whatever may begin next. Repeatedly applying GOTO from the initial set constructs the whole automaton. The construction terminates because only finitely many item sets exist.
Please log in or register to report this question.
The grammar is augmented before the LR item sets are constructed in order to
Answer: D
Adding S prime going to S means the parser accepts exactly when it reduces that one production with the input exhausted. Without it, acceptance would need an awkward special case. The cost is one extra state and one extra production.
Please log in or register to report this question.
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
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.
Please log in or register to report this question.
In the SLR construction, a reduction by A goes to alpha is entered for lookahead a when
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.
Please log in or register to report this question.
SLR parsing can report a conflict where canonical LR does not because
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.
Please log in or register to report this question.
An LR(1) item differs from an LR(0) item by carrying
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.
Please log in or register to report this question.
The core of an LR(1) state is
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.
Please log in or register to report this question.
LALR parsing is constructed by
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.
Please log in or register to report this question.
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.
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.
Please log in or register to report this question.
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.
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.
Please log in or register to report this question.
