Zum Inhaltsverzeichnis
Der Parser
Bottom-Up-Parser
LR-Parser
Vorherige Seite Nächste Seite
Trennlinie

 
 
LR-Parser

Einordnung

 

Eine Unterklasse von SR-Parsern bilden die LR-Parser, wobei das "L" deutlich machen soll, dass die Eingabe von links nach rechts abgearbeitet wird; das "R" steht für die Bildung einer Rechtsableitung. Die Auswahl der nächsten Aktion erfolgt mit Hilfe einer Aktion- und einer Sprungtabelle. Nachfolgend wird die Zusammenfassung dieser Tabellen als Parsetabelle bezeichnet.

LR-Parser haben eine Reihe von Vorteilen:

  • LR-Parser sind so mächtig, daß eine Vielzahl von kontextfreien Grammatiken erkennt werden können. Insbesondere können für praktisch alle Konstrukte von Programmiersprachen entsprechende Grammatiken geschrieben werden.
  • LR-Parser benötigen kein Backtracking und können effizient implementiert werden.
  • Die Klasse der von LR-Parsern syntaktisch analysierbaren Grammatiken ist eine echte Obermenge der Klasse von Grammatiken, die mit prädiktiven Parsern syntaktisch analysiert werden können.
  • Da der LR-Parser die Eingabe von links nach rechts abarbeitet, werden Fehler früh erkannt. Insbesondere werden keine reduce-Aktionen durchgeführt.

Der Parsingalgorithmus liest das nächste Zeichen und wählt auf Grund des Eintrages in der Parsertabelle die nächste durchzuführende Aktion, wobei es folgende Aktionen des Parsers gibt:
  
shift k: nächstes Token von dem Eingabeband auf den Stack verschiebenverschieben und in den Zustand k wechseln, also k auf den Stack legen
  
reduce(i): oben auf dem Stack wurde ein " handle " erkannt; ersetze das handle durch die linke Seite der iten Regel
  
accept: Eingabe wurde vollständig gelesen und als Wort der Sprache erkannt. Realisiert wird dieses Erkennen durch die Erweiterung der Grammatik um eine Produktion S'->S. Ein Eingabewort wird nach der Reduktion mit dieser Regel akzeptiert, wenn die Eingabe vollständig konsumiert wurde.
  
error: Es ist ein Syntaxfehler aufgetreten
  

 

 
 
Beispiel

Sei die erweiterte Grammatik:
S' --> S (Regel 0)
S --> C C (Regel 1)
C --> c C (Regel 2)
C --> d (Regel 3)

Funktionsweise eines LR-Parser

Mit der Parsetabelle aus obiger Abbildung führt der Parser bei Eingabe des Wortes 'ccdcd' folgende Schritte durch:

Zeile Aktion Rest des Eingabewortes
nach Aktion
Stack
nach Aktion
1 Initialisieren ccdcd 0
2 shift 3 cdcd 0 c3
3 shift 3 dcd 0 c3 c3
4 shift 4 cd 0 c3 c3 d4
5 reduce mit
C->d
cd 0 c3 c3 C8
6 reduce mit
C->c C
cd 0 c3 C8
7 reduce mit
C->c C
cd 0 c3 C2
... ... ... ...

Die Zeile 3 bis 5 der Abarbeitung sollen erläutert werden, um dies zu verdeutlichen:
Der aktuelle Zustand ist 3 (zu erkennen an der Zahl oben im Stack) und das nächste Symbol ein 'd'. Ein Blick auf die Parsetabelle zeigt, dass in diesem Fall ein 'shift 4' durchgeführt wird und das 'd' und der neue Zustand 4 werden auf den Stack gelegt (vgl. Zeile 4). Im Zustand 4 (jetzt auf der Spitze des Stacks) bei einem neuen nächsten Symbol 'c' findet sich der Eintrag 'reduce 3', dh. es wird mit der Regel 3 (C->d) reduziert. Dazu wird das 'd' (und der dazugehörige Zustand) von Stack entfernt. Danach steht der Zustand 3 an der Spitze des Stacks und es wird der Sprung aus dem Zustand 3 mit dem Symbol 'C' ermittelt. Ein Blick auf die Sprungtabelle zeigt, dass dabei in den neuen Zustand 8 gesprungen wird. Also wird das Symbol 'C' und der Zustand 8 auf der Spitze des Stacks gelegt.

Es gibt verschiedene Techniken zur Generierung von Parsetabellen, die ein LR-Parser zur Auswahl seiner Aktionen benötigt und den Parsern ihren Namen geben:
  
SLR-Parser
  
Kanonischer LR-Parser
  
LALR-Parser

Die verschiedenen Klassen von LR-Parsern unterscheiden sich in ihrer Mächtigkeit und Leichtigkeit der Implementierung.

 

Trennlinie
Zum Seitenanfang Vorherige Seite Nächste Seite

Letzte Änderung 2. Juni 1999 © Copyright Thomas App