FIRST und FOLLOW-Mengen, LL1 < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 13:27 Fr 19.02.2010 | | Autor: | RalU |
| Aufgabe | Hallo,
von folgender KNF-Grammatik soll geprüft werden, ob diese eine LL1-Grammatik ist (FIRST- und FOLLOW-Mengen bilden und dann entscheiden).
G [mm] =_{def}(\summe [/mm] , N, P, S) mit
[mm] \summe [/mm] ={+,*,(,),0,1}
N={S,K,K',I,I',T}
P={
S -> KS'
S' -> +kS' | [mm] \varepsilon
[/mm]
K -> IK'
K' -> IK' | [mm] \varepsilon
[/mm]
I -> TI'
I' -> *I' | [mm] \varepsilon
[/mm]
T -> [mm] 0|1|\emptyset|e|(S)
[/mm]
}
Zur Bildung der FOLLOW-Mengen kann ich folgende Regeln benutzen:
1) Nehme $ zu FOLLOW(S) hinzu (Sonderzeichen für das Ende der Eingabe)
2) Falls A -> [mm] \alpha [/mm] A [mm] \beta [/mm] nehme [mm] FIRST(\beta) [/mm] \ { [mm] \varepsilon [/mm] } zu FOLLOW(B) hinzu
3) Falls A -> [mm] \alpha [/mm] B oder A -> [mm] \alpha [/mm] B [mm] \beta [/mm] mit [mm] \varepsilon \in FIRST(\beta), [/mm] nehem FOLLOW(A) zu FOLLOW(B) hinzu. |
Ich habe einige Fragen wegen der FOLLOW-Mengen, zunächst aber mal meine Lösung für FIRST-Mengen und die FIRST-Mengen der rechten Seiten, falls Alternativen bei den Produktionsregeln auftreten
FIRST-Mengen:
FIRST(0)={0}
FIRST(1)={1}
[mm] FIRST(\emptyset)={ \emptyset }
[/mm]
FIRST(e)={e}
FIRST(( ) = { ( }
FIRST( ) ) = { ) }
FIRST(+)={+}
FIRST(*)={*}
FIRST(T)={ [mm] 0,1,\emptyset,e,( [/mm] }
FIRST(I')={ [mm] *,\varepsilon [/mm] }
FIRST(I)=FIRST(T)={ [mm] 0,1,\emptyset,e,( [/mm] }
FIRST(K')=FIRST(I) [mm] \cup [/mm] { [mm] \varepsilon [/mm] } = { [mm] \varepsilon,0,1,\emptyset,e,( [/mm] }
FIRST(K)=FIRST(I)={ [mm] 0,1,\emptyset,e,( [/mm] }
FIRST(S')={ [mm] +,\varepsilon [/mm] }
FIRST(S)=FIRST(K)={ [mm] 0,1,\emptyset,e,( [/mm] }
FIRST-Mengen für die rechten Seiten der Produktionsregeln
FIRST(+KS')={+}
[mm] FIRST(\varepsilon)={ \varepsilon }
[/mm]
FIRST(IK')=FIRST(I)={ [mm] 0,1,\emptyset,e,( [/mm] }
[mm] FIRST(\varepsilon)={ \varepsilon }
[/mm]
FIRST(*I')={*}
[mm] FIRST(\varepsilon)={\varepsilon}
[/mm]
FIRST(0)={0}
FIRST(1)={1}
[mm] FIRST(\emptyset)={ \emptyset }
[/mm]
FIRST(e)={e}
FIRST( (s) ) = { ( }
Nun komme ich zu den FOLLOW-Mengen bezüglich der Aufgabe:
FOLLOW(S)={ $, ) }
// $ Sonderzeichen für Eingabeende und S ist Startsymbol
FOLLOW(S') = FOLLOW(S)={ $, /) }
FOLLOW(K) = FIRST(S') \ { [mm] \varepsilon [/mm] } [mm] \cup [/mm] FOLLOW(S') = { $, ), + } (laut Musterlösung)
Warum muss hier Regel 2 (siehe Aufgabenstellung) für die Bildung der FOLLOW-Menge verwendet werden? Regel 2 sieht doch vor, dass die Produktionsregel folgende Form hat:
Falls A -> [mm] \alphaA\beta [/mm] . Aber in diesem Fall lautet die Produktionsregel ja konkret K -> IK' . Jetzt kann ich mir noch vorstellen, dass A meinem K' entpsricht, aber ein [mm] \beta [/mm] hab ich doch gar nicht und ein [mm] \alpha [/mm] hab ich auch nicht (höchstens ein I, was aber ein Nichtterminalsymbol ist und kein Terminalsymbol wie [mm] \alpha [/mm] )!
FOLLOW(K')=FOLLOW(K)
[mm] FOLLOW(I)=FIRST(I)\{\varepsilon} \cup [/mm] FOLLOW(K) = { [mm] 0,1,\emptyset,e,(,+,$,) [/mm] }
FOLLOW(I')=FOLLOW(I)
FOLLOW(T) = FOLLOW(I) [mm] \cup FIRST(I')\{\varepsilon}
[/mm]
={ [mm] *,0,1,\emptyset,e,(,+,$,) [/mm] } (laut Musterlösung)
Warum ist FOLLOW(T) nicht einfach nur =FOLLOW(I) ?
Ich muss doch nachschauen, wo mein T auf der rechten Seite einer Produktionsregel steht und das ist ja bei I -> TI' der Fall, also muss es doch FOLLOW(I) sein.
Ich bitte um Hilfe bei den in rot markierten Fragen.
Gruß, Ralf
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 14:20 So 21.02.2010 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
