prolog - Prolog：将 DCG 语法与其他限制相结合

Question

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

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

是否可以将这样的额外约束添加到 DCG 语法？还是我基本上必须将 DCG 翻译回正常的 Prolog 子句并开始修改它们？

score 8 · Accepted Answer

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

?- 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).

所以这允许你现在表达两个非终结符的交集。但是请注意，这里的终止非常脆弱。特别地，第一个非终结符的终止不一定限制第二个非终结符。

score 6 · Accepted Answer

好吧，您总是可以使用 {} 并在两者之间编写任何类型的 prolog 谓词，例如：

foo(X)-->
    { valid(X) },
    [a].
foo(X)-->
    [b].

所以你可以添加某种字数计数器。当然，如果每个标记都是一个单词，你可以简单地写成：length(L,N), N<11, start(L,[])。

另一方面，根据约束的复杂性，将它们编码到不同的部分可能会更好。编译器中的 parser->semantic checker 之类的东西。

2 回答 2