In
computer science
Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical discipli ...
, a graph-structured stack (GSS) is a
directed acyclic graph
In mathematics, particularly graph theory, and computer science, a directed acyclic graph (DAG) is a directed graph with no directed cycles. That is, it consists of vertices and edges (also called ''arcs''), with each edge directed from one ve ...
where each directed
path
A path is a route for physical travel – see Trail.
Path or PATH may also refer to:
Physical paths of different types
* Bicycle path
* Bridle path, used by people on horseback
* Course (navigation), the intended path of a vehicle
* Desire p ...
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
In the theory of computation, a branch of theoretical computer science, a pushdown automaton (PDA) is
a type of automaton that employs a stack.
Pushdown automata are used in theories about what can be computed by machines. They are more capab ...
. This allows the algorithm to encode the nondeterministic choices in parsing an
ambiguous grammar
In computer science, an ambiguous grammar is a context-free grammar for which there exists a string that can have more than one leftmost derivation or parse tree, while an unambiguous grammar is a context-free grammar for which every valid string ...
, sometimes with greater efficiency.
In the following diagram, there are four stacks: , , , and .
:
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.
:
Operations
GSSnode* GSS::add(GSSnode* prev, int elem)
void GSS::remove(GSSnode* node)
References
*Masaru Tomita. ''Graph-Structured Stack And Natural Language Parsing''. Annual Meeting of the Association of Computational Linguistics, 1988
*Elizabeth Scott, Adrian Johnstone ''GLL Parsing'
gll.pdf
Graph data structures
Application-specific graphs
{{Comp-sci-stub