Анализа навише — разлика између измена
Садржај обрисан Садржај додат
мНема описа измене |
Нема описа измене |
||
Ред 1:
'''Анализа навише''' ({{јез-ен|bottom-up parsing}}) је стратегија која се користи за анализирање односа између података. Прво се идентификују основне јединице, а затим се постепено, навише, изграђује структура која приказује однос између података. Ова стратегија се примењује како у анализи [[природни језици|природних језика]], тако и у анализи програмских језика. У [[рачунарство|рачунарству]], уместо појма анализе навише, користи се и појам ''-{shift – reduce}-'' анализа.
Ред 10:
Различити програмски језици захтевају различите технике анализе, није неуобичајено да се у анализи користе технике које су моћније од захтеваних.
У пракси се често користе анализатори навише ({{Јез-ен|bottom-up parsers}}) опште примене, који могу да анализирају дати језик или могу да генеришу анализатор за [[програмски језик|програмски језик]] који је задат својом [[граматика|граматиком]]. Најпознатији алати који генеришу анализаторе за програмске језике су [[
== Пример илуструје како се гради дрво анализе ==
Ред 19:
A → b<br>
За улазну ниску ax, најлевље [[извођење]] је
S → Ax → ax
Ред 29:
A → a
Анализатор препознаје '''a''', враћа назад у '''S''' и то је крај. [[Дрво извођења]] је следеће:
S
Ред 45:
Прва акција коју ће анализатор у овом случају применити је замена [[терминал|терминала]] '''a''' [[нетерминал|нетерминалом]] '''A'''. Затим се '''Ax''' замењује са '''S'''. Када се добије реченична форма која се састоји само од симбола '''S''', то значи да је анализатор успешно завршио рад.
Као и код [[анализа наниже|анализе наниже]] и овде се можемо послужити грубом силом. Односно, може се независно од предувидног симбола покушавати са свођењем симбола све док не понестане симбола који се могу свести или док не појави [[реченична форма]] која садржи само симбол '''S'''. Овај алгоритам је неефикасан, познат је као [[бектрекинг]]. Дакле, може се закључити да се укључивањем [[предувид]]ног симбола знатно смањује број неуспелих покушаја.
== Типови анализатора навише ==
*[[ЛР анализатор]]
**[[СЛР (1)]] , ({{Јез-ен|Simple LR}}) - Користи један предувидни симбол
**[[ЛАЛР (1)]], ({{Јез-ен|Lookahead}}) – Једноставнија од ЛР (1), погодна је за имплементацију. [[
**[[ЛР (1)]] – општији језик од претходних, сложен је за имплементацију
**[[ЛР (n)]] , n је позитиван цео број - Могу се изградити језици који захтевају n предувидних симбола, уобичајено је да овакви језици захтевају велики број линија кода и простора за податке, па се из тих разлога у пракси ретко користе.
== ''-{Shift-reduce}-'' анализатори ==
Уобичајени анализатори навише су ''-{shift-reduce}-'' анализатори. Њихов рад се заснива на испитивању улазног
== ''-{Action}-'' таблице ==
''-{Action}-'' таблице служе за одређивање наредног корака у раду анализатора. Акције које се налазе у таблици су:
*Пребацивање ({{јез-ен|ѕhift}}) - токен се поставља на стек
*Свођење ({{јез-ен|reduce}}) - ручка се уклања са стека, и замењује одговарајућим нетерминалом
Ред 65:
*Грешка ({{јез-ен|error}}) - до грешке долази уколико ништа од претходног није могуће урадити, односно улазна ниска тада није реченица језика
== ''-{Shift – Reduce}-'' ==
Током рада анализатора врше се акције пребацивања симбола са улаза на стек, као и акције свођења симбола на стеку. Уколико [[префикс]] симбола на врху стека одговара десној страни неког правила [[граматика|граматике]], тада се врши акција свођења, односно десна страна правила граматике са врха стека се смењује одговарајућом левом страном. Поступци пребацивања и свођења симбола се понављају све док анализатор не заврши са радом. Могуће су две ситуације које означавају крај рада анализатора. У првом случају [[ниска]] је успешно прихваћена, а у другом случају анализатор је завршио са радом услед грешке која се појавила на улазу.
Уопштено, анализатор представља [[механизам]] који управља стеком, и који има неколико дискретних стања. У пракси се често на стеку чувају ознаке стања анализатора уместо симбола граматике.
== Пример ''-{shift-reduce}-'' анализе ==
#Почетна [[реченична форма]] је реченица која се анализира
#Док се не појави реченична форма која је састоји само од почетног симбола понављају се следећи кораци
##Улаз се скенира док се не препозна [[ручка]]
##Десна страна правила се замењује одговарајућом левом страном
Анализатор чији се рад заснива на применама корака 2.1 и 2.2 назива се ''-{shift-reduce}-'' анализатор. У пракси су често имплементирани помоћу стека. Дакле, рад ''-{shift-reduce}-'' анализатора се заснива на примени следећих акција:
*На почетку је стек празан
*''-{Shift}-'' акција одговара пребацивању улазних симбола на стек
*''-{Reduce}-'' акција се примењује када се на врху стека налази [[ручка]]. Тада се ручка скида са стека, а на стек се поставља нетерминал који одговара левој стани правила
=== Пример 1 ===
Ред 105:
стек улаз акција
() ()
(весео) (дечак пева)
(Придев) (дечак пева)
(Придев дечак) (пева)
(Придев Именица) (пева)
(Именски_део) (пева)
(Именски_део пева) ()
(Именски_део Глагол) ()
(Реченица) () успех
</pre>
Ред 127:
стек улаз акција
() (2 * [ 1 + 3 ] )
(2) ( * [ 1 + 3 ] )
(Фактор) ( * [ 1 + 3 ] )
(Фактор * ) ( [ 1 + 3 ] )
(Фактор * [ ) ( 1 + 3 ] )
(Фактор * [ 1 ) ( + 3 ] )
(Фактор * [ Терм ) ( + 3 ] )
(Фактор * [ Терм + ) ( 3 ] )
(Фактор * [ Терм + 3 ) ( ] )
(Фактор * [ Терм + Израз) ( ] )
(Фактор * [ Израз ) ( ] )
(Фактор * [ Израз ] ) ( )
(Фактор * Фактор ) ( )
(Фактор * Терм ) ( )
( Терм ) ( )
( Израз ) ( )
( Израз ) ( ) успех
Ред 147:
== Разлике у анализи наниже и анализи навише ==
У анализи наниже доносе се одлуке само о томе које следеће [[правило граматике|правило]] треба применити у извођењу [[ниска|ниске]] налево. Током анализе навише доносе се одлуке о томе да ли симбол треба да се пребаци на стек или је потребно извршити редукцију, у случају редукције доноси се одлука о правилу на основу кога ће се извршити редукција.
[[Категорија:Преводиоци (рачунарство)]]
| |||