Я пытаюсь написать грамматику dcg в прологе, которая будет описывать языкa^nb^n n>=0"",ab,aabb,aaabbb itd
Все, что я написал,
s --> slowo.
slowo --> [a],slowo,[b],!.
slowo --> [].
И это хорошо, пока все, что я хочу сделать, это просто проверить правильность слова, но как должна выглядеть грамматика dcg в прологе для ?-phrase(s,X), которая будет генерировать все слова из моего языка?
Если вы начинаете с Пролога, старайтесь избегать использования !/0. Как правило, вы можете обойтись без него.
Например, ваша грамматика может быть записана следующим образом:
s --> [].
s --> [a], s, [b].
и запросил следующим образом:
?- phrase(s, X).
Обратите внимание, что предложения пролога выбираются слева направо и сверху вниз, поэтому правило, написанное поверх другого, будет иметь приоритет при возврате.
once/1, если необходимо: once(phrase(s, ['a', 'b'])). или использовать phrase((s, {!}), ['a', 'b']). или что-то в этом роде. Но научиться терпеть ;fail — тоже интересный способ решить проблему :p
- person m09; 26.03.2012
В дополнение к ответу @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) найдет все ответы для этой фиксированной длины. В качестве примера посмотрите на ответ Мэта на эту грамматику.
Итак, это общий метод проверки предложений грамматики. Однако за эту общность приходится платить! Для грамматик с конечным числом предложений метод out не завершится:
:- 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**
Этот метод часто называют итеративным углублением, хотя этот термин точнее накладывает ограничение на глубина происхождения. Но мы накладываем ограничение на фактический «выход». Таким образом, итеративное углубление также может обрабатывать левую рекурсию, тогда как length/2 работает только для грамматик, которые завершаются при фиксированной длине ввода.
Что делает эту технику особенно интересной в Прологе, так это то, что она идеально сочетается с механизмом хронологического возврата Пролога.
В SWI Prolog я мог бы использовать:
s(X, []).
or
phrase(s, X).
(как вы предложили), чтобы получить все строки. Однако для того, чтобы получить какие-либо ответы без переполнения стека, мне нужно было изменить порядок двух правил для slowo и удалить вырез из рекурсивного правила.
