Graph-structured stack
From Free net encyclopedia
(Difference between revisions)
| Revision as of 20:14, 26 March 2006 TimBentley (Talk | contribs) Corrected link to disambiguation page. (you can help!) ← Previous diff |
Current revision TimBentley (Talk | contribs) Corrected link to disambiguation page. (you can help!) |
Current revision
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.
