Prolog:将DCG语法与其他限制相结合

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

如果您不使用库(lambda),则仅需要以下内容:

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

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

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

Answer 2

好吧,你总是可以使用{}并在其间编写任何类型的prolog谓词,例如:

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

所以你可以添加某种单词计数器.当然,如果每个标记都是一个单词,你可以简单地写出如下内容:length(L,N),N <11,start(L,[]).

另一方面,根据约束的复杂性,将它们编程在不同的部分可能会更好.像编译器中的解析器 - >语义检查器.