Материал: Волченков Логическое программирование язык пролог 2015

и глагола, а во втором случае – между существительным и прилагательными внутри группы существительного.

Пример 6.2. Рассмотрим классический пример «абстрактного»

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

С использованием нотации DCG анализатор этого языка может

быть представлен следующим образом (код 6.2):

Код 6.2

test1("aaaaabbbbbccccc"). test2("abc"). test3("aaaabbbbccc").

an_s(s(K, X, Y)) -->

an_m(X, K), an_n(Y, K). an_m(m(a, b), 1) --> "ab".

an_m(m(a, X, b), K1) --> % K1 - выходной параметр. "a",

an_m(X, K), "b",

{K1 is K + 1}. an_n(n(c), 1) --> "c".

an_n(n(c, X), K) --> % K - входной параметр. "c",

{K1 is K - 1}, an_n(X, K1).

В данном анализаторе за основу была взята следующая контек- стно-свободная грамматика:

S M N

M a b | a M b N c | c N

Но такая грамматика порождает цепочки, в которых число символов c никак не связано с числом символов a (или b). Для того чтобы их число было одинаковым, в первом правиле анализатора используется параметр K – это переменная, значение которой фор-

86

мируется в ходе «раскрытия» нетерминального символа M. «Раскрытие» нетерминального символа N начинается с уже означенной переменной K, в режиме проверки того, что длина цепочки, состоящей из символов c, в точности равняется значению этой переменной.

Пример 6.3. Задача о «счастливом трамвайном билете».

Один из вариантов игры в «счастливый трамвайный билет» заключается в следующем. Считается, что «номер» билета – цепочка из шести цифр. Цепочка разбивается на две равные подцепочки по 3 цифры в каждой. Между цифрами нужно поместить знаки арифметических действий (+, –, *, /) так, чтобы результаты их применения для первой и для второй цепочек совпали.

Например, для цепочки «565729» можно предложить такое ре-

шение: 5 * 6 – 5 = 7 + 2 * 9.

Допускается использование скобок: 5 / (6 – 5) = 7 * 2 – 9.

Для решения данной задачи на Прологе можно воспользоваться механизмом DCG – использовать идею нисходящего синтаксического разбора. Код 6.3 демонстрирует эту идею:

ht(N, F, L) :- an_S(N, F, L, []).

an_S(N, F) --> an_S3(N, F1), an_S3(N, F2), {F = p(F1, F2)}.

an_S3(N, F) --> an_S1(N1), an_S2(N2, F2), {val(N1, N2, N, Z), F=..[Z, N1, F2]}.

an_S3(N, F) --> an_S2(N1, F1), an_S1(N2), {val(N1, N2, N, Z), F=..[Z, F1, N2]}.

an_S2(N, F) --> an_S1(N1), an_S1(N2),

{val(N1, N2, N, Z), F=..[Z, N1, N2]}. an_S1(N) --> [C], {48=<C, C=<57, N is C - 48}.

% C – ASCII-код цифры.

87

val(N1, N2, N, '+') :- N is N1 + N2. val(N1, N2, N, '-') :- N is N1 - N2. val(N1, N2, N, '*') :- N is N1 * N2.

val(N1, N2, N, '/') :- N2 =\= 0, N is N1 / N2.

Комментарий. Легко восстановить грамматику, которую необходимо составить для решения данной задачи:

S S3 S3

S3 S1 S2 | S2 S1

S2 S1 S1

S1 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

В этой грамматике интересны не сами приведённые правила, а действия, которые с ними «сопряжены». Эти действия следующие:

формирование структур арифметических выражений (значения переменной F в правилах для нетерминального символа

S3):

вычисление значений арифметических выражений (значения переменной N в правилах для нетерминального символа S3),

сравнение полученных значений по совпадению значений

«контекста» – переменной N в двух предикатах правой части правила an_S(N, F) --> an_S3(N, F1), an_S3(N, F2), ...

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

2.Вычисление значения арифметического выражения

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

88

Например, вызов ?– an_Expr(Val, ”12+34-56+78”, []). должен дать результат Val = 68.

Сначала маленькое «лирическое отступление», посвящённое арабским цифрам.

Почему современные цифры называются «арабскими»? Допод-

линно известно лишь одно – в Европу их «занесли» арабы примерно в XIII веке.

Арабское число ۹۸۷۶۵۴۳۲۱ в евро-американской нотации выглядит так: 123456789. И хотя арабы читают это число не слева направо, как американцы или русские («сто двадцать три миллиона, четыреста пятьдесят шесть тысяч, семьсот восемьдесят девять»), а справа налево, – арабская запись ничем не отличается от «нашей». Дело в том, что арабы начинают читать сначала единицы (здесь «девять»), затем десятки (здесь «восемьдесят»), затем сотни (здесь «семьсот») и т.д.

С точки зрения синтаксического анализа чтение и запись не только чисел, но и арифметических выражений не «слева направо», как предпочитаем делать мы, а «справа налево», как это делают арабы, оказывается, существенно лучше! Дело в том, что в первом случае при анализе возникает так называемая «проблема левосторонней рекурсии», приводящая к «зацикливанию». А во втором случае такой проблемы не возникает. Заключается эта проблема в следующем.

Для арифметических выражений, не содержащих скобок (такое допущение мы принимаем для упрощения нашего примера), имеет место следующая грамматика:

Expr Term | Expr + Term | Expr - Term

Term Number | Term * Number | Term / Number

Правила для нетерминального символа Number здесь пока не приводятся.

В этой грамматике отражён тот факт, что арифметические операции являются существенно не право-ассоциативными, а левоассоциативными.

Например, в выражении 12 + 34 – 56 + 78 скобки расставляются так: (((12 + 34) – 56) + 78), а не так: (12 + (34 – (56 + 78))).

89

Попытка построить анализатор с помощью механизма DCG Пролога приведёт к «зацикливающимся» программам в силу наличия таких, например, правил:

an_Expr(…) --> an_Expr(…), [’+’], an_Term(…).

Это и есть «левосторонняя рекурсия».

Чтобы её избежать, вспомним арабов и их способ письма и чтения, – не только чисел, но и произвольных текстов (например, Корана). Это способ чтения и письма «справа налево». Возьмём этот способ на вооружение.

Сначала произведем реверс арифметического выражения, на-

пример: ”12+34-56+78” => ”87+65-43+21”.

А теперь применим к нему вполне корректную с точки зрения возможного «зацикливания» грамматику:

Expr Term | Term + Expr | Term – Expr

Term Number | Number * Term | Number / Term

Здесь применена уже не «криминальная» левосторонняя, а вполне корректная правосторонняя рекурсия.

Эта идея, воплощённая в жизнь, заключена в следующем коде:

Код 6.4

pars(Exp, Val) :-

reverse(Exp, RExp), an_expr(Val, RExp, []).

an_expr(Z) -->

an_term(X), "+", an_expr(Y), {Z is Y+X}. an_expr(Z) -->

an_term(X), "-", an_expr(Y), {Z is Y-X}. an_expr(X) -->

an_term(X).

an_term(Z) -->

an_number(X), "*", an_term(Y), {Z is Y*X}. an_term(Z) -->

an_number(X), "/", an_term(Y), {Z is Y/X}. an_term(X) -->

an_number(X).

90