Teoria kompilacji i kompilatory (2017/18)

Zadanie 1

Metody rozbioru gramatycznego.

metody prawostronne i lewostronne
generacyjna "top-down"
redukcyjna "bottom-up"

Zadanie 2

Dla gramatyki:

S \rightarrow L = E \\ L \rightarrow a\ |\ a(E) \\ E \rightarrow E + V\ |\ V \\ V \rightarrow a\ |\ a(E)\ |\ (E)

zbudować tablicę parsera LL(1) i sprawdzić, czy ciąg $a(a+a)=a+a(a)$ należy do gramatyki.

Usunięcie lewostronnej rekursji
$S \rightarrow L=E \\ L \rightarrow a\ |\ a(E) \\ E \rightarrow VE' \\ E' \rightarrow +VE'\ |\ \epsilon \\ V \rightarrow a\ |\ a(E)\ |\ (E)$
Usunięcie lewostronnej faktoryzacji
$S \rightarrow L=E \\ L \rightarrow aL' \\ L' \rightarrow (E)\ |\ \epsilon \\ E \rightarrow VE' \\ E' \rightarrow +VE'\ |\ \epsilon \\ V \rightarrow L\ |\ (E)$
Wyznaczenie zbiorów FIRST i FOLLOW

FIRST FOLLOW

$S$ a $

$L$ a =, +, $, )

$L'$ (, $\epsilon$ =, +, $, )

$E$ a, ( $, )

$E'$ +, $\epsilon$ $, )

$V$ a, ( +, $, )

	FIRST	FOLLOW
$S$	a	$
$L$	a	=, +, $, )
$L'$	(, $\epsilon$	=, +, $, )
$E$	a, (	$, )
$E'$	+, $\epsilon$	$, )
$V$	a, (	+, $, )

Tworzenie tablicy parsera

$S \rightarrow L=E$
$L \rightarrow aL'$
$L' \rightarrow (E)$
$L' \rightarrow \epsilon$
$E \rightarrow VE'$
$E' \rightarrow +VE'$
$E' \rightarrow \epsilon$
$V \rightarrow L$
$V \rightarrow (E)$

	a	(	)	+	=	$
$S$	$L=E$ - 1
$L$	$aL'$ - 2
$L'$		$(E)$ - 3	$\epsilon$ - 4	$\epsilon$ - 4	$\epsilon$ - 4	$\epsilon$ - 4
$E$	$VE'$ - 5	$VE'$ - 5
$E'$			$\epsilon$ - 7	$+VE'$ - 6		$\epsilon$ - 7
$V$	$L$ - 8	$(E)$ - 9

Sprawdzenie ciągu $a(a+a)=a+a(a)$

stos	symbole	produkcje
#S	a(a+a)=a+a(a)$	$\epsilon$
#E=L	a(a+a)=a+a(a)$	1
#E=L'a	a(a+a)=a+a(a)$	1, 2
#E=L'	(a+a)=a+a(a)$	1, 2
#E=)E(	(a+a)=a+a(a)$	1, 2, 3
#E=)E	a+a)=a+a(a)$	1, 2, 3
#E=)E'V	a+a)=a+a(a)$	1, 2, 3, 5
#E=)E'L	a+a)=a+a(a)$	1, 2, 3, 5, 8
#E=)E'L'a	a+a)=a+a(a)$	1, 2, 3, 5, 8, 2
#E=)E'L'	+a)=a+a(a)$	1, 2, 3, 5, 8, 2
#E=)E'	+a)=a+a(a)$	1, 2, 3, 5, 8, 2, 4
#E=)E'V+	+a)=a+a(a)$	1, 2, 3, 5, 8, 2, 4, 6
#E=)E'V	a)=a+a(a)$	1, 2, 3, 5, 8, 2, 4, 6
#E=)E'L	a)=a+a(a)$	1, 2, 3, 5, 8, 2, 4, 6, 8
#E=)E'L'a	a)=a+a(a)$	1, 2, 3, 5, 8, 2, 4, 6, 8, 2
#E=)E'L'	)=a+a(a)$	1, 2, 3, 5, 8, 2, 4, 6, 8, 2
#E=)E'	)=a+a(a)$	1, 2, 3, 5, 8, 2, 4, 6, 8, 2, 4
#E=)	)=a+a(a)$	1, 2, 3, 5, 8, 2, 4, 6, 8, 2, 4, 7
#E=	=a+a(a)$	1, 2, 3, 5, 8, 2, 4, 6, 8, 2, 4, 7
#E	a+a(a)$	1, 2, 3, 5, 8, 2, 4, 6, 8, 2, 4, 7
#E'V	a+a(a)$	1, 2, 3, 5, 8, 2, 4, 6, 8, 2, 4, 7, 5
#E'L	a+a(a)$	1, 2, 3, 5, 8, 2, 4, 6, 8, 2, 4, 7, 5, 8
#E'L'a	a+a(a)$	1, 2, 3, 5, 8, 2, 4, 6, 8, 2, 4, 7, 5, 8, 2
#E'L'	+a(a)$	1, 2, 3, 5, 8, 2, 4, 6, 8, 2, 4, 7, 5, 8, 2
#E'	+a(a)$	1, 2, 3, 5, 8, 2, 4, 6, 8, 2, 4, 7, 5, 8, 2, 4
#E'V+	+a(a)$	1, 2, 3, 5, 8, 2, 4, 6, 8, 2, 4, 7, 5, 8, 2, 4, 6
#E'V	a(a)$	1, 2, 3, 5, 8, 2, 4, 6, 8, 2, 4, 7, 5, 8, 2, 4, 6
#E'L	a(a)$	1, 2, 3, 5, 8, 2, 4, 6, 8, 2, 4, 7, 5, 8, 2, 4, 6, 8
#E'L'a	a(a)$	1, 2, 3, 5, 8, 2, 4, 6, 8, 2, 4, 7, 5, 8, 2, 4, 6, 8, 2
#E'L'	(a)$	1, 2, 3, 5, 8, 2, 4, 6, 8, 2, 4, 7, 5, 8, 2, 4, 6, 8, 2
#E')E(	(a)$	1, 2, 3, 5, 8, 2, 4, 6, 8, 2, 4, 7, 5, 8, 2, 4, 6, 8, 2, 3
#E')E	a)$	1, 2, 3, 5, 8, 2, 4, 6, 8, 2, 4, 7, 5, 8, 2, 4, 6, 8, 2, 3
#E')E'V	a)$	1, 2, 3, 5, 8, 2, 4, 6, 8, 2, 4, 7, 5, 8, 2, 4, 6, 8, 2, 3, 5
#E')E'L	a)$	1, 2, 3, 5, 8, 2, 4, 6, 8, 2, 4, 7, 5, 8, 2, 4, 6, 8, 2, 3, 5, 8
#E')E'L'a	a)$	1, 2, 3, 5, 8, 2, 4, 6, 8, 2, 4, 7, 5, 8, 2, 4, 6, 8, 2, 3, 5, 8, 2
#E')E'L'	)$	1, 2, 3, 5, 8, 2, 4, 6, 8, 2, 4, 7, 5, 8, 2, 4, 6, 8, 2, 3, 5, 8, 2
#E')E'	)$	1, 2, 3, 5, 8, 2, 4, 6, 8, 2, 4, 7, 5, 8, 2, 4, 6, 8, 2, 3, 5, 8, 2, 4
#E')	)$	1, 2, 3, 5, 8, 2, 4, 6, 8, 2, 4, 7, 5, 8, 2, 4, 6, 8, 2, 3, 5, 8, 2, 4, 7
#E'	$	1, 2, 3, 5, 8, 2, 4, 6, 8, 2, 4, 7, 5, 8, 2, 4, 6, 8, 2, 3, 5, 8, 2, 4, 7
#	$	1, 2, 3, 5, 8, 2, 4, 6, 8, 2, 4, 7, 5, 8, 2, 4, 6, 8, 2, 3, 5, 8, 2, 4, 7, 7

Zadany ciąg należy do tej gramatyki.

Zadanie 3

Mamy daną gramatykę i zbudowaną tablicę parsera SLR(1). Mamy sprawdzić, czy zadany ciąg należy do tej gramatyki.

A \rightarrow BA \\ A \rightarrow \epsilon \\ B \rightarrow aB \\ B \rightarrow b

	a	b	#	A	B
0	s3	s3	r2	1	2
1			acc
2	s3	s4	r2	5	2
3	s3	s4			6
4	r4	r4	r4
5			r1
6	r3	r3	r3

Ciąg do sprawdzenia: $aabb\#$

stos	symbole	wejście	akcja
0		aabb#	przesunięcie
0 3	a	abb#	przesunięcie
0 3 3	aa	bb#	przesunięcie
0 3 3 4	aab	b#	redukcja $B \rightarrow b$
0 3 3 6	aaB	b#	redukcja $B \rightarrow aB$
0 3 6	aB	b#	redukcja $B \rightarrow aB$
0 2	B	b#	przesunięcie
0 2 4	Bb	#	redukcja $B \rightarrow b$
0 2 2	BB	#	redukcja $A \rightarrow \epsilon$
0 2 2 5	BBA	#	redukcja $A \rightarrow BA$
0 2 5	BA	#	redukcja $A \rightarrow BA$
0 1	A	#	akceptacja