prolog - Prolog dcg 从语言中生成所有单词

Question

我正在尝试在 prolog 中编写一些 dcg 语法来描述
a^nb^n n>=0
"",ab,aabb,aaabbb itd

我写的都是

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

只要我想做的只是检查单词是否正确，它就很好，但是 dcg 语法应该如何在 prolog 中查看?-phrase(s,X)它将从我的语言中生成所有单词？

Answer 1

除了@Mog 的回答，让我们考虑更一般的情况：

什么，如果语法如此复杂，重新排序 DCG 规则将无济于事？我们怎么还能枚举所有的句子呢？如果语法以这样一种方式表达，它以固定长度终止，我们得到所有句子

?-长度（Xs，N），短语（s，Xs）。

仅此目标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)将找到该固定长度的所有答案。例如，看看 Mat 对这个语法的回答。

所以这是检查语法句子的一般方法。然而——这种普遍性是要付出代价的！对于具有有限多个句子的语法，out 方法不会终止：

:- use_module(library(double_quotes)).

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

?-短语(s, Xs)。
Xs = "a" ;
Xs = "b"。

这个语法开箱即用，但length/2我们现在得到：

?-长度（Xs，N），短语（s，Xs）。
Xs = "a",
N = 1 ;
Xs = "b",
N = 1 ;
**循环**

这种方法通常被称为迭代深化，尽管这个术语更精确地对推导的深度施加了限制。但是我们对实际的“输出”施加了约束。因此迭代深化也能够处理左递归，而length/2 仅适用于以固定输入长度终止的语法。

使这项技术在 Prolog 中特别有趣的原因在于它与 Prolog 的时间回溯机制完美结合。

Answer 2

如果您从 Prolog 开始，请尽量避免使用!/0. 没有它，您通常可以做得更好。

例如，你的语法可以写成如下：

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

并查询如下：

?- phrase(s, X).

请注意，序言子句是从左到右和从上到下挑选的，因此在涉及回溯时，将优先考虑写在另一个顶部的规则。

Answer 3

在 SWI Prolog 中，我可以使用：

s(X, []).

或者

phrase(s, X).

（如您所建议）获取所有字符串。然而，为了在没有堆栈溢出的情况下产生任何答案，我需要颠倒两个规则的顺序slowo并从递归规则中删除切割。