next up previous contents
Next: SLR(1) Parsers Up: Handle-recognising DFAs and LR(0) Previous: The parsers   Contents

Inadequte States

It is possible that some of the DFA states constructed using the previous algorithm will contain items which suggest both ``shift'' and ``reduce'' actions. This situation is known as a shift/reduce conflict.

Because we have conflicts in the handle-recognising DFA, the parser will not know which action to take; it will have to pick one arbitrarily and try it out. Because of this non-determinism, we say that the grammar was not $LR(0)$.

An alternative problem could arise if we have two or more items in a state which have the `` ${}_{\triangle}$'' marker to the right of their r.h.s.; thus we would not know which one to reduce by. This situation is called a reduce/reduce conflict. Instances of this are rarer than shift/reduce conflicts.

[Note that no state can have a shift/shift conflict since we are using a DFA; this sort of problem would arise only as a result of using an NFA.]

Any state in a handle-recognising DFA which contains either a shift/reduce or a reduce/reduce conflict is known as an inadequate state.

It is the ideal of $LR$ parser design to minimise the number of inadequate states without sacrificing efficiency. The most common way of doing this is to introduce lookahead into the parser construction, leading to the $LR(1)$ family of parsers.


next up previous contents
Next: SLR(1) Parsers Up: Handle-recognising DFAs and LR(0) Previous: The parsers   Contents
James Power 2002-11-29