Science Fair Project Encyclopedia
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}.
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.
10-26-2009 08:16:03
The contents of this article is licensed from www.wikipedia.org under the GNU Free Documentation License. Click here to see the transparent copy and copyright details
The contents of this article is licensed from www.wikipedia.org under the GNU Free Documentation License. Click here to see the transparent copy and copyright details