Анализа навише

Анализа навише (енгл. bottom-up parsing) је стратегија која се користи за анализирање односа између података. Прво се идентификују основне јединице, а затим се постепено, навише, изграђује структура која приказује однос између података. Ова стратегија се примењује како у анализи природних језика, тако и у анализи програмских језика. У рачунарству, уместо појма анализе навише, користи се и појам shift – reduce анализа.

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

У рачунарству, анализа навише се примењује у изградњи компајлера. Овај метод се заснива на идентификацији терминалних симбола који затим учествују у стварању нетерминалних симбола. Резултати анализе се користе у изградњи дрвета анализе програма написаног на изворном језику. Различити програмски језици захтевају различите технике анализе, није неуобичајено да се у анализи користе технике које су моћније од захтеваних.

У пракси се често користе анализатори навише (енгл. bottom-up parsers) опште примене, који могу да анализирају дати језик или могу да генеришу анализатор за програмски језик који је задат својом граматиком. Најпознатији алати који генеришу анализаторе за програмске језике су Yacc и GNU bison.

Овај тривијалан пример илуструје разлике у анализи наниже и навише. Нека је граматика задата са:

S → Ax
A → a
A → b

За улазну ниску ax, најлевље извођење је

S → Ax → ax

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

Рад ЛЛ(1) анализатора почиње од симбола S, поставља се питање које ће се извођење применити из овог симбола. У овом случају не постоји конфликт јер постоји само једно извођење из почетног симбола. Затим се позива метод A (рекурзивна ЛЛ анализа) који треба даље да пореди улаз. У овом случају потребно је разматрати предувидни симбол на основу којег се доноси одлука о правилу које ће се применити у извођењу. Како је предувидни симбол a, тада:

A → a

Анализатор препознаје a, враћа назад у S и то је крај. Дрво извођења је следеће:

  S
 / \
A   x
|
a

У анализи навише се изводе идентични кораци, али у обрнутом редоследу:

ax → Ax → S

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

Прва акција коју ће анализатор у овом случају применити је замена терминала a нетерминалом A. Затим се Ax замењује са S. Када се добије реченична форма која се састоји само од симбола S, то значи да је анализатор успешно завршио рад.

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

• ЛР анализатор
  • СЛР (1), (енгл. Simple LR) - Користи један предувидни симбол
  • ЛАЛР (1), (енгл. Lookahead) – Једноставнија од ЛР (1), погодна је за имплементацију. Yacc имплементира овај језик
  • ЛР (1) – општији језик од претходних, сложен је за имплементацију
  • ЛР (n), n је позитиван цео број - Могу се изградити језици који захтевају n предувидних симбола, уобичајено је да овакви језици захтевају велики број линија кода и простора за податке, па се из тих разлога у пракси ретко користе.

Уобичајени анализатори навише су shift-reduce анализатори. Њихов рад се заснива на испитивању улазног токена, акције које се затим могу предузети су shift, односно пребацивање токена на стек, и reduce, односно свођене десне стране правила на одговарајућу леву.

Action таблице служе за одређивање наредног корака у раду анализатора. Акције које се налазе у таблици су:

• Пребацивање (енгл. shift) - токен се поставља на стек
• Свођење (енгл. reduce) - ручка се уклања са стека, и замењује одговарајућим нетерминалом
• Прихватење (енгл. accept) – реченица је прихваћена, улазна линија је празна а на стеку се налази јединствени симбол
• Грешка (енгл. error) - до грешке долази уколико ништа од претходног није могуће урадити, односно улазна ниска тада није реченица језика

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

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

1. Почетна реченична форма је реченица која се анализира
2. Док се не појави реченична форма која је састоји само од почетног симбола понављају се следећи кораци
   1. Улаз се скенира док се не препозна ручка
   2. Десна страна правила се замењује одговарајућом левом страном

Анализатор чији се рад заснива на применама корака 2.1 и 2.2 назива се shift-reduce анализатор. У пракси су често имплементирани помоћу стека. Дакле, рад shift-reduce анализатора се заснива на примени следећих акција:

• На почетку је стек празан
• Shift акција одговара пребацивању улазних симбола на стек
• Reduce акција се примењује када се на врху стека налази ручка. Тада се ручка скида са стека, а на стек се поставља нетерминал који одговара левој стани правила

 Реченица -> Именски_део Глагол

 Именски_део -> Придев Именица

 Придев -> леп | весео | уморан | …

 Глагол -> скаче | пева | игра | …

 Именица -> пас | човек | дечак | … 


    Нека је улаз следећа реченица: 
    весео дечак пева 


 Следећа табела представља симулацију рада анализатора навише:

стек				улаз			акција
()				()			
(весео)				(дечак пева)		shift
(Придев)			(дечак пева)		reduce
(Придев дечак)			(пева)			shift
(Придев Именица)		(пева)			reduce
(Именски_део)			(пева)			reduce
(Именски_део пева)		()			shift
(Именски_део Глагол)		()			reduce
(Реченица)			()			успех
 

Израз --> Терм | Терм + Израз

Терм --> Фактор | Фактор * Терм

Фактор --> [ Израз] | 0 … 9


стек				улаз			акција
()				(2 * [ 1 + 3] )		
(2)				(* [ 1 + 3] )        shift
(Фактор) 			(* [ 1 + 3] )	          reduce
(Фактор * )			([ 1 + 3] )	      shift
(Фактор  * [ )			(1 + 3] )            shift
(Фактор  * [ 1 )		(+ 3] )              shift
(Фактор  * [ Терм )		(+ 3] )                 reduce
(Фактор  * [ Терм + )		(3] )               shift
(Фактор  * [ Терм + 3 )		(] )                  shift
(Фактор  * [ Терм + Израз)	(] )                      reduce
(Фактор * [ Израз )		(] )                      reduce
(Фактор * [ Израз] )		()                   shift
(Фактор * Фактор )		()                       reduce
(Фактор * Терм )		()                       reduce
(Терм )			        ()                       reduce
(Израз ) 			()                       reduce
(Израз ) 			()                     успех

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