处理prolog上下文无关语法

Question

鉴于CFG

S --> a S b | c | d

我想写一个谓词,如语法('S',句子),它可以产生所有可能的

sentences like
sentence=acb,
sentence=acd,
sentence=c,
sentence=ab......................

使用最左边的推导,如果遇到的符号是终端,它应该打印出该终端,如果遇到的符号是非终端 'S',它应该回溯并替换其中一个语法a S b或c或d并重复处理.

我不想要任何代码......只是帮我提一些如何开始的提示

Answer 1

让我们用DCG来编码你的语法!

s --> [a], s, [b] | [c] | [d].

?- phrase(s,Xs).
ERROR: Out of local stack

似乎此查询未终止.即Prolog的非常简单的执行策略没有找到解决方案.另一方面,想一想:你的语法描述了一组无限的句子.如果您枚举无限集,则很容易"错误地"开始.这就是Prolog在这里真正做到的.

但事情并没有那么糟糕.怎么样枚举固定长度的所有句子.我会尝试5:

?- length(Xs,5), phrase(s,Xs).
Xs = "aacbb" ;
Xs = "aadbb" ;
false.

在这种情况下,所有句子都被找到,Prolog甚至向我们保证没有其他句子.

?- length(Xs,4), phrase(s,Xs).
false.

没有长度为4的句子.

我们现在可以按长度列举所有句子.

?- length(Xs,N), phrase(s,Xs).
Xs = "c",
N = 1 ;
Xs = "d",
N = 1 ;
Xs = "acb",
N = 3 ;
Xs = "adb",
N = 3 ;
Xs = "aacbb",
N = 5 ;
Xs = "aadbb",
N = 5 ;
Xs = "aaacbbb",
N = 7

我们在这里使用了什么样的推导？老实说,我不知道,我也不在乎.重要的是要知道Prolog何时终止.在这种情况下,如果长度已知,它将终止.这就是我们需要知道的所有内容,以保证我们对无限集进行公平的枚举.事情甚至稍微好一点:s//0也会在长度不知道的情况下终止

?- Xs = [a,a,b|_], phrase(s,Xs).
false.

?- Xs = [a,a,c|_], phrase(s,Xs).
Xs = "aacbb" ;
false.

?- dif(X,Y), Xs = [X,Y|_], phrase(s,Xs).
X = a,
Y = c,
Xs = "acb" ;
X = a,
Y = d,
Xs = "adb" ;
false.

编辑:我有一些关于使用"acb"列表的顶级答案的问题[a,c,b]:请参考这个答案的解释和library(double_quotes).