Graficky strukturovaný zásobník - Graph-structured stack

v počítačová věda, a grafově strukturovaný zásobník (GSS) je a směrovaný acyklický graf kam každý směřoval cesta představuje a zásobník Graficky strukturovaný zásobník je podstatnou součástí Tomitův algoritmus, kde nahrazuje obvyklé zásobník a zasunovací automat. To umožňuje algoritmu kódovat nedeterministické možnosti při analýze nejednoznačná gramatika, někdy s vyšší účinností.

V následujícím diagramu jsou čtyři řady: {7,3,1,0}, {7,4,1,0}, {7,5,2,0} a {8,6,2,0} .

Graph-structured_stack _-_ Borneq.png

Dalším způsobem, jak simulovat nedeterminismus, by bylo duplikování zásobníku podle potřeby. Duplikace by byla méně efektivní, protože vrcholy by nebyly sdíleny. V tomto příkladu by bylo zapotřebí 16 vrcholů místo 9.

Hromádky _-_ Borneq.dot.png

Operace

GSSnode* GSS::přidat(GSSnode* předchozí, int elem){	int předchozí úroveň = předchozí->úroveň;	tvrdit(úrovně.velikost() >= předchozí úroveň + 1);	int úroveň = předchozí úroveň + 1;	-li (úrovně.velikost() == úroveň)	{		úrovně.změnit velikost(úroveň + 1);	}	GSSnode* uzel = findElemAtLevel(úroveň, elem);	-li (uzel == nullptr)	{		uzel = Nový GSSnode();		uzel->elem = elem;		uzel->úroveň = úroveň;				úrovně[úroveň].zatlačit zpátky(uzel);	}	uzel->přidat(předchozí);	vrátit se uzel;}
prázdnota GSS::odstranit(GSSnode* uzel){	-li (úrovně.velikost() > uzel->úroveň + 1)		-li (findPrevAtLevel(uzel->úroveň + 1, uzel)) házet Výjimka("Lze odstranit pouze shora.");	pro (int i = 0; i < úrovně[uzel->úroveň].velikost(); i++)		-li (úrovně[uzel->úroveň][i] == uzel)		{			úrovně[uzel->úroveň].vymazat(úrovně[uzel->úroveň].začít() + i);			přestávka;		}	vymazat uzel;}

Reference

  • Masaru Tomita. Graficky strukturovaný zásobník a analýza přirozeného jazyka. Výroční zasedání Asociace počítačové lingvistiky, 1988. [1]
  • Elizabeth Scott, Adrian Johnstone Analýza GLL gll.pdf