Teoria kompilacji i kompilatory (2016/17)

Zadanie 1

Podać definicję gramatyki LL(1).

Niech:

\omega, x, y \in \Sigma^* \\ \beta, \gamma \in (V \cup E)^* \\ A \in V

$G=<V, \Sigma, P, S> \in G_{BK}$ jest klasy LL(1) $\Leftrightarrow$ dla każdej pary wywodów lewostronnych:

$S\Rightarrow^*_L\omega A\alpha\Rightarrow_L\omega\beta\alpha\Rightarrow^*_L\omega x$
$S\Rightarrow^*_L\omega A\alpha\Rightarrow_L\omega\gamma\alpha\Rightarrow^*_L\omega y$

jeżeli FIRST₁(x) = FIRST₁(y) to $\beta=\gamma$

Nieformalnie: Gramatyka LL(1) w wywodzie lewostronnym ma własność taką, że zawsze pierwszy symbol słowa końcowego w sposób jednoznaczny określa regułę (produkcję), jaką należy zastosować.

Zadanie 2

Dla gramatyki:

S \rightarrow S@\ |\ L \\ L \rightarrow a[S]\ |\ a

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

Podpowiedź: być może z tą gramatyką coś najpierw trzeba zrobić.

Usunięcie lewostronnej rekursji
$S \rightarrow LS' \\ S' \rightarrow @S'\ |\ \epsilon \\ L \rightarrow a[S]\ |\ a$
Usunięcie lewostronnej faktoryzacji
$S \rightarrow LS' \\ S' \rightarrow @S'\ |\ \epsilon \\ L \rightarrow aL' \\ L' \rightarrow [S]\ |\ \epsilon$
Wyznaczenie zbiorów FIRST i FOLLOW

FIRST FOLLOW

$S$ a $, ]

$S'$ @, $\epsilon$ $, ]

$L$ a @, $, ]

$L'$ [, $\epsilon$ @, $, ]

	FIRST	FOLLOW
$S$	a	$, ]
$S'$	@, $\epsilon$	$, ]
$L$	a	@, $, ]
$L'$	[, $\epsilon$	@, $, ]

Tworzenie tablicy parsera

$S \rightarrow LS'$
$S' \rightarrow @S'$
$L \rightarrow aL'$
$L' \rightarrow [S]$
$S' \rightarrow \epsilon$
$L' \rightarrow \epsilon$

	a	@	[	]	$
$S$	$LS'$ - 1
$S'$		$@S'$ - 2		$\epsilon$ - 5	$\epsilon$ - 5
$L$	$aL'$ - 3
$L'$		$\epsilon$ - 6	$[S]$ - 4	$\epsilon$ - 6	$\epsilon$ - 6

Sprawdzenie ciągu $a[a@]@$

stos	symbole	produkcje
#S	a[a@]@$	$\epsilon$
#S'L	a[a@]@$	1
#S'L'a	a[a@]@$	1, 3
#S'L'	[a@]@$	1, 3
#S']S[	[a@]@$	1, 3, 4
#S']S	a@]@$	1, 3, 4
#S']S'L	a@]@$	1, 3, 4, 1
#S']S'L'a	a@]@$	1, 3, 4, 1, 3
#S']S'L'	@]@$	1, 3, 4, 1, 3
#S']S'	@]@$	1, 3, 4, 1, 3, 6
#S']S'@	@]@$	1, 3, 4, 1, 3, 6, 2
#S']S'	]@$	1, 3, 4, 1, 3, 6, 2
#S']	]@$	1, 3, 4, 1, 3, 6, 2, 5
#S'	@$	1, 3, 4, 1, 3, 6, 2, 5
#S'@	@$	1, 3, 4, 1, 3, 6, 2, 5, 2
#S'	$	1, 3, 4, 1, 3, 6, 2, 5, 2
#	$	1, 3, 4, 1, 3, 6, 2, 5, 2, 5

Zadany ciąg należy do tej gramatyki.

Zadanie 3

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

S \rightarrow AS \\ S \rightarrow b \\ A \rightarrow aB \\ B \rightarrow aB \\ B \rightarrow b

	a	b	#	S	A	B
0	s2	s3	r1	1	1
1	s2	s3	acc	4	1
2	s5	s3				4
3	r5	r5	r2
4	r3	r3	r1
5	s5	s3				6
6	r4	r4

Ciąg do sprawdzenia: $abaabb\#$

stos	symbole	wejście	akcja
0		abaabb#	przesunięcie
0 2	a	baabb#	przesunięcie
0 2 3	ab	aabb#	redukcja $B \rightarrow b$
0 2 4	aB	aabb#	redukcja $A \rightarrow aB$
0 1	A	aabb#	przesunięcie
0 1 2	Aa	abb#	przesunięcie
0 1 2 5	Aaa	bb#	przesunięcie
0 1 2 5 3	Aaab	b#	redukcja $B \rightarrow b$
0 1 2 5 6	AaaB	b#	redukcja $B \rightarrow aB$
0 1 2 4	AaB	b#	redukcja $A \rightarrow aB$
0 1 1	AA	b#	przesunięcie
0 1 1 3	AAb	#	redukcja $S \rightarrow b$
0 1 1 4	AAS	#	redukcja $S \rightarrow AS$
0 1 4	AS	#	redukcja $S \rightarrow AS$
0	S	#	akceptacja

Zadany ciąg należy do tej gramatyki.