Als ich einen Compiler-Kurs in der Universität nahm, habe ich FIRST und FOLGS überhaupt nicht verstanden. Ich habe die im Dragon-Buch beschriebenen Algorithmen implementiert, aber ich hatte keine Ahnung, was vor sich ging. Ich denke ich mache es jetzt.
Ich nehme an, Sie haben ein Buch, das eine formale Definition dieser beiden Sätze gibt, und das Buch ist völlig unverständlich. Ich werde versuchen, eine informelle Beschreibung von ihnen zu geben, und hoffentlich wird das Ihnen helfen, zu verstehen, was in Ihrem Buch ist.
Der erste Satz besteht aus den Terminals, die Sie möglicherweise als ersten Teil der Erweiterung eines Nicht-Terminals sehen. Der FOLLOWS-Satz ist der Satz von Terminals, den Sie möglicherweise nach der Erweiterung eines Nicht-Terminals sehen könnten.
In Ihrer ersten Grammatik gibt es nur drei Arten von Terminals: = , * und id . (Sie könnten auch $ , das Symbol für das Ende der Eingabe, als Terminal betrachten.) Die einzigen Nicht-Terminals sind S (eine Anweisung) und L (ein Lvalue - ein "Ding" Sie kann zuweisen).
Denken Sie an FIRST (S) als die Menge der Nicht-Terminals, die möglicherweise eine Aussage auslösen könnten. Intuitiv wissen Sie, dass Sie keine Anweisung mit = starten. Du würdest also nicht erwarten, dass das in FIRST (S) auftaucht.
Wie beginnt eine Aussage? Es gibt zwei Produktionsregeln, die definieren, wie ein S aussieht, und beide beginnen mit L . Um herauszufinden, was in FIRST (S) ist, musst du wirklich schauen, was in FIRST (L) ist. Es gibt zwei Produktionsregeln, die definieren, wie ein Lvalue aussieht: Er beginnt entweder mit einem * oder mit einem id . Also ERSTE (S) = FIRST (L) = { * , id }.
S , weil es das Startsymbol ist. In FOLLOWS (S) ist also nur $ , das Eingabeende-Symbol.
L erscheint, und sehen, was danach kommt. In der ersten Regel sehen Sie, dass = auf L folgen kann. Also ist = in FOLGEN (L). In dieser Regel merkt man aber auch, dass am Ende der Produktionsregel noch ein L steht. Eine andere Sache, die L folgen könnte, ist alles, was dieser Produktion folgen könnte. Wir haben bereits herausgefunden, dass das einzige, was der S -Produktion folgen kann, das Ende der Eingabe ist. Also FOLGE (L) = { = , $ }. (Wenn Sie sich die anderen Produktionsregeln anschauen, erscheint L immer am Ende von ihnen, also erhalten Sie nur $ von diesen.)
Sieh dir diese einfache Erklärung an und ignoriere vorerst all die Sachen über ϵ , weil Sie keine Produktionen haben, die den leeren String enthalten. Unter "Regeln für erste Sets" sollten Regeln # 1, # 3 und # 4.1 sinnvoll sein. Unter "Regeln für Follows Sets" sollten Regeln # 1, # 2 und # 3 sinnvoll sein.
Die Dinge werden komplizierter, wenn Sie ϵ in Ihren Produktionsregeln haben. Angenommen, Sie haben so etwas:
Wenn Sie nun FIRST (D) berechnen wollen, können Sie nicht nur FIRST (S) betrachten, weil S möglicherweise "leer" ist. Sie wissen intuitiv, dass FIRST (D) { static , const , int , float } ist. Diese Intuition ist in Regel # 4.2 kodifiziert. Denken Sie an SCT in diesem Beispiel als Y1Y2Y3 in den Regeln "Einfache Erklärung".
Wenn du FOLLOWS (S) berechnen willst, kannst du nicht nur FIRST (C) betrachten, weil das vielleicht leer ist, also musst du auch auf FIRST (T) schauen. Also FOLGE (S) = { const , int , float }. Sie erhalten das, indem Sie "Regeln für Folgen" # 2 und # 4 (mehr oder weniger) anwenden.
Ich hoffe, dass das hilft und dass Sie FIRST und FOLGEN für die zweite Grammatik selbst herausfinden können.
Wenn es hilft, stellt R einen Rvalue dar - ein "Ding", dem Sie nicht zuweisen können, wie eine Konstante oder ein Literal. Ein L-Wert kann auch als R-Wert dienen (aber nicht umgekehrt).
Tags und Links grammar context-free-grammar