Prolog DCG генерирует все слова из языка - PullRequest
Новая
       28

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

0 голосов
/ 26 марта 2012

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

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

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

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

Ответы [ 3 ]

4 голосов
/ 27 марта 2012

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

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

?- <b>length(Xs, N), phrase(s, Xs).</b>

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

?- <b>length(Xs, N).</b>
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) найдет все ответы для этой фиксированной длины. Как пример, посмотрите на ответ Мата на эту грамматику .

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

:- use_module(library(double_quotes)).

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

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

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

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

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

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

2 голосов
/ 26 марта 2012

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

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

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

и иметь следующий запрос: 

?- phrase(s, X).

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

2 голосов
/ 26 марта 2012

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

s(X, []).

или 

phrase(s, X).

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

...