Анализа навише — разлика између измена
Садржај обрисан Садржај додат
м ispravke |
м Бот: исправљена преусмерења; козметичке измене |
||
Ред 7:
== Рачунарство ==
У [[Рачунарство|рачунарству]], анализа навише се примењује у изградњи [[
Различити програмски језици захтевају различите технике анализе, није неуобичајено да се у анализи користе технике које су моћније од захтеваних.
У пракси се често користе анализатори навише ({{Јез-ен|bottom-up parsers}}) опште примене, који могу да анализирају дати језик или могу да генеришу анализатор за [[програмски језик]] који је задат својом [[граматика|граматиком]]. Најпознатији алати који генеришу анализаторе за програмске језике су ''-{[[Yacc|YACC]]}-'' и ''-{[[GNU bison]]}-''.
== Пример илуструје како се гради дрво анализе ==
Ред 41:
ax → Ax → S
Интуитивно, [[лЛ анализатор|анализатор наниже]] покушава да прошири нетерминале тако што их замењује њиховим десним странама, док анализатор навише покушава да редукује десне стране тако што их замењује одговарајућим нетерминалом.
Прва акција коју ће анализатор у овом случају применити је замена [[терминал
Као и код [[анализа наниже|анализе наниже]] и овде се можемо послужити грубом силом. Односно, може се независно од предувидног симбола покушавати са свођењем симбола све док не понестане симбола који се могу свести или док не појави [[реченична форма]] која садржи само симбол '''S'''. Овај алгоритам је неефикасан, познат је као [[бектрекинг]]. Дакле, може се закључити да се укључивањем [[предувид]]ног симбола знатно смањује број неуспелих покушаја.
Ред 50:
* [[ЛР анализатор]]
** [[СЛР (1)]], ({{Јез-ен|Simple LR}}) - Користи један предувидни симбол
** [[ЛАЛР (1)]], ({{Јез-ен|Lookahead}}) – Једноставнија од ЛР (1), погодна је за имплементацију. ''-{[[Yacc|YACC]]}-'' имплементира овај језик
** [[ЛР (1)]] – општији језик од претходних, сложен је за имплементацију
** [[ЛР (n)]], n је позитиван цео број - Могу се изградити језици који захтевају n предувидних симбола, уобичајено је да овакви језици захтевају велики број линија кода и простора за податке, па се из тих разлога у пракси ретко користе.
Ред 68:
Током рада анализатора врше се акције пребацивања симбола са улаза на стек, као и акције свођења симбола на стеку. Уколико [[префикс]] симбола на врху стека одговара десној страни неког правила [[граматика|граматике]], тада се врши акција свођења, односно десна страна правила граматике са врха стека се смењује одговарајућом левом страном. Поступци пребацивања и свођења симбола се понављају све док анализатор не заврши са радом. Могуће су две ситуације које означавају крај рада анализатора. У првом случају [[ниска]] је успешно прихваћена, а у другом случају анализатор је завршио са радом услед грешке која се појавила на улазу.
Уопштено, анализатор представља [[механизам (филм из 2000)|механизам]] који управља стеком, и који има неколико дискретних стања. У пракси се често на стеку чувају ознаке стања анализатора уместо симбола граматике.
== Пример ''-{shift-reduce}-'' анализе ==
| |||