Compilerbau & Formale Sprachen: Beispiele für FIRST- und FOLLOW-Mengen

Mit diesem Beispiel sollen die Berechnungen der nullable-Tabelle und der FIRST- und FOLLOW-Mengen veranschaulicht werden. Die Grammatik ist mehrdeutig, da X und Y beide auf ε ableitbar sind. Also ist diese Grammatik auch keine LL(1)-Grammatik.

Die Grammatik

G = (N, T, P, S)
N :	{ Z, X, Y }
T :	{ a, c, d }
S :	Z
P :	Z	::=	d
	Z	::=	X Y Z
	X	::=	Y
	X	::=	a
	Y	::=
	Y	::=	c

Die Iterationen bei der Berechnung der nullable-Symbole

	Z	X	Y
0.	-	-	-
1.	-	-	true
2.	-	true	true
3.	-	true	true

X und Y sind auf ε ableitbar.

Die Iterationen bei der Berechnung der FIRST-Mengen

	Z	X	Y
0.	{ }	{ }	{ }
1.	{ d }	{ a }	{ c }
2.	{ d, a, c }	{ a, c }	{ c }
3.	{ d, a, c }	{ a, c }	{ c }

Die FIRST-Mengen werden schrittweise über Y und X bis zu Z hin vergrößert.

Die Iterationen bei der Berechnung der FOLLOW-Mengen

	Z	X	Y
0.	{ }	{ }	{ }
1.	{ }	{ c, d, a }	{ d, a, c }
2.	{ }	{ c, d, a }	{ d, a, c }

Die FOLLOW-Menge Z ist leer, da hier nicht mit der erweiterten Grammatik gearbeitet wurde.

Die LL-Parser-Tabelle

	a	c	d
Z	Z ::= X Y Z	Z ::= X Y Z	Z ::= d Z ::= X Y Z
X	X ::= Y X ::= a	X ::= Y	X ::= Y
Y	Y ::=	Y ::= Y ::= c	Y ::=

Die Grammatik ist nicht LL(1): 3 Zelle(n) mit Konflikten

Wegen der Mehrdeutigkeiten ist die Grammatik keine LL-Grammatik.

Dieses ist ein Beispiel für eine LL(1)-Grammatik. Man erkennt, dass die rechten Seiten von S und L immer mit einem jeweils eindeutigen Terminalsymbol beginnen.

Es wird im folgenden mit der erweiterten Grammatik gearbeitet.

Die Grammatik

G = (N, T, P, S)
N :	{ S', S, L, E }
T :	{ :=, ;, begin, else, end, id, if, num, then, $ }
S :	S'
P :	S'	::=	S $
	S	::=	if E then S else S
	S	::=	begin S L
	S	::=	id := E
	L	::=	end
	L	::=	; S L
	E	::=	num
	E	::=	id

Die Iterationen bei der Berechnung der nullable-Symbole

	S'	S	L	E
0.	-	-	-	-
1.	-	-	-	-

Da keine ε-Produktionen existieren, ist die Berechnung trivial.

Die Iterationen bei der Berechnung der FIRST-Mengen

	S'	S	L	E
0.	{ }	{ }	{ }	{ }
1.	{ }	{ if, begin, id }	{ end, ; }	{ num, id }
2.	{ if, begin, id }	{ if, begin, id }	{ end, ; }	{ num, id }
3.	{ if, begin, id }	{ if, begin, id }	{ end, ; }	{ num, id }

Die Iterationen bei der Berechnung der FOLLOW-Mengen

	S'	S	L	E
0.	{ }	{ }	{ }	{ }
1.	{ }	{ $, else, end, ; }	{ $, else, end, ; }	{ then, $, else, end, ; }
2.	{ }	{ $, else, end, ; }	{ $, else, end, ; }	{ then, $, else, end, ; }

Diese Berechnung ist redundant, da kein Symbol auf ε ableitbar ist.

Die LL-Parser-Tabelle

	:=	;	begin	else	end	id	if	num	then	$
S'	-	-	S' ::= S $	-	-	S' ::= S $	S' ::= S $	-	-	-
S	-	-	S ::= begin S L	-	-	S ::= id := E	S ::= if E then S else S	-	-	-
L	-	L ::= ; S L	-	-	L ::= end	-	-	-	-	-
E	-	-	-	-	-	E ::= id	-	E ::= num	-	-

Die Grammatik ist LL(1)

Beispiele für FIRST- und FOLLOW-Mengen

FIRST- und FOLLOW-Mengen

Die Grammatik

Die Iterationen bei der Berechnung der nullable-Symbole

Die Iterationen bei der Berechnung der FIRST-Mengen

Die Iterationen bei der Berechnung der FOLLOW-Mengen

Die LL-Parser-Tabelle

Beispiel für eine LL-Grammatik

Die Grammatik

Die Iterationen bei der Berechnung der nullable-Symbole

Die Iterationen bei der Berechnung der FIRST-Mengen

Die Iterationen bei der Berechnung der FOLLOW-Mengen

Die LL-Parser-Tabelle