3

与えられたCFG

S --> a S b | c | d

可能なすべてを生成するgrammar（'S'、sentence）のような述語を書きたい

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

左端の派生を使用して、検出された記号が終端記号である場合はその終端記号を出力し、検出された記号が非終端 記号'S'である場合は、バックトラックして置換し、文法の1つa S bまたはcまたはdを繰り返して、処理する。

コードは必要ありません...開始方法のヒントを教えてください

4

1 に答える 1

8

DCG を使用して文法を文字どおりにエンコードしましょう。

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

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

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

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

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

この場合、すべての文が検出され、Prolog はそれ以上の文がないことを保証します。

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

于 2011-11-30T20:57:25.380 に答える