In some grammars, Bison’s deterministic LR(1) parsing algorithm cannot decide whether to apply a certain grammar rule at a given point. That is, it may not be able to decide (on the basis of the input read so far) which of two possible reductions (applications of a grammar rule) applies, or whether to apply a reduction or read more of the input and apply a reduction later in the input. These are known respectively as reduce/reduce conflicts (see section Reduce/Reduce Conflicts), and shift/reduce conflicts (see section Shift/Reduce Conflicts).
To use a grammar that is not easily modified to be LR(1), a more general
parsing algorithm is sometimes necessary. If you include
among the Bison declarations in your file (see section Outline of a Bison Grammar), the
result is a Generalized LR (GLR) parser. These parsers handle Bison
grammars that contain no unresolved conflicts (i.e., after applying
precedence declarations) identically to deterministic parsers. However,
when faced with unresolved shift/reduce and reduce/reduce conflicts, GLR
parsers use the simple expedient of doing both, effectively cloning the
parser to follow both possibilities. Each of the resulting parsers can
again split, so that at any given time, there can be any number of possible
parses being explored. The parsers proceed in lockstep; that is, all of
them consume (shift) a given input symbol before any of them proceed to the
next. Each of the cloned parsers eventually meets one of two possible
fates: either it runs into a parsing error, in which case it simply
vanishes, or it merges with another parser, because the two of them have
reduced the input to an identical set of symbols.
During the time that there are multiple parsers, semantic actions are recorded, but not performed. When a parser disappears, its recorded semantic actions disappear as well, and are never performed. When a reduction makes two parsers identical, causing them to merge, Bison records both sets of semantic actions. Whenever the last two parsers merge, reverting to the single-parser case, Bison resolves all the outstanding actions either by precedences given to the grammar rules involved, or by performing both actions, and then calling a designated user-defined function on the resulting values to produce an arbitrary merged result.
|• Simple GLR Parsers||Using GLR parsers on unambiguous grammars.|
|• Merging GLR Parses||Using GLR parsers to resolve ambiguities.|
|• GLR Semantic Actions||Considerations for semantic values and deferred actions.|
|• Semantic Predicates||Controlling a parse with arbitrary computations.|