Definition
|
Eine Parser-Tabelle ist eine Matrix.
|
|
Die Spalten sind mit den Terminalsymbolen markiert.
|
|---|
|
Die Zeilen sind mit den Nichtterminalsymbolen markiert.
|
|---|
|
Jede Zelle enthält eine (möglicherweise leere) Menge von Produktionen.
|
|---|
Einträge
|
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): Ableitungsschritt mit
dieser Regel
|
| |
|
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:
|
|
|
|---|
|
|
|---|
|
|
|---|
|
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
|
| |
|
zur Berechnung der FIRST- und FOLLOW-Mengen, der LL(1)-Parsertabellen und
der Konstruktion von Linksableitungen und Syntaxbäumen.
|
Compilerbau: LL(1) Grammatiken
