реализация алгоритма унификации

Question

Последние 5 дней я работал, чтобы понять, как работает алгоритм объединения в Прологе. Теперь я хочу реализовать такой алгоритм в Java ..

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

, чтобы прояснить:

предположим, что пользовательский ввод: a (X, c (d, X)) = a (2, c (d, Y)).

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

Answer 1

Сначала вам нужно проанализировать входные данные и построить деревья выражений. Затем примените алгоритм объединения Милнера (или какой-либо другой алгоритм объединения), чтобы выяснить, как соотнести переменные с константами и выражениями.

Действительно хорошее описание алгоритма Милнера можно найти в Книге Дракона: «Компиляторы: принципы, методы и инструменты» Ахо, Сетхи и Уллмана. (Алгоритм Милнерса также может справиться с унификацией циклических графов, и книга Дракона представляет его как способ сделать вывод типа). Судя по звукам, вы могли бы немного узнать о разборе ... который также описан в Книге Дракона.

РЕДАКТИРОВАТЬ: Другие ответы предлагали использовать генератор парсера; например ANTLR. Это хороший совет, но (судя по вашему примеру) ваша грамматика настолько проста, что вы также можете обойтись с помощью StringTokenizer и рукописного парсера рекурсивного спуска. Фактически, если у вас есть время (и склонность), стоит реализовать парсер в обоих направлениях в качестве учебного упражнения.

Answer 2

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

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

В AST для Prolog у вас могут быть классы для Term, а CompoundTerm, Variable и Atom - это все термины. Полиморфизм позволяет аргументам составного термина быть любым Термин.

Ваш алгоритм объединения затем объединяет имя любого составного термина и рекурсивно объединяет значение каждого аргумента соответствующих составных терминов.

Answer 3

Похоже, что эта проблема больше связана с разбором, а не с объединением. Использование типа ANTLR может помочь превратить исходную строку в некую древовидную структуру.

(Не совсем понятно, что вы подразумеваете под «делать это вложенным», но если вы имеете в виду, что вы делаете что-то вроде попытки прочитать выражение и повторения при встрече с каждым «(», то это на самом деле одно из правильные способы сделать это - в основе того, что будет делать код, который ANTLR генерирует для вас.)

Если вы более заинтересованы в механизме объединения вещей, чем в синтаксическом анализе, тогда один очень хороший способ сделать это - напрямую создать внутреннее представление в коде и отложить аспект синтаксического анализа на данный момент. Это может немного раздражать во время разработки, так как ваши операторы в стиле Prolog теперь представляют собой довольно подробный набор Java-операторов, но позволяют сосредоточиться на одной проблеме за раз, что обычно полезно.

(Если вы структурируете вещи таким образом, это должно упростить вставку правильного парсера позже, который будет производить дерево такого же типа, какое вы до этого создавали вручную. Это позволит вам атаковать две проблемы по отдельности в довольно аккуратной манере.)