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

Код 5.2

% Разборщик с использованием разностных списков

:- op(200, xfx, '\').

test1([большой, чеpный, кот, вскочил, в, пеpеполненный,

московский, тpамвай]). test2([кот,пpогуливался]).

test3([большой, pыжий, лохматый, пес, выскочил, на, тpотуаp]).

s_list([кот,пес,тpамвай,тpотуаp]).

p_list([большой, лохматый, московский, пеpеполненный, pыжий, чеpный]).

g_list([вскочил, выскочил, пpогуливался]). pd_list([в, на]).

an_ph(ph(X, Y), L\M) :-

an_gs(X, L\M1),

an_gg(Y, M1\M).

an_gs(gs(X), L\M) :-

an_s(X, L\M).

an_gs(gs(X,Y), L\M) :-

an_p(X, L\M1),

an_gs(Y, M1\M).

an_gg(gg(X), L\M) :-

an_g(X, L\M).

an_gg(gg(X,Y,Z), L\M) :-

an_g(X, L\M1),

an_pd(Y, M1\M2),

an_gs(Z, M2\M).

an_s(s(X), [X|M]\M) :- s_list(L), member(X,L).

76

an_p(p(X), [X|M]\M) :- p_list(L), member(X,L).

an_g(g(X), [X|M]\M) :- g_list(L), member(X,L).

an_pd(pd(X), [X|M]\M) :- pd_list(L), member(X,L).

%Целевые утверждения:

%?-test1(L), an_ph(Res, L\[]).

%?-test2(L), an_ph(Res, L\[]).

%?-test3(L), an_ph(Res, L\[]).

Консоль (для 1-го теста):

# 0.000 seconds to consult pars_dl.pl [c:\prolog\lpa2002\] | ?- test1(L), an_ph(Res, L\[]).

L = [большой, чеpный, кот, вскочил, в, пеpеполненный, московский, тpамвай] ,

Res = ph(gs(p(большой), gs(p(чеpный), gs(s(кот)))),

gg(g(вскочил), pd(в), gs(p(пеpеполненный), gs(p(московский), gs(s(тpамвай))))))

| ?-

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

Этот аргумент после успешного срабатывания данного предиката получает значение, равное оставшейся части входной цепочки после отделения от нее анализируемой конструкции. Так, приведенный выше предикат an_ph/2 превращается в предикат an_ph/3:

an_ph(ph(X, Y), L, M):-

an_gs(X, L, M1),

an_gg(Y, M1, M).

Рассмотрим более общий абстрактный пример.

77

Пусть грамматическое правило содержит N нетерминальных символов в правой части: A → B1 B2 ... BN

Соответствующее правило на Прологе будет иметь вид

an_a(a(X1, X2, ..., XN), L, M):- an_b1(X1, L, M1), an_b2(X2, M1, M2),

...

an_bN(XN, MN-1, M).

Обычно, M = []. После успешного срабатывания предиката an_b1 от исходной цепочки L останется остаток M1, который будет исходной цепочкой для предиката an_b2 и т.д.

В Прологе существует встроенный механизм, обеспечивающий компактную форму записи приведенных выше правил.

Аргументы предикатов, соответствующие входной цепочке и остаткам (L, M, M1, M2, …, MN-1), не записываются, знак :- заменяется на знак -->. Вышеприведенное правило приобретает вид

an_a(a(X1, X2, ..., XN)) --> an_b1(X1), an_b2(X2),

...

an_bN(XN).

При трансляции этого правила в Пролог получится

an_a(a(X1, X2, ..., XN), A, B) :-

an_b1(X1, A, C1),

an_b2(X2, C1, C2),

...

an_bN(XN, CN-1, B).

Обратим внимание на то, что при трансляции переменные A, B, Ci добавляются к остальным аргументам предикатов всегда «справа» – после уже имеющихся.

Терминальным символам в правых частях грамматических правил в нашей нотации соответствуют списки, элементы которых – указанные терминальные символы.

Например, правилу грамматики

78

S → a S b c,

где S – нетерминальный символ; a, b, c – терминальные символы, соответствует следующее правило в представляемой нотации:

an_s(s(a, X, b, c)) --> [a], an_s(X), [b, c].

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

an_s(s(a, X, b, c), L, M) :- L = [a|M1],

an_s(X, M1, M2), M2 = [b, c|M].

Очевидно, при трансляции запись этого правила «оптимизируется»:

an_s(s(a, X, b, c), [a|M1], M) :- an_s(X, M1, [b, c|M]).

Проверка показывает, что это соответствует действительности. Если в процессе анализа необходимо реализовать какие-либо

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

Указанные выше соглашения, относящиеся к «новой» нотации правил, представляют так называемый механизм DCG – Definite Clause Grammar; с его помощью удобно определять эффективные нисходящие синтаксические анализаторы по заданным порождающим грамматикам, которые, как это будет видно из дальнейшего, не обязательно должны быть контекстно-свободными!

Пример 5.5. Представим программу (код 5.3) в нотации DCG, реализующую анализатор для приведенного выше Примера 5.4 контекстно-свободной грамматики, порождающей фразы типа:

«большой кот вскочил в переполненный московский трамвай».

79