OFFTOPIC Compiler:First,Follow & Predict Menge
Stefan Richter
aber leider find ich keine deutschsprachige Compiler Newsgroup,
deshalb will ich es mal hier versuchen.
Arbeite mich gerade in Compiler ein, benutze dazu das Buch
"Praxis des Compilerbaus" von Franz Josef Schmitt.
Leider verstehe ich die Erklärungen zur First(), Follow(),
und Predict() Menge nicht ganz, bzw. bin mir nicht sicher.
a)
Also die Firstmenge zu einem Nichtterminal besteht aus jedem
Terminal, das "zuerst" von diesem Nichtterminal aus erreicht wird,
inklusive Epsilon, falls in der Menge der Terminale vorhanden.
Richtig?
Kann es eine Firstmenge auch Terminal geben?
b)
Follow()
Die Followmenge zu einem Nichtterminal besteht aus dem Terminalsymbol,
das neben dem angegebenen Nichtterminal steht, oder aus den
Terminalsymbolen,
die aus dem dem angegebenen Nichtterminal folgenden Nichtterminal gebildet
werden kann.
(Ich weiß dieser Satz ist ziemlich verwirrend, aber ich wollte das mal
richtig "festnageln")
Kann es auch eine Followmenge zu einem Terminal geben?
c)
Predict()
Hierbei bin ich mir am unsichersten, aber ich glaube es bedeutet:
First+ Followmenge zusammen.
Und last but not least:
Für was genau brauche ich diese drei Mengen?
Danke,
Robert
Achim Peters
> leider find ich keine deutschsprachige Compiler Newsgroup,
IMHO wärst Du in de.sci.informatik.misc nicht OT.
Bye
Achim
Stefan Matthias Aust
> Leider verstehe ich die Erklärungen zur First(), Follow(),
> und Predict() Menge nicht ganz, bzw. bin mir nicht sicher.
Google liefert mir z.B.
http://www.fh-wedel.de/~si/vorlesungen/cb/SyntaxAnalyse/FirstFollow.html
als ersten Treffer. Dort ist ein Beispiel für das Bilden von First()
und Follow().
Ist dir klar, warum man diese Mengen berechnet? Sie dienen dazu, einen
tabellengestützen Parser zu bauen. Man kann zudem damit prüfen, ob eine
Grammatik überhaupt mit LL(1) parsbar ist.
> a)
> Also die Firstmenge zu einem Nichtterminal besteht aus jedem
> Terminal, das "zuerst" von diesem Nichtterminal aus erreicht wird,
> inklusive Epsilon, falls in der Menge der Terminale vorhanden.
> Richtig?
Ja.
> Kann es eine Firstmenge auch Terminal geben?
Dieser Satz nicht vollständig. Fehlt ein "für Terminals"? Dann nein.
> b)
> Follow()
> Die Followmenge zu einem Nichtterminal besteht aus dem Terminalsymbol,
> das neben dem angegebenen Nichtterminal steht, oder aus den
> Terminalsymbolen,
> die aus dem dem angegebenen Nichtterminal folgenden Nichtterminal gebildet
> werden kann.
> (Ich weiß dieser Satz ist ziemlich verwirrend, aber ich wollte das mal
> richtig "festnageln")
> Kann es auch eine Followmenge zu einem Terminal geben?
Nein.
> c)
> Predict()
> Hierbei bin ich mir am unsichersten, aber ich glaube es bedeutet:
> First+ Followmenge zusammen.
Hier findet google
www-pu.informatik.uni-tuebingen.de/%20compilerbau-2001/material/cc-2.ps
wo predict als
p(q) = { B -> v(t) | A -> ab(p))V+ B -> v(t) for A -> ab(p) el q}
(fast alles griechische Zeichen, die ich hier nicht darstellen will)
definiert ist. Das hilft mir allerdings überhaupt nicht. Sorry :)
> Und last but not least:
> Für was genau brauche ich diese drei Mengen?
S.o.
bye
--
Stefan Matthias Aust // "A new beginning always starts at the end" -WT
Patrick Roemer
Stefan Matthias Aust wrote:
>> Kann es eine Firstmenge auch Terminal geben?
>
> Dieser Satz nicht vollständig. Fehlt ein "für Terminals"? Dann nein.
Echt? Besteht nicht die Firstmenge eines Terminals (bzw. einer Folge,
die mit einem Terminal beginnt) genau aus diesem Terminal, und nur
Follow ist ausschliesslich fuer Nichtterminale definiert?
Viele Gruesse,
Patrick
Jochen Theodorou
> Sorry, ich weiß dass das ziemlich Offtopic ist,
>
> aber leider find ich keine deutschsprachige Compiler Newsgroup,
> deshalb will ich es mal hier versuchen.
Compilerbau liegt schon lange zurück, aber ich schaue mal was sich
machen lässt.
http://users.informatik.fh-hamburg.de/~voeller/fc/comp/node16.html hilft
dabei schon mal etwas
[...]
> a)
> Also die Firstmenge zu einem Nichtterminal besteht aus jedem
> Terminal, das "zuerst" von diesem Nichtterminal aus erreicht wird,
> inklusive Epsilon, falls in der Menge der Terminale vorhanden.
> Richtig?
> Kann es eine Firstmenge auch Terminal geben?
Sie besteht nur aus Terminalen und zwar aus denen die durch die
Ableitung des Nicht-Terminals zuerst erreichbar sind.
Beispiel:
S-> A C
A -> computer | B desktop
B -> $ | A
C -> window | item
First(A) = {c,$,d}
Die Firstmenge zu einem Terminal ist das Terminal selber.
> b)
> Follow()
> Die Followmenge zu einem Nichtterminal besteht aus dem Terminalsymbol,
> das neben dem angegebenen Nichtterminal steht, oder aus den
> Terminalsymbolen,
> die aus dem dem angegebenen Nichtterminal folgenden Nichtterminal gebildet
> werden kann.
> (Ich weiß dieser Satz ist ziemlich verwirrend, aber ich wollte das mal
> richtig "festnageln")
> Kann es auch eine Followmenge zu einem Terminal geben?
Mit obiger Grammatik:
Follow(A) = First(C) = {w,i}
Follow(d) = {e,o}
Und wofür das alles gut ist? Zum erstellen der Parsertabelle, zum Prüfen
ob eine Grammatik LL(k), LALR oder sonstwas ist.
Gruss theo