LL analizator

LL analizator (LL parser) je analizator naniže (engl. top-down parsing) za potklasu konteksno-slobodnih gramatika (engl. context-free grammars). Analizira ulaznu nisku s Leva nadesno, i generiše najLevlje izvođenje date rečenice (otuda i skraćenica LL, uporedi sa LR analizatorom). Gramatike koje je moguće analizirati na ovaj način su poznate kao LL gramatike.

Ostatak ovog članka opisuje analizator zasnovan na tablicama, dok alternativni način podrazumeva analiziranje tehnikom rekurzivnog spusta, koja se obično ručno implementira (mada ne uvek - pogledati ANTLR za dodatna objašnjenja LL(*) analizatora, koji koristi tehniku rekurzivnog spusta).

LL analizator je LL(k) analizator ako prilikom analize rečenice koristi k preduvidnih simbola (tokena).

Za gramatiku se kaže da je LL(k) gramatika ako za nju postoji takav analizator, koji analizira rečenice date gramatike bez vraćanja unazad (back tracking). Među ovim gramatikama popularne su LL(1) gramatike, čak iako su jako ograničene, jer odgovarajući analizator koristi samo jedan preduvidni karakter da bi doneo odluku o sledećem koraku u izvođenju, i potreban je značajan napor da bi se izvršila njihova analiza.

Postoje izvesne nesuglasice između Evropske škole dizajna jezika, koja preferira LL gramatike, i ostalih, koje pretežno koriste LR gramatike. Za ovo je najviše zaslužan uticaj Niklausa Virta (ETH Zürich), čija istraživanja su opisala razne načine za optimizaciju LL(1) jezika i kompilatora.

Opšti slučaj

Analizator radi nad niskama (stringovima) određene gramatike.

Analizator se sastoji od:

• ulaznog bafera, koji sadrži nisku gramatike
• potisne liste (steka), koja se koristi za čuvanje završnih i nezavršnih simbola (engl. terminals, non-terminals) gramatike koji tek treba da budu obrađeni
• tablice za parsiranje (engl. parsing table), pomoću koje se određuje pravilo gramatike koje treba da bude primenjeno, u zavisnosti od simbola na

vrhu steka i sledećeg tokena

Analizator primenjuje pravilo pronađeno u tabeli, za dati simbol na vrhu potisne liste (red), i trenutni simbol na ulazu (kolona).

Kada analizator počne sa radom na steku se već nalaze 2 simbola: [ S, $] gde je '$' specijalni završni simbol koji se koristi da se naznači dno steka, kao i kraj ulazne niske, a 'S' je početni simbol (aksioma) gramatike. Analizator će pokušati da upiše na stek ono na šta naiđe na ulazu, ali će na steku zadržati samo ono što tek treba da se izvede.

Konkretan primer

Da bi pojasnili kako analizator radi, posmatraćemo sledeći primer gramatike:

1. S → F
2. S → (S + F )
3. F → 1

i analiziraćemo sledeću nisku:

  (1 + 1)

Tablica za analizu izgleda ovako:

	(	)	1	+	$
S	2	-	1	-	-
F	-	-	3	-	-

(Primetiti da postoji kolona i za specijalni terminal, označen sa $, koji služi da naznači kraj ulaza.)

Tok analize

Analizator čita prvi karakter ulazne niske - '(', kao i 'S' sa steka. Iz tablice čita da treba da primeni pravilo pod rednim brojem 2.; skida 'S' sa steka i upisuje odgovarajuću desnu stranu pravila na stek- '(S+F)'; i ispisuje broj ovog pravila na izlazu. Sadržaj steka je tada:

[ (, S, +, F,), $]

U sledećem koraku uklanja '(' sa ulaza, kao i sa steka, čiji sadržaj postaje:

[ S, +, F,), $]

Sada analizator čita '1' sa ulaza i zna da treba da primeni pravilo (1), a zatim i pravilo (3), i ispisuje te brojeve na izlazu. To daje sledeća stanja steka:

[ F, +, F,), $]
[ 1, +, F,), $]

U sledeća dva koraka analizator čita '1' i '+' sa ulaza, i kako se ovi karakteri poklapaju sa sledeća dva karaktera na vrhu steka, uklanja ih sa steka. To daje sledeći sadržaj steka:

[ F,), $]

U sledeća tri koraka, 'F' se na steku zamenjuje sa '1', broj 3 se ispisuje na izlazu, a zatim se '1' i ')' uklanjaju sa steka, i sa ulaza. Tako analizator završava sa '$' kako na steku, tako i na ulazu. U tom slučaju prijavljuje da je prihvatio ulaznu nisku, a na izlazu ispisuje sledeći niz brojeva:

[ 2, 1, 3, 3]

što je zaista najlevlje izvođenje date niske u ovoj gramatici, koje izgleda ovako:

 S → (S+F) → (F+F) → (1+F) → (1+1)

Zapažanja

Kao što se može videti iz primera, analizator izvršava 3 vrste akcija u zavisnosti od toga da li se na steku nalazi završni simbol, nezavršni simbol, ili specijalni karakter '$':

• Ako se na vrhu nalazi nezavršni simbol, gleda u tabelu kako bi na osnovu tog neterminala, i sledećeg simbola sa ulaza odlučio koje pravilo treba da primeni kako bi ga zamenio na steku. Broj pravila ispisuje na izlazu. Ako u tabeli takvo pravilo nije definisano, onda prijavljuje grešku i zaustavlja rad.
• Ako se na vrhu steka nalazi završni simbol, poredi ga sa simbolom na ulazu, i ako su jednaki, oba se uklanjaju. Ako nisu jednaki, analizator prijavljuje grešku, i zaustavlja rad.
• Ako je na vrhu steka '$', kao i na ulazu, onda analizator prijavljuje da je niska uspešno prihvaćena, u suprotnom prijavljuje grešku. U oba slučaja zaustavlja rad.

Ovi koraci se ponavljaju sve dok analizator ne prekine rad, nakon čega je ulazna niska ili potpuno obrađena i ispisano je njeno najlevlje izvođenje, ili je prijavljena greška, što znači da data niska ne pripada jeziku opisanom datom gramatikom.

Konstrukcija tablica za LL(1) analizu

Kako bi konstruisali tabelu, neophodno je da ustanovimo koje pravilo gramatike analizator treba da primeni ako vidi neterminal A na vrhu steka, i simbol a na ulazu. Lako je primetiti da to pravilo treba da bude u obliku A → w, i da niska koja se može izvesti iz w mora da počinje sa a. U te svrhe se definiše skup Prvi(w) (Fi(w)), koji sadrži sve one završne simbole kojima može da počne niska koja se izvodi iz w, kao i ε ako se iz w može izvesti prazna niska. Za gramatiku datu pravilima A₁ → w₁, ..., А_n → w_n, možemo odrediti skupove Prvi(w_i), kao i Prvi(А_i) za svako pravilo, na sledeći način:

1. Inicijalno, skupovi Prvi(w_i), kao i Prvi(A_i), su prazni
2. dodati Prvi(w_i) u Prvi(A_i) za svako pravilo A_i → w_i, gde se skup Prvi definiše sa:
   • Prvi(a w' ) = { a } za svaki terminal a
   • Prvi(A w' ) = Prvi(A) za svaki neterminal A, ako skup Prvi(A) ne sadrži ε
   • Prvi(A w' ) = Prvi(A) \ { ε } ∪ Prvi(w' ) za svaki neterminal A, ako skup Prvi(A) sadrži ε
   • Prvi(ε) = { ε }
3. dodati Prvi(w_i) u Prvi(Ai) za svako pravilo A_i → w_i
4. ponavljati korake 2 i 3 sve dok se skup Prvi menja.

Nažalost, skupovi Prvi nisu dovoljni kako bi se formirala tablica. Problem nastaje kada se desna strana pravila-w može svesti na praznu nisku. Analizator treba da primeni pravilo A → w ako ε pripada skupu Prvi(w) i na ulazu se javi simbol koji može da sledi posle A. Zbog toga je potrebno odrediti i skupove Sledi(A) (Fo(A)), koji sadrže sve one završne simbole a koji u izvođenju mogu da slede nakon simbola A tj, ako niska αAaβ može da se izvede iz startnog simbola. Skupovi Sledi za svaki od neterminala gramatike se konstruišu na sledeći način:

1. Inicijalno, Sledi(A_i) je prazan skup
2. Ako postoji pravilo oblika A_j → wA_iw' onda:
   • ako terminal a pripada skupu Prvi(w' ), dodati a u Sledi(A_i)
   • ako ε pripada skupu Prvi(w' ), dodati Sledi(A_j) u skup Sledi(A_i)
3. ponavljati korak 2 svi dok se nešto novo može dodati u skup Sledi.

Sada možemo precizno odrediti kako da popunimo tablicu analize. Ako T[A,a] odgovara sadržaju tablice za neterminal A i terminal a, onda

T[A,a] sadrži pravilo A → w ako i samo ako

a pripada skupu Prvi(w) ili

ε pripada skupu Prvi(w) i a pripada skupu Sledi(A).

Ako tablica sadrži najviše jedno pravilo u svakom od polja, onda će analizator uvek znati tačno koje pravilo da primeni, i moći će da analizira niske bez vraćanja unazad. Upravo u toj situaciji za datu gramatiku kažemo da je LL(1) gramatika.

Konstrukcija tablica za LL(k) analizu

Do sredine 1990-ih godina bilo je široko rasprostranjeno uverenje da je LL(k) analiza (za k>1) nepraktična, jer je postojala mogućnost da veličina tablice (u najgorem slučaju) bude eksponencijalne složenosti u odnosu na k. Ovo razmišljanje je promenjeno nakon objavljivanja knjige „Purdue Compiler Construction Tool Set“ (PCCTS, poznata kao ANTLR), oko 1992. godine, gde je pokazano da mnogi programski jezici mogu efikasno da se analiziraju koristeći LL(k) analizator, bez izazivanja najgoreg mogućeg ponašanja.

Šta više, u nekim slučajevima LL analiza je izvodljiva čak i sa neograničenim brojem preduvidnih karaktera. Sa druge strane, tradicionalni generatori analizatora, kao yacc/GNU bison konstruišu tablice na osnovu LALR(1) principa, sa fiksiranim jednim preduvidnim karakterom.