Предувид

Предувид је техника у алгоритмима за узимање неколико следећих улазних ставки пре доношења најекономичније одлуке у одређеној етапи алгоритма.

Предувид и лењо израчунавање

Предувид је у супротности са лењим израчунавањем која одлаже процену (израчунавање) све док не буде стварно неопходна. Обе технике се користе за економично коришћење простора или времена. Предувид доноси исправну одлуку и тиме избегава враћање (енгл. backtracking) из непожељних стања у каснијим фазама алгоритма чиме штеди простор науштрб продужења времена због додатног гледања улаза. Лењо израчунавање обично прескаче неиспитане алгоритамске путеве и тако у општем случају штеди и време и простор. Неке од примена лењог израчунавања су страничење на захтев (енгл. demand paging) код оперативних система и споро (лењо) анализирају таблице у компајлерима.

Код испитивању простора за претрагу примењују се обе технике. Када већ постоје обећавајуће путање у алгоритму који се процењује, користи се лења процена и путање које ће бити испитане се стављају у ред или на стек. Када нема обећавајућих путања за процену или проверу да ли нова путања може бити више обећавајућа у довођењу до решења, користи се предувид.

Компајлери такође користе обе технике. У генерисању таблица анализе из датих правила користе лењо израчунавање, а у анализи улаза предувид.

Предувид у проблемима претраге

Код вештачке интелигенције, предувид је важна компонента комбинаторне претраге која одређује, грубо, колико се дубоко испитује граф који представља проблем. Потреба за специфичним ограничењем за предувид долази од великих проблемских графова у многим апликацијама, као што су рачунарски шах и рачунарски го. Први очигледни избор, претрага у ширину, би брзо потрошила сву расположиву меморију било којег модерног рачунара. Постављањем специфичног предувидног ограничења, време алгоритма се може пажљиво контролисати; његово време расте експоненцијално са растом предувидног ограничења.

Префињеније технике претраге као што је алфа-бета поткресивање могу да елиминишу читава подстабла у стаблу претраге из разматрања. Када се користе ове технике, количина предувида није прецизно одређена, него је било највећа претражена дубина било нека врста просека.

Предувидни симбол у синтаксичкој анализи

Предувид је такође важан концепт у синтаксичним анализаторима у компајлерима који су засновани на максималном броју улазних токена које анализатор може да види и да на основу њих одлучи које правило треба да примени.

Предувид је нарочито значајан код ЛЛ, ЛР, и ЛАЛР синтаксичких анализатора, где је чест случај да се у називу алгоритма у заградама експлицитно нагласи предувид, на пример ЛАЛР(1).

Већина програмских језика, иначе примарних циљева за синтаксичке анализаторе, су пажљиво дефинисани граматикама тако да их могу обрађивати анализатори са ограниченим (најчешће један) предувидом, зато што су такви анализатори често ефикаснији. Важна промена у овом прилазу начињена је 1990. године када је Terence Parr направио АНТЛР (као своју постдипломску тезу), генератор синтаксичких анализатора за ефикасну ЛЛ(к) анализу, где је к фиксирана величина.

Анализатори обично имају на располагању пар акција после гледања сваког токена. Оне су: пребацивање (померање) – додавање токена на стек ради каснијег свођење (скидања), свођење – скидање токена са стека и формирање синтаксичког конструкта, крај, грешка – ниједно познато правило није применљиво или конфликт – непознато да ли треба урадити пребацивање или свођење.

Предувид има две предности.

• Помаже да анализатор изврши одговарајућу акцију у случају конфликта. На пример, да анализира if исказ у случају да се појави else клаузула.
• Уклања многа двострука стања и олакшава терет додатног стека. Анализатор за програмски језик C који не користи предувид би имао око 10,000 стања, а који користи – око 300.

Пример: Анализа израза 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 *

Већина програмских језика (изузев неких као што је APL) и алгебарских формула дају већи приоритет множењу него сабирању. Правилно тумачење наведеног примера је (1 + (2 * 3)). Приметите да је Правило 4 семантичко правило. Могуће је прерадити граматику тако да се приоритет убаци у синтаксу. Међутим, није могуће сва семантичка правила превести у синтаксу.

Једноставне акције не-предувидног анализатора

1. Свођење броја 1 на улазу на израз Е по правилу 3
2. Пребацивање симбола + са улаза на стек да би се могло искористити правило 1.
3. Свођење броја 2 на улазу на израз Е по правилу 3.
4. Скидање ниске Е+ Е са стека и стављање симбола Е по правилу 1.
5. Пребацивање симбола * са улаза на стек у ишчекивању да ће се применити правило 2.
6. Пребацивање броја 3 са улаза на стек у ишчекивању да ће се применити правило 3.
7. Свођење броја 3 на израз Е по правилу 3.
8. Скидање ниске Е*Е са стека и стављање на стек симбола Е на основу правила 2.

Стабло синтаксичке анализе и резултујући код нису коректни по семантичким правилима језика.

Да би се исправила анализа без предувида постоје три начина.

• Корисник мора да стави израз у заграду. Ово често није одговарајуће решење.
• Анализатор мора да садржи додатну логику да уради бектрекинг и покуша поново кад год је правило прекршено или није испуњено. Сличан метод се користи код ЛЛ анализатора.
• Алтернативно, анализатор или граматика морају да поседују додатну логику да одложе свођење и да своде само онда када су потпуно које правило да сведу прво. Овај метод користе ЛР анализатори. На овај начин се правилно ради анализа израза, али са много више стања и са увећаном дубином стека.

Акција анализатора са предувидом

1. Пребацивање броја 1 на стек у очекивању да се искористи правило 3. Не врши се одмах свођење.
2. Свођење елемента стека на једноставан израз по правилу 3. Ово се врши зато што је предувидни симбол +, па је анализа на путу ка реченичној форми Е+, па се мозе извршити свођење стека на Е.
3. Пребацивање улазног симбола + на стек у очекивању да ће се применити правило 1.
4. Пребацивање са улаза на стек броја 2 у очекивању правила 3.
5. Свођење броја 2 на Е због симбола * на улазу по правилу 3. Предувидни карактер * очекује само Е пре њега.
6. Сада је на стеку Е+Е, а на улазу је јос увек *. Сада постоје две могућности - да се изврши пребацивање на основу правила 2 или свођење на основу правила 1. Пошто оператор * има већи приоритет од оператора + на основу правила 4, пребацује се * на стек по правилу 2.
7. Пребацује се број 3 са улаза на стек у ишчекивању да ће се применити правило 3.
8. Врши се свођење броја 3, на стеку, на Е пошто је виђен крај улаза, по правилу 3.
9. Свођење израза Е*Е који је на стеку на Е, по правилу 2.
10. Свођење израза Е+Е који је на стеку на Е, на основу правила 1.

Стабло синтаксичне анализе које је генерисано је исправно и много ефикасније од не-предувидних анализатора. Ову стратегију користи ЛАЛР анализатор.