Graph-structured stack

Graph-structured stack

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.:


Wikimedia Foundation. 2010.

Игры ⚽ Нужна курсовая?

Look at other dictionaries:

  • List of graph theory topics — This is a list of graph theory topics, by Wikipedia page. See glossary of graph theory for basic terminology Contents 1 Examples and types of graphs 2 Graph coloring 3 Paths and cycles 4 …   Wikipedia

  • Semantic Web Stack — The Semantic Web Stack , also known as Semantic Web Cake or Semantic Web Layer Cake , illustrates the architecture of the Semantic Web. Overview The Semantic Web Stack is illustration of the hierarchy of languages, where each layer exploits and… …   Wikipedia

  • Список структур данных — …   Википедия

  • Tomita-Parser — Ein Tomita Parser (nach Masaru Tomita) ist ein Parsverfahren für kontextfreie Grammatiken, das eine Verallgemeinerung des LR(k) Verfahrens ist. Das Verfahren wird deshalb auch GLR(k) Verfahren (für Generalized LR(k)) genannt. Ausgangspunkt des… …   Deutsch Wikipedia

  • Windows Vista networking technologies — This article is part of a series on Windows Vista New features Overview Technical and core system Security and safety Networking technologies I/O technologies Management and administration Removed features …   Wikipedia

  • Superlens — A superlens, super lens or perfect lens is a lens which uses metamaterials to go beyond the diffraction limit. The diffraction limit is an inherent limitation in conventional optical devices or lenses.[1] In 2000, a type of lens was proposed,… …   Wikipedia

  • Subprime mortgage crisis — Part of a series on: Late 2000s financial crisis Major dimensions …   Wikipedia

  • Data model — Overview of data modeling context: A data model provides the details of information to be stored, and is of primary use when the final product is the generation of computer software code for an application or the preparation of a functional… …   Wikipedia

  • List of mathematics articles (S) — NOTOC S S duality S matrix S plane S transform S unit S.O.S. Mathematics SA subgroup Saccheri quadrilateral Sacks spiral Sacred geometry Saddle node bifurcation Saddle point Saddle surface Sadleirian Professor of Pure Mathematics Safe prime Safe… …   Wikipedia

  • Mono (software) — This article is about the computing platform. For other uses, see Mono (disambiguation). Mono Developer(s) Xamarin (formerly by Novell and originally by Ximian) and the Mono community …   Wikipedia

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”