 |
|||
| HSG |
|
Beispiel
S --> T*S S --> T T --> i
Um bei der späteren Rückverfolgung ein eindeutiges Ende zu haben, wird ein neues Startsymbol S' hinzugefügt.
S'--> S S --> T*S S --> T T --> i
Terminale Symbole: *, i
Nonterminale Symbole: S', S, T
Das Wort i*i wird akzeptiert, eine Ableitung könnte so aussehen:
S' --> S --> T*S --> T*T --> T*i --> i*i
Die Idee ist nun, diese Ableitung durch einen Automaten gesteuert rückwärts zu gehen. Dazu stellt man zunächst alle möglichen Zustände, die man bei einer Ableitung durchlaufen kann, in einem Zustandsdiagramm dar
Die Erstellung des Zustandsdiagramms
Eine Produktion mit einem Punkt irgendwo in der rechten Seite heißt LR(0)-Element. Ein LR(0)-Element zeigt an, wo man bei der Bearbeitung einer Produktion gerade steht (Punkt=Standpunkt). Im Drachenbuch S.293 wird das so beschrieben:
Intuitiv gesehen zeigt ein Item an, wie viel wir an einem bestimmten Punkt der Analyse von der Produktion bereits gesehen haben. Das Item A → .XYZ zeigt beispielsweise, dass wir hoffen, als nächsten Teil der Eingabe einen von XYZ ableitbaren String zu sehen. Item A → X.YZ bedeutet, dass wir in der Eingabe gerade einen von X ableitbaren String gesehen haben und hoffentlich demnächst einen von YZ ableitbaren String sehen. Item A → XYZ. heißt, dass wir den Rumpf XYZ gesehen haben und es an der Zeit sein mag, XYZ auf A zu reduzieren.
Es ist klar, dass man mit .S beginnen wird, man steht so vor dem Start einer Ableitung. S könnte im vorliegenden Fall durch T*S oder T ersetzt werden, dh. der Anfangszustand wird bisher durch S'→.S, S→.T*S und S→.T beschrieben. Nachdem aber auch T durch i ersetzt werden könnte, wird er auf {S'→.S , S→.T*S , S→.T , T→.i} (.i*S geht nicht, da i*S keine rechte Seite einer Produktion) erweitert. Die beschriebenen Erweiterungen nennt man Hüllenbildung oder CLOSURE. Die Menge von LR(0)-Elementen wird mit einem Zustand, hier dem Anfangszustand, gleichgesetzt.
So könnte man also starten! Wie könnte es weitergehen?
Man sieht, dass man Produktionen mit S oder T auf der linken Seite oder auch das Terminal i verarbeiten könnte. Für diese drei Möglichkeiten werden mögliche Folgezustände, die GOTO-Mengen bestimmt. GOTO(q0,S) = q1 bestimmt dann die Menge von LR(0)-Elementen, die den Fortgang einer Ableitung beschreiben unter der Voraussetzung, dass das nonterminale Symbol S verwendet werden soll. Da in q0 das einzige Element mit S nach dem Punkt S'→.S ist, kann nur das Element S'→S. folgen. In diesem Element steht der Punkt ganz rechts, dh. eine komplette Produktion wurde durchgegangen. Der Zustand q1 wird deshalb als 'final' gekennzeichnet. Hier wird später reduziert (rechte Seite einer Produktion wird durch die linke ersetzt) werden können. Übrigens ohne Konflikt, da nur eine Möglichkeit besteht. GOTO(q0,T) = q2 ist etwas interessanter, hier gibt es zwei Möglichkeiten: S→T. oder S→T.*S . Die erste Möglichkeit wäre wieder final, da die ganze Produktion S→T abgearbeitet ist. Die zweite Möglichkeit bedeutet, dass man in der Abarbeitung von S→T*S mit dem terminalen Symbol * fortfahren könnte. Hier muss später eine reduce-shift (shift - erst mal auf den Stack schieben) - Entscheidung gefällt werden. GOTO(q0,i) = q3 gibt ausgehend von T→.i die weitere Abarbeitung an. Hier findet man nur das Element T→i. , dh. der Zustand ist final.
Die Zustände q1 und q3 lassen sich im Sinne des Erkennens einer Produktion nicht fortsetzen, q2 hingegen schon. Hier ist GOTO(q2,*) = q4 zu bestimmen. Natürlich ist S→T*.S in der Menge. Man könnte aber das S hinter dem Punkt als Anfang einer neuen Abarbeitung einer Produktion auffassen. In der Hüllenbildung werden daher die Elemente S→.T und S→.T*S hinzugenommen. Da man T aber wieder als Anfang einer Produktion haben kann, kommt noch T→.i hinzu.
Beim Durchmustern der Elemente von q4 sieht man, dass S, T oder i als Grammatiksymbole folgen könnten. GOTO(q4,S) = q5 besteht nur aus S→T*S. und ist final (später Reduzierung ohne Konflikt). GOTO(q4,T) wird exakt als q2 erkannt. GOTO(q4,i) enthält nur das Element T→i. , das ist der schon aufgestellte Zustand q3. Der Zustandsgraph ist nun komplett. Er enthält in gewisser Weise alle Zustände, in die man im Verlauf einer Ableitung geraten könnte.
Das Aufstellen der Syntaxanalyse-Tabelle
Die Tabelle gibt an, in welchen neuen Zustand einer Ableitung man in Abhängigkeit vom aktuellen Zustand und vom nächsten zu verarbeitenden Symbol übergehen soll. Ist man z.B. im Zustand 0 und soll das Symbol i verarbeiten, so gerät man in Zustand 3 und merkt sich aber die Eingabe i auf einem Stack. Üblicherweise wird der Stack zum Speichern der Symbole und zum Speichern der Zustände verwendet.
* i $ | S T
0 s3 | Stack: 3i0
1 |
2 |
3 |
4 |
5 |
In einem finalen Zustand könnte eine Reduktion erfolgen, dh. eine auf dem Stack gespeicherte Eingabe könnte einer rechten Seite einer Produktion entsprechen und durch die linke Seite der Produktion ersetzt werden. Durch die Ersetzung fällt man gewissermaßen etwas in die Vergangenheit zurück. Man ist wieder in dem Zustand in dem der Aufbau der rechten Seite begonnen hat. Beim LR(0)-Verfahren wird kein lookahead beim Reduzieren verwendet, dh. es wird ganz gleich was kommt reduziert.
* i $ | S T
0 s3 |
1 |
2 |
3 r3 r3 r3 | Stack: T0
4 |
5 |
In der Tabelle steht daher bei Zustand 3 überall r3, dh. es soll reduziert werden und zwar mit der 3. Produktion (man beginnt bei Null zu zählen). Nach der Reduzierung ist man wieder im Zustand 0, was man oben auf dem Stack ablesen kann. Da bei jedem Shift nicht nur das Symbol, sondern anschließend auch der neue Zustand auf den Stack gelegt wird, müssen natürlich bei einer Reduktion zweimal so viele Einträge vom Stack geholt werden wie die zu ersetzende rechte Seite lang ist. Nach einer Reduktion liegt ein nonterminales Symbol auf dem Stack, das es zu verarbeiten gilt, dh. es muss ein 'Sprung' zu einem neuen Zustand erfolgen, der folgen soll. Im Beispiel lesen wir am Automaten ab, dass der Zustand 2 folgen muss. Dieser Zustand wird dann auf den Stack gelegt.
* i $ | S T
0 s3 | 2
1 |
2 |
3 r3 r3 r3 | Stack: 2T0
4 |
5 |
Da ein * folgt, sind wir an der Stelle S → T.*S und gehen über nach S → T*.S. Der Tabelleneintrag dazu lautet [2,*] = s4. Das folgende i führt zum Eintrag [4,i] = s3.
* i $ | S T
0 s3 | 2
1 |
2 s4 | Stack: 4*2T0
3 r3 r3 r3 |
4 s3 | Stack: 3i4*2T0
5 |
Der Zustand 3 ist final, es wird reduziert, die Einträge sind schon in der Tabelle. Da reduziert wird, muss entsprechend der linken Seite, hier T, und dem obersten Zustand auf dem Stack, hier 4, gesprungen werden. Am Automatengraphen liest man ab [4,T] = 2.
* i $ | S T
0 s3 | 2
1 |
2 s4 |
3 r3 r3 r3 | Stack: 2T4*2T0
4 s3 | 2
5 |
Der Zustand 2 ist final, es liegt T oben auf dem Stack, es kann also reduziert werden. Aus dem T wird ein S, das ist Produktion 2. Es wird nun bei LR(0) überall in Zeile 2 r2 eingetragen, was bei [2,*] zu einem shift-reduce-Konflikt führt. Da reduziert wurde, folgt wieder ein Sprung, [4,S] = 5 wird eingetragen.
* i $ | S T
0 s3 | 2
1 |
2 s4/r2 r2 r2 | Stack: 5S4*2T0
3 r3 r3 r3 |
4 s3 | 5 2
5 |
Der Zustand 5 ist final, es wird mit r1 reduziert.
* i $ | S T
0 s3 | 2
1 |
2 s4/r2 r2 r2 |
3 r3 r3 r3 |
4 s3 | 5 2
5 r1 r1 r1 | Stack: 0
Da reduziert wurde, erfolgt ein Sprung, [0,S] = 1. Der Zustand 1 ist final, also wird reduziert, da auf S' reduziert wird, weiß man, dass das Verfahren hier erfolgreich endet. Statt der Reduktion r0 überall in Zeile 1 wird oft nur acc bei $ eingetragen.
* i $ | S T
0 s3 | 2
1 r0 r0 r0 | Stack: 0
2 s4/r2 r2 r2 |
3 r3 r3 r3 |
4 s3 | 5 2
5 r1 r1 r1 |
Algorithmus zum Aufstellen der Tabelle
Um die Syntaxanalyse-Tabelle aufstellen zu können, schaut man sich zunächst die Transitionen des Zustandsgraphen an. Man findet drei Kanten, die mit terminalen Symbolen beschriftet sind. Sie führen zu den Einträgen [2,*]=s4, [0,i]=s3 und [4,i]=s3.
* i $ | S T
0 s3 |
1 |
2 s4 |
3 |
4 s3 |
5 |
Die Transitionen mit nonterminalen Symbolen führen zu Einträgen in der 'Sprungtabelle': [0,S]=1, [0,T]=2, [4,T]=2 und [4,S]=5
* i $ | S T
0 s3 | 1 2
1 |
2 s4 |
3 |
4 s3 | 5 2
5 |
Reduktionen können nur in finalen Zuständen stattfinden. Um sie bequemer eintragen zu können, werden die Produktionen durchnummeriert, wobei die zusätzliche Produktion S'→S die Nummer 0 bekommt. Zustand 1 führt dann zum Eintrag r0 in der kompletten Zeile 1. Zustand 2 führt zur Reduktion r2 (S ← T), dh. die Zeile 2 wird mit r2 gefüllt. Zustand 3 führt zur Reduktion r2, Zustand 5 zur Reduktion r1. Jeweils wird die Zeile gefüllt.
* i $ | S T
0 s3 | 1 2
1 r0 r0 r0 |
2 s4/r2 r2 r2 |
3 r3 r3 r3 |
4 s3 | 5 2
5 r1 r1 r1 |
Aufgabe
Verfolge mit Hilfe der Compilertools ct1.py auf der Python-Konsole zu obiger Grammatik den Weg zur LR(0)-Syntaxanalyse-Tabelle.
a) Baue dazu sukzessive die Zustandsmenge Z als Liste von Mengen und die Menge T der Transitionen als Dictionary auf. Erstelle abschließend mit Hilfe von JFLAP einen Automatengraphen.
b) Erstelle aus dem Automaten die LR(0)-Tabelle LR0 als Dictionary. Gib die Tabelle mit der Funktion print_Tabelle aus den Compilertools aus. Achte auch auf shift-reduce-Konflikte.
Beispiel G1
Dr. Kunert, LR(k)-Analyse für Pragmatiker
