9

Prolog の文脈自由文法に関するこのチュートリアルを読んでいます。ページの下部で、Prolog の文脈自由文法を差分リストを使用して実装することに言及しており、次のコード ブロックが含まれています。

s(X,Z):-  np(X,Y),  vp(Y,Z). 

np(X,Z):-  det(X,Y),  n(Y,Z). 

vp(X,Z):-    v(X,Y),  np(Y,Z). 
vp(X,Z):-    v(X,Z). 

det([the|W],W). 
det([a|W],W). 

n([woman|W],W). 
n([man|W],W). 

v([shoots|W],W).

それは言及しています：

これらのルールを慎重に検討してください。たとえば、 s ルールは次のように述べています。 (1) X を消費して Y を残すことができ、 X と Y のペアが名詞句を表し、(2)次に、Z を残して Y を消費することができます。ペア YZ は動詞句を表します。np ルールと 2 番目の vp ルールは同様に機能します。

と

最初のリストは消費する必要があるもの (または必要に応じて入力リスト) と考え、2 番目のリストは残すもの (または出力リスト) と考えてください。この（むしろ手続き的な）観点から見ると、違いのリスト

[a,woman,shoots,a,man]  [].

は、女性が男性を撃つ文を表しています。なぜなら、次のように書かれているからです。左側のすべての記号を消費し、右側の記号を残す場合、私は興味のある文を持っています。つまり、私たちが興味を持っている文です。は、これら 2 つのリストの内容の違いです。

レコグナイザーを書き直すために違いリストについて知っておく必要があるのはこれだけです。何かを消費し、何かを置き去りにするという考えを単純に心に留めると、次の認識子が得られます。

説明として、しかし、それは私にこのコードを明確にするために何もしていません. を使用するよりも効率的であることは理解していますappend/3が、ものを消費して他のものを置き去りにするという概念に関しては、以前のappend/3実装よりもはるかに混乱しているようで、頭も尻尾もできません。さらに、そのコードをコピーしてProlog ビジュアライザーに貼り付けて理解しようとすると、ビジュアライザーにエラーがあると表示されます。誰かがこれに光を当てることができますか?

4

4 に答える 4

2

この回答は、@mat による回答のフォローアップです。ステップバイステップで進みましょう：

  1. @mat の回答に示されているコードから始めます。

    s --> np、vp。

np --> det, n.

vp --> v, np.
vp --> v.

det --> [the]。
詳細 --> [a]。

n --> [女性].
n --> [男].

v --> [シュート]。

  2. これまで、(',')/2:(A,B)はシーケンスのA後にシーケンスが続くBことを意味します。

    次に、('|')/2:(A|B)はシーケンスAまたはシーケンスBを意味します。

    文法本体の制御構文については、このマニュアルのセクションをお読みください。

    s --> np、vp。

np --> det, n.

vp --> v, np | v。

det --> [the] | [a]。

n --> [女性] | [男]。

v --> [シュート]。

  3. 少し「インライン化」することで、コードをより簡潔にすることができます。

    s --> np、vp。

np --> ([the] | [a]), ([woman] | [man]).

vp --> v,np | v。

v --> [シュート]。

  4. @mat のコメントで提案されているように、さらにインライン化はどうですか...

    s --> np, [シュート], (np | []).

np --> ([the] | [a]), ([woman] | [man]).

  5. それを最大限に活用してください！(以下は、ワンライナーとして記述できます。)

    ?- フレーズ((( [the]
           | | [女性]
                   | | [男])、[シュート]、( ( [ザ]
                                         | | [女性]
                                                 | | [男]）
                                       | | [])))、
          WS)。

たとえば、非常にコンパクトなコードは拡張が難しくなりますが、プレゼンテーション スライドにコードを配置する場合など、スペースが不足している場合に必要になる場合があります。

サンプルクエリ:

?- phrase(s,Ws).
  Ws = [the, woman, shoots, the, woman]
; Ws = [the, woman, shoots, the, man]
; Ws = [the, woman, shoots, a, woman]
; Ws = [the, woman, shoots, a, man]
; Ws = [the, woman, shoots]
; Ws = [the, man, shoots, the, woman]
; Ws = [the, man, shoots, the, man]
; Ws = [the, man, shoots, a, woman]
; Ws = [the, man, shoots, a, man]
; Ws = [the, man, shoots]
; Ws = [a, woman, shoots, the, woman]
; Ws = [a, woman, shoots, the, man]
; Ws = [a, woman, shoots, a, woman]
; Ws = [a, woman, shoots, a, man]
; Ws = [a, woman, shoots]
; Ws = [a, man, shoots, the, woman]
; Ws = [a, man, shoots, the, man]
; Ws = [a, man, shoots, a, woman]
; Ws = [a, man, shoots, a, man]
; Ws = [a, man, shoots].                  % 20 solutions
于 2015-09-28T21:16:50.663 に答える
1

私はあなたが何を意味するかを正確に知っています。リストの違いについて考えるのは、最初はかなり難しいです。幸いなことに、通常はこれを行う必要はありません。

Definite Clause Grammars (DCG) と呼ばれる組み込みの形式があり、あなたのような場合にリストの違いを手動でエンコードする必要はまったくありません。

あなたの例では、これを次のように書くことをお勧めします。

s --> np, vp.

np --> det, n.

vp --> v, np.
vp --> v.

det --> [the].
det --> [a].

n --> [woman].
n --> [man].

v --> [shoots].

[T]DCG 内では、端末Tを表し、 ,「and then」と読まれるという事実を受け入れます。これが、DCG を使用したリストの記述方法です。

phrase/2DCGへのインターフェースを使用して、これを使用してすべてのソリューションを求めることができます。

?- phrase(s, Ls).
Ls = [the, woman, shoots, the, woman] ;
Ls = [the, woman, shoots, the, man] ;
Ls = [the, woman, shoots, a, woman] ;
etc.

最初はこれを手続き的に理解するのは難しいので、これを試さないことをお勧めします。代わりに、文法の宣言的な読み方に焦点を当て、それがリストを記述していることを確認してください。

後で、実装の詳細に進むことができます。単純な端末がどのように変換されるかから始めて、より高度な文法構成に進みます。つまり、単一の端末を含む規則、次に端末と非端末を含む規則などです。

于 2015-09-28T20:07:56.083 に答える