Preduvid

Preduvid je tehnika u algoritmima za uzimanje nekoliko sledećih ulaznih stavki pre donošenja najekonomičnije odluke u određenoj etapi algoritma.

Preduvid i lenjo izračunavanje

Preduvid je u suprotnosti sa lenjim izračunavanjem koja odlaže procenu (izračunavanje) sve dok ne bude stvarno neophodna. Obe tehnike se koriste za ekonomično korišćenje prostora ili vremena. Preduvid donosi ispravnu odluku i time izbegava vraćanje (engl. backtracking) iz nepoželjnih stanja u kasnijim fazama algoritma čime štedi prostor nauštrb produženja vremena zbog dodatnog gledanja ulaza. Lenjo izračunavanje obično preskače neispitane algoritamske puteve i tako u opštem slučaju štedi i vreme i prostor. Neke od primena lenjog izračunavanja su straničenje na zahtev (engl. demand paging) kod operativnih sistema i sporo (lenjo) analiziraju tablice u kompajlerima.

Kod ispitivanju prostora za pretragu primenjuju se obe tehnike. Kada već postoje obećavajuće putanje u algoritmu koji se procenjuje, koristi se lenja procena i putanje koje će biti ispitane se stavljaju u red ili na stek. Kada nema obećavajućih putanja za procenu ili proveru da li nova putanja može biti više obećavajuća u dovođenju do rešenja, koristi se preduvid.

Kompajleri takođe koriste obe tehnike. U generisanju tablica analize iz datih pravila koriste lenjo izračunavanje, a u analizi ulaza preduvid.

Preduvid u problemima pretrage

Kod veštačke inteligencije, preduvid je važna komponenta kombinatorne pretrage koja određuje, grubo, koliko se duboko ispituje graf koji predstavlja problem. Potreba za specifičnim ograničenjem za preduvid dolazi od velikih problemskih grafova u mnogim aplikacijama, kao što su računarski šah i računarski go. Prvi očigledni izbor, pretraga u širinu, bi brzo potrošila svu raspoloživu memoriju bilo kojeg modernog računara. Postavljanjem specifičnog preduvidnog ograničenja, vreme algoritma se može pažljivo kontrolisati; njegovo vreme raste eksponencijalno sa rastom preduvidnog ograničenja.

Prefinjenije tehnike pretrage kao što je alfa-beta potkresivanje mogu da eliminišu čitava podstabla u stablu pretrage iz razmatranja. Kada se koriste ove tehnike, količina preduvida nije precizno određena, nego je bilo najveća pretražena dubina bilo neka vrsta proseka.

Preduvidni simbol u sintaksičkoj analizi

Preduvid je takođe važan koncept u sintaksičnim analizatorima u kompajlerima koji su zasnovani na maksimalnom broju ulaznih tokena koje analizator može da vidi i da na osnovu njih odluči koje pravilo treba da primeni.

Preduvid je naročito značajan kod LL, LR, i LALR sintaksičkih analizatora, gde je čest slučaj da se u nazivu algoritma u zagradama eksplicitno naglasi preduvid, na primer LALR(1).

Većina programskih jezika, inače primarnih ciljeva za sintaksičke analizatore, su pažljivo definisani gramatikama tako da ih mogu obrađivati analizatori sa ograničenim (najčešće jedan) preduvidom, zato što su takvi analizatori često efikasniji. Važna promena u ovom prilazu načinjena je 1990. godine kada je Terence Parr napravio ANTLR (kao svoju postdiplomsku tezu), generator sintaksičkih analizatora za efikasnu LL(k) analizu, gde je k fiksirana veličina.

Analizatori obično imaju na raspolaganju par akcija posle gledanja svakog tokena. One su: prebacivanje (pomeranje) – dodavanje tokena na stek radi kasnijeg svođenje (skidanja), svođenje – skidanje tokena sa steka i formiranje sintaksičkog konstrukta, kraj, greška – nijedno poznato pravilo nije primenljivo ili konflikt – nepoznato da li treba uraditi prebacivanje ili svođenje.

Preduvid ima dve prednosti.

• Pomaže da analizator izvrši odgovarajuću akciju u slučaju konflikta. Na primer, da analizira if iskaz u slučaju da se pojavi else klauzula.
• Uklanja mnoga dvostruka stanja i olakšava teret dodatnog steka. Analizator za programski jezik C koji ne koristi preduvid bi imao oko 10,000 stanja, a koji koristi – oko 300.

Primer: Analiza izraza 1+ 2 * 3

Skup pravila za analizu izraza (koji se naziva gramatika) je sledeći:
Pravilo 1:  E → E + E      Izraz je zbir dva izraza.
Pravilo 2:  E → E * E      Izraz je proizvod dva izraza.
Pravilo 3:  E → broj       Izraz je običan broj.
Pravilo 4:  operator + ima manji prioritet od operatora *

Većina programskih jezika (izuzev nekih kao što je APL) i algebarskih formula daju veći prioritet množenju nego sabiranju. Pravilno tumačenje navedenog primera je (1 + (2 * 3)). Primetite da je Pravilo 4 semantičko pravilo. Moguće je preraditi gramatiku tako da se prioritet ubaci u sintaksu. Međutim, nije moguće sva semantička pravila prevesti u sintaksu.

Jednostavne akcije ne-preduvidnog analizatora

1. Svođenje broja 1 na ulazu na izraz E po pravilu 3
2. Prebacivanje simbola + sa ulaza na stek da bi se moglo iskoristiti pravilo 1.
3. Svođenje broja 2 na ulazu na izraz E po pravilu 3.
4. Skidanje niske E+ E sa steka i stavljanje simbola E po pravilu 1.
5. Prebacivanje simbola * sa ulaza na stek u iščekivanju da će se primeniti pravilo 2.
6. Prebacivanje broja 3 sa ulaza na stek u iščekivanju da će se primeniti pravilo 3.
7. Svođenje broja 3 na izraz E po pravilu 3.
8. Skidanje niske E*E sa steka i stavljanje na stek simbola E na osnovu pravila 2.

Stablo sintaksičke analize i rezultujući kod nisu korektni po semantičkim pravilima jezika.

Da bi se ispravila analiza bez preduvida postoje tri načina.

• Korisnik mora da stavi izraz u zagradu. Ovo često nije odgovarajuće rešenje.
• Analizator mora da sadrži dodatnu logiku da uradi bektreking i pokuša ponovo kad god je pravilo prekršeno ili nije ispunjeno. Sličan metod se koristi kod LL analizatora.
• Alternativno, analizator ili gramatika moraju da poseduju dodatnu logiku da odlože svođenje i da svode samo onda kada su potpuno koje pravilo da svedu prvo. Ovaj metod koriste LR analizatori. Na ovaj način se pravilno radi analiza izraza, ali sa mnogo više stanja i sa uvećanom dubinom steka.

Akcija analizatora sa preduvidom

1. Prebacivanje broja 1 na stek u očekivanju da se iskoristi pravilo 3. Ne vrši se odmah svođenje.
2. Svođenje elementa steka na jednostavan izraz po pravilu 3. Ovo se vrši zato što je preduvidni simbol +, pa je analiza na putu ka rečeničnoj formi E+, pa se moze izvršiti svođenje steka na E.
3. Prebacivanje ulaznog simbola + na stek u očekivanju da će se primeniti pravilo 1.
4. Prebacivanje sa ulaza na stek broja 2 u očekivanju pravila 3.
5. Svođenje broja 2 na E zbog simbola * na ulazu po pravilu 3. Preduvidni karakter * očekuje samo E pre njega.
6. Sada je na steku E+E, a na ulazu je jos uvek *. Sada postoje dve mogućnosti - da se izvrši prebacivanje na osnovu pravila 2 ili svođenje na osnovu pravila 1. Pošto operator * ima veći prioritet od operatora + na osnovu pravila 4, prebacuje se * na stek po pravilu 2.
7. Prebacuje se broj 3 sa ulaza na stek u iščekivanju da će se primeniti pravilo 3.
8. Vrši se svođenje broja 3, na steku, na E pošto je viđen kraj ulaza, po pravilu 3.
9. Svođenje izraza E*E koji je na steku na E, po pravilu 2.
10. Svođenje izraza E+E koji je na steku na E, na osnovu pravila 1.

Stablo sintaksične analize koje je generisano je ispravno i mnogo efikasnije od ne-preduvidnih analizatora. Ovu strategiju koristi LALR analizator.