Lookahead

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche
Dieser Artikel behandelt Lookaheads bei der Syntaxanalyse im Compilerbau. Zu Look-ahead-assertions in regulären Ausdrücken siehe Regulärer Ausdruck.

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 Tokenizer (lexikalischer Scanner) vorausschaut (der Wert ist 1 für die meisten Programmiersprachen).

Parser ohne Lookahead wie LR(0)-Parser oder SLR-Parser (Simple-LR-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[Bearbeiten]

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

Nehmen wir 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. 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[Bearbeiten]

Weblinks[Bearbeiten]