Analiza naniže

Analiza naniže je strategija analiziranja odnosa nepoznatih podataka, postavljanjem hipoteze o strukturi drveta sintaksičke analize (stablo parsiranja), a zatim razmatrajući da li su poznate fundamentalne strukture podudarne sa hipotezom. Koristi se prilikom analiziranja kako prirodnih, tako i programskih jezika.

Analiza naniže predstavlja pokušaj da se generiše najlevlje izvođenje ulazne struje tokena, pronalaženjem odgovarajućeg drveta sintaksičke analize, koristeći data pravila gramatike. Ispitivanje ulazne niske se vrši sleva nadesno.

U pokušaju da se ukloni dvosmislenost (engl. ambiguity), polazeći od početnog simbola, ispituju se sva moguća izvođenja, dok se ne utvrdi da li analizirana reč pripada jeziku ili ne.

Analiza naniže počinje, dakle, od aksiome gramatike, a tokom analize se postupno generiše izvođenje nalevo niske koja se poredi sleva nadesno sa ulaznim nizom tokena.

Jednostavne implementacije izvođenja naniže se ne mogu primeniti nalevo-rekurzivne gramatike, i analiza naniže sa vraćanjem unazad (back-tracking) može da ima eksponencijalnu složenost, u odnosu na dužinu ulazne niske višeznačne konteksno-slobodne gramatike. Ipak, sofisticiranije metode analize naniže, čiji su tvorci Frost, Hariz, i Kalahan, omogućavaju ispitivanje višeznačnih i levo-rekurzivnih gramatika sa polinomijalnom složenosti, i generišu reprezentacije polinomijalne dužine, za potencijalno eksponencijalni broj drveta sintaksičke analize.

Primena u programskim jezicima

Kompajler analizira ulaz programskog jezika poredeći simbole sa pravilima gramatike koja su najčešće zadata u Bekus-Naurovoj formi.

LL-analizator, ili analizator naniže, počinje od početnog simbola date gramatike, i primenjuje pravila gramatike, tako što se najlevlji neterminal zamenjuje odgovarajućom desnom stranom pravila, koja odgovara datom neterminalu. Zatim se primenjuje sledeće pravilo gramatike, koje odgovara sledećem neterminalu na koji se naišlo u izvođenju.

Na taj način analiza se odvija nalevo u rezultujućoj (desnoj) strani pravila, izračunavajući vrednosti neterminala sleva nadesno, i time napredujući naniže duž drveta sintaksičke analize, za svaki novi neterminal na koji se naiđe, pre nego što se pređe na sledeći simbol koji se javlja u pravilu.

Na primer:

• A→aBC
• cd
• eg

Prvo bi se izvelo A→aBC i pokušalo sa izvođenjem cd. Zatim bi se pokušalo sa primenom pravila eg. Kod jednoznačnih jezika svako izvođenje neterminala daje jedinstvene niske: niska izvedena na osnovu jednog pravila neće počinjati istim simbolom kao niska izvedena na osnovu nekog drugog pravila. Jezici koji nisu višeznačni se mogu predstaviti LL(1) gramatikom, gde (1) označava da analizator koristi 1 preduvidni karakter u svakom trenutku. Za višeznačne jezike, da bi mogli da se analiziraju LL-analizatorom, moraju se koristiti više od 1 preduvidnog simbola, na primer LL(3).

Uobičajeno rešenje je da se u tim slučajevima koristi LR analizator (LR parser) poznat još kao analizator naviše, ili analizator prebacivanjem i svođenjem.

Leva rekurzija u analizi naniže

Formalne gramatike koje sadrže levu rekurziju se ne mogu analizirati tehnikom rekurzivnog spusta, osim ako se ne svedu na ekvivalentne desno-rekurzivne gramatike.

Ipak, skorija istraživanja su pokazala da je moguće analizirati levo-rekurzivne gramatike (kao i ostale klase konteksno slobodnih gramatika) korišćenjem sofisticiraniranijih metoda analize naniže, zasnovanih na skraćivanju. Frost i Hafiz su 2006. godine opisali algoritam koji omogućava analiziranje višeznačnih gramatika i skraćuje izvođenje zasnovano na levoj rekurziji, nametanjem posebnih pravila o dužini izvođenja. Frost, Hafiz i Kalahan su 2007. godine usavršili ovaj algoritam, čime je omogućena analiza levo-rekurzivnih gramatika (kako sa direktnom, tako i sa indirektnom rekurzijom) u polinomijalnom vremenu. Takođe je omogućeno generisanje kompaktne reprezentacije polinomijalne dužine potencijalno eksponencijalnog broja drveta sintaksičke analize kod jako višeznačnih gramatika.

Od tada je algoritam implemetniran kao kombinacija više analizatora, napisanih na programskom jeziku Haskel.

Detalji o implementaciji ovih novih metoda su predstavljeni u PADL'08, čiji su autori gore pomenuti. Na sajtu X-SAIGA se može naći više detalja vezanih za implementaciju i algoritme.

Vremenska i prostorna složenost analize naniže

Kada analizator naniže pokuša sa analizom niske višeznačne konteksno slobodne gramatike, postoji mogućnost da mu je potreban eksponencijalan broj koraka (u odnosu na dužinu ulazne niske) da ispita sva moguća izvođenja u datoj gramatici, i generiše sve potencijalne oblike drveta sintaksičke analize, da bi utvrdio da li data niska pripada jeziku opisanom datom gramatikom. To može da prouzrokuje i zahtevanje prevelike količine memorijskog prostora, što se takođe eksponencijalno uvećava pri svakom koraku. Norving je 1991. godine rešio problem eksponencijalne vremenske složenosti u analizi naniže, nastao zbog skupa uzajamno rekurzivnih funkcija. Tehnika koju je on koristio je slična korišćenju dinamičkog programiranja i skupa stanja u Erlijevom algoritmu, kao i tabela korišćenih u CYK algoritmu (od Coocke-Younger-Kasami).

Ključ ideje sastoji se u čuvanju rezultata primene analizatora p na poziciji j u tabeli, a zatim ponovnom korišćenju tih rezultata kad god se naiđe na istu situaciju. Frost, Hafiz i Kalahan takođe koriste čuvanje podataka, kako bi izbegli suvišno izračunavanje, što omogućava analizu bilo koje konteksno-slobodne gramatike u polinomijalnom vremenu (Θ(n⁴) kod levo rekurzivnih gramatika, odnosno složenosti Θ(n³) za gramatike koje nisu levo-rekurzivne). Njihov algoritam analize naniže takođe zahteva količinu memorije u polinomijalnom odnosu, za potencijalno eksponencijalno velika višeznačna drveta sintaksičke analize, zahvaljujući 'kompaktnoj reprezentaciji' i 'lokalnom grupisanju višeznačnosti'. Kompaktna reprezentacija koju koriste pomenuti autori se može uporediti sa kompaktnom reprezentacijom koju koristi Tomita u analizi naviše.