Lookahead

The Look Ahead function is defined as the perspective on inputs during automatic processing of texts in the compiler.

The number of tokens that looks ahead a parser, is a measure of the effort that must be operated in order to clearly distinguish grammatical constructions of the input from each other. Based on this number k can be parsers and grammars classify formally:

An LR parser with a lookahead of k () can reduce conflict-free LR (k ) grammars.

As lookahead also the number of characters is called, among other things, that a tokenizer ( lexical scanner) looking ahead (the value is 1 for most programming languages).

Parser without lookahead as LR ( 0) parser or SLR parser ( Simple LR parser ) can in many popular grammars that are used for the description of programming languages ​​fall into two different conflicts:

Shift -Reduce Example

There is a known shift-reduce problem, the so-called dangling -else problem.

Suppose the rule in Backus- Naur Form:

:: = IF THEN                | IF THEN ELSE Here the compiler knows not whether to reduce or should proceed with ELSE, if an alternative should follow. This problem occurs most often when you can automatically generate the parser with the parser generator Yacc or Bison GNU. It does not matter if a look-ahead is present or not.

A possible solution to this problem is the following:

:: =                | :: = IF THEN ELSE                | Other statements :: = IF THEN                | IF THEN ELSE However, this is extremely difficult to read.

A simple way in other GNU Bison ( Yacc ) would be:

% token KW_ELSE % token KW_IF % nonassoc LOWER_THAN_ELSE % nonassoc KW_ELSE IFSTATEMENT: KW_IF ' ( ' assignment ')' block2 % prec LOWER_THAN_ELSE             | KW_IF ' ( ' assignment ')' block2 KW_ELSE block2            ; % prec LOWER_THAN_ELSE here has the rule in which it stands, the precedence of LOWER_THAN_ELSE to. This is about the token definition of KW_ELSE, is the first rule to IFSTATEMENT so a lower precedent in the Reduce- decision as the second.