Стек с графовой структурой

В информатике стек со структурой графа (GSS) — это ориентированный ациклический граф , где каждый направленный путь представляет собой стек .Стек с графовой структурой — важнейшая часть алгоритма Томиты , где он заменяет обычный стек автомата с выталкиванием вниз . Это позволяет алгоритму кодировать недетерминированный выбор при анализе неоднозначной грамматики , иногда с большей эффективностью.

На следующей диаграмме четыре стопки: {7,3,1,0}, {7,4,1,0}, {7,5,2,0} и {8,6,2,0}. .

Другой способ симулировать недетерминизм — дублировать стек по мере необходимости. Дублирование будет менее эффективным, поскольку вершины не будут общими. Для этого примера потребуется 16 вершин вместо 9.

Операции

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();		node->elem = elem;		node->level = level;				levels[level].push_back(node);	}	node->add(prev);	return node;}

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;}

Ссылки

• Масару Томита. Графоструктурированный стек и синтаксический анализ естественного языка . Ежегодное собрание Ассоциации компьютерной лингвистики, 1988 г. [1]
• Элизабет Скотт, Адриан Джонстон GLL Анализ gll.pdf