Kurze Antwort: Das Teachingtool hatte einen Fehler bei der Berechnung der First-Mengen von Wörtern, der in diesem Beispiel zu einer falschen Berechnung geführt hatte. Dies wurde nun korrigiert, vielen Dank für diesen Hinweis!
Lange Antwort: Für die Grammatik
S -> U | V
U -> TaT | TaU | UaT
V -> TbT | TbV | VbT
T -> ϵ | aTbT | bTaTerhält man
| First | Follow |
|---|
| S | {a,b} | {$} |
| T | {a,b,ϵ} | {$,a,b} |
| U | {a,b} | {$,a} |
| V | {a,b} | {$,b} |
Um die Parse-Tabelle zu bestimmen, muss man alle Grammatikregeln anschauen und zunächst die First-Mengen von deren rechten Seiten bestimmen (hier war ein Fehler im Tool, der nun behoben worden ist).
S -> U : First(U) = {a,b}
S -> V : First(V) = {a,b}
T -> ϵ : First(ϵ) = {ϵ}
T -> aTbT: First(aTbT) = {a}
T -> bTaT: First(bTaT) = {b}
U -> TaT : First(TaT) = {a,b}
U -> TaU : First(TaU) = {a,b}
U -> UaT : First(UaT) = {a,b}
V -> TbT : First(TbT) = {a,b}
V -> TbV : First(TbV) = {a,b}
V -> VbT : First(VbT) = {a,b}
Man sieht, dass das leere Wort ϵ nur in der First-Menge von T -> ϵ vorkommt. Daher werden alle Produktionsregeln außer T -> ϵ allein durch deren First-Mengen bestimmt. Für die Regel T -> ϵ erhält man First(ϵ) = {ϵ}, so dass diese Regel zunächst in PI(T,$) eingetragen wird. Da aus T das leere Wort abgeleitet werden kann, muss die Regel ferner auch in alle Einträge PI(T,x) eingetragen werden, bei denen x in FOLLOW(T) vorkommt. Daher wird die Regel T -> ϵ auch in alle Einträge PI(T,a), PI(T,b) und PI(T,ϵ) eingetragen.
| a | b | $ |
S | S → U | V | S → U | V | |
T | T → ϵ | aTbT | T → ϵ | bTaT | T → ϵ |
U | U → TaT | TaU | UaT | U → TaT | TaU | UaT | |
| V | V → TbT | TbV | VbT | V → TbT | TbV | VbT | |
