Парсирање и рекурзивни спуст¶

Рекурзивни спуст¶

Пошто је граматички опис суштински рекурзиван, један природан начин да се приступи решавању проблема је да и програм користи рекурзију. Обрада структурираног текстуалног улаза рекурзивним функцијама се назива рекурзивни спуст (енгл. recursive descent). Дефинишемо рекурзивну функцију чији је задатак да израчуна вредност дела ниске који представља исправан аритметички израз. Он може бити или број или израз у заградама.

• Случај када је израз број је излаз из рекурзије и израчунавање вредности таквог израза је тривијално, јер је вредност израза једнака вредности тог броја тј. цифре.

• У случају израза у заградама читамо прво отворену заграду, затим рекурзивним позивом израчунавамо вредност првог операнда, након тога читамо оператор, затим рекурзивним позивом израчунавамо вредност другог операнда, након тога читамо затворену заграду и израчунавамо вредност познајући оператор и вредност оба операнда.

Ниска која се обрађује не мора да се мења током рекурзивних позива, међутим, рекурзивна функција у сваком рекурзивном позиву обрађује део ниске, који креће од неке позиције. Нека се та позиција чува у променљивој i. Ако, на пример, израз облика (izraz+izraz) почиње на некој позицији i, тада први рекурзивни позив треба да анализира ниску од позиције i+1 (јер се отворена заграда прескаче). Након завршетка првог рекурзивног треба очитати оператор, међутим не знамо на којој се позицији он налази. Кључна идеја је да наша рекурзивна функција добије додатни задатак: задатак рекурзивне функције је да прочита израз који почиње на позицији i, да израчуна његову вредност и да променљиву i промени тако да њена нова вредност указује на позицију ниске непосредно након израза који је прочитан. Променљива i мења своју вредност кроз рекурзивне позиве. Стога ћемо је преносити по референци, тако да представља и улазну и излазну величину функције.

Имајући све ово у виду, једноставно можемо направити имплементацију у језику C#.

Коришћење стека¶

Као што је већ познато, рекурзија се може елиминисати коришћењем стека. На стек можемо стављати све симболе док не наиђемо на затворену заграду. У том тренутку:

• са стека скидамо два операнда, оператор и отворену заграду;

• израчунавамо вредност израза добијеног применом оператора на операнде;

• на стек стављамо резултат.

Размотримо пример израза ((3+4)*(5+6)). Обрађујемо редом један по један карактер. До прве затворене заграде, на стек стављамо један по један симбол и стек тада изгледа овако.

 4     <-  vrh
 +
 3
 (
 (
----
stek

Пошто смо наишли на затворену заграду покрећемо израчунавање и долазимо до следећег стања:

 7     <-  vrh
 (
----
stek

Након тога настављамо читање до наредне затворене заграде. Пре њеног читања, стек овако изгледа:

 6      <-  vrh
 +
 5
 (
 *
 7
 (
----
stek

Наилазимо на прву од две затворене заграде, покрећемо израчунавање и долазимо до следећег стања.

11     <-  vrh
 *
 7
 (
----
stek

На крају долазимо до друге затворене заграде, покрећемо израчунавање и долазимо до стања:

77     <-  vrh
----
stek

Примећујемо да се тражена вредност израза налази на стеку вредности.

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

Имплементацију овог алгоритма у језику C# отежава то што није јасно који тип података се поставља на стек (за разлику од, на пример, језика Python у коме листе могу садржати истовремено податке различитог типа, у језику C# сви елементи колекције морају имати јединствен тип). Зато ћемо уместо једног у програму одржавати два стека: један на који ћемо постављати бројеве (вредности операнада), а на други карактере (ознаке оператора).

• Када наиђемо на цифру постављаћемо је на стек вредности операнада.

• Када наиђемо на оператор, постављаћемо га на стек оператора.

• Када наиђемо на затворену заграду, тада ћемо скидати два операнда са стека вредности операнада, оператор са стека оператора, применићемо оператор на операнде и резултат стављати на стек вредности операнада.

Размотримо пример израза ((3+4)*(5+6)). Обрађујемо редом један по један карактер. Отворене заграде можемо да прескочимо, а када наићемо на карактер 3, стављамо га на стек вредности. Након тога + стек оператора, а затим 4 на стек вредности. У том тренутку стекови изгледају овако:

    4
    3             +
---------     ---------
vrednosti     operatori

Пошто смо наишли на затворену заграду покрећемо израчунавање и долазимо до следећег стања:

    7
---------     ---------
vrednosti     operatori

Након тога на стек оператора постављамо оператор множења *.

    7             *
---------     ---------
vrednosti     operatori

Отворену заграду прескачемо, а затим на стек вредности стављамо 5, на стек оператора +, па на стек вредности 6. У том тренутку стекови изгледају овако.

    6
    5             +
    7             *
---------     ---------
vrednosti     operatori

Наилазимо на прву од две затворене заграде, покрећемо израчунавање и долазимо до следећег стања.

   11
    7             *
---------     ---------
vrednosti     operatori

На крају долазимо до друге затворене заграде, покрећемо израчунавање и долазимо до стања:

   77
---------     ---------
vrednosti     operatori

Примећујемо да се тражена вредност израза налази на стеку вредности.

Имплементација ове технике је дата у следећем C# коду. Користимо библиотечку имплементацију стека (класа Stack са методима Push за постављање елемената на стек и Pop за скидање елемента са стека).

Рекурзивни спуст¶

Кренимо од рекурзивног спуста. Проблем са граматиком

<izraz> ::= <konstanta>
<izraz> ::= <promenjiva>
<izraz> ::= "(" <izraz> ")"
<izraz> ::= <izraz> "+" <izraz>
<izraz> ::= <izraz> "*" <izraz>

је то што се у њој дефинисани оператори + и * никако не разликују по свом приоритету. Размотримо зато шта треба да се промени у дефиницији граматике, да бисмо узели у обзир и приоритет оператора. Пошто је сабирање операција нижег приоритета, на највишем нивоу сваки израз се састоји од једног или више сабирака. На пример:

• 2+3*4 има два сабирка, 2 и 3*4

• (3+4)*2+(5+2)*3+1 има три сабирка, (3+4)*2, (5+2)*3 и 1

• (1+2)*(3+4) има само један сабирак (без обзира што његови подизрази имају више сабирака).

Сваки сабирак се састоји од једног или више чинилаца. Сваки чинилац је или број или израз у заградама. На пример, израз (3+4)*2 има два чиниоца, док 1 и (4*2+5) имају само један чинилац. Тиме се долази до следеће граматике у EBNF (сабирци су именовани називом терм, а чиниоци називом фактор).

<izraz>  ::= <term> {"+" <term>}
<term>   ::= <faktor> {"*" <faktor>}
<faktor> ::= <broj> | "(" <izraz> ")"

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

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

<izraz>  ::= <term> {("+"|"-") <term>}
<term>   ::= <faktor> {("*"|"/") <faktor>}
<faktor> ::= <broj> | "(" <izraz> ")"

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

Вредност израза рачунамо техником рекурзивног спуста. Сваки нетерминал граматике ћемо представити посебном функцијом, која чита део израза који настаје из тог нетерминала и враћа вредност тог дела израза. Функцији се по референци преноси индекс i који означава почетак дела ниске s који се анализира. На крају рада функције овај индекс се премешта иза прочитаног дела ниске. Променљива ok која се такође преноси по референци је индикатор да ли је дошло до грешке дељења нулом током израчунавања вредности израза. Још једно проширење у односу на претходни, упрошћени програм је то што допуштамо да у изразима учествују и вишецифрени бројеви (а не само једноцифрени). Читање и одређивање вредности бројева је ручно имплементирано, а за вежбу вам остављамо да покушате да за ово употребите регуларне изразе.

Приметимо да се у претходном програму користи узајамна рекурзија (функција izraz позива функцију term која позива функцију faktor, а која позива функцију izraz).

Коришћење стека¶

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

Једноставности ради претпоставимо прво да не израчунавамо вредност израза, већ само израз пребацујемо у тзв. постфиксни облик који нам даје веома једноставно упутство како би се вредност израза могла израчунати (уз коришћење помоћног стека). У постфиксном облику, оператор се не пише између, него након операнада. На пример, постфиксни облик израза (3+4)*5 је 34+5*. Захваљујући оваквом редоследу писања, у постфиксном облику израза заграде нису потребне. Погледајмо на примеру истог израза како тече израчунавање вредности на основу постфиксног записа: прво на стек вредности (овде је то једини стек) треба ставити бројеве 3 и 4; затим, наиласком на знак + те две вредности треба скинути са стека и заменити њиховим збиром (бројем 7); затим се на стек ставља и број 5, а наиласком на знак * са стека се скидају вредности 7 и 5 и замењују њиховим производом (бројем 35).

Изрази се обично записују у једном од три наредна облика:

• постфиксни облик (на пример, 34+5*) је, видели смо, облик у ком се оператор исписује након својих операнада

• инфиксни облик (на пример, (3+4)*5) је класичан облик записа израза и у њему се оператор записује између својих операнада

• префиксни облик (на пример, *+345) је облик у коме се оператор записује испред својих операнада. Овај облик је веома погодан за парсирање, јер се структура израза (водећи оператор) може открити већ на самом почетку (у примеру се види да је у питању „производ збира бројева 3 и 4 и броја 5”).

Превођење потпуно заграђених израза у постфиксни облик би било јако једноставно:

• када наиђемо на број преписујемо га на излаз;

• када наиђемо на оператор стављамо га на стек;

• када наиђемо на затворену заграду скидамо оператор са стека и преписујемо га на излаз.

Заиста, потпуно заграђена форма претходног израза је ((3+4)*5). Отворене заграде прескачемо, преписујемо 3 на излаз, стављамо + на стек, преписујемо 4 на излаз и онда, пошто смо наишли на затворену заграду пребацујемо + са стека на излаз. Након тога на стек стављамо *, преписујемо 5 на излаз и при наиласку на другу затворену заграду пребацујемо * са стека на излаз, чиме добијамо постфиксни облик 34+5*. Ако излаз заменимо стеком вредности и пребацивање оператора на излаз заменимо њиховом применом на стеку вредности, добићемо алгоритам који израчунава вредност израза.

Пређимо сада на случај израза који не мора бити потпуно заграђен. Кључна дилема је шта радити у ситуацији када се прочита op2 у изразу облика i1 op1 i2 op2 i3 где су i1, i2 и i3 три израза (било броја било израза у заградама), а op1 и op2 два оператора. У том тренутку на излазу ће се налазити израз i1 преведен у постфиксни облик и иза њега израз i2 преведен у постфиксни облик, док ће се оператор op1 налазити на врху стека оператора. Уколико op1 има виши приоритет од оператора op2 или уколико им је приоритет исти, али је асоцијативност лева (врши се израчунавање слева надесно, што је прилично уобичајено), тада је потребно прво израчунавати израз i1 op1 i2 тиме што се оператор op1 са врха стека пребаци на излаз. У супротном (ако op2 има виши приоритет или ако је приоритет исти, а асоцијативност десна) оператор op1 остаје на стеку и изнад њега се поставља оператор op2.

Наредна анимација приказује примену овог алгоритма на једном примеру.

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

У наставку је приказана имплементација овог алгоритма у језику C#. И стек вредности и стек оператора су представљени библиотечком колекцијом Stack (метода Push ставља елемент на врх стека, Pop скида елемент са врха стека, Peek очитава елемент са врха непразног стека, али га не скида са стека, док својство Count означава тренутни број елемената на стеку и користи се да би се проверило да ли је стек празан).

Ово је један од многих алгоритама које је извео Едсгер Дијкстра и назива се на енглеском језику Shunting yard algortihm, што би се могло слободно превести као алгоритам сортирања железничких вагона. Замислимо да израз треба да пређе са једног на други крај пруге. На прузи се налази споредни колосек (пруга је у облику слова Т и споредни колосек је усправна црта). Делови израза прелазе са десног на леви крај (замислимо да иду по горњој ивици слова Т). Бројеви увек прелазе директно. Оператори се увек задржавају на споредном колосеку, али тако да се пре него што оператор уђе на споредни колосек са њега на излаз пребацују сви оператори који су вишег приоритета у односу на текући или имају исти приоритет као текући а лево су асоцијативни. И отворене заграде се постављају на споредни колосек, а када наиђе затворена заграда, са споредног колосека се уклањају сви оператори до отворене заграде. Када се исцрпи цео израз на десној страни, сви оператори са споредног колосека се пребацују на леву страну. Јасно је да споредни колосек има понашање стека, тако да се у имплементацији користи стек (на њега се стављају оператори).