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

仅当您不使用库( lambda):

^(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屋！