Stos o strukturze grafowej
Stos o strukturze grafowej jest skierowanym grafem acyklicznym, gdzie każda skierowana ścieżka reprezentuje stos. Struktura ta jest ważną częścią algorytmu Tomity (GLR)[1] gdzie zastępuje zwykły stos automatu ze stosem jak również GLL Johnstone'a[2]. To pozwala algorytmowi wybierać z powrotami z większą wydajnością.
W następującym diagramie są cztery stosy: {7,3,1,0}, {7,4,1,0}, {7,5,2,0}, and {8,6,2,0}.
Innym sposobem symulacji niedeterminizmu była by duplikacja stosu. Jest ona mniej wydajna ponieważ wierzchołki nie są dzielone. W tym przykładzie jest 16 wierzchołków zamiast 9.
Aby zwiększyć wydajność takich operacji jak dodawanie do grafu, powinna istnieć tablica poziomów takiego jak maksymalny rozmiar stosu gdzie w każdym poziomie byłaby tablica węzłów. Dodatkowo przydaje się węzeł "root" oznaczający pusty stos.
Operacje
edytujDodawanie do węzła
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;
}
Często występuje tylko operacja dodawania bez usuwania węzłów z GSS. Gdyby była potrzebna, to wykonuje się:
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;
}
Przypisy
edytuj- ↑ Masaru Tomita , Graph-Structured Stack And Natural Language Parsing [online] .
- ↑ Elizabeth Scott , Adrian Johnstone , GLL Parsing [online] .