Волченков Логическое программирование язык пролог 2015
.pdfЗадав целевые утверждения (как и в Примере 5.4): ?-test1(L), an_ph(Res, L, []).
?-test2(L), an_ph(Res, L, []). ?-test3(L), an_ph(Res, L, []).
в качестве значения переменной Res получим следующие структуры данных:
Res = ph(gs(p(большой), gs(p(чеpный), gs(s(кот)))),
gg(g(вскочил), pd(в), gs(p(пеpеполненный), gs(p(московский), gs(s(тpамвай))))))
Res = ph(gs(s(кот)), gg(g(пpогуливался)))
Res = ph(gs(p(большой), gs(p(pыжий), gs(p(лохматый), gs(s(пес))))),
gg(g(выскочил), pd(на), gs(s(тpотуаp))))
5.Решение обратной задачи – восстановление цепочки языка по дереву разбора
Интересно отметить, что с успехом решается задача «обратного перевода»: по заданной синтаксической структуре восстанавливается исходная цепочка! Это демонстрируется, например, отработкой таких запросов:
?-test1(L), an_ph(Res, L, []), ?-test2(L), an_ph(Res, L, []), ?-test3(L), an_ph(Res, L, []),
an_ph(Res, L1, []). an_ph(Res, L1, []). an_ph(Res, L1, []).
Значения переменной L1 ничем не будут отличаться от значений переменной L. Неожиданный результат, демонстрирующий не всегда очевидные и не всегда предсказуемые следствия логического вывода, реализованного в Прологе.
81
Лекция 6
Программирование на Прологе эффективных синтаксических анализаторов
Как было отмечено в предыдущей лекции, язык Пролог обладает уникальной особенностью – средствами для быстрого создания программ, назначением которых является эффективный грамматический разбор фраз формальных языков. В данной и в следующей лекциях будут рассмотрены примеры практического применения указанной особенности Пролога. В частности, в данной лекции обсуждается имеющаяся в механизме DCG Пролога возможность учёта контекстной зависимости между подцепочками анализируемой фразы. Эта возможность будет проиллюстрирована примерами: анализатором ограниченного естественного языка, в котором есть зависимость между частями фразы по роду, числу и падежу; анализатором контекстно-зависимого языка {an bn cn}; анализатором «номеров трамвайных билетов» – 6-значных цифровых цепочек – с целью выявления их принадлежности к классу «счастливых»; анализатором арифметических выражений, который не только устанавливает «правильность» выражения, но и вычисляет его значение в ходе синтаксического разбора. И, наконец, будет представлен анализатор фраз ограниченного естественного (английского) языка, смысл которых выражается на языке исчисления предикатов первого порядка (ЯИП-1П). Результатом анализа являются выражения на этом языке, в частности выражения, содержащие кванторы всеобщности и существования.
1. Учёт контекстной зависимости
Речь будет идти о весьма распространенном в языках явлении – связи отдельных частей предложений между собой. Например, в естественных языках, в частности русском, подлежащее и сказуемое связаны между собой по роду, числу и падежу. В Примере 5.4, рассмотренном на прошлой лекции, такая связь неявно просматривалась между группой существительного и группой глагола, а также внутри группы существительного – между прилагательными и существительным.
82
Пример 6.1. Расширим Пример 5.4 из предыдущей лекции («большой чёрный кот вскочил в переполненный московский трамвай») новыми прилагательными, существительными и глаголами не только единственного, но и множественного числа, не только мужского, но и женского рода. Падежи для простоты рассматривать не будем.
В программе, представленной кодом 5.2 из предыдущей лекции, заменим факты
s_list([кот, пес, трамвай, тротуар]).
p_list([большой, лохматый, московский, переполненный, рыжий, черный]).
g_list([вскочил, выскочил, прогуливался]).
другими фактами, «задающими» словари существительных, прилагательных и глаголов, в которые включаются контекстные признаки, например:
s_list([rod(жен), ch(един)], [кошка, собака, улицу]). s_list(ch(множ), [кошки, собаки]).
Здесь факты s_list/2 кроме списка существительных в качестве первого аргумента содержат контекстные признаки рода и числа.
Будем строить синтаксический разбор таким образом, чтобы группа существительного и группа глагола в начале предложений контролировались на совпадение их контекстных признаков. Такой же контроль должен производиться и при анализе группы существительного: контекстные признаки существительного и стоящих левее его прилагательных должны совпадать!
Указанный контроль легко и наглядно реализуется на Прологе путем введения дополнительного аргумента в предикаты an_gs, an_gg, an_s, an_p, an_g. Значением этого аргумента является контекстный признак, который будет передаваться от одного предиката другому.
Например, если первым проанализированным словом в группе существительного окажется слово «большой», то значением аргумента K окажется контекстный признак [rod(муж),ch(един)], и в соответствии с правилом для предиката an_gs это значение будет передано другим предикатам этого правила. Другими словами, ос-
83
тальные прилагательные и существительное анализируемой группы должны будут иметь тот же самый контекстный признак!
В новой редакции, учитывающей контекстную зависимость, анализатор языка, приводимого здесь в качестве примера, будет выглядеть следующим образом (код 6.1):
Код 6.1
test1([большой, черный, кот, вскочил, в, переполненный, московский, трамвай]).
test2([большие, рыжие, лохматые, собаки, выбежали, на, широкую, московскую, улицу]).
test3([маленькая, белая, кошка, выбежала, на, тротуар]). test4([большой, рыжий, лохматый, пес, прогуливались]). test5([большой, рыжий, лохматый, собака, прогуливался]).
s_list([rod(муж), ch(един)], [кот, пес, трамвай, тротуар]).
s_list([rod(жен), ch(един)], [кошка, собака, улицу]). s_list(ch(множ), [кошки, собаки]).
p_list([rod(муж), ch(един)], [большой, лохматый, московский,
переполненный, рыжий, черный]). p_list([rod(жен), ch(един)], [белая, маленькая, московскую,
широкую]). p_list(ch(множ), [большие, лохматые, рыжие]).
g_list([rod(муж), ch(един)], [вскочил, выскочил, прогуливал-
ся]).
g_list([rod(жен), ch(един)], [выбежала, прогуливалась]). g_list(ch(множ), [выбежали, прогуливались]). pd_list([в, на]).
an_ph(ph(X, Y)) -->
an_gs(X, K), an_gg(Y, K). an_gs(gs(X), K) -->
an_s(X, K).
an_gs(gs(X, Y), K) --> an_p(X, K), an_gs(Y, K).
an_gg(gg(X), K) -->
an_g(X, K). an_gg(gg(X, Y, Z), K1) -->
an_g(X, K1), an_pd(Y), an_gs(Z, K2). an_s(s(K, X), K) -->
84
[X], {s_list(K, L), member(X, L)}. an_p(p(K, X), K) -->
[X], {p_list(K, L), member(X, L)}. an_g(g(K, X), K) -->
[X], {g_list(K, L), member(X, L)}. an_pd(pd(X)) -->
[X], {pd_list(L), member(X, L)}.
После обработки целевых утверждений
?-test1(L), an_ph(Res, L, []). ?-test2(L), an_ph(Res, L, []). ?-test3(L), an_ph(Res, L, []).
будет получен положительный результат, и в качестве значения переменной Res будут возвращены следующие структуры данных:
Res = ph(gs(p([rod(муж), ch(един)], большой), gs(p([rod(муж), ch(един)], чеpный), gs(s([rod(муж), ch(един)], кот)))), gg(g([rod(муж), ch(един)], вскочил), pd(в), gs(p([rod(муж), ch(един)], пеpеполненный), gs(p([rod(муж),ch(един)], московский), gs(s([rod(муж), ch(един)], тpамвай))))))
Res = ph(gs(p(ch(множ), большие), gs(p(ch(множ), pыжие), gs(p(ch(множ), лохматые), gs(s(ch(множ), собаки))))),
gg(g(ch(множ), выбежали), pd(на), gs(p([rod(жен), ch(един)], шиpокую), gs(p([rod(жен), ch(един)], московскую), gs(s([rod(жен), ch(един)], улицу))))))
Res = ph(gs(p([rod(жен), ch(един)], маленькая), gs(p([rod(жен), ch(един)], белая), gs(s([rod(жен), ch(един)], кошка)))), gg(g([rod(жен), ch(един)], выбежала), pd(на), gs(s([rod(муж), ch(един)], тpотуаp))))
После обработки целевых утверждений
?-test4(L), an_ph(Res, L, []). ?-test5(L), an_ph(Res, L, []).
будет получен отрицательный результат в силу того, что в первом случае нарушено согласование между группами существительного
85
и глагола, а во втором случае – между существительным и прилагательными внутри группы существительного.
Пример 6.2. Рассмотрим классический пример «абстрактного»
языка: |
|
L = {an bn cn}, |
n = 1, 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 демонстрирует эту идею:
|
|
Код 6.3 |
% |
"Happy ticket" – Н.Г. Волченков © |
|
% |
?- ht(N, F, "565729"). => |
|
% |
N = 5, F = p(5 * (6 - 5), 7 * 2 - 9) ; => |
|
% |
N = 5, F = p(5 / (6 - 5), |
7 * 2 - 9) ; => |
% |
N = 25, F = p(5 * 6 - 5, |
7 + 2 * 9) |
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