Prolog DCG генерируя все слова из языка

Question

Я пытаюсь написать некоторые DCG грамматику в прологе, который будет описывать язык
a^nb^n n>=0
"",ab,aabb,aaabbb itd

Все, что я написал это

s --> slowo. 
slowo --> [a],slowo,[b],!. 
slowo --> []. 

И его хорошо, пока все, что я хочу сделать, это просто проверить правильность слова, но как должна выглядеть грамматика dcg в прологе для ?-phrase(s,X), которая будет генерировать все слова с моего языка?

Answer 1

Если вы начинаете с Пролога, старайтесь избегать использования !/0. Вы можете вообще сделать лучше без него.

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

s --> []. 
s --> [a], s, [b]. 

и запрашиваются следующим образом:

?- phrase(s, X). 

Обратите внимание, что пролога пункты выбраны слева направо и сверху вниз, поэтому правило, написанное в верхней части другого, будет приоритетным, если будет задействовано обратное отслеживание.

Answer 2

В SWI Prolog, я мог бы использовать:

s(X, []). 

или

phrase(s, X). 

(как вы предложили), чтобы получить все строки. Однако для того, чтобы для получения любых ответов без переполнения стека, мне нужно было отменить порядок двух правил для slowo и удалить разрез из рекурсивного правила.

Answer 3

В дополнение к @ ответ MOG, давайте рассмотрим более общий случай:

Что, если грамматика настолько сложна, что переназначения DCG-правила не помогут? Как мы можем все еще перечислять все предложения? Если грамматика сформулирована таким образом, что она оканчивается на фиксированную длину, мы получаем все предложения с

?- length(Xs, N), phrase(s, Xs). 

Целью length только будет перечислять все списки справедливым образом. То есть, начиная с самой короткой [] всех списки перечисляются:

 
?- length(Xs, N). 
Xs = [], 
N = 0 ; 
Xs = [_G307], 
N = 1 ; 
Xs = [_G307, _G310], 
N = 2 ; 
Xs = [_G307, _G310, _G313], 
N = 3 ; 
Xs = [_G307, _G310, _G313, _G316], 
N = 4 ; ... 

И теперь, длина фиксируется, цель phrase(s, Xs) найти все ответы на эту фиксированную длину. В качестве примера посмотрим на ответ Матса на this grammar.

Так что это общий метод проверки предложений грамматики. Однако - есть такая цена, чтобы заплатить за эту общность!Для грамматик с конечным числом предложений, из метода не прекращается:

:- use_module(library(double_quotes)).

s --> "a"|"b".

 
?- phrase(s, Xs). 
Xs = "a" ; 
Xs = "b". 

Эта грамматика работает из коробки, но вместе с length/2 мы получаем в настоящее время:

?- length(Xs, N),phrase(s, Xs). 
Xs = "a", 
N = 1 ; 
Xs = "b", 
N = 1 ; 
**loops** 

Этот метод часто называют iterative deepening, хотя этот термин более точно налагает привязку к глубине вывода. Но мы навязываем привязку к фактическому «выходу». Таким образом, итеративное углубление также способно обрабатывать левую рекурсию, тогда как length/2 работает только для грамматик, которые заканчиваются для фиксированной входной длины.

Что делает эту технику особенно интересной в Prolog, так это то, что она идеально сочетается с хронологическим механизмом обратного отслеживания Prolog.