Graph-structured stack - Revision history

David Eppstein: better cat

2022-03-11T07:46:57Z

better cat

← Previous revision		Revision as of 07:46, 11 March 2022
Line 56:		Line 56:
	{{DEFAULTSORT:Graph-Structured Stack}}		{{DEFAULTSORT:Graph-Structured Stack}}
	[[Category:Graph data structures]]		[[Category:Graph data structures]]
	[[Category:~~Graph~~ ~~theory~~]]		[[Category:Application-specific graphs]]

	{{Comp-sci-stub}}		{{Comp-sci-stub}}

2022-03-11T02:43:34Z

← Previous revision		Revision as of 02:43, 11 March 2022
Line 56:		Line 56:
	{{DEFAULTSORT:Graph-Structured Stack}}		{{DEFAULTSORT:Graph-Structured Stack}}
	[[Category:Graph data structures]]		[[Category:Graph data structures]]
			[[Category:Graph theory]]

	{{Comp-sci-stub}}		{{Comp-sci-stub}}

2022-01-08T22:50:58Z

← Previous revision		Revision as of 22:50, 8 January 2022
Line 1:		Line 1:
			{{No footnotes\|date=January 2022}}

	In [[computer science]], a '''graph-structured stack''' (GSS) is a [[directed acyclic graph]] where each directed [[Path (graph theory)\|path]] represents a [[Stack (data structure)\|stack]].		In [[computer science]], a '''graph-structured stack''' (GSS) is a [[directed acyclic graph]] where each directed [[Path (graph theory)\|path]] represents a [[Stack (data structure)\|stack]].

2020-07-25T10:28:04Z

change source to syntaxhighlight

← Previous revision		Revision as of 10:28, 25 July 2020
Line 11:		Line 11:
	==Operations==		==Operations==

	<~~source~~ lang="cpp">		<syntaxhighlight lang="cpp">
	GSSnode* GSS::add(GSSnode* prev, int elem)		GSSnode* GSS::add(GSSnode* prev, int elem)
	{		{
Line 32:		Line 32:
	return node;		return node;
	}		}
			</syntaxhighlight>
	</source>

	<~~source~~ lang="cpp">		<syntaxhighlight lang="cpp">
	void GSS::remove(GSSnode* node)		void GSS::remove(GSSnode* node)
	{		{
Line 47:		Line 47:
	delete node;		delete node;
	}		}
			</syntaxhighlight>
	</source>

	== References ==		== References ==

2020-07-23T09:38:11Z

Operations

← Previous revision		Revision as of 09:38, 23 July 2020
Line 15:		Line 15:
	{		{
	int prevlevel = prev->level;		int prevlevel = prev->level;
	assert(levels.size()>= prevlevel+1);		assert(levels.size() >= prevlevel + 1);
	int level = prevlevel + 1;		int level = prevlevel + 1;
	if (levels.size() == level)		if (levels.size() == level)
Line 38:		Line 38:
	{		{
	if (levels.size() > node->level + 1)		if (levels.size() > node->level + 1)
	if (findPrevAtLevel(node->level + 1, node)) throw Exception("~~can~~ remove only from top");		if (findPrevAtLevel(node->level + 1, node)) throw Exception("Can remove only from top.");
	for (int i = 0; i < levels[node->level].size(); i++)		for (int i = 0; i < levels[node->level].size(); i++)
	if (levels[node->level][i] == node)		if (levels[node->level][i] == node)

2019-03-15T16:29:07Z

Added GSS as an abreviation for graph-structured stack

← Previous revision		Revision as of 16:29, 15 March 2019
Line 1:		Line 1:

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

2019-02-01T18:59:28Z

s/root/node in GSS::add method

2017-05-23T23:29:32Z

← Previous revision		Revision as of 23:29, 23 May 2017
Line 51:		Line 51:
	== References ==		== References ==
	*Masaru Tomita. ''Graph-Structured Stack And Natural Language Parsing''. Annual Meeting of the Association of Computational Linguistics, 1988. [http://www.aclweb.org/anthology/P88-1031]		*Masaru Tomita. ''Graph-Structured Stack And Natural Language Parsing''. Annual Meeting of the Association of Computational Linguistics, 1988. [http://www.aclweb.org/anthology/P88-1031]
	*Elizabeth Scott, Adrian Johnstone ''GLL Parsing'' [http://dotat.at/tmp/gll.pdf\|gll.pdf]		*Elizabeth Scott, Adrian Johnstone ''GLL Parsing'' [http://dotat.at/tmp/gll.pdf gll.pdf]

	{{DEFAULTSORT:Graph-Structured Stack}}		{{DEFAULTSORT:Graph-Structured Stack}}

2017-03-13T09:07:51Z

WP:CHECKWIKI error fix. Section heading problem. Violates WP:MOSHEAD.

← Previous revision		Revision as of 09:07, 13 March 2017
Line 9:		Line 9:
	:[[Image:Stacks_-_Borneq.dot.png\|Stacks_-_Borneq.dot.png\|350px]]		:[[Image:Stacks_-_Borneq.dot.png\|Stacks_-_Borneq.dot.png\|350px]]

	===Operations===		==Operations==

	<source lang="cpp">		<source lang="cpp">
	GSSnode* GSS::add(GSSnode* prev, int elem)		GSSnode* GSS::add(GSSnode* prev, int elem)

2017-03-12T21:44:22Z

c++ code for add and remove nodes

← Previous revision		Revision as of 21:44, 12 March 2017
Line 9:		Line 9:
	:[[Image:Stacks_-_Borneq.dot.png\|Stacks_-_Borneq.dot.png\|350px]]		:[[Image:Stacks_-_Borneq.dot.png\|Stacks_-_Borneq.dot.png\|350px]]

			===Operations===
			<source lang="cpp">
			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();
			root->elem = elem;
			root->level = level;
			levels[level].push_back(root);
			}
			node->add(prev);
			return node;
			}
			</source>

			<source lang="cpp">
			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;
			}
			</source>

	== References ==		== References ==