Graph-structured stack
Vai alla navigazione
Vai alla ricerca
Questa voce o sezione sull'argomento teoria dei grafi non cita le fonti necessarie o quelle presenti sono insufficienti.
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}.
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.
