Gramatyki LL(1)
Pierwsze L  przeglÄ…danie od lewej do prawej.
Gramatyki typu LL(k)
Drugie L  tworzenie lewostronnego wyprowadzenia.
Języki formalne i techniki translacji - Wykład 8
1  używanie do podejmowania decyzji jednego symbolu w
każdym kroku.
Dla każdego nieterminala z dwóch różnych prawych stron
Maciek Gębala
produkcji nie da się wyprowadzić ciągów zaczynających się od
tego samego terminala.
10 kwietnia 2013
Niestety nie wszystkie gramatyki bezkontekstowe dają się sprowadzić
do postaci LL(1).
Maciek Gębala Gramatyki typu LL(k) Maciek Gębala Gramatyki typu LL(k)
Gramatyki LL(1) Testowanie na własność LL(1)
Gramatyka nazywa siÄ™ LL(1) gdy z (rozpatrujemy wyprowadzenia
lewostronne)
G jest LL(1), gdy dla S Ò!" wAÄ… i dowolnych produkcji A ², A Å‚
S Ò!" wAÄ… Ò! w²Ä… Ò!" wx, S Ò!" wAÄ… Ò! wÅ‚Ä… Ò!" wy
mamy
FIRST (²Ä…) )" FIRST (Å‚Ä…) = ".
oraz
FIRST (x) = FIRST (y)
Zalety własności: FIRST można efektywnie obliczyć!
wynika, że ² = Å‚.
Inaczej: jeÅ›li S Ò!" wAÄ… Ò! w²Ä… Ò!" wx, to aby odgadnąć nastÄ™pny
krok w wyprowadzeniu należy poznać pierwszy znak x.
Maciek Gębala Gramatyki typu LL(k) Maciek Gębala Gramatyki typu LL(k)
Dowód własności Test na LL(1)
G jest LL(1) wtedy i tylko wtedy, gdy dla każdego A i każdej produkcji
1 A ²|Å‚ : FIRST (² FOLLOW (A)) )" FIRST (Å‚ FOLLOW (A)) = ".
Niech c " FIRST (²Ä…) )" FIRST (Å‚Ä…), ² = Å‚. Wtedy potrafimy

zbudować wyprowadzenia z ²Ä… i Å‚Ä… uzyskujÄ…c c na pierwszym
miejscu. Otrzymamy S Ò!" wAÄ… Ò! w²Ä… Ò!" wcx
Dowód (Ð!) - z pustoÅ›ci wynika LL(1)
i S Ò!" wAÄ… Ò! wÅ‚Ä… Ò!" wcy, ponieważ
Oczywiście:
FIRST (cy) = c = FIRST (cx), z definicji LL(1) mielibyÅ›my ² = Å‚.
JeÅ›li S Ò!" wAÄ… Ò! w²Ä… Ò!" wx to FIRST (x) należą do
Zatem gramatyka nie jest LL(1).
FIRST (² FOLLOW (A)).
2
Niech G nie bÄ™dzie LL(1), tj.: jeÅ›li S Ò!" wAÄ… Ò! w²Ä… Ò!" wcx
Gdyby S Ò!" wAÄ… Ò! wÅ‚Ä… Ò!" wy oraz
i S Ò!" wAÄ… Ò! wÅ‚Ä… Ò!" wcy, wtedy
FIRST (x) = FIRST (y) = c, to mielibyśmy
c " FIRST (²Ä…) )" FIRST (Å‚Ä…). (oczywiste!)
c " FIRST (² FOLLOW (A)) )" FIRST (Å‚ FOLLOW (A)).
Ale jest to niemożliwe.
Maciek Gębala Gramatyki typu LL(k) Maciek Gębala Gramatyki typu LL(k)
Test na LL(1) Test na LL(1)
ZakÅ‚adamy, że c " FIRST (² FOLLOW (A)) )" FIRST (Å‚ FOLLOW (A)).
Dowód: (Ò!) z LL(1) wynika pustość
Dowód: (Ò!) z LL(1) wynika pustość
3
c " FIRST (Å‚), c " FIRST (²), ale c " FOLLOW (A)
1
c " FIRST (²) )" FIRST (Å‚) wtedy S Ò!" vAÄ… Ò! v²Ä… Ò!" vcx dla
i µ " FIRST (²). Wtedy: S Ò!" wAÄ… Ò! w²Ä… Ò!" wÄ… Ò!" wcx.
pewnego x, S Ò!" vAÄ… Ò! vÅ‚Ä… Ò!" vcy dla pewnego y,
Także: S Ò!" wAÄ… Ò! wÅ‚Ä… Ò!" wcyÄ… Ò!" wcycx. Ponieważ
i FIRST (cy) = c = FIRST (cx). RównoczeÅ›nie ² = Å‚, wiÄ™c G nie

FIRST (cx) = c = FIRST (cycx) oraz ² = Å‚, mamy sprzeczność

jest LL(1)!
z LL(1).
2
c " FIRST (²), c " FIRST (Å‚), ale c " FOLLOW (A);
µ " FIRST (²), µ " FIRST (Å‚). Wtedy:
S Ò!" vAÄ… Ò! v²Ä… Ò!" vÄ… Ò!" vcx. Także
S Ò!" vAÄ… Ò! vÅ‚Ä… Ò!" vÄ… Ò!" vcx. Wbrew definicji LL(1).
Maciek Gębala Gramatyki typu LL(k) Maciek Gębala Gramatyki typu LL(k)
Tabele parsowania dla LL(1) Gramatyka spoza LL(1)
Gramatyka G
S µ|abA
M[A, a] zawiera A ², jeÅ›li a " FIRST (² FOLLOW (A)).
A Saa|b
Zgodnie z poprzednim twierdzeniem nie ma konfliktów dla LL(1).
G nie jest LL(1):
Parsing z taką tabelą określa jednoznacznie jedyne możliwe
wyprowadzenie lewostronne.
S Ò! abA Ò! abSaa Ò! ababAaa Ò!" aba...
S Ò! abA Ò! abSaa Ò! abaa
Jeden znak nie wystarczy aby rozróżnić pomiÄ™dzy S µ i
S abA dla drugiego kroku wyprowadzenia.
Maciek Gębala Gramatyki typu LL(k) Maciek Gębala Gramatyki typu LL(k)
FIRSTk Gramatyka LL(k)
Gramatyka jest LL(k) Ô! z
S Ò!" wAÄ… Ò! w²Ä… Ò!" wx
FIRSTk(Ä…) zdefiniowane tak jak FIRST (Ä…):
S Ò!" wAÄ… Ò! wÅ‚Ä… Ò!" wy
" Ä… Ò!" w, w skÅ‚ada siÄ™ z terminali, |w| k i x jest prefiksem w
długości k, to x " FIRSTk(ą), lub
i
" Ä… Ò!" w, w skÅ‚ada siÄ™ z terminali, |w| < k i x = w, to
FIRSTk (x) = FIRSTk(y)
x " FIRSTk(Ä…).
wynika, że ² = Å‚.
Inaczej: jeÅ›li S Ò!" wAÄ… Ò! w²Ä… Ò!" wx, to wystarcza poznać k
znaków x aby okreÅ›lić nastÄ™pny krok wyprowadzenia S Ò!" wAÄ….
Maciek Gębala Gramatyki typu LL(k) Maciek Gębala Gramatyki typu LL(k)
Gramatyka nie-LL(k) dla dowolnego k Podstawowa własność
Przykład
G jest LL(k) wtedy i tylko wtedy, gdy dla dowolnych S Ò!" wAÄ…, oraz
A ², A Å‚ mamy
Gramatyka
FIRSTk(²Ä…) )" FIRSTk(Å‚Ä…) = "
S A|B
A aAb|0
Następująca własność nie jest równoważna LL(k)!
B aBbb|1
JeÅ›li A ², A Å‚, ² = Å‚, to

definiuje
FIRSTk (² FOLLOWk(A)) )" FIRSTk (Å‚ FOLLOWk(A)) = "
{an0bn : n 0} *" {an1b2n : n 0}.
Przykład
Jest to język rozpoznawany deterministycznym automatem ze
S aAaa|bAba i A b|µ, to widać z definicji, że gramatyka jest
stosem, ale nie jest w żadnym LL(k).
LL(2).
(Blok symboli a może być dowolnie długi i nie można się zdecydować
Ale: FOLLOW2(A) = {aa, ba},
na S Ò! A lub S Ò! B.)
FIRST2(b FOLLOW2(A)) )" FIRST2(µ FOLLOW2(A)) = {ba}
Maciek Gębala Gramatyki typu LL(k) Maciek Gębala Gramatyki typu LL(k)
Konstrukcja parsera LL(k) Tabele LL(k)
Notacja
L1 •"k L2 = {w : "x"L "y"L (w = xy '" |xy| k) (" (w = FIRSTk(xy))}
1 2
G - gramatyka LL(k), wx " LG
TA,L trzeba traktować jednocześnie jako funkcję. Niech u ma długość
Konstruujemy lewostronne wyprowadzenie dla wx, zakładamy,
k. Wtedy
że mamy S Ò!" wÄ…, takie że Ä… zaczyna siÄ™ nieterminalem,
Ä… Ò!" x. 1
TA,L(u) = , jeśli dla żadnej produkcji A ą nie zachodzi
u " FIRSTk(Ä…) •"k L,
Z definicji, z w i k następnych znaków x można określić
następny krok wyprowadzenia. 2
TA,L(u) = (A ą, Y1, . . . , Ym ) jeśli dla dokładnie jednej
produkcji A Ä… mamy u " FIRSTk(Ä…) •"k L, ( Y1, . . . , Ym
Problem: w nie można przechować na stosie (tam jest ą).
zdefiniowane poniżej)
3
TA,L(u) = jeśli dla więcej niż jednej produkcji A ą
mamy u " FIRSTk(Ä…) •"k L, (dla jÄ™zyka LL(k) nie powinno to
zajść).
Maciek Gębala Gramatyki typu LL(k) Maciek Gębala Gramatyki typu LL(k)
Definicja Y1, . . . , Ym Konstrukcja tabel LL(k)
Niech Ä… = x0B1x1B2x2 . . . Bmxm, gdzie Bi jest nieterminalem, xi -ciÄ…g
Konstruujemy tylko takie TA,L, które okazują się niezbędne: dla
terminali. Wtedy:
sytuacji poczÄ…tkowej I = {TS,{µ}} Rozszerzamy dopóty, dopóki coÅ›
nowego się pojawia. Reguła:
Yi = FIRSTk(xiBi+1 . . . Bmxm •"k L).
jeśli T " I i
T (u) = (A x0B1x1B2x2 . . . Bmxm, Y1, . . . , Ym ),
Yi mówi jakie ciągi wyprowadzane za Bi są dopuszczalne o ile
dołącz TB ,Yi do I.
i
skorzystamy z A Ä….
Maciek Gębala Gramatyki typu LL(k) Maciek Gębala Gramatyki typu LL(k)
Parser LL(k) Podstawowa własność
1
Na poczÄ…tku TS,{µ} na stosie.
2
Krok parsera:
Dla każdej LL(k)-gramatyki LL(k)-parser określa wyprowadzenie
M[TA,L, u] zdefiniowany jak następuje: niech
lewostronne gdy w " LG, lub daje komunikat błędu w przeciwnym
TA,L(u) = (A x0B1x1B2x2 . . . Bmxm, Y1, . . . , Ym ),
wypadku.
wtedy usuń TA,L ze stosu, zapisz x0TB1,Y1, x1, . . . , TBm,Ym , xm na
stosie, (głowica nie porusza się).
Dowód długi i oczywisty.
M[a, av] = usuń a ze stosu i przesuń głowicę o 1 pozycję,
M[$, µ] = accept,
M[X , u] = reject, w p.p.
Maciek Gębala Gramatyki typu LL(k) Maciek Gębala Gramatyki typu LL(k)