Использования языка пролог для работы с КС-грамматиками
Первая программа, написанная на прологе в 1972, была предназначена для работы 
с естественным языком.

Структура продукций КС-грамматик и правила пролога почти идентичны. Например,
продукция A->xyz похожа на логическое правило A:-x,y,z. Разница только в 
том, что в правой части продукции важен порядок членов, а в логическом 
правиле этот порядок теоретически не важен. Поддержку порядка можно ввести,
используя переменные и списки.

Списки в прологе --- это последовательность элементов в квадратных скобках 
через запятую. Первый элемент или голову списка можно отделить, используя 
знак вертикальной черты, например, 
[1,2,3] = [1|[2,3]] = [1,2|[3]] = [1,2,3|[]]. Список после вертикальной 
черты --- это остаток или хвост.

Для записи КС-грамматик в виде логических продукций можно использовать 
несколько способов. Рассмотрим два из них. Согласно первому каждому 
нетерминалу назначается одноместный предикат. Правая часть логического 
правила состоит из собирания списка, при помощи append или буквального, 
эквивалентного правой части КС-продукции. Стандартный предикат append --- 
истинен, если его третий аргумент --- это соединение двух первых 
аргументов-списков, например, после append([1,2],[2,3],X) X=[1,2,2,3], 
а после append([1,2],X,[1,2,3]) X=[3]. Собранный список затем 
унифицируется с аргументом в левой части. Например, для грамматики
S->01|0S1
получаются следующие правила
s([0,1])
s(S) :- append([0|X],[1],S),s(X).

Согласно второму всем терминалам и нетерминалам назначаются двухместные 
предикаты, первый аргумент которых --- это список, хвост которого --- это 
второй аргумент. Правила для терминалов имеют стандартную форму. Если 
использовать этот способ, то получим правила
s([0,1|X],X).
s(L,X) :- zero(L,X1), s(X1,X2), one(X2,X).
zero([0|X],X). %zero --> [0].
one([1|X],X).
При использовании этого способа в запросе нужно задавать второй аргумент 
пустым списком. Такой способ из-за медленности append гораздо быстрее. Он 
основан на идее разностных списков, когда список L представляется в виде 
разности списков [L|X] и X.

Грамматики, для анализа и синтеза фраз которых можно использовать 
формальное преобразование их продукций в предложения пролога, называют 
грамматиками определенных клауз (Definite Clause Grammar, DCG) или 
ОК-грамматиками. КС-языки --- это подмножество ОК-языков. ОК-грамматика 
не должна быть леворекурсивной.

Большинство реализаций пролога поддерживают упрощенный синтаксис для описания 
ОК-грамматик вторым способом. Например, рассмотренная грамматика запишется в 
виде

s --> [0,1]; [0], s, [1].

Цель

s(L,[]).

приведет к генерации всех цепочек языка, хотя, как правило, ОК-грамматики 
не используют таким образом.

Рассмотрим недетерминированной язык палиндромов на основе английского 
алфавита, грамматика которого в КС-форме несколько громоздка.

S -> e | С
С -> a | b | ... | z
S -> aSa | bSb | ... | zSz

Используя пролог, эту грамматику для любого алфавита можно записать гораздо 
компактнее. 

1)

s([]).
s([_]).
s(S) :- append([L|X],[L],S), s(X).

2)

s --> []; [_]; [L], s, [L].

Можно получать дерево вывода добавлением дополнительных аргументов-легенд, 
например, грамматика палиндромов с легендой может иметь вид

s(s(e)) --> [].
s(s(B)) --> [B].
s(s(B,S,B)) --> [B], s(S), [B].

Рассмотрим КС язык S->e|aSbS|bSaS. Его ОК-грамматика с легендой --

s(s(e)) --> [].
s(s(a,S1,b,S2)) --> [a], s(S1), [b], s(S2).
s(s(b,S1,a,S2)) --> [b], s(S1), [a], s(S2).

Запрос 

?-s(T,[a,b,a,b],[]), write(T), nl, fail. 

приведет к распечатке двух деревьев разбора -- эта грамматика неоднозначна.

s(a,s(e),b,s(a,s(e),b,s(e)))
s(a,s(b,s(e),a,s(e)),b,s(e))

Переменная T накапливает строимое дерево. Предикат s и функциональный 
символ s в легенде независимы. Таким же образом можно добавлять другие 
атрибуты. 

Используя ОК-грамматики, можно работать с контекстно-зависимыми языками. 
Рассмотрим, например, грамматику-анализатор для языка a^nb^nc^n.

s --> a(N), b(N), c(N).
a(0) --> [].
a(M) --> [a], a(N), {M is N + 1}.
b(0) --> [].
b(M) --> [b], b(N), {M is N + 1}.
c(0) --> [].
c(M) --> [c], c(N), {M is N + 1}.

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

Включение и отключение режима отладки производится предикатами trace и notrace.