Как реализовать структурированный графиком стек?
Хорошо, таким образом, я хотел бы сделать генератор GLR парсера. Я знаю, там существуют такие программы лучше, чем, что я, вероятно, сделаю, но я делаю это для забавы/изучения, таким образом, это не важно.
Я читал о GLR-анализе, и я думаю, что у меня есть достойное понимание высокого уровня его теперь. Но теперь пора приступить к делу.
Структурированный графиком стек (GSS) является ключевой структурой данных для использования в GLR парсерах. Концептуально я знаю, как GSS работает, но ни один из источников, на которые я смотрел до сих пор, не объясняет, как реализовать GSS. У меня даже нет авторитетного списка операций для поддержки. Кто-то может указать на меня на некоторый хороший пример кода / учебное руководство для GSS? Google не помог до сих пор. Я надеюсь, что этот вопрос не слишком неопределенен.
2 ответа
Вопрос, который вы задаете, нетривиален. Я вижу два основных способа сделать это:
Прямое представление. Ваша структура данных представлена в памяти как объекты / структуры узлов, где каждый узел имеет ссылку / указатель на структуры под ним в стеке (в качестве альтернативы можно также сделать ссылки двунаправленными). Это способ представления списков и деревьев в памяти. В этом случае это немного сложнее, потому что в отличие от дерева или списка, где нужно поддерживать только ссылку на корневой узел или головной узел, чтобы отслеживать дерево, здесь нам нужно будет поддерживать список ссылок на все узлы «верхнего уровня».
Представление списка смежности. Это похоже на то, как математики любят думать о графах: G = (V, E). Вы ведете список ребер, индексированных вершинами, которые являются исходными и конечными точками для каждого ребра.
Первый вариант имеет то преимущество, что обход может быть быстрее, если GSS не слишком плоский. Но со структурой работать немного сложнее. Вам придется накатить множество собственных алгоритмов.
Второй вариант имеет то преимущество, что с ним проще работать. Кажется, что большинство алгоритмов в учебниках предполагают некое представление списка смежности, что упрощает применение множества алгоритмов графов.
Некоторые ресурсы:
Существуют различные типы списков смежности, напримерНа основе хэш-таблиц, массивов и т. д. Хорошее место для начала - страница со списком смежности в Википедии .
Вот запись в блоге человека, который боролся с той же проблемой. Код - это clojure, который может быть знаком, а может и не быть, но его обсуждение заслуживает внимания, даже если это не так.
Я должен упомянуть, что я думаю, что мне хотелось бы получить больше информации о представлении направленных ациклических графов (или структурированных стеков графов, если хотите), учитывая широкое применение такого рода моделей. Я думаю, что есть возможности для поиска лучших решений.
Во-первых , если вы еще этого не сделали, вам следует прочитать статью МакПика о GLR http://www.cs.berkeley.edu/~smcpeak/papers/elkhound_cc04.ps . Это академический документ, но он дает хорошие подробности о GSS, GLR и методах, используемых для их реализации. Это также объясняет некоторые сложные проблемы с реализацией парсера GLR.
У вас есть три части для реализации стека с графической структурой.
I. Сама структура данных графа
II. Стеки
III. Использование GSS в GLR
Вы правы, Google не очень помогает. И если вы не любите читать книги по алгоритмам, они тоже не сильно помогут.
I. Структура данных графа
Ответ Роба о «прямом представлении» проще всего реализовать. Это очень похоже на связанный список, за исключением того, что каждый узел имеет список следующих узлов, а не только один.
Эта структура данных является ориентированным графом, но, как утверждает МакПик, в GSS могут быть циклы для эпсилон-грамматик.
II. Стеки
Стек с графической структурой концептуально представляет собой просто список обычных стеков. Для однозначной грамматики вам понадобится всего одна стопка. Когда возникает конфликт синтаксического анализа, вам нужно больше стеков, чтобы вы могли выполнять оба действия синтаксического анализа одновременно и поддерживать различное состояние, создаваемое обоими действиями. Использование графа позволяет вам воспользоваться тем фактом, что эти стеки разделяют элементы.
Это может помочь понять, как сначала реализовать единственный стек со связным списком.Заголовок связанного списка - это вершина стека. Помещение элемента в стек - это просто создание новой головы и указание ее на старую. Выталкивание элемента из стека просто перемещает указатель на head-> next.
В GSS принцип тот же. Выталкивание элемента просто создает новый головной узел и указывает его на старую головку. Если у вас есть две операции сдвига, вы вставите два элемента в старую головку, а затем получите два головных узла. Концептуально это всего лишь два разных стека, которые разделяют все элементы, кроме верхних. Выталкивание элемента просто перемещает указатель головы вниз по стеку, следуя за каждым из следующих узлов.
III. Использование GSS в GLR
Здесь полезно прочитать статью МакПика.
Алгоритм GLR использует преимущества GSS путем объединения заголовков стека, которые имеют одинаковый элемент состояния. Это означает, что у одного элемента состояния может быть более одного дочернего элемента. При сокращении алгоритм GLR должен будет исследовать все возможные пути от головы стека.
Вы можете оптимизировать GLR, поддерживая детерминированную глубину каждого узла. Это просто расстояние от разделения в стеке. Таким образом, вам не всегда нужно искать разделение стека.
Это сложная задача! Удачи!