prolog - 特定の文脈自由文法の記号（文）の文字列を生成する

Question

私は次のような簡単な文法を持っています

S::=a S b
S::=[] (empty string)

今、私は上記の文法のためのパーサーを次のように書きたいです

cfg('S', [a,'S',b])

これは、左端の派生によって文aaabbbを生成します。

私はプロローグでdcg/cfgを処理するのに十分ではありません。したがって、plsはこの例で私を助けてくれるので、先に進んでもっと大きなことを試すことができます。

Answer 1

このDCGコードを検討してください。

s-->[].
s-->[a],s,[b].

DCGで定義した述語を実行するには、最後に「入力」とその残りの2つの引数を追加する必要があります。リスト全体を認識したい場合は、[]を入力するだけです。したがって、実行すると次のようになります。

38 ?- s(C,[]).
C = [] ;
C = [a, b] ;
C = [a, a, b, b] ;
C = [a, a, a, b, b, b] ;
C = [a, a, a, a, b, b, b, b] ;
...

ある種の「戻り」文字列が必要な場合は、それを追加の引数として追加できます。dcg句にプロローグコードを書くには、{}を使用します。

s('')-->[].
s(S)-->
    [a],s(SI),[b],
    { atomic_list_concat([a,SI,b],S)}.

そしてあなたは得る：

40 ?- s(R,X,[]).
R = '',
X = [] ;
R = ab,
X = [a, b] ;
R = aabb,
X = [a, a, b, b] ;
R = aaabbb,
X = [a, a, a, b, b, b] ;
R = aaaabbbb,
X = [a, a, a, a, b, b, b, b] ;
R = aaaaabbbbb,
...

この文法で認識されるすべての文字列を生成しました。通常、文字列が文法によって認識されるかどうかを確認したいだけです。これを行うには、入力として入力するだけです。

41 ?- s([a,b],[]).
true 

42 ?- s([a,b,b],[]).
false.

S :: = []ルールを最初に置くことに注意してください。そうしないと、すべてのソリューションを生成するように要求した場合、プロローグは無限ループに陥ります。この問題は、より複雑な文法で解決するのは簡単ではないかもしれません。ソリューションを取得するには、length/2を使用できます。

?- length(X,_),s(X,[]).
X = [] ;
X = [a, b] ;
X = [a, a, b, b] ;
X = [a, a, a, b, b, b] ;
X = [a, a, a, a, b, b, b, b] 

コードが次の場合でも：

s-->[].
s-->[a],s,[b].