LL(1): Grammatik First und Follow berechnen

Wie man die First- und Follow-Mengen für deterministisches LL(1)-Parsing berechnet.
Korrektur:
Da B rechts unter dem S steht, erbt B die Follow-Menge von S, also ist Follow(B) = {a, $, b}
Quelle:
Kallmeyer, Laura ; Roos, Magnus: Deterministic Top-Down Parsing: LL(k)-Parsing (Parsing). Düsseldorf, Sommersemester 2014. URL user.phil-fak.u... S. 5 ff.

[@janves]

Danke für das Video! Hat mir auch Jahre später noch sehr geholfen :)

[@l3Nerd]

Follow(B) muss doch, da am Ende von S, auch alle Follow(S) erben, also konkret: Follow(B)={a,$,b) (Beweis: S->aAB->aSB->aaABB->aaABb)

[@SamyaDaleh]

+Lennart Kindermann Danke. Ich hab das als Anmerkung hinzugefügt.

[@lasse261]

Habe kurz an meinen Fähigkeiten gezweifelt, danke für den Kommentar :D

[@enisalperkale5168]

Handelt es sich nun um eine LL(1) Grammatik oder nicht?

[@SamyaDaleh]

Stimmt, das kommt nicht ganz im Video heraus. Die Grammatik ist LL(1), wenn
1. Alle Produktionsregeln, die zu einem Nichtterminal gehören, paarweise disjunkt sind. First(aAB) und First (Ba) gehören beide zu S-Regeln und haben in der First-Menge beide das a. -> Kein LL(1).
2. Wenn die First-Menge einer Produktionsregel das Epsilon enthält, dann muss man die First-Mengen auch mit allen Follow-Mengen vergleichen, die zu einem Nichtterminalen gehören. Hier hat B eine Epsilon-Produktion und damit Epsilon in der First-Menge. Follow (B) ist im Video falsch, das ist eigentlich {a, $, b} und hat ein gemeinsames Element mit First(b). Auch nach dem Kriterium ist es keine LL(1)-Grammatik. Es genügt aber, dass es am ersten Kriterium bereits scheitert und man müsste eigentlich keine Follow-Mengen berücksichtigen.

[@NightcoreAsuna_music]

Bist du fertig mit dem Studium?

[@SamyaDaleh]

Ich habe den Master abgeschlossen und arbeite jetzt am Doktor. :)

[@Egoralex]

First(Ba) -> { ba } ?? Oder doch First(Ba) -> { b , a }

[@SamyaDaleh]

Ja, da hab ich ein Komma vergessen. Nur einzelne Zeichen sind First-Items.

[@knallerdecks]

danke

[@thrakiamaria]

{b,a, ε} nicht nur {b, a} und wenn du mich fragst, warum, frag mal meine Professoren.

[@friedrichwilhelmhufnagel3577]

* falschen Post editiert. Ich hatte gesagt, dass epsilon auch noch zu First(S) gehört.

[@SamyaDaleh]

Du sagst gerade, dass S die Menge ist, die aus a, b und Epsilon besteht. S ist das Startsymbol und keine Menge.
Angenommen du meinst First(S): Du willst wissen, welches Terminal (bei Lookahead der Länge 1) als erstes erzeugt werden kann, wenn dir ein S vorliegt. Epsilon ist kein Terminal, sondern das leere Wort mit Länge 0. Wenn im Fall S => Ba das B zu Epsilon expandiert, welches Terminal steht dann an erster Stelle?

[@friedrichwilhelmhufnagel3577]

Ja Du hast Recht, natürlich meine ich First(S). Und das kann nicht epsilon produzieren? Obwohl die eine Alternative B ist und dieses epsilon produzieren kann?
Viele Grüße

[@friedrichwilhelmhufnagel3577]

Und wofür muss man die First-Mengen der RHS's berechnen?

[@friedrichwilhelmhufnagel3577]

a würde ich sagen

[@SamyaDaleh]

@@friedrichwilhelmhufnagel3577 Du musst die ganze RHS betrachten. Dann kann S kein Epsilon produzieren. Wenn es eine Regel S -> B gäbe ohne irgendwas dahinter, wäre das wieder was Anderes. Du brauchst die First-Mengen, damit du beim Parsen entscheiden kannst, welche Regel du als nächstes verwendest. Z. B. hast du gerade ein S in der Ableitung und das nächste Eingabezeichen ist b. Dann weißt du anhand der First-Mengen, dass du nur S -> Ba gebrauchen kannst. Den Rest brauchst du dir nicht anzugucken.

[@se1yagyn]

sau gute videos. top

[@clover6480]

hammer. !

[@JeyDnox]

sorry wenn ich so frage aber wie alt bist du o.O du hast eine sehr junge stimme :D

[@SamyaDaleh]

Ich bin 25. Nein, ich bin kein kleiner Junge. :P

[@TheTavaro11]

Bist du männlich oder weiblich?

[@anonymous1177]

Bist du dumm?

[@janves]

@@TheTavaro11 Ist doch offensichtlich oder?

[@ea8455]

​@@SamyaDalehund heute bist du 34. Wie die Zeit fliegt...