Граф-структурирани стек

С Википедије, слободне енциклопедије

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

На следећем дијаграму постоје четири стека: {7,3,1,0}, {7,4,1,0}, {7,5,2,0}, и {8,6,2,0}.

Graph-structured stack 1 - jaredwf.png

Други начин да се симулира недетерминизам би било да се дуплира стек по потреби. Дуплирање ће бити мање ефикасно, јер путеви до темена неће бити дељени. У овом примеру биће потребно 16 темена уместо 9.

Stacks jaredwf.png