Grammars often contain multiple alternative productions that start in the same way and differ only by their terminal elements. Parser working through input from left to right cannot choose between alternative productions after having seen just a few initial symbols, especially if these symbols are same in multiple productions. Parser must be considering multiple alternative interpretations of input sequence in parallel and keep reading. When, after reading enough symbols, only single interpretation remains valid, parser can choose it.
One of greatest strengths of LR(1) algorithm is ability to deal with such cases.
Example given below illustrates how LR(1) parser chooses between multiple alternatives which start in the same way. Studying this example can be very educative and help analyze automatons for production grammars.
Grammar is:
The grammar can accept two inputs which differ only by last terminal:
Note that depth of nesting grammar productions is different for both these inputs:
Parser reading input sequence starting with 'he drinks' is not capable of telling whether it matches first or second expansion. In first case after reading symbol he parser should recursively nest into production @3 for symbol drinks. In second case after reading he next terminal symbol drinks is on the same level in production @2.
Parser automaton is built to consider both these scenarios in parallel. This means that after reading 'he drinks' parser is at the same time inside production @2 as well as inside nested productions @1 and @3. Final decision is made after reading following token (coffee or tea). This final decision results in a sequence of reductions which can handle any nesting depth.
Here is automaton for the grammar:
Example will be explained using two scenarios. Initial steps are the same for both these scenarios:
After reading he:
After reading drinks:
Now depending on next input terminal either of two scenarios will take place.
Studying further steps pay attention to the sequence of reductions which convert sequence of tokens of, actually, the same length into parse trees of different depths.
Providing next symbol is coffee, situation is:
Sequence of reductions follows (turn attention to stack contents).
Current state is #9. Action for next symbol $end is to reduce coffee to BEVERAGE which replaces top of stack with nonterminal:
In state #7 next action is to reduce two top-of-stack elements drinks BEVERAGE to DOESWHAT.
In state #4 last reduction leads to:
If last input symbol is tea situation is:
In state #8 action under next symbol $end is to reduce by @4:
In state #6 next action is to reduce by @2 which leads to:
If grammar contains multiple similar productions, parser can postpone decision on choosing one of them and read more input symbols until only one production matches.
When reduction is executed, length of reduced production tells how many elements will be removed off the stack. It also determines the state in which parser resumes its operation after reduction. As a consequence similar stack configurations can be 'sliced' into different numbers of nested productions.