First/Follow-Mengen < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Hi Leute!
Ich hab hier einige Aufgaben zum Thema Compilerbau. Ich soll zu einer gegebenen Grammatik die sogenannten First- und Follow-Mengen aufstellen.
In meinem Skript hab ich auch einen (anscheinend) passenden Algorithmus gegeben, den ich aber einer bestimmten Stelle nicht verstehe! ![[]](/images/popup.gif) http://www.directupload.net/file/d/3648/khzpvfat_png.htm
Die First-Menge hab ich soweit drauf!
Nehmen wir mal an, dass ich nun folgende Grammatik G gegeben habe:
$G = [mm] \{N,T,P,S\}, N=\{S,A,B\}, T=\{a,b\}, P=\{\hat{S}\rightarrow S,\rightarrow AB, A \rightarrow aA|a, B \rightarrow bB|b\}$
[/mm]
Nun steht in meiner Lösung, dass die Follow-Menge $S:= [mm] \epsilon, [/mm] A:= b, B:= [mm] \epsilon$ [/mm] sein soll...
Ich verstehe (auch mit Algo) nur zum Teil, wie man darauf kommt! Das Follow(A) ist mir soweit klar. Es gilt ja die Produktionskette $S [mm] \rightarrow [/mm] AB [mm] \rightarrow [/mm] AbB$. Da ich laut Algo. bei Follow(A) das nachfolgende Nichtterminal von A der rechten Seite der Produktion $S [mm] \rightarrow [/mm] AB$ anschaun muss (also Nichtterminal B), ergibt sich als Follow(A)-Symbol das "b" der Produktion $B [mm] \rightarrow [/mm] bB|b$; egal welche ich nun von den zwei Produktion nehmen würde, es steht da ja als Follow-Symbol dann immer "b" (wegen dem Oder-Zeichen, ergibt sich ja immer ein "b")
Wie aber kommt man auf den leeren String [mm] $\epsilon$ [/mm] bei Follow(S) und Follow(B)?
Bei Follow(S) gibt es ja von Haus aus nur eine Produktion die ein S auf der rechten Seite der Produktion hat; diese Produktion heißt: [mm] $\hat{S}\rightarrow [/mm] S$. Wie ergibt sich hier das [mm] $\epsilon$? [/mm] Das [mm] $\hat{S}$ [/mm] soll das "Startsymbol" sein... Ein Leerstring ergibt sich meines Wissens ja nur, wenn eine Schleife gebaut werden kann. Nach obigen Produktionen ist aber doch in Bezug auf "S" nur folgendes möglich: [mm] $\hat{S}\rightarrow [/mm] S [mm] \rightarrow [/mm] AB [mm] \rightarrow...$
[/mm]
Wie kann da eine Schleife gebaut werden, so dass es einen Leerstring rechtfertigt?
Bei Follow(B) hingegen ist es mir klar, denke ich. Es gibt aber noch $B [mm] \rightarrow [/mm] bB|b$. Hier kann man $B [mm] \rightarrow [/mm] bB [mm] \rightarrow [/mm] bbB [mm] \rightarrow [/mm] bbbB [mm] \rightarrow...$ [/mm] imer wieder ableiten und es wird nur der Leerstring rechts vom B erzeugt. Genauso wie bei Produktionsfolge $S [mm] \rightarrow [/mm] AB$; hier ist auch nur der Leerstring rechts B der rechten Seite der Produktion zu finden!
Kann mir jemand helfen? Ist das alles so richtig?
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 19:20 Mi 11.06.2014 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
