Lookahead

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

Weblinks


Wikimedia Foundation.

Игры ⚽ Нужна курсовая?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Lookahead — is a tool in algorithms for looking ahead a few more input items before making a cost effective decision at one stage of the algorithm. Lookahead vs. Lazy evaluation This is in contrast to another technique called lazy evaluation that delays the… …   Wikipedia

  • lookahead — noun The analysis in advance of subsequent decisions that would be made if a particular branch of an algorithm was followed. Our computer chess program uses lookahead to avoid difficult endgames …   Wiktionary

  • Lookahead Carry Unit — A Lookahead Carry Unit (LCU) is a logical unit in digital circuit design used to decrease calculation time in adder units and used in conjunction with carry look ahead adders (CLAs).16 bit adderBy combining four 4 bit CLAs, a 16 bit adder can be… …   Wikipedia

  • lookahead routing —    A switching system feature that uses a dedicated communications channel to verify the availability of all links required to switch the call …   IT glossary of terms, acronyms and abbreviations

  • Carry-lookahead adder — 4 bit adder with carry lookahead A carry lookahead adder (CLA) is a type of adder used in digital logic. A carry lookahead adder improves speed by reducing the amount of time required to determine carry bits. It can be contrasted with the simpler …   Wikipedia

  • Carry look-ahead adder — A carry look ahead adder is a type of adder used in digital logic. It can be contrasted with the simpler, but usually slower, ripple carry adder ( see adder for detail on ripple carry adders ). A ripple carry adder works in the same way as pencil …   Wikipedia

  • Compiler — Historisches Beispiel anhand von CBASIC Ein Compiler (auch Übersetzer oder Kompilierer genannt) ist ein Computerprogramm, das ein in einer Quellsprache geschriebenes Programm (Quelltext/Quellprogramm, meist von einem Programmierer in einer… …   Deutsch Wikipedia

  • Compiler-Front-End — Ein Compiler (auch Übersetzer oder Kompilierer genannt) ist ein Computerprogramm, das ein in einer Quellsprache geschriebenes Programm – genannt Quellprogramm – in ein semantisch äquivalentes Programm einer Zielsprache (Zielprogramm) umwandelt.… …   Deutsch Wikipedia

  • Kompilierer — Ein Compiler (auch Übersetzer oder Kompilierer genannt) ist ein Computerprogramm, das ein in einer Quellsprache geschriebenes Programm – genannt Quellprogramm – in ein semantisch äquivalentes Programm einer Zielsprache (Zielprogramm) umwandelt.… …   Deutsch Wikipedia

  • Kompiliert — Ein Compiler (auch Übersetzer oder Kompilierer genannt) ist ein Computerprogramm, das ein in einer Quellsprache geschriebenes Programm – genannt Quellprogramm – in ein semantisch äquivalentes Programm einer Zielsprache (Zielprogramm) umwandelt.… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”