Parser-Tabelle
|
für jedes Paar (X, z) mit X ∈ N, z ∈ T werden Einträge
(Grammatik-Regeln) in
der Parser-Tabelle nach folgenden zwei Verfahren berechnet
|
|
|
1.
|
X ::= w ∈ ParserTabelle(X, z) für alle z ∈ FIRST(w) |
|
|
2.
|
X ::= w ∈ ParserTabelle(X, z) mit nullable(w) für alle z ∈ FOLLOW(X)
Beispiel
|
|
|
|
Genau eine Regel ∈ ParserTabelle(X,z): Alles gut
|
|
|
|
Keine Regel ∈ ParserTabelle(X,z): Syntaxfehler
|
|
|
|
Mehrere Regeln ∈ ParserTabelle(X,z): Kein LL-Parsen möglich
|
|
|
Definition
|
Grammatiken, die keine mehrfachen Einträge in der Parser-Tabelle enthalten,
heißen LL(1)-Grammatiken
|
|
|
L.(.) |
Von links nach rechts lesen
|
.L(.) |
Linksableitung konstruieren
|
..(1) |
Ein Zeichen vorausschauen
|
|
|
|
Aus einer Parser-Tabelle kann auf einfache und systematische Weise ein Parser mit rekursivem Abstieg
automatisch generiert werden.
|
? |
Welche Grammatik-Regeln zerstören die LL(1) Eigenschaft?
|
|
|
Mehrdeutigkeiten
|
Mehrdeutige Grammatiken sind nie LL(1) Grammatiken.
|
|
|
Linksrekursion
|
Beispiel:
|
|
|
|---|
|
FIRST(T) ⊆ FIRST(E+T)
|
|---|
|
1.Beispiel: Arithmetische Ausdrücke
|
|---|
|
2.Beispiel: Anweisungsfolgen
|
|---|
|
|
|
Für LL-Parser nur Rechtsrekursion verwenden
|
|
|
Transformation
|
Linksrekursive Regeln in rechtsrekursive Regeln
|
|
Beispiel:
|
|---|
|
E ::= T E'
E' ::= + T E'
E' ::=
|
|---|
|
|
|
Anderer Syntaxbaum: Andere Semantik
|
|
|
Transformations-
Schema
|
Linksrekursive Regeln in rechtsrekursive Regeln
|
|
X ::= X w1
X ::= X w2
X ::= u1
X ::= u2
|
|---|
|
wird transformiert in
|
|---|
|
X ::= u1 X'
X ::= u2 X'
X' ::= w1 X'
X' ::= w2 X'
X' ::=
|
|---|
|
|
|
Es entstehen Epsilon-Produktionen
|
|
|
gemeinsame Anfangsstücke
|
in Regeln für ein NT-Symbol
|
|
|
|---|
|
|
|
FIRST-Mengen für beide Regeln gleich
|
|
|
Faktorisierung
|
eliminiert diese Eigenschaft
|
|
X ::= Y X'
X' ::= w1
X' ::= w2
|
|---|
|
|
|
if-then und if-then-else
|
|
|
Compilerbau & Formale Sprachen: LL(1) Grammatiken
