DCG (Definite Clause Grammars) -
грамматики определяющих предложений

Содержание раздела

Введение и пример

Нотация DC-грамматик в Прологе

Вызов DC-грамматики

Вывод в DC-грамматике. Ограничения на грамматики

Пример 3: арифметические выражения

Трансляция DC-грамматик

Введение и пример

DC-грамматики были введены в Пролог в 1980 году Ф. Перейрой и Д. Уорреном как расширение КС-грамматик, в котором терминальные и нетерминальные символы грамматики могут иметь параметры, определяющие значения соответствующих атрибутов в узлах дерева вывода. Параметры являются произвольными термами и могут содержать переменные, которые получают значения в процессе грамматического вывода с помощью того же механизма унификации, что и в Прологе. Добавление параметров делает DC-грамматики более мощным механизмом порождения языков, чем КС-грамматики. Они порождают любые рекурсивно-перечислимые языки, т.е. эквивалентны грамматикам Хомского общего вида (типа 0).

Пример 1: Язык {aⁿbⁿcⁿ | n≥0} порождается DC-грамматикой с нетерминальными символами abc, a(_), d(_) и с(_) и правилами, записанными в нотации, принятой в Прологе:

abc --> a(N),b(N),c(N). 
	% Переменная N определяет число символов,
	% порождаемых нетерминалами a, b и c,
	% а правило требует, чтобы они порождали
	% одинаковое число символов.

% Следующие правила задают способ подсчёта числа символов.

a(0) --> "". 
	% Справа - пустая терминальная цепочка.
a(N+1) --> "a",a(N). 
	% В кавычках - терминальная цепочка.
b(0) --> "".
b(N+1) --> "b",b(N).
c(0) --> "".
c(N+1) --> "c",c(N).

Дерево вывода цепочки "aabbcc" имеет вид:

Оно получается следующим левым выводом:

	abc --> 
(1) 	a(N),b(N),c(N) --> 		% a(N)=a(0) при N=0
(2) 	b(0),c(0) --> c(0) --> "" 	% Ошибка вызывает возврат к (1)
	a(N),b(N),c(N) --> 		% a(N)=a(М+1) при N=М+1
(2') 	"a",a(M),b(N),c(N) --> 		% M=0, N=0+1
(3) 	"a",b(0+1),c(0+1) 		% --> "ab",b(0),c(0+1) - ошибка,
					% возврат к (2')
	"a",a(M),b(N),c(N) --> 		% M=P+1, N=P+1+1
(3') 	"aa",a(P),b(N),c(N) --> 	% a(P)=a(0) при P=0 (и N=0+1+1)
	"aa",b(0+1+1),c(0+1+1) --> 	% Дальше однозначно
	"aab",b(0+1),c(0+1+1) --> 
	"aabb",b(0),c(0+1+1) -->
	"aabb",c(0+1+1) --> 
	"aabbc",c(0+1) -->
	"aabbcc",c(0) --> "aabbcc" 	% Успешное завершение вывода

В DC-грамматике можно использовать любые встроенные предикаты Пролога. Они играют роль семантических процедур при синтаксически управляемой трансляции. Кроме того, роль семантических процедур могут играть нетерминальные символы, не зависящие от терминальных (они могут порождать только пустые терминальные цепочки). Такие нетерминалы (с возможными параметрами) являются обычными прологовскими предикатами, а правила для них можно записывать как обычные правила Пролога.

Нотация DC-грамматик в Прологе

Правило грамматики - это терм специального вида:

<левая часть> --> <правая часть>.

Левая часть правила - произвольная структура, функтор которой (возможно, 0-местный) не является встроенным предикатом. Он называется нетерминальным символом.

Правая часть правила - непустая последовательность элементов, разделяемых запятой (,) или точкой с запятой (;). Запятая играет роль конкатенации и конъюнкции, а точка с запятой - разделителя альтернатив и дизъюнкции.

Элементом правой части может быть:

нетерминальный символ (с параметрами, как в левой части),
терминальная цепочка,
семантический терм.

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

Терминальный символ - ASCII-код символа или структура, функтор которой (возможно, 0-местный) не является встроенным или определённым какими-нибудь правилами. Список ASCII-кодов может быть заменён цепочкой соответствующих символов, взятой в кавычки ("...").

Семантический терм - произвольный прологовский терм, взятый в фигурные скобки ({...}). Представляет собой обычную прологовскую цель, которая должна быть доказана по обычным правилам Пролога.

Пример 2. Другой вариант предыдущей грамматики:

abc --> a(N),b(N),c(N). 
 	% Подсчитывается количество символов "а"
a(N) --> [a],a(N1),{N is N1+1}.
a(0) --> "".
 	% Проверяется, что символов "b" и "c" 
	% столько же, сколько "а"
b(0) --> "".
b(N) --> [b],{N1 is N-1},b(N1).
c(0) --> "".
c(N) --> [c],{N1 is N-1},c(N1).

Замечание. Здесь терминалы уже не символы, а атомы. Важен также порядок правил.

Вызов DC-грамматики

Для вызова DC-грамматики используются нетерминальные символы в качестве прологовской цели.

Если правило грамматики имеет вид

p(t₁,...,t_n) --> ...,

то соответствующая цель должна иметь вид

p(s₁,...,s_n,in,out),

где in - входная терминальная цепочка, а out - выходная, полученная после удаления из in начала, распознанного нетерминальным p.

Так, в первом из предыдущих примеров цель может иметь, например, вид

abc("aabbcc",""), или abc("abcabc","abc") - обе с ответом yes,

или a(N,"aabbb",X) с ответом N=2, X=[98,98,98] (т.е. X="bbb"),

или b(2,In,"") с ответом In=[98,98].

Во втором примере в этих целях параметр "aabbcc" нужно заменить на [a,a,b,b,c,c] и т.д.

Вывод в DC-грамматике. Ограничения на грамматики

Вывод в грамматике ведётся Прологом его обычным методом (механизм использования дополнительных параметров in и out будет рассмотрен позже, т.к. его понимание нужно только при трассировке вывода в отладчике).

Таким образом, Пролог осуществляет нисходящий анализ с неограниченным возвратом. Отсюда следует и единственное ограничение:

В грамматике не должно быть левой рекурсии.

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

Пример 3: арифметические выражения

За основу возьмём стандартную КС-грамматику арифметических выражений (в нотации DC-грамматик):

expr --> term,terms.
term --> factor,factors.
factor --> [i(I)] ; 	% терминал "идентификатор"
	   [n(N)] ; 	% терминал "число"
	   "(",expr,")".
terms --> "+",term,terms ;
	  "-",term,terms ;
	  "".
factors --> "*",factor,factors ;
	    "/",factor,factors ;
	    "".

Параметры I и N позволяют (в отличие от КС-грамматик) включать в терминальную цепочку конкретные идентификаторы и числа. Для распознавания выражения (3-x)*y можно использовать цель

expr([`(,n(3),`-,i(x),`),`*,i(y)],"").

Идентификаторам (переменным) можно присвоить числовые значения, записав в базу данных предикаты типа val(x,5). Грамматику же можно модифицировать так, чтобы она не только проверяла правильность выражений, но и вычисляла их значение:

expr(E) --> 
	term(T),terms(T,E).
	% E - значение выражения, а T - слагаемого
term(T) --> 
	factor(F),factors(F,T). 
	% F - значение сомножителя
factor(N) --> 
	[i(I)],{val(I,N)} ;
	[n(N)] ;
	"(",expr(N),")".
terms(T1,N) --> 
	"+",term(T2),{T is T1+T2},terms(T,N) ;
	"-",term(T2),{T is T1-T2},terms(T,N).
terms(N,N) --> 
	"".
factors(F1,N) --> 
	"*",factor(F2),{F is F1*F2},factors(F,N) ;
	"/",factor(F2),{F is F1/F2},factors(F,N).
factors(N,N) --> 
	"".

Добавив правила для значений переменных

val(x,5). 
val(y,-3).

получим полную систему для вычисления любого выражения с переменными x и y.

Трансляция DC-грамматик

Правила DC-грамматик транслируются системой в обычные правила Пролога. При трассировке вывода в грамматике мы видим на самом деле вывод по правила, полученным при трансляции. Для облегчения процесса отладки следует знать простые принципы трансляции:

Нетерминалp(t₁,...,t_n) транслируется в предикат
p(t₁,...,t_n,In,Out),где In - входная терминальная цепочка, а Out - выходная, полученная после удаления из In начала, распознанного предикатом p. Отсюда следуют пп. 2 и 3.
При отсутствии непустых терминальных цепочек и семантических термов связь между In и Out следующая:
- ```
p(...) --> "". ==> p(...,In,In).
```
- ```
p(...) --> p₁(...),...,p_n(...). ==> 
p(...,In,Out):- p₁(...,In,Out₁),...,p_n(...,In_n,Out).
и Out_i=In_i+1 для 0<i<n.
```
Все терминальные цепочки "втягиваются" в параметры In или Out предыдущего нетерминала следующим образом (T - терминальная цепочка):

```
p(...) --> [T]. ==> p(...,[T|Out],Out).
```

p(...) --> [T],p₁(...)... ==> 
p(...,[T|In₁],Out):- p₁(...,In₁,Out₁)...

...p_i(...),[T],p_i+1(...)... ==>
...p_i(...,In_i,[T|In_i+1]),p_i+1(...,In_i+1,Out_i+1)...

p(...) --> ...p_n(...),[T]. ==>
p(...,In,Out):- ...p_n(...,In_n,[T|Out]}.

Фигурные скобки в семантических термах опускаются.

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

expr(E,In,Out):- 
	term(T,In,Out1),
	terms(T,E,Out1,Out).
term(T,In,Out):- 
	factor(F,In,Out1),
	factors(F,T,Out1,Out).
factor(N,[i(I)|Out],Out):- 
	val(I,N).
factor(N,[n(N)|Out],Out).
factor(N,[`(|In1],Out):- 
	expr(N,In1,[`)|Out1]).
terms(T1,N,[`+|In1],Out):- 
	term(T2,In1,Out1),T is T1+T2,
	terms(T,N,Out1,Out).
terms(T1,N,[`-|In1],Out):- 
	term(T2,In1,Out1),T is T1-T2,
	terms(T,N,Out1,Out).
terms(N,N,In,In).
factors(F1,N,[`*|In1],Out):- 
	factor(F2,In1,Out1),F is F1*F2,
	factors(F,N,Out1,Out).
factors(F1,N,[`/|In1],Out):- 
	factor(F2,In1,Out1),F is F1/F2,
	factors(F,N,Out1,Out).
factors(N,N,In,In).

DCG (Definite Clause Grammars) - грамматики определяющих предложений