Graph-Structured Stack¶

Represent many simultaneously live stack histories as a shared directed acyclic graph whose paths encode stacks, whose frontier nodes are tops, and whose split, merge, and pop operations avoid duplicating common history during nondeterministic parsing.

Version: v2 · 2026-09-06 · History
Domain-specific #: 1957
Origin domain: computer science
Subdomain: generalized parsing
Aliases: GSS, Graph structured stack

Core Idea¶

A graph-structured stack (GSS) compactly represents a set of simultaneously active stacks by sharing their common history in a directed graph. A designated root or bottom anchors the structure, frontier nodes represent current stack tops, and a directed path from a top toward the root spells one ordinary stack. When nondeterministic computation forks, the graph adds multiple frontier branches instead of copying an entire stack. When histories become equivalent under the algorithm's merge key, nodes or suffixes can be shared. A pop follows predecessor edges and may reveal several predecessor alternatives, so the structure supports multiple LIFO histories without pretending there is one globally accessible top.

Masaru Tomita introduced the device for generalized parsing and then described it as a general mechanism for nondeterministic stack operations. His 1988 ACL paper explicitly identifies splitting, combining, and local ambiguity packing, applies the structure to LR, ATN, categorial, and principle-based parsing, and relates it to chart parsing.^[1] This source fixes the abstraction above any one software representation. The load-bearing invariant is not merely a DAG with labels; it is each valid path denotes a stack configuration, and graph operations preserve exactly the live configurations intended by the parser.

The GSS is most familiar in generalized LR parsing. When an LR table has several permitted actions, the parser pursues them without making full private stack copies. Shift operations create or reuse nodes at a new input position; reductions traverse paths corresponding to the rule's right-hand-side length, create goto states, and add edges that represent resulting histories. Equivalent state/input-position nodes can be merged under the algorithm's rules. A separate shared packed parse forest normally records derivation results. Keeping these structures separate matters: the GSS represents control histories or continuations, while the forest represents parse structure and ambiguity.

Generalized LL parsing reuses the central idea with different node meanings. Scott and Johnstone's GLL algorithm handles arbitrary context-free grammars and uses descriptors plus a graph-structured representation of continuations; later work refines GSS implementations for practical performance.^[2] This transfer demonstrates autonomy beyond Tomita's original LR algorithm. The common structure is multiple continuations, shared stack suffixes, explicit pop bookkeeping, and deduplication of already scheduled work. The exact labels and operations vary with the parsing discipline.

Sharing is semantic only under a correct equivalence relation. Two nodes can merge because the future computation cannot distinguish the histories relevant to that node, not simply because their displayed labels match. Algorithms may key nodes by parser state, grammar slot, return label, input position, or other context. Premature merging can invent paths that were never live, while insufficient merging preserves correctness but wastes time and memory. Cycles are generally excluded in the finite computation representation or managed through deduplicated descriptors so that path-as-stack meaning and termination arguments remain intelligible.

The candidate survives collision review against Stack, Directed Acyclic Graph, Graph Data Type, Parsing, chart parsing, and parse forests. Stack supplies LIFO path semantics but not shared alternatives; DAG supplies the representation shape but not push/pop or configuration meaning; Parsing supplies the task but not the data structure. Their conjunction still needs the GSS-specific invariants, merge keys, frontier management, and reduction traversal. It is therefore a distinct domain-specific abstraction rather than a composite label for graph + stack.

Structural Signature¶

The root or bottom. A distinguished node anchors the shared stack history.
The labeled nodes or edges. Parser states, grammar symbols, return labels, or continuations encode stack content under a declared convention.
The directed acyclic structure. Edge orientation orders stack history and prevents a path from containing an unbounded cyclic ancestry.
The path-as-stack invariant. Every live root-to-frontier or frontier-to-root path, by convention, denotes one ordinary LIFO stack.
The frontier. One or more current top nodes identify active computational configurations.
The split operation. A nondeterministic choice branches the frontier while retaining shared history.
The merge criterion. Equivalent configurations reuse a node or continuation instead of duplicating future work.
The push or shift update. A new element extends one or more live stack paths at the current input position.
The pop or reduction traversal. Predecessor paths of a required depth enumerate valid exposed histories.
The work-deduplication layer. Descriptors, memo sets, or local packing prevent identical computation from being repeated.

What It Is Not¶

Not one ordinary stack. A GSS can have multiple tops and represents a set of stacks.
Not an arbitrary directed acyclic graph. Paths and operations must carry stack semantics.
Not a parse forest. The GSS stores control histories; a packed forest stores derivation structure.
Not a graph database stack. The name does not mean software layers used by a graph system.
Not unrestricted backtracking. Sharing and deduplication are the defining alternative to full stack copying.
Not guaranteed linear performance. Ambiguity and grammar structure can still cause polynomial or large workloads.
Not one immutable layout. GLR and GLL variants use different labels, orientations, and pop bookkeeping while preserving the shared-stack idea.

Scope of Application¶

A GSS is literal when multiple live pushdown or continuation histories are represented as paths in a shared graph and algorithmic operations preserve their stack meaning.

Generalized LR parsing. Sharing LR stack histories across shift/reduce conflicts and ambiguity.
Generalized LL parsing. Sharing call/return continuations while handling left recursion and nondeterminism.
Natural-language parsing. Avoiding full duplication across competing syntactic analyses.
Programming-language parsing. Supporting grammars or extensions that exceed a deterministic parser's conflict policy.
Augmented transition networks. Sharing nondeterministic return-stack histories.
Categorial and principle-based parsing. Reusing the device where algorithms employ stack-like continuations.
Parsing research. Comparing graph sharing with chart items, memoization, and packed forests.
Implementation analysis. Measuring node, edge, descriptor, reduction-path, and ambiguity growth separately.

Clarity¶

A clear GSS description states edge orientation, root, node and edge labels, frontier definition, path-to-stack reading order, merge key, input-position role, push/shift operation, pop/reduction traversal, epsilon handling, descriptor or agenda policy, and relationship to the parse forest. It distinguishes a graph node from a complete parser configuration. Complexity claims name grammar restrictions, input length, ambiguity, and whether recognition or forest construction is counted. Diagrams should enumerate which paths correspond to which stacks and must not imply nonexistent cross-combinations after merging. Implementation claims specify whether identical nodes, edges, reductions, and descriptors are deduplicated. Correctness requires both soundness—every path is a live history—and completeness—every live history is represented.

Manages Complexity¶

A naïve nondeterministic parser copies a stack whenever it forks. Common prefixes or suffixes are then stored and processed repeatedly, and later convergence is invisible. A GSS turns repeated history into shared graph structure and makes convergence explicit. The saving can be dramatic for locally ambiguous inputs, because an unchanged lower stack region exists once while many tops point into it. Complexity does not disappear: reductions may traverse many paths, ambiguous grammars may create many frontier nodes and forest alternatives, and an overly coarse merge key corrupts semantics. Good implementations separately deduplicate nodes, edges, pop results, and scheduled descriptors, and they measure graph growth rather than citing sharing as an unconditional efficiency proof.

Abstract Reasoning¶

Define the ordinary stack configuration that each graph path must encode.
Choose node and edge labels and orient paths from bottom to top or top to bottom consistently.
Identify the computational key under which two live configurations have equivalent futures.
On nondeterministic choice, branch frontier representations without copying shared history.
On push or shift, create or reuse the correctly keyed successor node and connecting edge.
On pop or reduction, traverse exactly the predecessor paths of the required depth.
Create resulting continuations or goto states for every valid exposed history.
Deduplicate graph edges, pop results, and scheduled work while preserving distinct semantics.
Record derivation output in a separate packed forest when parsing rather than recognition is required.
Check path soundness, configuration completeness, termination, and graph-size behavior on ambiguous cases.

Knowledge Transfer¶

The GSS transfers a general representation technique: when many evolving histories obey the same nested discipline, share equal history segments and represent alternatives as a graph rather than copying sequences. The transfer applies only when path semantics and equivalence are explicit. Persistent data structures, symbolic execution, and workflow histories use related sharing, but they are not automatically GSSs because their operations may not be LIFO or their merges may mean something else. The strongest transferable lesson is that compression depends on semantic equivalence, not visual equality.

Examples¶

Canonical¶

An LR parser reaches a table conflict after reading the same input prefix. One branch shifts; another reduces by a grammar rule. A naïve implementation copies the entire LR state stack. A GSS retains the common lower path and creates two frontier alternatives. If later operations produce the same parser state at the same input position under the algorithm's merge rule, the frontier nodes combine. A reduction of length three follows all predecessor paths of length three, computes the appropriate goto for each exposed state, and adds the resulting edges. Tomita calls out splitting, combining, and local ambiguity packing as the central notions.^[1]

Mapped back: one LR history → conflict-induced split → shared graph of state-stack paths → pathwise reductions and shifts → merge of equivalent frontiers.

Applied / In Practice¶

A GLL parser encounters left recursion and multiple grammar alternatives. Instead of using the host-language call stack for every alternative, it stores return points and caller relations in a GSS. Descriptors combine a grammar position, input position, forest node, and GSS node; a work set ensures an identical descriptor is not executed repeatedly. A pop records a result for a GSS node and schedules continuations that are already waiting there. The GSS shares continuations, while the separate forest shares parse results. Scott and Johnstone's formulation shows that the device is not confined to bottom-up LR control.^[2]

Mapped back: recursive-descent continuations + nondeterministic descriptors → shared continuation graph → memoized pop propagation → separate packed derivation forest.

Structural Tensions¶

Sharing vs. false merging. Coarser keys save more but can invent histories. Diagnostic: Is future behavior identical for every merged configuration?
Compact storage vs. path enumeration. Few nodes can encode many stacks. Diagnostic: Do reductions still traverse exponentially many relevant paths?
Control graph vs. result graph. Both may be directed and shared. Diagnostic: Is each node a continuation/state or a parse-forest symbol?
General grammar coverage vs. practical performance. Polynomial bounds can still be costly. Diagnostic: How do nodes, edges, descriptors, and packed alternatives scale separately?
Local ambiguity packing vs. semantic distinctions. Equivalent control can carry distinct derivations. Diagnostic: Are derivations preserved outside the GSS when required?
Acyclic representation vs. recursive grammar. The grammar can recurse while the finite run graph remains controlled. Diagnostic: Which input-position or memo invariant prevents unbounded graph cycles?
Abstract device vs. variant layout. GLR and GLL label nodes differently. Diagnostic: Does each path still encode a valid stack or continuation history?

Structural–Framed Character¶

The structure is a rooted directed acyclic sharing graph, path-as-stack semantics, multiple tops, split and merge rules, LIFO path traversal, and work deduplication. The frame is the parsing strategy, grammar formalism, node labels, input-position convention, edge orientation, and parse-forest integration. This separation permits Tomita's device to move from GLR to other stack-using parsers without claiming that every implementation has identical nodes or operations.

Structural Core vs. Domain Accent¶

The transferable core is many related LIFO histories → share common segments in a DAG → operate on paths while deduplicating equivalent frontiers. The parsing accent is LR states, grammar slots, shifts, reductions, goto actions, input positions, descriptors, and packed forests. Remove the accent and the technique approaches persistent sequence sharing; retain it and Graph-Structured Stack remains a distinct generalized-parsing abstraction.

Directed Acyclic Graph is the strict parent by specialization. A GSS is literally a DAG whose edge orientation imposes a one-way ancestry order. It adds path-as-stack meaning, frontier tops, split/merge operations, and parsing equivalence. Stack is an equally important semantic neighbor, but one GSS represents multiple stacks and therefore does not satisfy the prime Stack's single-top condition as a whole.

The prospective workspace queue contains one strict upward edge to prime:directed_acyclic_graph. No live DAG mutation is authorized.

Relationships to Other Abstractions¶

Current abstraction Graph-Structured Stack Domain-specific

Parents (1) — more general patterns this builds on

Graph-Structured Stack is a kind of Directed Acyclic Graph Prime

Directed Acyclic Graph is the strict parent by specialization.

Hierarchy path (1) — routes to 1 parentless root

Graph-Structured Stack → Directed Acyclic Graph → Network → Reservoir-Flux Network → Conservation Laws → Invariance

Neighborhood in Abstraction Space¶

Graph-Structured Stack sits in a sparse region of the domain-specific corpus (91^st percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.

Family — Discrete Structures & Graph Algorithms (17 abstractions)

Nearest neighbors

Tree (Set Theory) — 0.78
Tree (Data Structure) — 0.78
Trie — 0.78
Merge Conflict — 0.78
Collider (Causal Graph) — 0.77

Computed from structural-signature embeddings · 2026-09-08

Not to Be Confused With¶

Ordinary Stack. One LIFO sequence with one accessible top.
Shared Packed Parse Forest. Compact representation of parse trees and ambiguity rather than control stacks.
Chart. Set or table of partial parsing results indexed by spans and states.
Parse DAG. Any acyclic graph of parse relations without GSS stack-path semantics.
Persistent Stack. Versioned immutable stacks that share tails but may lack merge and parser-frontier operations.
Graph Data Type. General node-edge programming abstraction without LIFO invariants.
Generalized LR Parser. Full parsing algorithm in which the GSS is one central component.

References¶

[1] Masaru Tomita, Graph-Structured Stack and Natural Language Parsing, in Proceedings of the 26^th Annual Meeting of the Association for Computational Linguistics (1988), 249–257, https://doi.org/10.3115/982023.982054. registry ↩a ↩b

[2] Elizabeth Scott and Adrian Johnstone, GLL Parsing, Electronic Notes in Theoretical Computer Science 253, no. 7 (2010): 177–189, https://doi.org/10.1016/j.entcs.2010.08.041. registry ↩a ↩b