prolog - プロローグ : DCG 文法と他の制約との結合

Question

Prolog の DCG と、特定の文法に適合するすべての可能な構造をいかに迅速に生成できるかに非常に感銘を受けました。

しかし、この検索を他の制約と組み合わせたいと思います。たとえば、複雑な文法を定義し、Prolog に 10 語以下のすべての文を生成するように依頼します。または、同じ単語を 2 回繰り返さないすべての文。

このような追加の制約を 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)}.

それでも満足できない場合は、2 つの非終端記号の交差を表現する必要があります。これは、一般的に判断できない 2 つの文脈自由言語の共通点を尋ねることと同じです。しかし、ずっと前に、終了の問題が発生します。したがって、次の点に注意してください。

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

これにより、2 つの非終端記号の交点を表現できるようになりました。ただし、ここでは終端が非常に脆弱であることに注意してください。特に、最初の非終端の終了は、必ずしも 2 番目の非終端を制限しません。

score 6 · Accepted Answer

いつでも {} を使用して、その間に任意の種類のプロローグ述語を記述できます。次に例を示します。

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

そのため、ある種の単語カウンターを追加できます。もちろん、各トークンが単語の場合、次のように簡単に記述できます: length(L,N), N<11, start(L,[])。

一方、制約の複雑さによっては、制約を別の部分にエンコードした方がよい場合があります。コンパイラの parser->semantic checker のようなもの。

2 に答える 2