Graph-structured stack

From Free net encyclopedia

In computer science, a graph-structured stack is a directed acyclic graph where each directed path is a stack. They are used in parsing to efficiently simulate nondeterminism for ambiguous grammars.

In the following diagram, there are four stacks: {7,3,1,0}, {7,4,1,0}, {7,5,2,0}, and {8,6,2,0}.

Image:Graphstructuredstack jaredwf.png

Another way to simulate nondeterminism would be to duplicate the stack as needed. The duplication would be less efficient since vertices would not be shared. For this example, 16 vertices would be needed instead of 9.

Image:Stacks jaredwf.png