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

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

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

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

Ответ 1

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

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

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

II. Стеки

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

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

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

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

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

II. Стеки

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

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

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

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

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

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

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

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

Ответ 2

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

Прямое представление. Ваша структура данных представлена в памяти как node объекты/структуры, где каждый node имеет ссылку/указатель на структуры под ним в стеке (в качестве альтернативы можно также сделать ссылки двунаправленными). Таким образом, списки и деревья обычно представлены в памяти. В этом случае это немного сложнее, потому что в отличие от дерева или списка, где нужно только поддерживать ссылку на root node или head node, чтобы отслеживать дерево, здесь нам нужно будет сохранить список ссылок на все узлы верхнего уровня.
Представление списка смежности. Это похоже на то, как математики любят думать о графиках: G = (V, E). Вы сохраняете список ребер, проиндексированных вершинами, которые являются точками начала и окончания для каждого ребра.

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

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

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

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

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

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