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 的时间顺序回溯机制完美结合。