FIRST(w) |
gegeben: w ∈ (N ∪ T)*
|
|
FIRST(w) = { z ∈ T | w ⊢* zw1, w1 ∈ (N ∪ T)* }
|
|---|
Beispiel |
arithmetische Ausdrücke:
|
|
w= T*F
|
|---|
|
FIRST(T*F) = {id, num, (}
|
|---|
| |
Problem |
X ::= w1
X ::= w2
FIRST(w1) ∩ FIRST(w2) ≠ {}
|
|
Für Eingabezeichen aus der Schnittmenge ist nicht
entscheidbar,
welche Regel angewandt werden soll.
|
| |
|
Grammatik nicht mit rekursivem Abstieg analysierbar.
|
| |
Berechnung |
von FIRST und FOLLOW
|
einfach aber unvollständig |
w = XYZ :
FIRST(w) = FIRST(X)
|
| |
Problem |
X kann auf ε ableitbar sein
|
|
w = XYZ, X ⊢* ε :
FIRST(w) = FIRST(X) ∪ FIRST(YZ)
|
|---|
| |
Problem |
X und Y können auf ε ableitbar sein
|
|
w = XYZ, X ⊢* ε, Y ⊢* ε :
FIRST(w) = FIRST(X) ∪ FIRST(Y) ∪ FIRST(Z)
|
|---|
| |
|
Alle auf ε ableitbaren Nichtterminalsymbole müssen bekannt sein und berücksichtigt werden
|
| |
nullable(X) |
Prädikat
|
|
X ∈ (N ∪ T)
nullable(X) := X ⊢* ε
|
|---|
| |
2.Problem |
Wann werden ε-Produktionen angewandt?
|
|
|
|---|
FOLLOW(X) |
die Menge aller Terminalsymbole, die in einer
Satzform auf ein Zeichen X ∈ (N ∪ T) folgen können
|
|
FOLLOW(X) = { z ∈ T | S ⊢* aXzb, a,b ∈ (N ∪ T)* }
|
|---|
Problem |
X ::= w1
X ::= ε
FIRST(w1) ∩ FOLLOW(X) ≠ {}
|
|
Für Eingabezeichen aus der Schnittmenge ist nicht
entscheidbar,
ob die ε-Produktion oder die andere Produktion angewandt werden soll.
|
| |
|
Grammatik nicht mit rekursivem Abstieg analysierbar.
|
Berechnung |
von FIRST, FOLLOW und nullable: Berechnung des kleinsten Fixpunktes einer Funktion
|
Definition |
Ein Punkt
x ∈ D
ist ein Fixpunkt einer Funktion
f : D -> D
wenn gilt:
x = f x
|
nullable |
f : N ∪ T -> N ∪ T
f ns = ns
∪ { X | X ::= Y1...Yn ∈ P,
∀ 1 ≤ i ≤ n ⋅ i ∈ ns }
|
Compilerbau: Definition FIRST- und FOLLOW-Mengen
