As already observed in Section 4, the use of Generalized LR parsing is essential for solving the parsing problem for large, existing, languages that have many dialects.
LR parsing is based on shift/reduce parsing: symbols from the input stream are either ``shifted'' (i.e., placed on an auxiliary stack) or a ``reduce'' action is performed (i.e., the top symbols pushed on the stack represent one side of a grammar rule and can be replaced by the other side of the rule). For the class of LR-parsable languages, one can always make a unique choice between shifting or reducing. For the larger class of all context-free grammars this is no longer the case and there may shift/reduce conflicts (reading the next symbol or reducing the current stack) or reduce/reduce conflicts (the stack can be reduced according to different grammar rules).
The basic idea of GLR parsing is to fork the parse process at points where several choices are possible. All parses are synchronized on reading the next input symbol and parallel parses are joined whenever possible. In this manner, a parse forest is build that maximizes the sharing between the parallel parses.
A striking similarity exists between GLR parsing and parallel rewriting where a rewrite system may contain critical pairs and parallel reduction takes place for all possible redexes. In principle, the same (parallel) rewriting machinery could be used for both rewriting and GLR parsing.
In the context of the ASF+SDF Meta-Environment the benefits would be substantial:
