Erste und folgt dem nicht-Terminals in zwei Grammatiken

Question

folgende Grammatik gegeben

S -> L=L 
s -> L 
L -> *L 
L -> id 

Was ist die erste und folgt für das Nicht-Terminals?

Wenn die Grammatik in

geändert

S -> L=R 
S -> R 
L -> *R 
L -> id 
R -> L 

Was die erste sein wird, und folgen Sie?

Answer 1

Als ich einen Compiler-Kurs in der Schule nahm, habe ich FIRST und FOLLOWS ü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 Sets 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, einen Sinn darin zu finden, was in Ihrem Buch ist.

Der erste Satz ist die Menge der Terminals, die Sie möglicherweise als den ersten Teil der Erweiterung eines Nicht-Terminals sehen könnten. Der FOLLOWS-Satz ist der Satz von Anschlüssen, den Sie möglicherweise nach der Erweiterung eines Nicht-Endgeräts sehen können. In Ihrer ersten Grammatik gibt es nur drei Arten von Terminals: =, * und id. (Sie könnten auch $, das Symbol für das Ende des Eingangs, als Terminal betrachten.) Die einzigen Nicht-Terminals sind S (eine Anweisung) und L (ein Lvalue - ein "Ding", das Sie zuweisen können).

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 FIRST (S) = FIRST (L) = {*, id}.

FOLGEN (S) ist einfach. Nichts folgt S, weil es das Startsymbol ist. Das einzige, was in FOLLOWS (S) passiert, ist $, das Ende-des-Eingabe-Symbols.

FOLGEN (L) ist ein wenig komplizierter. Sie müssen sich jede Produktionsregel anschauen, in der L erscheint, und sehen, was danach kommt. In der ersten Regel sehen Sie, dass =L folgen kann. So ist = in FOLGEN (L). Man merkt aber auch, dass am Ende der Produktionsregel ein weiterer 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 FOLGT (L) = {=, $}. (Wenn Sie sich die anderen Produktionsregeln ansehen, erscheint L immer am Ende von ihnen, so dass Sie nur $ von denen bekommen.)

Werfen Sie einen Blick auf diese Easy Explanation, und jetzt ignorieren Sie alle Sachen über ϵ, weil Sie keine Produktionen haben, die die leere Zeichenfolge enthalten. Unter "Regeln für erste Sets" sollten Regeln # 1, # 3 und # 4.1 sinnvoll sein. Unter "Regeln für Follows Sets" sollten die Regeln # 1, # 2 und # 3 sinnvoll sein.

Dinge werden komplizierter, wenn Sie ϵ in Ihren Produktionsregeln haben. Angenommen, Sie haben so etwas wie dieses:

D -> S C T id = V // Declaration is [Static] [Const] Type id = Value 
S -> static | ϵ // The 'static' keyword is optional 
C -> const | ϵ  // The 'const' keyword is optional 
T -> int | float // The Type is mandatory and is either 'int' or 'float' 
V -> ...   // The Value gets complicated, not important here. 

Nun, wenn Sie FIRST (D) berechnen möchten, können Sie nicht nur auf den ersten Blick (S), weil S sein kann „leer“. 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 "Easy Explanation" -Regeln.

Wenn Sie FOLLOWS (S) berechnen möchten, können Sie nicht nur FIRST (C) betrachten, da dieser leer sein kann, also müssen Sie auch FIRST (T) betrachten. Also FOLGT (S) = {const, int, float}. Sie erhalten das, indem Sie "Regeln für Folgen" # 2 und # 4 (mehr oder weniger) anwenden.

Ich hoffe, dass hilft und dass Sie herausfinden können, FIRST und FOLGT für die zweite Grammatik auf eigene Faust.

Wenn es hilft, R stellt einen Rvalue - eine "Sache", die Sie nicht zuweisen können, wie eine Konstante oder ein Literal. Ein L-Wert kann auch als R-Wert dienen (aber nicht umgekehrt).

a = 2; // a is an lvalue, 2 is an rvalue 
a = b; // a is an lvalue, b is an lvalue, but in this context it's an rvalue 
2 = a; // invalid because 2 cannot be an lvalue 
2 = 3; // invalid, same reason. 
*4 = b; // Valid! You would almost never write code like this, but it is 
     // grammatically correct: dereferencing an Rvalue gives you an Lvalue.