Schwäche
|
von LL(k): Entscheidung, welche Produktion zu wählen ist, an
Hand von k Eingabesymbolen
|
| |
LR(k)
|
Auswahl der Produktion erst, nachdem eine ganze rechte Seite
analysiert wurde unter Verwendung von k Symbolen Vorausschau
|
| |
L.(.) |
Von links nach rechts lesen
|
.R(.) |
Rechtsableitung konstruieren
|
..(k) |
k Zeichen vorausschauen
|
| |
Rechtsableitung
|
entspricht einem Aufbau des Syntaxbaumes von den Blättern zur
Wurzel hin, indem links im Baum reduziert wird, also eine rechte Seite durch ein Nichtterminalsymbol ersetzt wird.
|
| |
Parser |
Bestandteile
|
Stack |
noch zu reduzierende Symbole
|
Input |
mit k Symbolen Vorausschau
|
| |
Aktionen |
|
| |
shift |
ein Zeichen auf den Stack packen
|
| |
reduce |
|
.1 |
Regel
|
|
|
|---|
|
wählen
|
|---|
| |
.2 |
Rechte Seite
|
|
|
|---|
|
vom Stack löschen
|
|---|
| |
.3 |
Linke Seite
|
|
|
|---|
|
auf dem Stack speichern
|
|---|
| |
accept |
mit
|
|
|
|---|
|
reduzieren
|
|---|
| |
Start |
Stack ist leer
Input enthält gesammtes Programm mit Ende-Marke $
|
| |
Beispiel |
.0 S ::= E $
.1 E ::= T
.2 E ::= E + T
.3 T ::= F
.4 T ::= T * F
.5 F ::= id
.6 F ::= ( E )
|
| |
LR-parsen
|
allgemeiner als LL-Parsen
|
|
jede LL(k)-Grammatik ist auch eine LR(k)-Grammatik
|
| |
Linksrekursion
|
kein Problem
sogar erwünscht
|
| |
Linksfaktorisierung
|
kein Problem
nicht nötig
|
| |
Kunst |
an Hand des Stack-Inhaltes entscheiden, ob geshifted oder reduziert werden soll.
|
Kunst |
Reduzieren: welche rechte Seite
welche Regel
wieviele Symbole vom Stack nehmen
|
| |
Parser- Strategien |
|
LR(0) |
ohne Vorausschau
|
|
nur sehr wenige Grammatiken
|
| |
SLR |
Simple LR
|
|
LR(0) mit einem Zeichen Vorausschau
|
|
Reduzieren nur dann, wenn lookahead aus der Follow-Menge
|
| |
LALR(1) |
lookahead LR(1)
|
|
etwas allgemeiner als SLR(1)
|
|
Stand der Technik in verbreiteten Parser-Generatoren
|
| |
LR(1) |
allgemeiner als LALR(1)
|
|
größere Parser-Tabellen
|
| |
LR(k) |
allgemeiner als LR(1)
|
|
keine praktische Relevanz: zu große Parser-Tabellen
|
| |
Generatoren |
für LALR(1) Grammatiken
|
|
yacc, bison für C
CUP für Java
happy für Haskell
|
|---|
| |
Syntaxbaum |
Aufbau wärend des Parsens
|
| |
Stack |
enthält pro Eintrag 2 Informationen
- das Symbol
- ein zusätzliches Attribut von frei wählbarer Art
|
| |
reduzieren |
Beim Reduzieren werden aus den Attributen der rechten Seiten ein neues Attribut
für die linke Seite berechnet
|
| |
|
Semantische Aktionen |
| |
|
Arithmetische Ausdrücke mit CUPS
|
Compilerbau: LR-Analyse
