Defaulting
Using lookahead symbols to resolve ambiguity is the essence of LR(1) algorithm (the '1' stands for one lookahead symbol). There are however situations when analyzing lookahead is not necessary.
Reduction does not require reading next input symbol since it modifies elements already on stack. If a state contains only a single possible action, reading next symbol is not necessary to choose between available actions. That's why states with single reduction can be processed in a simplified way, without fetching lookahead symbol.
Replacing multiple actions with a single default action is called 'defaulting'. A state that was simplified this way is called a defaulted state. Defaulting is a method of decreasing parser table sizes and is done for optimization reasons only.
If input data is valid, parser behavior is the same whether defaulting is used or not. However if input data contains errors, parser behavior can be different when defaulting is used.
This problem will be illustrated using following grammar:
@2 WHO_WHAT: Mary had;
@3 WHOM: lamb;
@4 WHOM: goat;
Below is an automaton for the grammar. The automaton was built without defaulting (all states have full lookahead tables). Only states relevant to analyzed scenario are shown:
position in grammar
SENTENCE: WHO_WHAT . WHOM
actions
lamb shift to #7
goat shift to #8
WHOM goto #6
state #4
position in grammar
WHO_WHAT: Mary . had
actions
had shift to #5
state #5
position in grammar
WHO_WHAT: Mary had .
actions
lamb reduce by @2 to WHO_WHAT
goat reduce by @2 to WHO_WHAT
state #7
position in grammar
WHOM: lamb .
actions
$end reduce by @3 to WHOM
state #8
position in grammar
WHOM: goat .
actions
$end reduce by @4 to WHOM
In above grammar state #5 corresponds to end of production WHO_WHAT:
WHO_WHAT: Mary had ^
State #5 has just one action defined, a reduction by production @2. It is a potential candidate for defaulting.
Without defaulting
When not configured explicitly LR(1) parser generated by Alpag does not use defaulting. All states have action tables with explicit entries for various lookahead symbols
Action table for state #5 contains two entries:
goat reduce by @2 to WHO_WHAT
During parser construction list of all terminals that can possibly appear next is calculated for each state. In state #5 after 'Mary had' next possible terminal symbols are lamb or goat. That's why action table for state #5 contains two explicit entries for these symbols.
When parser reaches state #5 a lookahead symbol is fetched and compared against action table. If lookahead symbol is lamb or goat reduction by production 2 is done. For other symbols an error is reported.
For example if input sequence is 'Mary had Mary' then automaton upon reaching state #5 fetches 'Mary' as lookahead symbol. Since this symbol has no action defined in state #5 parsing fails.
With defaulting
State #5 contains only one action and can be defaulted.
When defaulting is on, definition of state #5 changes as follows:
position in grammar
WHO_WHAT: Mary had .
actions
all symbols reduce by @2 to WHO_WHAT
A single catch-all action is defined for all possible terminals. When parser reaches state #5 it does not fetch a lookahead symbol. It simply performs a reduction regardless what next symbol is.
Assuming that input text is 'Mary had Mary' parser steps are:
Do not fetch lookahead. Use default rule and perform reduction by production @2 to WHO_WHAT:
State #3 has multiple actions for different terminals, so lookahead symbol is necessary. Read lookahead symbol:
There is no action for terminal Mary in state #3. Parsing fails
Conclusions
If input contains no errors (conforms to grammar) then parser behavior is the same with and without defaulting. When input contains an error, exact moment this error is detected may be different with defaulting on or off.
- Without defaulting errors are detected very early. Lookahead symbols are inspected in all states. If next symbol is not present in action table, error is generated immediately.
- With defaulting enabled errors are detected only in those states, where erroneous symbol is fetched. It is possible that multiple reductions occur before a non-defaulted state is reached and input symbol is checked against parser table .
Consider following grammar which matches input sequence 'a b c d':
@2 ABC: a BC
@3 BC: b C
@4 C: c
If input sequence is 'a b c z' and current parser state is immediately after 'c' like this:
pending input: z
Current position in grammar:
@1 ABCD: ABC ^ d
@2 ABC: a BC ^
@3 BC: b C ^
@4 C: c ^
then:
- with defaulting disabled, error is detected right away, and production @4 is not reduced
- with defaulting enabled parser will reduce productions @4, @3, @2 and will not fail until trying to shift d in production @1. If productions have any code attached, then code for productions @4, @3, @2 will fire as well.
Reduction preview
Alpag provides reduction preview mechanism which enables both defaulting and early error detection.
When option Parser.Reduction.PreviewCheck is on, parser performs simulated reductions before performing actual reductions.
When parser is in defaulted state it cannot verify next input symbol. It performs simulated reduction and gets to the after-reduction state. If this state is also defaulted parser performs the procedure again, until non-defaulted state is found. Then it verifies next input symbol against action table of this non-defaulted state. If result of verification is positive parser gets back to starting point and performs reductions once again, this time 'for real'. If result is negative parser gets back to starting point and reports error there. Error is reported as if defaulting was not used.
Reduction preview mechanism introduces processing overhead though is not prohibitively costly. Note that mechanism is activated only in defaulted states. For non-defaulted states parser works as usual.