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

Question

Хорошо, я хотел бы создать генератор синтаксического анализатора GLR.Я знаю, что существуют такие программы лучше, чем то, что я, вероятно, сделаю, но я делаю это для развлечения / обучения, так что это не важно.

Я читал о разборе GLR и думаю, что у меня достаточно высокий уровеньпонимание этого сейчас.Но теперь пришло время приступить к делу.

Графо-структурированный стек (GSS) является ключевой структурой данных для использования в парсерах GLR.Концептуально я знаю, как работает GSS, но ни один из источников, на которые я смотрел, не объясняет, как реализовать GSS.У меня даже нет авторитетного списка операций для поддержки.Может кто-нибудь указать мне хороший пример кода / учебник для GSS?Google пока не помог.Надеюсь, этот вопрос не слишком расплывчатый.

Answer 1

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

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

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

II. Стеки

III. GLR использует GSS

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

I. График структуры данных

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

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

II. Стеки

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

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

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

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

Здесь статья Макпика полезна для чтения.

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

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

Это сложная задача! Так что удачи!

Answer 2

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

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

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

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

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

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

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

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

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