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

v3 · 2026-09-19 · History

Domain-specific #

1957

Domain group

Applied Sciences & Engineering

Origin domain

Computer Science & Software Engineering

Subdomain

Generalized Parsing → Computer Science & Software Engineering

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.

How would you explain it like I'm…

Shared-Bottom Plate Stacks

Imagine stacking blocks, but you're not sure which block goes next, so you try a few at once. Instead of building several whole towers, the towers all share the same bottom blocks and split apart at the top like branches. Each path from a top block down to the bottom is one tower.

Many Stacks, Shared Bottoms

A stack is a pile where you add and remove only at the top. Some computer programs, especially ones that read sentences or code, aren't sure which choice is right, so they try several at once, each needing its own stack. A graph-structured stack keeps all those stacks together by sharing the parts they have in common, with arrows pointing back toward a shared bottom. Each path from a top down to the bottom is one ordinary stack. When you take something off the top, you might find more than one path below, because several stacks branch from there.

Shared-History Parallel Stacks

A graph-structured stack (GSS) stores many active stacks at once in a directed graph that shares their common history. A root anchors the bottom, the frontier nodes are the current tops, and following edges from a top to the root spells out one normal stack. When a computation faces several choices, it adds new branches instead of copying whole stacks; when two histories are equivalent for the future, they can merge. Popping may reveal several predecessors, so there isn't one single top. Masaru Tomita introduced it for generalized parsing, where a parser follows every possible action for ambiguous grammars. Merging has to be done carefully: merge things that aren't truly equivalent and you create stacks that never existed.

 

A graph-structured stack compactly represents a set of simultaneously live stacks as a directed graph with a root, frontier nodes as stack tops, and directed paths from top to root each denoting one stack configuration. Nondeterministic forks add frontier branches rather than copying stacks; equivalent histories under the algorithm's merge key share nodes or suffixes. Pops follow predecessor edges and may expose multiple alternatives. Tomita introduced it for generalized LR parsing, describing splitting, combining and local ambiguity packing, and applied it to several parsing frameworks. In GLR, shifts create or reuse nodes at a new input position, reductions traverse paths of the rule's right-hand-side length and add goto edges, while a separate shared packed parse forest records derivations; the GSS tracks control histories, the forest tracks parse structure. Scott and Johnstone's GLL algorithm reuses the idea for continuations, showing it isn't tied to LR. The core invariant is that every valid path is a live configuration: premature merging invents spurious paths, while under-merging is correct but wasteful.

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.

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.

Abstract Reasoning

1. Define the ordinary stack configuration that each graph path must encode.
2. Choose node and edge labels and orient paths from bottom to top or top to bottom consistently.
3. Identify the computational key under which two live configurations have equivalent futures.
4. On nondeterministic choice, branch frontier representations without copying shared history.
5. On push or shift, create or reuse the correctly keyed successor node and connecting edge.

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.

Relationships to Other Abstractions

Current abstraction Graph-Structured Stack Domain-specific

Parents (1) — outgoing typed relations

• 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 → is a kind of Directed Acyclic Graph → is a kind of Network

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 — Unclustered & Miscellaneous (2769 abstractions)

Nearest neighbors

• Two-Terminal Series–Parallel Graph — 0.80
• Tree-Adjoining Grammar — 0.79
• Nested Set Model — 0.79
• Tree (Set Theory) — 0.78
• Suffix Tree — 0.78

Computed from structural-signature embeddings · 2026-10-25