LL(1)-Parser, FIRST-,FOLLOW-M. < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 11:24 Mi 27.05.2009 | | Autor: | RalU |
| Aufgabe | Hallo,
es geht darum, für folgende kontextfreie Grammatik die FIRST- und FOLLOW-Mengen aufzustellen:
[mm] G_{expr}:
[/mm]
I'-> [mm] aI'|bI'|0I'|1I'|\varepsilon
[/mm]
I-> aI'|bI'
F->( E )|I
[mm] T'->*FT'|\varepsilon
[/mm]
T -> FT'
E'-> + [mm] TE'|\varepsilon
[/mm]
E -> TE'
|
Ich habe zunächst die FIRST-Mengen erstellt:
[mm] FIRST(I')={a,b,0,1,\varepsilon}
[/mm]
FIRST(I)={a,b}
FIRST(F)={(,a,b}
[mm] FIRST(T')={*,\varepsilon}
[/mm]
FIRST(T)={(,a,b}
[mm] FIRST(E')={+,\varepsilon}
[/mm]
FIRST(E)={c,a,b}
Dann, wurde vorgegeben, die FIRST-Mengen für die rechten Seiten der Grammatik zu erstellen, wobei nur die Nichtterminale mit mehr als einer rechten Seite interessieren:
FIRST(+TE')={+}
[mm] FIRST(\varepsilon)={\varepsilon}
[/mm]
FIRST(*FT')={*}
[mm] FIRST(\varepsilon)={\varepsilon} [/mm] Warum eigentlich nochmal?
FIRST((E))={(}
FIRST(I)={a,b}
FIRST(aI')={a}
FIRST(bI')={b}
Diese FIRST-Mengen sollten laut meiner Vorgaben so stimmen.
Mein Problem liegt bei der jetzt folgenden Erstellung der FOLLOW-Mengen, wobei folgendermaßen vorgegangen werden soll:
1) Nehme $ zu FOLLOW(S) hinzu
("$"entspr. Sonderzeichen für das Ende der Eingabe)
2) Falls A -> [mm] \alphaB\beta [/mm] nehme [mm] FIRST(\beta)\{\varepsilon} [/mm] zu FOLLOW(B) hinzu
3) Falls A -> [mm] \alphaB [/mm] oder A -> [mm] \alphaB\beta [/mm] mit [mm] \varepsilon \in FIRST(\beta), [/mm] nehme FOLLOW(A) zu FOLLOW(B) hinzu
Als Lösung sind die folgenden FOLLOW-Mengen angegeben:
FOLLOW(E)={$,)} Muss man immer beim letzten Nichtterminal der Grammatik, also hier dem E anfangen? Mir ist nicht klar, warum hier schon ")" hinzukommt...
FOLLOW(E')=FOLLOW(E) Kann ich nicht nachfollziehen...
FOLLOW(T) = FOLLOW(E) [mm] \cup [/mm] FIRST(E)/{ [mm] \varepsilon [/mm] }={$,),+} Wie kommt man auf das FOLLOW(E)?
FOLLOW(T')=FOLLOW(T) ist nicht klar
FOLLOW(F)=FIRST(T')/{ [mm] \varepsilon [/mm] } [mm] \cup [/mm] FOLLOW(T)={*,$,),+}
Wie kommt man auf FIRST(T')?
FOLLOW(I)=FOLLOW(F)
FOLLOW(I')=FOLLOW(I) ...werden mir ebenfalls nicht klar
Wer kann mir bei den Follow-Mengen helfen???
Gruß, Ralf
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 12:20 Fr 29.05.2009 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
