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

если существует последовательность отношений1 n.

Языком, порождаемым грамматикой G, называется следующее множество:

L(G) = { S }

(множество терминальных цепочек – цепочек, состоящих только из символов терминального словаря VT).

Грамматики и языки подразделяют на типы. В практических задачах наиболее часто используются грамматики и языки следующих трех типов.

Типы грамматик:

Если нетерминальный символ в левой части какого-либо правила грамматики находится в окружении других символов (терминальных и/или нетерминальных), то такая грамма-

тика называется контекстно-зависимой.

Грамматика называется контекстно-свободной, если левая часть каждого правила вывода этой грамматики – это цепочка, состоящая из единственного нетерминального символа.

Контекстно-свободная грамматика называется автоматной,

если каждое правило вывода этой грамматики имеет следующий вид:

А аВ или А а или А ,

где A, B – нетерминальные символы, a – терминальный символ, λ – пустая цепочка.

Типы языков:

Язык называется автоматным, если для его порождения можно построить автоматную грамматику. (Разумеется, для порождения этого языка можно построить грамматики и других типов.)

71

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

Язык называется контекстно-зависимым, если для его порождения нельзя построить контекстно-свободной грамматики.

2. Простейший анализатор для автоматного языка

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

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

Правила эти такие:

Г_С → СУЩ | ПР Г_С СУЩ → кот | пес | ...

ПР → большой | огромный | черный | лохматый | рыжий |

Нетрудно показать, что для рассмотренного «языка» можно построить автоматную грамматику. Можете сделать это самостоятельно.

Здесь Г_С означает «группу существительного» («noun group» в англоязычной литературе – отсюда и «калька»), СУЩ, ПР – существительное и прилагательное.

Отметим, что среди представленных выше правил есть рекурсивное: Г_С → ПР Г_С. Оно позволяет порождать бесчисленное множество сколь угодно длинных «групп существительного».

Если исходные конструкции представить в виде списков Пролога, например, [большой, черный, кот], можно легко организовать их анализ с помощью очень простого приведенного ниже определения на Прологе (код 5.1).

Код 5.1

test1([большой, чеpный, кот]). test2([кот]).

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

an(gs(s(H)), [H]). an(gs(p(H), X), [H|T]):-

an(X, T).

72

Отметим, что это определение представляет собой интерпретируемый код, то есть может быть непосредственно загружено в базу данных Пролога и проинтерпретировано (тексты в данной лекции с помощью системы LPA Win Prolog 4.200).

Задав целевые утверждения:

?-test1(L), an(Res, L). ?-test2(L), an(Res, L). ?-test3(L), an(Res, L).

в качестве значения переменной Res мы получим следующие структуры данных:

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

Res = gs(s(кот));

Res = gs(p(большой), gs(p(рыжий), gs(p(лохматый), gs(s(пес))))).

3. «Наивный» анализатор для КС-грамматики

Пример 5.2. Усложним задачу. Если в предыдущем примере анализатор работал как детерминированный автомат, то для произвольных контекстно-свободных грамматик (КС-грамматик) мы вынуждены перейти к недетерминированным методам.

В частности, если необходимо анализировать более сложные фразы, состоящие как из групп существительного, так и из глагольных групп, например:

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

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

Прежде всего, зададим грамматику, порождающую фразы из выбранного нами класса:

ФР → Г_С Г_Г Г_С → СУЩ | ПР Г_С

Г_Г → ГЛ | ГЛ ПД Г_С СУЩ → кот | пес | трамвай | тротуар | ...

ПР → большой | огромный | черный | рыжий | лохматый | московский | переполненный | ...

ГЛ → вскочил | выскочил | прогуливался | ...

ПД → в | на | ...

73

Первое, что напрашивается при попытке написания синтаксического анализатора на Прологе – это использование предиката append/3 для разбиения списка, представляющего исходную цепочку, на части:

an_ph(ph(X, Y), L):- append(L1, L2, L), an_gs(X, L1), an_gg(Y, L2).

...

Такая «наивная» попытка построения анализатора с использованием предиката append/3 оказывается весьма неудачной, так как указанный предикат работает неэффективно, особенно тогда, когда цепочку в соответствии с грамматикой необходимо разбивать более чем на две части.

4. Встроенный в Пролог механизм DCG

Как выяснилось, можно обойтись без неэффективного предиката append/3, воспользовавшись понятием разностного списка или (что эквивалентно) введя дополнительный аргумент в предикаты анализатора.

Разностный список – это структура инфиксного типа с именем \ и двумя компонентами: списком [A1, …, An | T] и списком T:

[A1, …, An | T] \ T.

Такая структура эквивалентна обычному списку, содержащему n элементов: [A1, …, An]. Но в записи разностного списка есть неозначенная переменная T, значением которой может быть любой список. Можно привести аналогию: любое число, например 5, равно разности, содержащей переменную: (5 + X) – X.

Использование понятия «разностный список» позволяет существенно повысить эффективность работы многих предикатов обработки списков, например предиката append/3 (конкатенации или «склеивания»). Вместо определения

append([], L, L).

append([H|T], L, [H|R]) :- append(T, L, R).

можно воспользоваться гораздо более эффективным определением:

74

append_dl(X\Y, Y\Z, X\Z).

Последнее определение позволяет «склеивать» списки (длина их может быть весьма большой) без многочисленных рекурсивных вызовов, – а только на уровне сопоставления структур!

Z

Рис. 5.1. Демонстрация конкатенации разностных списков

Пример 5.3. Пусть L1 = [a, b, c]; L2 = [d, e, f].

Необходимо найти конкатенацию этих списков.

Вызов ?- append([a, b, c], [d, e, f], Z).

приводит к необходимости трёх рекурсивных вызовов, в то время как вызов

?- append_dl([a, b, c|X] \ X, [d, e, f] \ [], Z).

дает результат Z = [a, b, c, d, e, f] \ [] за единственный шаг логиче-

ского вывода.

Эксперимент в системе Win Prolog LPA 4.200:

:- op(200, xfx, '\'). append_dl(X\Y, Y\Z, X\Z).

Консоль:

# 0.000 seconds to consult untitled [c:\prolog\lpa2002\] | ?- append_dl([a, b, c|X]\X, [d,e,f]\[], Z).

X = [d,e,f] ,

Z = [a,b,c,d,e,f] \ []

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

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

с использованием разностных списков вместо предиката append/3.

75