Parser operation with lookaheads

The important element of LR(1) parser operation scheme is reading one input symbol ahead, and using it to resolve ambiguities. This will be explained using following recursive grammar:

Grammar reads a sequence of CMD commands which can be followed by optional Int or St.
Example input might look like this:

Each COMMAND starts with CMD terminal. If it is standalone CMD (production @3) reduction should happen next. If however next input terminal is Int or Str parser should continue reading to match productions @4 or @5. Available alternatives are:

Decision should depend on next input symbol.

To resolve cases like this LR(1) parser reads one symbol ahead just for preview. This lookahead symbol is used to resolve current situation but is not 'consumed' yet. Lookahead symbol is eventually removed from input and put to stack when parser performs a shift.

Example

Below is a fragment of parser automaton generated for above grammar:

Parser operation with lookahead symbols is illustrated below. Some irrelevant steps were skipped:

In state #1 parser reads first symbol (providing it is CMD) and shifts it to the stack:

To decide between three available options parser will read next symbol and keep it as a lookahead:

When lookahead is known parser can decide between three actions available in state #4. Since lookahead is CMD parser will reduce by production @3 to COMMAND:

then to:

In current state action for next symbol (i.e. lookahead is to shift it to stack). Parser shifts current lookahead to stack:

Parser is again in state #4 where three actions are available. To choose between them next input symbol mast be fetched and used as lookahead:

This time parser will not perform reduction. Since next symbol is Int parser shifts it and goes to state #5.

Next parser fetches CMD as lookahead:

Then parser reduces by @4 to COMMAND:

And finally reduces to COMMAND_ARRAY, still under the same lookahead CMD:

Conclusions

Analyzing lookahead mechanism several observations can be made:

• Lookahead symbol is simply a first symbol of input stream that was prefetched in order to choose between available actions in some state. Next time parser needs to shift, it shifts lookahead symbol is one is prefetched.
• There are states when lookahead symbol is absolutely necessary to make next decision (like state #4 above). There are also states when inspecting lookahead symbol is not really necessary since only one action is possible: a reduction (state #5 above)
• A lookahead symbol can be preloaded by parser or can be empty (if it wasn't necessary to complete recent steps). In terms of current position of parser and current position of input stream this means that sometimes input stream is one token ahead of parser (when lookahead preloaded).

Author of grammar can usually ignore lookahead mechanism. There are however few situations when lookahead prefetch must be taken into account. If activity of parser must be in some way synchronized with activity of lexer, the potential shift by one symbol between them may be relevant. Examples of this situation include:

• code executed from within parser actions (during reductions) is used to control the lexer (e.g. switch modes)
• code attached to parser actions checks lexer state for some conditions like reaching end of file.
• some actions are taken for lexer based on results of parsing (e.g. new input file is open for lexer based using filename detected when parsing)
• lexer state and parser state are compared during joint parser-lexer debug session

Lookahead processing must be taken into account when designing error recovery. Parser reports an error when invalid (i.e. unexpected) symbol appears on input. This invalid symbol is preloaded as lookahead when error fires. Sometimes it may be necessary to explicitly discard erroneous lookahead symbol before attempting error recovery.