Графически-структурированный стек
 | Эта статья включает список ссылок , связанных материалов или внешних ссылок , но ее источники остаются неясными, поскольку в ней отсутствуют встроенные цитаты . ( Январь 2022 г. ) |
В информатике графоструктурированный стек (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 ( "Можно удалить только сверху." ); 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
 | Эта статья по информатике — заглушка . Вы можете помочь Википедии, расширив ее. |
