Encyclopedia

Graph-structured stack

Wikipedia contributorsAdapted for Fathomly · View authors

1 min read
Source updated March 11, 2022

Image credit is listed at the end of this article.

In computer science, a graph-structured stack (GSS) is a directed acyclic graph where each directed path represents a stack. The graph-structured stack is an essential part of Tomita's algorithm, where it replaces the usual stack of a pushdown automaton. This allows the algorithm to encode the nondeterministic choices in parsing an ambiguous grammar, sometimes with greater efficiency.

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.

01Operations

GSSnode* GSS::add(GSSnode* prev, int elem) { int prevlevel = prev->level; assert(levels.size() >= prevlevel + 1); int level = prevlevel + 1; if (levels.size() == level) { levels.resize(level + 1); } GSSnode* node = findElemAtLevel(level, elem); if (node == nullptr) { node = new GSSnode(); node->elem = elem; node->level = level; levels[level].push_back(node); } node->add(prev); return node; } void GSS::remove(GSSnode* node) { if (levels.size() > node->level + 1) if (findPrevAtLevel(node->level + 1, node)) throw Exception("Can remove only from top."); for (int i = 0; i < levels[node->level].size(); i++) if (levels[node->level][i] == node) { levels[node->level].erase(levels[node->level].begin() + i); break; } delete node; }

Watch videos about Graph-structured stackExplainers and documentaries on YouTube (opens in a new tab)

Sources and credits

This article is adapted from the Wikipedia article “Graph-structured stack”, written by its contributors and licensed under CC BY-SA 4.0. Fathomly has changed the layout, removed citation markers, navigation and maintenance notices, and adjusted punctuation. This adapted version is shared under the same license. For references, see the original article.

Images, from Wikimedia Commons:

Graph-structured stack - Borneq.png by Borneq, CC BY-SA 4.0

Fathomly is not affiliated with or endorsed by the Wikimedia Foundation. Spotted a problem? Tell us.