3

I ran into an infinite recursion problem while trying to implement a very simple constraint free grammar in prolog.

Here are my rules: (vp -> verb phrase, np -> noun phrase, ap -> adj phrase, pp -> prep phrase)

    verb(S) :- member(S, [put,  pickup, stack, unstack]).
    det(S) :- member(S, [the]).
    adj(S) :- member(S, [big, small, green, red, yellow, blue]).
    noun(S) :- member(S, [block, table]).
    prep(S) :- member(S, [on, from]).

    vp([V|R]) :- verb(V), pp(PP), np(NP), append(NP, PP, R).
    np([D, N]) :- det(D), noun(N).
    np([D|R]) :- det(D), ap(AP), noun(N), append(AP, [N], R).
    ap([A]) :- adj(A).
    ap([A|R]) :- adj(A), ap(R).
    pp([P|R]) :- prep(P), np(R).

The problem im running into is that the rule for ap can produce arbitrarily long strings of adjectives, so at some point, i get stuck trying to satisfy the query by trying all these infinite possibilities.

For example, the following query will never produce S = [put, the, red, block, on, the, green, block] because it will first expand the adjective phrase on the left "red" to infinite possibilities before ever trying on the right.

?- vp(S)
S = [put, the, red, green, block, on, the, block] ;
4

3 に答える 3

5

簡単な答えは次のとおりです。文法を表すには、定款文法 ( ) を使用します。典型的なエンコーディングについては、この回答を参照してください。

しかし、今あなたのプログラムの実際の問題に。望む答えが得られないだけではありません。状況はもっと悪いです: プログラムのより単純な部分でさえ、まったく同じ問題を抱えています。これは、まだ終了していないプログラムの最小のフラグメントです。

動詞 (S) :- メンバー (S、[置く、ピックアップ、スタック、アンスタック])。
det(S) :- member(S, [the])。
adj(S) :- メンバー(S、[大きい、小さい、緑、赤、黄、青])。
名詞(S) :- false , member(S, [ブロック, テーブル]) .
prep(S) :- member(S, [on, from]).

vp([V|R]) :- 動詞(V), pp(PP), false , np(NP), append(NP, PP, R) .
np([D, N]) :- false , det(D), noun(N) .
np([D|R]) :- det(D), ap(AP), false , noun(N), append(AP, [N], R) .
ap([A]) :- false , adj(A) .
ap([A|R]) :- adj(A), ap(R), false .
pp([P|R]) :- prep(P), np(R), false .

?- vp([プット、ザ、レッド、グリーン、ブロック、オン、ザ、ブロック])。

目標falseを挿入することで、まだ終了していないプログラムの小さな断片を取得しました。実際のソースはap/1再帰的ですが、実際の入力によって制限されません。を参照してください。

プログラムを修正する簡単な方法はありません。最も簡単な方法は、文法を使用することです。

于 2013-03-27T21:10:18.567 に答える
0

あなたはPrologの生成力を悪用しているようで、追加を最後の位置に配置しています。私はより賢明な場所に変更しようとしました:

...
vp([V|R]) :- verb(V), append(NP, PP, R), pp(PP), np(NP).
np([D, N]) :- det(D), noun(N).
np([D|R]) :- det(D), append(AP, [N], R), ap(AP), noun(N).
...

そして今、あなたのパーサーは明らかに動作します。

?- vp([put, the, red, green, block, on, the, block]).
true .

しかし、すでにfalseが（+1）したように、解析のためにDCGに切り替えることをお勧めします。

于 2013-03-28T07:44:02.947 に答える
0

根本的な問題は、Prolog がルールに対して DFS を実行するように定義されているため、無限の探索空間全体での生成の問題になると (あなたの場合のように)、空間の一部が手付かずになる可能性があることです。プラットフォームに依存しない修正は、深さの境界で文法を拡張し、再帰呼び出しごとに深さを減らすことです。深度が 0 になると、失敗します。クエリを繰り返して深さを段階的に増やすことで (例: vp(S, 1). vp(S, 2).)、状態空間のすべての部分が最終的に処理されることが保証されます。

これは基本的に反復的な深化です。SWI-PL を使用している場合は、call_with_depth_limit/3述語を使用して、文法を変更せずにまったく同じことを行うこともできます。

于 2014-06-23T06:38:59.880 に答える