Graph-structured stack

In informatica, un grafo-structured stack (stack strutturato a grafo) è un 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}. 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.