プロログコンテキストフリー文法の処理

Question

CFGが与えられた

S --> a S b | c | d

のような述語を書きたい、 文法（ 's'、文） 可能なすべてを生成します

sentences like
sentence=acb,
sentence=acd,
sentence=c,
sentence=ab......................

使用 最も派生したまま, 、遭遇したシンボルがある場合 ターミナル それはその端末を印刷する必要があり、遭遇したシンボルが 非端子 「s」, 、それはバックトラックして代用する必要があり、文法の1つは a bまたはcまたはd プロセスを繰り返します。

私はコードが欲しくありません...最初のヒントを手伝ってください

Answer 1

DCGを使用して文字通り文字通りをエンコードしましょう！

s --> [a], s, [b] | [c] | [d].

?- phrase(s,Xs).
ERROR: Out of local stack

このクエリは終了しないようです。 IE Prologの非常に単純な実行戦略では、解決策が見つかりませんでした。一方、考えてみてください。あなたの文法は無限の文のセットについて説明しています。無限のセットを列挙している場合、「間違った端で」開始するのは簡単です。それがプロログが実際にここで行うことです。

しかし、物事はそれほど悪くはありません。固定長のすべての文を列挙するのはどうですか。私は5を試します：

?- length(Xs,5), phrase(s,Xs).
Xs = "aacbb" ;
Xs = "aadbb" ;
false.

この場合、すべての文が見つかり、プロログはそれ以上の文がないことを保証します。

?- length(Xs,4), phrase(s,Xs).
false.

長さ4の文はありません。

これで列挙することができます 全て 文章、 長さによって.

?- length(Xs,N), phrase(s,Xs).
Xs = "c",
N = 1 ;
Xs = "d",
N = 1 ;
Xs = "acb",
N = 3 ;
Xs = "adb",
N = 3 ;
Xs = "aacbb",
N = 5 ;
Xs = "aadbb",
N = 5 ;
Xs = "aaacbbb",
N = 7

ここでどのような派生を使用しましたか？正直なところ、私は知りませんし、気にしません。知っておくべきことは、Prologがいつ終了するかです。この場合、長さがわかっている場合は終了します。そして、私たちが持っていることを保証するために私たちが知る必要があるすべてです 公正な列挙 無限セットの。物事は少し良くなっています： s//0 長さがのように知られていない場合にも終了します

?- Xs = [a,a,b|_], phrase(s,Xs).
false.

?- Xs = [a,a,c|_], phrase(s,Xs).
Xs = "aacbb" ;
false.

?- dif(X,Y), Xs = [X,Y|_], phrase(s,Xs).
X = a,
Y = c,
Xs = "acb" ;
X = a,
Y = d,
Xs = "adb" ;
false.

編集：トップレベルの回答についていくつか質問がありました "acb" リストの場合 [a,c,b]: ：参照してください この答え 説明とに library(double_quotes).