序言: Combining DCG grammars with other restrictions

Question

Prolog的DCG给我留下了很深刻的印象，我能以多快的速度产生适合特定语法的所有可能的结构。

但我想将此搜索与其他约束条件结合起来。例如，定义一个复杂的语法，并要求Prolog生成不超过10个单词的所有句子。或所有不重复同一单词两次的句子。

是否可以在DCG语法器中添加类似这样的额外约束？还是我基本上必须将DCG转换回普通的Prolog子句并开始对其进行修改？

Answer 1

如果只想查看所有生成的句子，则使用以下命令非常方便:

?- length(Xs, N), phrase(mynonterminal, Xs).

当然会生成所有句子。但这非常有用，它可以节省您思考具体限制的时间。如果您想进一步限制目标，请在前面添加目标between(0,10,N)。

如果要在语法中说某个非终结符应占一定长度，则最好明确地说出这一点:

seq([]) --> [].
seq([E|Es]) --> [E], seq(Es).

a --> {length(Es,10)}, seq(Es), {phrase(mynonterminal,Es)}.

如果您仍然不满意，那么您想表达两个非终端的交集。这相当于询问两种上下文无关语言的交集，这在一般情况下是无法确定的。但是，更早之前，您将遇到终止问题。因此，请注意以下内容:

:- op( 950, xfx, &).

(NT1 & NT2) -->
     call(Xs0^Xs^(phrase(NT1,Xs0,Xs),phrase(NT2,Xs0,Xs))).

仅在不使用library(lambda)时才需要以下内容:

^(V0, Goal, V0, V) :-
      call(Goal,V).

^(V, Goal, V) :-
     call(Goal).

因此，这现在允许您表达两个非终端的交集。但是请注意，此处的终止非常脆弱。特别地，第一非终端的终止不一定限制第二非终端。