Lookahead

Mit Lookahead bezeichnet man 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:

Ein LR-Parser mit einem Lookahead von k ($k \in \mathbb{N}$) kann LR(k)-Grammatiken konfliktfrei reduzieren.

Als Lookahead wird unter anderem auch die Anzahl von Zeichen bezeichnet, die ein Lexikalischer Scanner vorausschaut (der Wert ist 1 für die meisten Programmiersprachen).

Parser ohne Lookahead wie LR(0)-Parser oder SLR-Parser können bei vielen gängigen Grammatiken, die zur Beschreibung von Programmiersprachen verwendet werden, 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.

Shift-Reduce-Beispiel

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

Nehmen wir die Regel in BNF:

<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 Parser-Generator Yacc oder GNU Bison automatisch generieren lässt. 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.

Siehe auch

• LR-Parser
• LALR-Parser
• SLR-Parser

Weblinks

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