Анализа наниже

Анализа наниже је стратегија анализирања односа непознатих података, постављањем хипотезе о структури дрвета синтаксичке анализе (стабло парсирања), а затим разматрајући да ли су познате фундаменталне структуре подударне са хипотезом. Користи се приликом анализирања како природних, тако и програмских језика.

Анализа наниже представља покушај да се генерише најлевље извођење улазне струје токена, проналажењем одговарајућег дрвета синтаксичке анализе, користећи дата правила граматике. Испитивање улазне ниске се врши слева надесно.

У покушају да се уклони двосмисленост (енгл. ambiguity), полазећи од почетног симбола, испитују се сва могућа извођења, док се не утврди да ли анализирана реч припада језику или не.

Анализа наниже почиње, дакле, од аксиоме граматике, а током анализе се поступно генерише извођење налево ниске која се пореди слева надесно са улазним низом токена.

Једноставне имплементације извођења наниже се не могу применити налево-рекурзивне граматике, и анализа наниже са враћањем уназад (back-tracking) може да има експоненцијалну сложеност, у односу на дужину улазне ниске вишезначне контексно-слободне граматике. Ипак, софистицираније методе анализе наниже, чији су творци Фрост, Хариз, и Калахан, омогућавају испитивање вишезначних и лево-рекурзивних граматика са полиномијалном сложености, и генеришу репрезентације полиномијалне дужине, за потенцијално експоненцијални број дрвета синтаксичке анализе.

Примена у програмским језицима

Компајлер анализира улаз програмског језика поредећи симболе са правилима граматике која су најчешће задата у Бекус-Науровој форми.

ЛЛ-анализатор, или анализатор наниже, почиње од почетног симбола дате граматике, и примењује правила граматике, тако што се најлевљи нетерминал замењује одговарајућом десном страном правила, која одговара датом нетерминалу. Затим се примењује следеће правило граматике, које одговара следећем нетерминалу на који се наишло у извођењу.

На тај начин анализа се одвија налево у резултујућој (десној) страни правила, израчунавајући вредности нетерминала слева надесно, и тиме напредујући наниже дуж дрвета синтаксичке анализе, за сваки нови нетерминал на који се наиђе, пре него што се пређе на следећи симбол који се јавља у правилу.

На пример:

• A→aBC
• cd
• eg

Прво би се извело A→aBC и покушало са извођењем cd. Затим би се покушало са применом правила eg. Код једнозначних језика свако извођење нетерминала даје јединствене ниске: ниска изведена на основу једног правила неће почињати истим симболом као ниска изведена на основу неког другог правила. Језици који нису вишезначни се могу представити ЛЛ(1) граматиком, где (1) означава да анализатор користи 1 предувидни карактер у сваком тренутку. За вишезначне језике, да би могли да се анализирају ЛЛ-анализатором, морају се користити више од 1 предувидног симбола, на пример ЛЛ(3).

Уобичајено решење је да се у тим случајевима користи ЛР анализатор (ЛР парсер) познат још као анализатор навише, или анализатор пребацивањем и свођењем.

Лева рекурзија у анализи наниже

Формалне граматике које садрже леву рекурзију се не могу анализирати техником рекурзивног спуста, осим ако се не сведу на еквивалентне десно-рекурзивне граматике.

Ипак, скорија истраживања су показала да је могуће анализирати лево-рекурзивне граматике (као и остале класе контексно слободних граматика) коришћењем софистицираниранијих метода анализе наниже, заснованих на скраћивању. Фрост и Хафиз су 2006. године описали алгоритам који омогућава анализирање вишезначних граматика и скраћује извођење засновано на левој рекурзији, наметањем посебних правила о дужини извођења. Фрост, Хафиз и Калахан су 2007. године усавршили овај алгоритам, чиме је омогућена анализа лево-рекурзивних граматика (како са директном, тако и са индиректном рекурзијом) у полиномијалном времену. Такође је омогућено генерисање компактне репрезентације полиномијалне дужине потенцијално експоненцијалног броја дрвета синтаксичке анализе код јако вишезначних граматика.

Од тада је алгоритам имплеметниран као комбинација више анализатора, написаних на програмском језику Хаскел.

Детаљи о имплементацији ових нових метода су представљени у ПАДЛ'08, чији су аутори горе поменути. На сајту X-SAIGA се може наћи више детаља везаних за имплементацију и алгоритме.

Временска и просторна сложеност анализе наниже

Када анализатор наниже покуша са анализом ниске вишезначне контексно слободне граматике, постоји могућност да му је потребан експоненцијалан број корака (у односу на дужину улазне ниске) да испита сва могућа извођења у датој граматици, и генерише све потенцијалне облике дрвета синтаксичке анализе, да би утврдио да ли дата ниска припада језику описаном датом граматиком. То може да проузрокује и захтевање превелике количине меморијског простора, што се такође експоненцијално увећава при сваком кораку. Норвинг је 1991. године решио проблем експоненцијалне временске сложености у анализи наниже, настао због скупа узајамно рекурзивних функција. Техника коју је он користио је слична коришћењу динамичког програмирања и скупа стања у Ерлијевом алгоритму, као и табела коришћених у CYK алгоритму (од Coocke-Younger-Kasami).

Кључ идеје састоји се у чувању резултата примене анализатора p на позицији j у табели, а затим поновном коришћењу тих резултата кад год се наиђе на исту ситуацију. Фрост, Хафиз и Калахан такође користе чување података, како би избегли сувишно израчунавање, што омогућава анализу било које контексно-слободне граматике у полиномијалном времену (Θ(n⁴) код лево рекурзивних граматика, односно сложености Θ(n³) за граматике које нису лево-рекурзивне). Њихов алгоритам анализе наниже такође захтева количину меморије у полиномијалном односу, за потенцијално експоненцијално велика вишезначна дрвета синтаксичке анализе, захваљујући 'компактној репрезентацији' и 'локалном груписању вишезначности'. Компактна репрезентација коју користе поменути аутори се може упоредити са компактном репрезентацијом коју користи Томита у анализи навише.