Lookahead

Lookahead ist die Vorausschau auf Eingaben beim automatischen Verarbeiten von Texten im Compilerbau.

Die Anzahl von Tokens, die ein Parser vorausschaut, ist ein Maß für den Aufwand, der betrieben werden muss, um grammatikalische Konstruktionen der Eingabe eindeutig voneinander zu unterscheiden. Anhand dieser Anzahl k lassen sich Parser und Grammatiken formal klassifizieren.

Als Lookahead wird unter anderem auch die Anzahl der Zeichen bezeichnet, die ein Tokenizer (lexikalischer Scanner) vorausschaut (der Wert 1 genügt für die meisten Programmiersprachen).

Der Lookahead spielt eine Rolle beim Top-down-Parsing (LL-Parser), sowie beim Bottom-up-Parsing. Im Folgenden wird letzterer Fall beleuchtet. Shift-Reduce-Parser, wie LR(0)-, SLR-, LR(1)-Parser, können in zwei unterschiedliche Konflikte geraten:

Shift-reduce

Hier weiß der Compiler nicht, ob er shiften oder reduzieren soll.

Reduce-reduce

Hier weiß der Compiler nicht, nach welcher Regel er reduzieren soll.

Der Lookahead kann helfen, dies zu vermeiden. Kann eine Sprache anhand einer Grammatik konfliktfrei mit einem Lookahead vom $k=1$ mit einem LR(k)-Parser geparst werden, so handelt es sich um eine LR(1)-Grammatik.

Shift-Reduce-Beispiel

Es existiert ein bekanntes Shift-Reduce-Problem, das sogenannte Dangling-Else-Problem.

Gegeben sei die Regel in Backus-Naur-Form:

<statement> ::= IF <expression> THEN <statement>
              | IF <expression> THEN <statement> ELSE <statement>

Hier weiß der Compiler nicht, ob er reduzieren soll oder mit ELSE fortfahren soll, falls eine Alternative folgen sollte. Dieses Problem tritt meistens dann auf, wenn man den Parser mit dem Parsergenerator Yacc oder GNU Bison automatisch generieren lässt, wird allerdings von diesen automatisch richtig gelöst. Dabei spielt es keine Rolle, ob ein Lookahead vorhanden ist oder nicht.

Eine mögliche Lösung dieses Problems ist folgende:

<statement> ::= <matched>
              | <unmatched>

<matched>   ::= IF <expression> THEN <matched> ELSE <matched>
              | other statements

<unmatched> ::= IF <expression> THEN <statement>
              | IF <expression> THEN <matched> ELSE <unmatched>

Dies ist aber äußerst schwer zu lesen.

Eine schlichte andere Möglichkeit in GNU Bison (Yacc) wäre:

%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 weist hierbei der Regel, in der es steht, die Präzedenz von LOWER_THAN_ELSE zu. Diese steht über der Tokendefinition von KW_ELSE, gibt der ersten Regel zu ifstatement also eine niedrigere Präzedenz bei der Reduce-Entscheidung als der zweiten.

Weblinks

• Shift-Reduce- und Reduce-Reduce-Problem trotz Lookahead