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

Лекция 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