1

の言語を説明するプロローグに dcg 文法を書き込もうとしています
a^nb^n n>=0
"",ab,aabb,aaabbb itd

私が書いたものはすべて、

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

そして、私がやりたいことは単語が正しいかどうかをチェックすることだけである限り、それは良いことですが?-phrase(s,X)、私の言語からすべての単語を生成するプロローグで dcg 文法はどのように見えるべきですか?

4

3 に答える 3

5

@Mogの答えに加えて、より一般的なケースを考えてみましょう：

文法が非常に複雑で、DCG ルールを並べ替えても役に立たない場合はどうすればよいでしょうか? どうすればすべての文を列挙できますか? 文法が固定長で終わるように定式化されている場合、すべての文は次のようになります。

?-長さ (Xs、N)、句 (s、Xs)。

ゴールlengthだけで、すべてのリストが公平に列挙されます。つまり、最短のものから始めて、[]すべてのリストが列挙されます。

?-長さ (Xs, N)。
Xs = []、
N = 0;
Xs = [_G307]、
N = 1;
Xs = [_G307、_G310]、
N = 2;
Xs = [_G307、_G310、_G313]、
N = 3;
Xs = [_G307、_G310、_G313、_G316]、
N = 4; ...

そして今、長さが固定されているので、ゴールphrase(s, Xs)はその固定長に対するすべての答えを見つけます。例として、この文法に対するマットの回答を見てください。

したがって、これは文法の文を検査するための一般的な方法です。ただし、この一般性には代償が伴います。有限数の文を持つ文法の場合、 out メソッドは終了しません:

:- use_module(library(double_quotes)).

s --> "a"|"b".

?-句 (複数可、X)。
Xs = "a" ;
Xs = "b".

この文法はすぐに使用できますが、一緒に使用すると、次のlength/2ようになります。

?-長さ(Xs, N),句(s, Xs).
Xs = "a",
N = 1;
Xs = "b",
N = 1;
**ループ**

この方法はしばしば反復深化と呼ばれますが、この用語はより正確には導出の深さに制限を課します。しかし、実際の「出力」に制限を課しています。したがって、反復深化は左再帰も処理できlength/2 ますが、固定入力長で終了する文法に対してのみ機能します。

この手法が Prolog で特に興味深いのは、Prolog の時系列バックトラッキング メカニズムと完全に一致することです。

于 2012-03-26T20:30:02.560 に答える
3

Prolog を使い始めている場合は、!/0. 通常、それがなくてもうまくいくことができます。

たとえば、文法は次のように記述できます。

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

次のようにクエリされます。

?- phrase(s, X).

プロローグ句は左から右、上から下に選択されるため、バックトラッキングが関係する場合、別のルールの上に書かれたルールが優先されることに注意してください。

于 2012-03-25T22:37:04.560 に答える
2

SWI Prologでは、次を使用できます。

s(X, []).

また

phrase(s, X).

（あなたが提案したように）すべての文字列を取得します。ただし、スタックオーバーフローなしで回答を生成するには、2つのルールの順序を逆にしてslowo、再帰ルールからカットを削除する必要がありました。

于 2012-03-25T22:30:03.203 に答える