 |
|||
| HSG |
|
Beispiel 1
S --> ABcC A --> aA A --> λ B --> bbB B --> λ C --> BA
Für die Eingabe aacbb soll eine Ableitung gesucht werden. Dabei wird Folgendes bedacht:
- es wird die Eingabe von links nach rechts gelesen, L
- es wird jeweils das am weitesten links stehende Nonterminal ersetzt, L
- es wird jeweils ein terminales Symbol, das nächste verbleibende (lookahead), bei der Ersetzung berücksichtigt, 1
Es wird ein Stack benutzt und die Eingabe nach und nach abgebaut. $ ist ein Pseudo-Terminal, das das Ende der Eingabe anzeigt.
remaining stack nonterminal lookahead --------------------------------------------- aacbb$ S S a
Die einzige Möglichkeit, S zu ersetzen, führt zu
aacbb$ ABcC A a
A kann auf zwei Arten ersetzt werden, aber nur A --> aA führt zu einer Möglichkeit, remaining abzubauen
aacbb$ aABcC A a
Nachdem das a bei remaining und stack entfernt wurde, wird wieder A durch aA ersetzt
acbb$ aABcC A b
Der einzige Weg, den lookahead b mit dem Nonterminal A im Hinblick auf eine erfolgreiche Ableitung in Einklang zu bringen, ist eine Ersetzung A --> λ zu wählen.
cbb$ BcC B c
Jetzt muss B durch λ ersetzt werden, da B --> bbB nicht zu dem lookahead c passt.
cbb$ cC C b
C kann nur durch BA ersetzt werden
bb$ BA B b
Natürlich ersetzt man jetzt B durch bbB. Dadurch werden die letzten Zeichen der Eingabe abgebaut. Das Pseudo-Zeichen $ zeigt das Ende an.
bb$ bbBA B $
B wird durch λ ersetzt
$ A A $
A wird durch λ ersetzt
$ $
Die Eingabe ist abgebaut und der Stack ist leer, der String wird akzeptiert.
Wie könnte man das Vorgehen weiter algorithmisieren?
Man sieht, dass das Bestreben ist, das aktuelle Nonterminal so zu ersetzen, dass das lookahead-Zeichen in der Ersetzung bzw. in einer Ersetzungskette vornestehend auftaucht. Eine Ersetzung, die das nicht gewährleistet, ist sinnlos. Gibt es mehrere solche Ersetzungen, so hat man ein Entscheidungsproblem. Alle terminalen Zeichen, die irgendwann in einer Ableitungskette zu einer Folge von Grammatiksymbolen X vorne stehen können, gehören zur sogenannten FIRST(X) - Menge. Mit Hilfe der FIRST-Mengen fällt man die Entscheidung, welche Produktion bei mehreren Möglichkeiten zur Ersetzung ausgewählt wird.
Erstellen der Parser-Tabelle
Drachenbuch, S.271 (im Buch $ statt b in letzter Zeile, Druckfehler):
für jede Produktion A → α
begin
1. für jedes Terminal a in FIRST(α): α in T[A,a]
2. wenn λ in FIRST(α), dann
für jedes Terminal b in FOLLOW(A): α in T[A,b]
end
Parser-Tabelle zu obigem Beispiel
FIRST(ABcC) = {a,b,c} führt zum Eintrag
a b c $
--------------------------------------------
S ABcC ABcC ABcC
A
B
C
FIRST(aA) = {a} und FIRST(λ) = {λ}, dh. die beiden Möglichkeiten, A zu ersetzen, lassen sich eindeutig trennen. Wäre z.B. b in beiden Firstmengen, so könnte man im Falle, dass b lookahead ist, keine Entscheidung fällen. Die Grammatik wäre also nicht vom Typ LL(1). Da die rechte Seite λ natürlich zu λ reduziert werden könnte, muss bedacht werde, welche terminale Symbole A folgen könnten. Diese Symbole sind in der Menge FOLLOW(A) enthalten. Wegen FOLLOW(A) = {b,c,$} weiß man, dass auf A b, c oder $ folgen könnte, also ist es sinnvoll in diesem Fall die Ersetzung A --> λ zu wählen.
a b c $
--------------------------------------------
S ABcC ABcC ABcC
A aA λ λ λ
B
C
FIRST(bbB) = {b}, FIRST(λ) = {λ} und FOLLOW(B) = {a,c,$} führen zu den Einträgen
a b c $
--------------------------------------------
S ABcC ABcC ABcC
A aA λ λ λ
B λ bbB λ λ
C
FIRST(BA) = {a,b,λ} und FOLLOW(C) = {$} führen zu den Einträgen
a b c $
--------------------------------------------
S ABcC ABcC ABcC
A aA λ λ λ
B λ bbB λ λ
C BA BA BA
LL(1)-Kriterium
Eine Grammatik gehört genau dann zur Klasse LL(1), wenn für zwei unterschiedliche Produktionen A --> α und A --> β folgende Bedingungen gelten:
- FIRST(α) und FIRST(β) sind disjunkt, dh. sie haben keine gemeinsamen Elemente.
- Wenn λ ∈ FIRST(α) gilt, dann sind FIRST(β) und FOLLOW(A) disjunkt. Wenn λ ∈ FIRST(β) gilt, dann sind FIRST(α) und FOLLOW(A) disjunkt.
LL(1)-Kriterium am Beispiel
Man muss alle Produktionen mit gleicher linker und verschiedener rechter Seite untersuchen.
A --> aA FIRST(aA) = {a}
A --> λ FIRST(λ) = {λ}
1. FIRST(aA) ∩ FIRST(λ) = {}
2. λ ∈ FIRST(λ), aber FIRST(aA) = {a} und FOLLOW(A) = {b,c,$} sind disjunkt.
B --> bbB FIRST(bbB) = {b}
B --> λ FIRST(λ) = {λ}
1. FIRST(bbB) ∩ FIRST(λ) = {}
2. λ ∈ FIRST(λ), aber FIRST(bbB) = {b} und FOLLOW(B) = {a,c,$} sind disjunkt.
In beiden Fällen ist das Kriterium erfüllt.
Arbeitsweise eines LL(1)-Automaten
Zitat aus Rodger/Finley, JFLAP, An Interactive Formal Languages and Automata Package, S.108
How does LL(1) parsing work? A stack stores variables and terminals from right sides of productions, processing them by replacing variables with new productions and matching the terminals with corresponding terminals in the input string. The start symbol of the grammar is placed on the top of the stack to start. Variables are popped off the stack and replaced by the right side of a production, and terminals are popped off and matched in the order they appear in the string. When the stack is empty and all the terminals in the string have been matched, the string has been derived. How does the LL(1) parser know which production to use? The terminals in the input string are matched from left to right. The part of the string that has not been matched yet is called the input remaining. The leftmost symbol of the input remaining is the lookahead. For a particular variable, the production to use is chosen by comparing the variable's right sides with the lookahead. If all the terminals have been matched, then $ is the lookahead.
Aufgabe 1
Gib für die rechten Seiten der Grammatik
S → BAc A → Aa A → a B → AB B → bB B → d
jeweils die FIRST-Menge an. Die FIRST- und FOLLOW-Mengen von JFLAP können dabei als Hilfe dienen.
Fülle anschließend die Parser-Tabelle und gib bei jedem Eintrag an, ob 1. oder 2. des obigen Algorithmus angewandt wurde.
Wo taucht ein Konflikt auf?
Überprüfe deine Einträge mit JFLAP.
Aufgabe 2
Überprüfe die Grammatik
S → A A → aaA A → b
auf die LL(1)-Eigenschaft.
Aufgabe 3
Warum ist die Grammatik aus Aufgabe 1 nicht vom Typ LL(1)? Begründe deine Antwort.
Links
- Build LL(1) Parse Table - JFLAP
- Übungsaufgaben
- LL-Parser - wikipedia
