Философские аспекты проблемы систем ИИ




Язык Рефал - часть 4


Чтобы иметь возможность представлять обобщенные предложения, используются три типа переменных: е — для представления выражений; t — для термов; s — для символов. В простейшем случае переменные записываются в виде указателя типа (е, t, s) и индекса; например, е1, e2 — переменные, пробегающие в качестве значений выражения. Выражением в языке Рефал называется последовательность знаков, правильно построенная в соответствеии с синтаксисом языка Рефал. Терм языка Рефал — это либо символ, либо выражение в круглых или конкретизационных скобках. Выражения строятся из термов.

Пример. Предположим, требуется написать программу, которая выполняет раскрытие скобок в алгебраических выражениях, построенных из букв с помощью скобок, знаков сложения "+" и умножения"*". Рассмотрим процесс написания такой программы. Если некоторое выражение е имеет вид е1 + e1, где е1, e1 — выражения, то для раскрытия скобок надо: раскрыть скобки в e1, раскрыть скобки в е2, полученные результаты сложить. Эту мысль в компактном, но в то же время и наглядном виде выражает предложение:

§ 2.1 ke1 +e2^ --> ke1^ +ke2^

Если же выражение е имеет вид e1 * e2, то, вообще говоря, необходимо учитывать две возможности:

  • хотя бы один из сомножителей есть сумма (например, е = (А + В) *С),
  • ни одно из выражений е1 или е2 не представимо в виде суммы (например, е = (А * В) * (С * Л)).

В первом случае надо описать законы дистрибутивности:

§ 2.2ke1 * (e2 +e3) ^ --> ke1 * e2^ +ke1*e3^ ,

§ 2.3k(e1 +e2) * e3^ --> ke1 * e3^ + ke2*e3^ ,

§ 2.4ke1 * (e2 + e3) * e4 ^ --> k(e1 * е2 + e1 * e3) * e4^ .

Во втором случае по аналогии со сложением имеем

§ 2.5ke1 * е2^ --> ke1^ * ke2^ .

Наконец, осталось выразить возможность "снятия внешних скобок" и условие "терминальности" символов, что определяют предложения:

§ 2.6k(e) ^ --> ke^ ,

§ 2.7ks^ --> s

(буквы не подлежат конкретизации).

Приведенные семь предложений § 2.1 - § 2.7 решают задачу. Рассмотрим как эта программа обрабатывает выражение

k(A +B) * (С +D) ^.

Последовательно получим в результате работы программы (для удобства слева указываем номер правила, которое непосредственно привело к данному выражению):

§2.2 k(A +В)*С^ . + k(A +B)*D^ ,

§2.3 kA *C^ +kB*C^ + k(A+B)*D^ ,

§2.3 kA *C^ + kB*C^ + kA *D^ + kB*D^ .

Далее ограничимся рассмотрением первого слагаемого:

§ 2.5 kA^ * kC^ + ...,

§2.7 A * kC^ + ...,

§ 2.7 А * С + ... .

После аналогичной обработки остальных слагаемых получим искомое выражение

А*С+D*С+А * D + В * D.

Если на вход поступит выражение

kA + (B + С) ^ ,

то получим последовательно:

§ 2.1 kA^ + k(B + С) ^ ,

§ 2.7 А + k (Д + С) ^ ,

§ 2.6 А + kB + C^ ,

§2.1, 2.7 A + B + С.

Обратите внимание, что если расположить правило § 2.5 перед правилами § 2.2 и § 2.3, то придем к абсурду! Например, выражение А *(В+С) будет приведено к виду: А *В + С.




Содержание  Назад  Вперед