imported>IvanP: Rechtschreibung

2019-01-10T19:33:50Z

Rechtschreibung

Neue Seite

{{Dieser Artikel|behandelt Lookaheads bei der Syntaxanalyse im Compilerbau. Zu Look-ahead-assertions in regulären Ausdrücken siehe [[Regulärer Ausdruck#Look-around assertions|Regulärer Ausdruck]].}}

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

Die Anzahl von [[Token (Compilerbau)|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-Parser|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 <math>k=1</math> 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|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 <code>ELSE</code> 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
;
<code>%prec LOWER_THAN_ELSE</code> weist hierbei der Regel, in der es steht, die Präzedenz von <code>LOWER_THAN_ELSE</code> zu. Diese steht über der Tokendefinition von <code>KW_ELSE</code>, gibt der ersten Regel zu <code>ifstatement</code> also eine niedrigere Präzedenz bei der Reduce-Entscheidung als der zweiten.

== Weblinks ==
* [http://www.gobosoft.com/eiffel/gobo/geyacc/algorithm.html Shift-Reduce- und Reduce-Reduce-Problem] trotz Lookahead

[[Kategorie:Compilerbau]]

Lookahead - Versionsgeschichte

imported>IvanP: Rechtschreibung