3

{a、b、c、d} *の形式の文字列のセットを受け取るdcgを実装しようとしています。問題は、s（[a、c、b]、 []）、正しい答えであるtrueを返しますが、s（[a、c、f]、[]）の形式のクエリがある場合、答えを返さず、ローカルスタックが不足します。

s --> [].
s --> s,num.
num --> [a].
num--> [b].
num--> [c].
num--> [d].
4

2 に答える 2

9

使用するphrase/2

phrase(s,[a,b,c])の代わりに試してみましょうs([a,b,c],[])。理由は非常に単純です。このようにして、通常の述語ではなくDCG（ phrase/2文法への「公式」インターフェースです。

したがって、最初の質問は、あなたが言うように、「正しい答えを与える」間、なぜphrase(s,[a,c,f])終了しないのかということです。phrase(s,[a,b,c])さて、それはすぐに答えます：両方とも終了しません！しかしphrase(s,[a,b,c])、解決策/答えを見つけます。

ユニバーサルターミネーション

true区別するものは次の2つです。クエリを入力して、またはX = a;のような回答が得られた場合。あなたはもっと得ることに興味があるかもしれません。通常、これを行うには、トップレベルに入るSPACEまたは;ENTERトップレベルで行います。したがって、クエリは、最初の回答または複数の回答が見つかった後にのみループを開始する可能性があります。これは時間の経過とともにかなり混乱します。この述語が答えを生成する可能性があることを常に覚えておく必要があります。別の述語は2つを生成し、後でループしますか？

最も簡単な方法は、ここで最も堅牢な概念であるユニバーサルターミネーションの概念を確立することです。Goal終了する場合Goal, falseは終了します。この目標は、無期限falseにヒットすることに対応します。SPACEクエリ全体が失敗する瞬間まで。

だから今試してみてください：

？-フレーズ（s、[a、c、f]）、false。
**ループ**

だけでなく：

？-フレーズ（s、[a、b、c]）、false。
**ループ**

ユニバーサル終了の観点からは、両方のクエリは終了しません。単語の最も頻繁な使用法では、終了はユニバーサル終了に等しいです。そして、答えや解決策を見つけることはそれだけですが、終了のようなものではありません。したがって、回答に満足している限り無害に見えるが、本質的に終了しないクエリがあります。しかし、これをすぐに見つけたことを嬉しく思います。実行中のアプリケーションでのみこれを見つけた場合は、さらに悪化します。

理由を特定する

次のステップとして、終了しない理由を特定しましょう。デバッガーやトレーサーを試してみるかもしれませんが、おそらくそれはあなたに良い説明をまったく与えないでしょう。しかし、もっと簡単な方法がありを使用します。{false}文法に非終端記号を追加するだけです。false述語への目標。ここで非常に美しいプロパティを利用できます。

フェイルスライスが終了しない場合、元のプログラムは終了しません。

したがって、運が良ければ、そのようなスライスが見つかった場合、残りの表示部分が何らかの方法で変更された場合にのみ終了が発生することが確実にわかります。最も役立つスライスは次のとおりです。

？-フレーズ（s、[a、b、c]）、false

s-> []、{false}。
s-> s、{false}、num。

あなたのプログラムはあまり残っていません！なくなったnum//0！誰も気にしませんnum//0。つまり、プログラムはループしますが、何であれ、何でもnum//0記述できます。

この問題を解決するには、表示部分の何かを変更する必要があります。あまり残っていません！すでに観察したように、ここに左再帰があります。それを修正する古典的な方法は次のとおりです。

文法を再定式化する

文法を正しい再帰に簡単に再定式化できます。

s->[]。
s-> num、s。

これで、両方のクエリが終了します。これは、コンパイラー構築でも知られている古典的な方法です。

しかし、文法の再定式化が適切でない状況があります。この単純な例はこの種のものではありませんが、意図されたあいまいさを伴う文法で頻繁に発生します。その場合でも、次のことができます。

終了を誘発する引数を追加する

？-Xs = [a、b、c]、phrase（s（Xs、[]）、Xs）。

s（Xs、Xs）->[]。
s（[_ | Xs0]、Xs）-> s（Xs0、Xs1）、num、{Xs1=Xs}。

本質的に非終了クエリ

何をするにしても、すべてのクエリが終了できるわけではないことに注意してください。次のように質問した場合：»存在するすべての自然数を教えてください–実際にはすべてを1つずつ！«次に、これに答える唯一の方法は、たとえば0から始めて、それらを数えることです。したがって、答え/解決策が無限にあり、私たちの願いを実現しようとして貧しいPrologを非難することができないクエリがあります。ただし、このような状況で私たちが最も気に入っているのは、すべてのソリューションを公正に列挙することです。これは、優れた終了特性を備えた文法で最もよく行うことができます。つまり、固定長のリストで終了する文法です。そのようです：

？-長さ（Xs、M）、フレーズ（s、Xs）。

失敗スライスを適用する他の例については、タグスライスを参照してください。

于 2012-11-22T00:59:57.603 に答える
0

私が使用しているプロローグは非常に異なる構文を持っているように見えるので、これが助けになるかどうかはわかりませんが、私はあなたのプログラムと一致するように次のプログラムを書いただけで、問題なく動作します。

プログラム

s([]).
s([X|Xs]) :- num(X), s(Xs).

num(a).
num(b).
num(c).
num(d).

出力

?- [prologdcg].
% prologdcg compiled 0.00 sec, 2,480 bytes
true.

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

?- s([a,c,f]).
false.

SWI-prologを使用して実行します。

于 2012-11-22T00:06:30.663 に答える