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

Консоль:

# 0.000 seconds to consult sort_k.pl [c:\prolog\lpa\] | ?- test(List, Res, Key).

List = [f(d,m,8),f(d,m,3),f(d,k,9)] , Res = [f(d,k,9),f(d,m,3),f(d,m,8)] , Key = [2,3]

yes

Задача 11. Дан список списков list_lists([L1, …, Ln]), где Li – список термов.

Декларативно (!) определите предикаты maxlist/1 и minlist/1, выходной параметр которых – максимальный и минимальный по длине список из данного списка списков.

Указание: используйте определения предикатов longer(X,Y) и shorter(X,Y), с помощью которых списки сравниваются по длине (а также создаются списки, более длинные или более короткие, чем данный список):

longer([_|_], []).

longer([_|L1], [_|L2]) :- longer(L1, L2).

shorter([], [_|_]).

shorter([_|L1], [_|L2]) :- shorter(L1, L2).

Решение:

maxlist(L) :- list_lists(Ls), member(L, Ls), nolonger(L, Ls). nolonger(L, Ls) :- longer(M, L), member(M, Ls), !, fail.

% Предикат «нет списка длиннее» nolonger(_, _) :- !.

minlist(L) :- list_lists(Ls), member(L, Ls), noshorter(L, Ls). noshorter(L, Ls) :- shorter(M, L), member(M, Ls), !, fail.

% Предикат «нет списка короче»

noshorter(_, _) :- !.

longer([_|_], []).

longer([_|L1], [_|L2]) :- longer(L1, L2).

66

shorter([], [_|_]).

shorter([_|L1], [_|L2]) :- shorter(L1, L2).

Применение методов исходящей и входящей рекурсии в Прологе

Автор предлагает слушателям и читателям ответить на вопросы относительно использования методов входящей и выходящей рекурсии в задачах 8 – 11.

Вопрос 1. Какой из двух методов рекурсии используется в определении предиката arg1/3 ? ( Задача 8.)

Ответ: метод входящей рекурсии.

Вопрос 2. Какой из двух методов рекурсии используется в определении предиката sort_k/3 – сортировки списка термов по заданному ключу и в рекурсивных определениях трёх предикатов: sort_k/3, in_sort_k/4 и lista/3? ( Задача 10.)

Ответ: метод исходящей рекурсии.

Вопрос 3. Какой из двух методов рекурсии используется в определениях предикатов shorter/2 и longer/2? ( Задача 11.)

Ответ: метод исходящей рекурсии.

Задача 12. С помощью метода входящей рекурсии определите предикаты minlist/1 и maxlist/1. В этих определениях используйте традиционный для языков операторного типа способ нахождения максимального и минимального элементов (массива, например).

Указание: можно использовать встроенный предикат length(L, N) для определения длины N списка L.

Решение (одно из многих возможных):

% Тестовый пример списка списков: list_lists([[a,b],[c,d,e],[f],[g,h,i],[j],[k,l,m],[o],[p,q]]).

minlist(X) :- list_lists([L|Ls]), length(L, N), singlemin(N, M, Ls),

%Безвозвратный поиск длины минимального списка.

!, multim(M, X, [L|Ls]).

%Возвратный поиск всех списков данной длины.

67

maxlist(X) :- list_lists([L|Ls]), length(L, N), singlemax(N, M, Ls),

%Безвозвратный поиск длины максимального списка.

!, multim(M, X, [L|Ls]).

%Возвратный поиск всех списков данной длины.

length(L, K), K<N, !, singlemin(K, M, Ls). singlemin(N, M, [L|Ls]) :-

!, singlemin(N, M, Ls).

% Отсечение обеспечивает безвозвратность.

length(L, K), K>N, !, singlemax(K, M, Ls). singlemax(N, M, [L|Ls]) :-

!, singlemax(N, M, Ls).

% Отсечение обеспечивает безвозвратность.

multim(M, X, Ls) :- member(X, Ls), length(X, M).

% Поиск всех решений.

Консоль:

| ?-

# 0.000 seconds to consult minmaxls.pl [c:\prolog\lpa\] | ?- minlist(X).

X = [f] ; X = [j] ; X = [o] ; no

| ?- maxlist(X). X = [c,d,e] ; X = [g,h,i] ;

X = [k,l,m] ; no

68

Подумайте, какой из двух представленных выше стилей решения данной задачи (декларативный или процедурный) более красив, а какой стиль более эффективен?

69

Лекция 5

Синтаксический анализ на Прологе

В данной лекции рассматривается возможность использования Пролога для синтаксического анализа языков, представляемых формальными грамматиками, – контекстно-свободных и контекст- но-зависимых языков. Прежде всего, даётся определение порождающей грамматики. Определяются автоматная, контекстносвободная и контекстно-зависимая грамматики, а также языки соответствующих трёх типов. На примере показано, как можно реализовать на Прологе простейший анализатор для автоматного языка, – эта задача не представляет большого интереса. Рассматривается попытка создания «наивного» анализатора для КС-грамматики с помощью недетерминированного разбиения цепочки на подцепочки. Показано, что использование малоэффективного предиката append/3 делает такой анализатор бесперспективным. Наконец, рассказывается об идее замены указанного предиката разностными списками и, в частности, механизмом DCG – Definite Clause Grammar. Это приводит к возможности создания эффективно работающих нисходящих грамматических разборщиков на Прологе.

1. Формальные грамматики и языки

Вспомним определения порождающей грамматики и языка, порождаемого такой грамматикой.

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

G = <VT, VN, S, P>,

где VT, VN – соответственно, терминальный и нетерминальный словари, S – начальный символ, P = { i i} – множество правил вывода, причём i – цепочка, содержащая нетерминальный символ,i – произвольная цепочка из терминальных и нетерминальных символов.

Непосредственным порождением называется отношение

70