Prolog:将 DCG 语法与其他限制相结合 [英] Prolog : Combining DCG grammars with other restrictions

问题描述

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

I'm very impressed by Prolog's DCG and how quickly I can produce all the possible structures that fit a particular grammar.

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

But I'd like to combine this search with other constraints. For example, define a complex grammar and ask Prolog to generate all sentences with not more than 10 words. Or all sentences that don't repeat the same word twice.

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

Is it possible to add extra constraints like this to a DCG grammer? Or do I basically have to translate the DCG back into normal Prolog clauses and start modifying them?

推荐答案

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

If you only want to see all sentences that are generated, it is very convenient to use the following:

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

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

Of course that generates all sentences. But it is very useful and it saves you the time to think of a concrete limit. If you want to restrict that further, add the goal between(0,10,N) in front.

如果你想在语法中说某个非终结符应该占用一定的长度，最好明确地说出来:

If you want to say within a grammar, that a certain non-terminal should take a certain length, it is best to say this explicitly:

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

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

如果你还是不开心，那么你想表达两个非终结符的交集.这无异于询问两种上下文无关语言的交集，这在一般情况下是不可判定的.但在更早的时候，您将遇到终止问题.因此请注意以下内容:

If you are still not happy, then you want to express the intersection of two non-terminals. This is tantamount to asking the intersection of two context free languages which is in the general case undecidable. But much earlier, you will have problems with termination. So be aware of that in what follows:

:- op( 950, xfx, &).

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

仅当您不使用 library(λ):

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

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

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

So this permits you now to express the intersection of two non-terminals. But please, be aware that termination is very brittle here. In particular, the termination of the first non-terminal does not necessarily limit the second.

这篇关于Prolog:将 DCG 语法与其他限制相结合的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！