Compilerbau & Formale Sprachen: FIRST- und FOLLOW-Mengen

FIRST(w)	gegeben: w ∈ (N ∪ T)^*
	FIRST(w) = { z ∈ T \| w \|—^* zw₁, w₁ ∈ (N ∪ T)^* }
Beispiel	arithmetische Ausdrücke:
	w= T*F
	FIRST(T*F) = {id, num, (}

Problem	X ::= w₁ X ::= w₂ FIRST(w₁) ∩ FIRST(w₂) ≠ {}
	Für Eingabezeichen aus der Schnittmenge ist nicht entscheidbar, welche Regel angewendet 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 angewendet?
	X ::= w₁ X ::= ε
FOLLOW(X)	die Menge aller Terminalsymbole, die in einer Satzform auf X folgen können
	FOLLOW(X) = { z ∈ T \| S \|—^* aXzb, a,b ∈ (N ∪ T)^* }
Problem	X ::= w₁ X ::= ε FIRST(w₁) ∩ FOLLOW(X) ≠ {}
	Für Eingabezeichen aus der Schnittmenge ist nicht entscheidbar, ob die ε-Produktion oder die andere Produktion angewendet 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 ::= Y₁...Y_n ∈ P, ∀ 1 ≤ i ≤ n ⋅ i ∈ ns }
Berechnung	von FIRST, FOLLOW und nullable: iterativ

FIRST- und FOLLOW-Mengen

Definitionen