ЛЛ анализатор

ЛЛ анализатор (ЛЛ парсер) је анализатор наниже (енгл. top-down parsing) за поткласу контексно-слободних граматика (енгл. context-free grammars). Анализира улазну ниску с Лева надесно, и генерише најЛевље извођење дате реченице (отуда и скраћеница ЛЛ, упореди са ЛР анализатором). Граматике које је могуће анализирати на овај начин су познате као ЛЛ граматике.

Остатак овог чланка описује анализатор заснован на таблицама, док алтернативни начин подразумева анализирање техником рекурзивног спуста, која се обично ручно имплементира (мада не увек - погледати АНТЛР за додатна објашњења ЛЛ(*) анализатора, који користи технику рекурзивног спуста).

ЛЛ анализатор је ЛЛ(k) анализатор ако приликом анализе реченице користи k предувидних симбола (токена).

За граматику се каже да је ЛЛ(k) граматика ако за њу постоји такав анализатор, који анализира реченице дате граматике без враћања уназад (back tracking). Међу овим граматикама популарне су ЛЛ(1) граматике, чак иако су јако ограничене, јер одговарајући анализатор користи само један предувидни карактер да би донео одлуку о следећем кораку у извођењу, и потребан је значајан напор да би се извршила њихова анализа.

Постоје извесне несугласице између Европске школе дизајна језика, која преферира ЛЛ граматике, и осталих, које претежно користе ЛР граматике. За ово је највише заслужан утицај Никлауса Вирта (ETH Zürich), чија истраживања су описала разне начине за оптимизацију ЛЛ(1) језика и компилатора.

Општи случај

Анализатор ради над нискама (стринговима) одређене граматике.

Анализатор се састоји од:

улазног бафера, који садржи ниску граматике
потисне листе (стека), која се користи за чување завршних и незавршних симбола (енгл. terminals, non-terminals) граматике који тек треба да буду обрађени
таблице за парсирање (енгл. parsing table), помоћу које се одређује правило граматике које треба да буде примењено, у зависности од симбола на

врху стека и следећег токена

Анализатор примењује правило пронађено у табели, за дати симбол на врху потисне листе (ред), и тренутни симбол на улазу (колона).

Када анализатор почне са радом на стеку се већ налазе 2 симбола: [ S, $] где је '$' специјални завршни симбол који се користи да се назначи дно стека, као и крај улазне ниске, а 'S' је почетни симбол (аксиома) граматике. Анализатор ће покушати да упише на стек оно на шта наиђе на улазу, али ће на стеку задржати само оно што тек треба да се изведе.

Конкретан пример

Да би појаснили како анализатор ради, посматраћемо следећи пример граматике:

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

и анализираћемо следећу ниску:

  (1 + 1)

Таблица за анализу изгледа овако:

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

(Приметити да постоји колона и за специјални терминал, означен са $, који служи да назначи крај улаза.)

Ток анализе

Анализатор чита први карактер улазне ниске - '(', као и 'S' са стека. Из таблице чита да треба да примени правило под редним бројем 2.; скида 'S' са стека и уписује одговарајућу десну страну правила на стек- '(S+F)'; и исписује број овог правила на излазу. Садржај стека је тада:

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

У следећем кораку уклања '(' са улаза, као и са стека, чији садржај постаје:

[ S, +, F,), $]

Сада анализатор чита '1' са улаза и зна да треба да примени правило (1), а затим и правило (3), и исписује те бројеве на излазу. То даје следећа стања стека:

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

У следећа два корака анализатор чита '1' и '+' са улаза, и како се ови карактери поклапају са следећа два карактера на врху стека, уклања их са стека. То даје следећи садржај стека:

[ F,), $]

У следећа три корака, 'F' се на стеку замењује са '1', број 3 се исписује на излазу, а затим се '1' и ')' уклањају са стека, и са улаза. Тако анализатор завршава са '$' како на стеку, тако и на улазу. У том случају пријављује да је прихватио улазну ниску, а на излазу исписује следећи низ бројева:

[ 2, 1, 3, 3]

што је заиста најлевље извођење дате ниске у овој граматици, које изгледа овако:

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

Запажања

Као што се може видети из примера, анализатор извршава 3 врсте акција у зависности од тога да ли се на стеку налази завршни симбол, незавршни симбол, или специјални карактер '$':

Ако се на врху налази незавршни симбол, гледа у табелу како би на основу тог нетерминала, и следећег симбола са улаза одлучио које правило треба да примени како би га заменио на стеку. Број правила исписује на излазу. Ако у табели такво правило није дефинисано, онда пријављује грешку и зауставља рад.
Ако се на врху стека налази завршни симбол, пореди га са симболом на улазу, и ако су једнаки, оба се уклањају. Ако нису једнаки, анализатор пријављује грешку, и зауставља рад.
Ако је на врху стека '$', као и на улазу, онда анализатор пријављује да је ниска успешно прихваћена, у супротном пријављује грешку. У оба случаја зауставља рад.

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

Конструкција таблица за ЛЛ(1) анализу

Како би конструисали табелу, неопходно је да установимо које правило граматике анализатор треба да примени ако види нетерминал A на врху стека, и симбол a на улазу. Лако је приметити да то правило треба да буде у облику A → w, и да ниска која се може извести из w мора да почиње са a. У те сврхе се дефинише скуп Prvi(w) (Fi(w)), који садржи све оне завршне симболе којима може да почне ниска која се изводи из w, као и ε ако се из w може извести празна ниска. За граматику дату правилима A₁ → w₁, ..., А_n → w_n, можемо одредити скупове Prvi(w_i), као и Prvi(А_i) за свако правило, на следећи начин:

Иницијално, скупови Prvi(w_i), као и Prvi(A_i), су празни
додати Prvi(w_i) у Prvi(A_i) за свако правило A_i → w_i, где се скуп Prvi дефинише са:
- Prvi(a w' ) = { a } за сваки терминал a
- Prvi(A w' ) = Prvi(A) за сваки нетерминал A, ако скуп Prvi(A) не садржи ε
- Prvi(A w' ) = Prvi(A) \ { ε } ∪ Prvi(w' ) за сваки нетерминал A, ако скуп Prvi(A) садржи ε
- Prvi(ε) = { ε }
додати Prvi(w_i) у Prvi(Ai) за свако правило A_i → w_i
понављати кораке 2 и 3 све док се скуп Prvi мења.

Нажалост, скупови Prvi нису довољни како би се формирала таблица. Проблем настаје када се десна страна правила-w може свести на празну ниску. Анализатор треба да примени правило A → w ако ε припада скупу Prvi(w) и на улазу се јави симбол који може да следи после A. Због тога је потребно одредити и скупове Sledi(A) (Fo(A)), који садрже све оне завршне симболе a који у извођењу могу да следе након симбола A тј, ако ниска αAaβ може да се изведе из стартног симбола. Скупови Sledi за сваки од нетерминала граматике се конструишу на следећи начин:

Иницијално, Sledi(A_i) је празан скуп
Ако постоји правило облика A_j → wA_iw' онда:
- ако терминал a припада скупу Prvi(w' ), додати a у Sledi(A_i)
- ако ε припада скупу Prvi(w' ), додати Sledi(A_j) у скуп Sledi(A_i)
понављати корак 2 сви док се нешто ново може додати у скуп Sledi.

Сада можемо прецизно одредити како да попунимо таблицу анализе. Ако T[A,a] одговара садржају таблице за нетерминал A и терминал a, онда

T[A,a] садржи правило A → w ако и само ако

a припада скупу Prvi(w) или

ε припада скупу Prvi(w) и a припада скупу Sledi(A).

Ако таблица садржи највише једно правило у сваком од поља, онда ће анализатор увек знати тачно које правило да примени, и моћи ће да анализира ниске без враћања уназад. Управо у тој ситуацији за дату граматику кажемо да је ЛЛ(1) граматика.

Конструкција таблица за ЛЛ(k) анализу

До средине 1990-их година било је широко распрострањено уверење да је ЛЛ(k) анализа (за k>1) непрактична, јер је постојала могућност да величина таблице (у најгорем случају) буде експоненцијалне сложености у односу на k. Ово размишљање је промењено након објављивања књиге „Purdue Compiler Construction Tool Set“ (PCCTS, позната као АНТЛР), око 1992. године, где је показано да многи програмски језици могу ефикасно да се анализирају користећи ЛЛ(k) анализатор, без изазивања најгорег могућег понашања.

Шта више, у неким случајевима ЛЛ анализа је изводљива чак и са неограниченим бројем предувидних карактера. Са друге стране, традиционални генератори анализатора, као yacc/GNU bison конструишу таблице на основу ЛАЛР(1) принципа, са фиксираним једним предувидним карактером.