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

Question

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

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

, чтобы понять:

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

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

Answer 1

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

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

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

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

Answer 2

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

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

EDIT: Другие ответы предложили использовать генератор парсера; например ANTLR. Это хороший совет, но (судя по вашему примеру) ваша грамматика настолько проста, что вы также можете обойтись с помощью StringTokenizer и рукописного рекурсивного анализа спуска. На самом деле, если у вас есть время (и склонность), стоит использовать парсер в обоих направлениях как упражнение.

Answer 3

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

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

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

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