Graph-structured stack

Da Wikipedia, l'enciclopedia libera.

In informatica, un grafo-structured stack (stack strutturato a grafo) è un grafo diretto aciclico nel quale ogni cammino è uno stack. Viene usato nel parsing per simulare efficientemente il non determinismo per le grammatiche ambigue.

Nel seguente diagramma sono rappresentati quattro stack: {7,3,1,0}, {7,4,1,0}, {7,5,2,0}, e {8,6,2,0}.

Graph-structured stack 1 - jaredwf.png

Un altro modo di simulare il non determinismo sarebbe quello di duplicare lo stack per ogni ramo non deterministico. La duplicazione però è meno efficiente in quanto i vertici non vengono condivisi. Per questo esempio sarebbero necessario 16 vertici invece di 9.

Stacks jaredwf.png