Graph-structured stack
|
|
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}.
- Missing 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.
