 |
|||
| HSG |
|
Definition
Follow-Mengen werden nur zu Nichtterminal-Symbolen A ∈ N gebildet. Follow(A) enthält die Terminalsymbole, die in einer Satzform direkt hinter A stehen können.
Follow(A) = {t ∈ T | S ⇒ ... ⇒ βAtγ}
Steht in einer Satzform hinter A nichts mehr, so gehört auch das Pseudo-Terminalsymbol $ zu Follow(A). Man könnte auch sagen, dass das mögliche 'Ganz-rechts-Stehen' von A durch $ notiert wird. Das Startsymbol steht ganz am Anfang allein und damit ganz rechts, damit gehört $ zu FOLLOW(S).
Beispiel 1
S → Ac A → Bd A → ccB B → λ
Jede Ableitung in dieser Grammatik muss mit S ⇒ Ac beginnen. c ist ein Terminal und steht hier hinter A, also gehört c zu FOLLOW(A). A taucht auf keiner weiteren rechten Seite auf, sodass FOLLOW(A) = {c} ist. Leitet man weiter ab, S ⇒ Ac ⇒ Bdc, so sieht man, dass sicher d zu FOLLOW(B) gehört. Das hätte man auch direkt der rechten Seite von A → Bd ansehen können, vorausgesetzt diese Produktion kann irgendwann zum Einsatz kommen. Was ist aber, wenn man das A in S ⇒ Ac durch ccB ersetzt, S ⇒ Ac ⇒ ccBc? Dann steht plötzlich c hinter B, gehört also zu FOLLOW(B). Dabei ist es völlig unerheblich, was vor dem B steht.
Algorithmus
Die FOLLOW-Mengen für die nonterminalen Symbole einer Grammatik werden parallel nach folgenden Regeln berechnet. Die Regeln sind solange anzuwenden, bis sich die FOLLOW-Mengen nicht mehr ändern.
- Wenn S das Startsymbol ist, so gehört $ zu FOLLOW(S).
- Gibt es eine Produktion A → αBβ, so füge FIRST(β)\{ε} zu FOLLOW(B) hinzu.
- Gibt es eine Produktion A → αB oder A → αBβ mit β ⇒* ε, so füge FOLLOW(A) zu FOLLOW(B) hinzu.
Schrittweise Ermittlung der FOLLOW-Mengen zu Beispiel 1
bekannt: FIRST(S) = {c,d}, FIRST(A) = {c,d}, FIRST(B) = {λ}
S | {$} | {$} | {$} |
A | {} | {c} | {c} |
B | {} | {d,c} | {d,c} |
Python-Realisierung
def FOLLOW_Mengen(G):
"""
gibt die FOLLOW-Mengen zu den NonTerminalen der Grammatik G an,
die Mengen werden in einem Dictionary zurueckgegeben
"""
N = NonTerminale(G)
S = Start(G)
F = {}
for n in N:
if n == S:
F.update({n:{'$'}})
else:
F.update({n:set()})
while True:
Fa = copy.copy(F)
# print(Fa) # DEBUG
for p in G:
if len(p[1]) > 0:
for y in p[1]:
if y in N:
beta = p[1][p[1].index(y)+1:] # alles hinter y
fy = F.get(y) # bisherige FOLLOW-Menge von y
fy = fy|(FIRST(beta,G)-{''})
F.update({y:fy})
if (beta == '') or ('' in FIRST(beta,G)):
fA = F.get(p[0]) # fA FOLLOW-Menge der linken Seite
fy = fy|fA
F.update({y:fy})
if Fa == F: break
return F
def FOLLOW(X,G):
"""
gibt die FOLLOW-Menge zu einem NonTerminal X aus G zurueck
"""
return FOLLOW_Mengen(G).get(X)
Zweck
FOLLOW-Mengen benötigt man zum Aufstellen der Parser-Tabellen beim LL(1)- oder SLR(1)-Verfahren.
Follow-Mengen werden z.B. gebraucht, um zu unterscheiden, ob eine mögliche Reduzierung beim SLR(1)-Verfahren auch sinnvoll ist. Es darf nur auf das nonterminale Symbol X auf der linken Seite einer Produktion reduziert werden, wenn ein erlaubtes terminales Zeichen folgt. Die erlaubten Zeichen sind gerade die Elemente der Menge Follow(X).
Links
- Parser - wikipedia
