FOLLOW Menge erzeugen

anonymus

Hallo,

Gegeben ist eine Grammatik G = (N, T, P, S); // zum Erzeugen von arithmetischen Ausdrücken

nicht-Terminalsymbole N = {expr, term, fact, E, T}
Terminalsymbole       T = {v, +, -, *, /, (, )}
Startsymbol           S = {expr}
Leerstring              = [e]epsilon[/e]
Stringende              = $

Produktionen
P = 
{
expr -> term E
term -> fact T
fact -> v | (expr)
E    -> + term E | - term E | [e]epsilon[/e]
T    -> * fact T | / fact T | [e]epsilon[/e]
}

Als Lösung ist folgendes gegeben:

FIRST         FOLLOW
expr   (, v          ), $
term   (, v          ), +, -, $
fact   (, v          ), +, -, *, /, $
E      +, -, [e]epsilon[/e]       ), $
T      *, /, [e]epsilon[/e]       ), +, -, $

Frage:
wie kommt man auf das "$" in der FOLLOW-Menge von expr ?

soweit komm ich:

FOLOLOW(expr) = )
FOLLOW(term)  = FOLLOW(expr), FOLLOW(E), FIRST(E) = ), +, -, [e]epsilon[/e]
FOLLOW(fact)  = FOLLOW(term), FIRST(T)            = ), +, -, *, /, [e]epsilon[/e]
FOLLOW(E)     = FOLLOW(expr), FOLLOW(E)           = )
FOLLOW(T)     = FOLLOW(term), FOLLOW(T)           = ), +, -, [e]epsilon[/e]

gut, was ich so mitgekriegt hab, sind $ und ε irgendwie gleich, also passt das Ergebnis bis auf das verfluchte $ in FOLLOW(expr)

Der Algorithmus zum Erzeugen der FOLLOW-Menge:

wiederhole
    für { alle Vorkommen von X auf der rechten Seite einer Produktion p }
    {
    falls {p= A->...X[e]sigma[/e] mit [e]sigma[/e] [e]ne[/e] [e]epsilon[/e]} nimm FIRST([e]sigma[/e]) [e]cap[/e] T  in FOLLOW(X) auf

    falls {p= A->...X[e]sigma[/e] mit [e]sigma[/e] => [e]epsilon[/e]} nimm FOLLOW(A) [e]cap[/e] T  in FOLLOW(X) auf

    }
solange bis alle FOLLOW-Mengen stabil bleiben

thx
Martin