Next: Locations, Previous: Semantic Actions, Up: Concepts [Contents][Index]
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 Reduce/Reduce), and shift/reduce conflicts (see Shift/Reduce).
To use a grammar that is not easily modified to be LR(1), a
more general parsing algorithm is sometimes necessary. If you include
%glr-parser
among the Bison declarations in your file
(see Grammar Outline), 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. | |
• Compiler Requirements: | GLR parsers require a modern C compiler. |
Next: Locations, Previous: Semantic Actions, Up: Concepts [Contents][Index]