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 mit einem LR(k)-Parser geparst werden, so handelt es sich um eine LR(1)-Grammatik.
