Как реализовать стек с графической структурой?

Во-первых, если вы еще этого не сделали, вам следует прочитать статью МакПика о GLR http://www.cs.berkeley.edu/~smcpeak/papers/elkhound_cc04.ps. Это академический документ, но он дает хорошие подробности о GSS, GLR и методах, используемых для их реализации. Это также объясняет некоторые сложные проблемы с реализацией парсера GLR.

У вас есть три части для реализации стека с графической структурой.

I. Сама структура данных графика

II. Стеки

III. Использование GLR GSS

Вы правы, гугл не особо помогает. И если вы не любите читать книги по алгоритмам, они тоже не помогут.

I. Структура данных графика

Ответ Роба о «прямом представлении» было бы проще всего реализовать. Это очень похоже на связанный список, за исключением того, что каждый узел имеет список следующих узлов, а не только один.

Эта структура данных представляет собой ориентированный граф, но, как утверждает МакПик, в GSS могут быть циклы для эпсилон-грамматик.

II. Стеки

Стек с графической структурой концептуально представляет собой просто список обычных стеков. Для однозначной грамматики вам понадобится всего одна стопка. Когда возникает конфликт синтаксического анализа, вам нужно больше стеков, чтобы вы могли выполнять оба действия синтаксического анализа одновременно и поддерживать различное состояние, создаваемое обоими действиями. Использование графа позволяет вам воспользоваться тем фактом, что эти стеки разделяют элементы.

Это может помочь понять, как сначала реализовать единый стек со связанным списком. Заголовок связанного списка - это вершина стека. Помещение элемента в стек - это просто создание новой головы и указание ее на старую. Выталкивание элемента из стека просто перемещает указатель на head-> next.

В GSS принцип такой же. Выталкивание элемента просто создает новый головной узел и указывает его на старую головку. Если у вас есть две операции сдвига, вы вставите два элемента в старую головку, а затем получите два головных узла. Концептуально это всего лишь два разных стека, которые разделяют все элементы, кроме верхних. Выталкивание элемента просто перемещает указатель головы вниз по стеку, следуя за каждым из следующих узлов.

III. Использование GSS в GLR

Вот где полезно прочитать статью МакПика.

Алгоритм GLR использует преимущества GSS, объединяя заголовки стека, которые имеют одинаковый элемент состояния. Это означает, что у одного элемента состояния может быть более одного дочернего элемента. При сокращении алгоритм GLR должен будет исследовать все возможные пути от головы стека.

Вы можете оптимизировать GLR, поддерживая детерминированную глубину каждого узла. Это просто расстояние от разделения в стеке. Таким образом, вам не всегда нужно искать разделение стека.

Это сложная задача! Удачи!

Вопрос, который вы задаете, нетривиален. Я вижу два основных способа сделать это:

1. Прямое представительство. Ваша структура данных представлена ​​в памяти как объекты / структуры узлов, где каждый узел имеет ссылку / указатель на структуры под ним в стеке (в качестве альтернативы можно также сделать ссылки двунаправленными). Это способ представления списков и деревьев в памяти. В этом случае это немного сложнее, потому что в отличие от дерева или списка, где нужно поддерживать только ссылку на корневой узел или головной узел, чтобы отслеживать дерево, здесь нам нужно будет поддерживать список ссылок на все узлы «верхнего уровня».

2. Представление списка смежности. Это похоже на то, как математики любят думать о графах: G = (V, E). Вы ведете список ребер, индексированных вершинами, которые являются исходными и конечными точками для каждого ребра.

Первый вариант имеет то преимущество, что обход может быть быстрее, если GSS не слишком плоский. Но со структурой работать немного сложнее. Вам придется накатить множество собственных алгоритмов.

Второй вариант имеет то преимущество, что с ним проще работать. Большинство алгоритмов в учебниках, похоже, предполагают некое представление списка смежности, что упрощает применение множества алгоритмов графов.

Некоторые ресурсы:

Существуют различные типы списков смежности, например на основе хеш-таблиц, массивов и т. д. Хорошее место для начала - страница список смежности .

Вот сообщение в блоге от кто-то, кто борется с той же проблемой. Код - это clojure, который может быть вам знаком, а может и не быть, но его обсуждение заслуживает внимания, даже если это не так.

Я должен упомянуть, что я думаю, что мне хотелось бы получить больше информации о представлении направленных ациклических графов (или структурированных графов, если хотите), учитывая широкое применение такого рода моделей. Я думаю, что есть возможности для поиска лучших решений.