問題タブ [dcg]

置換SとリストXsがあり、 Xsで発生する各変数はSでも発生するとします。リストS(Xs)、つまりリストXsに置換Sを適用して得られるリストを見つけるにはどうすればよいでしょうか。

より具体的には、次のような一連の述語と DCG ルールがあります。

リストに対してパターンPと変数を一致させようとすると、置換Sが返されます。

置換S = {X = c, Y = e}を変数XおよびYを持つリストXsに適用し、置換が行われたリストを受け取りたいのですが、問題にアプローチする最善の方法がわかりません.

Haskell でこの問題に取り組んでいた場合、変数から値への有限マップを作成してから、置換を実行します。同等のアプローチは、変数と値のペアの DCG ルールでリストを作成し、マップを使用して目的のリストを見つけることです。ただし、これは適切なアプローチではありません。

標準の入力から読み取り、読み取られたすべての行のリストを作成していると仮定します。最後に、これらの行をコンマで区切って表示する必要があります。

このコードの問題は、append呼び出しにprocessInput/3O（n）のコストがかかることです。どうすればこのコストを回避し、述語を末尾再帰にすることができますか（標準入力から多くの行を読み取る可能性があるため）？

を次のように置き換えることができると思いましたappend。

そして、それを表示する前にリストを逆にすることができます。しかし、それはハッキーのようです。もっと良い方法はありますか？

PrologのDCG表記を使用して、大文字で始まるシーケンスを変数に解析するのに問題があります。たとえば、私が文字列を持っている場合

そして、この文字列を解析するDCGは、大文字の各文字を一意のProlog変数に解析する方法があります。たとえば、変数に解析Yし、それぞれXを変数に解析しますか？意図されたアプリケーションは、ファンクターを構築することです

ステートメントで終わるDCGルールを介して

Prolog で Lisp を解析するためのこの素敵なスニペットを見つけました (ここから):

ただし表現はカットを使用。これは効率化のためだと思います。このコードをカットせずに効率的に動作するように書くことは可能ですか?

マーキュリーのソフトカット/献身的な選択を含む興味深い回答にもなります.

Findw/ Replacein Request& put the answer inのすべての出現を置き換えるために、次のコードを思いつきましたResult。これはDCGを使用しているので、すべて文字コードのリストです。クライアント コードが使用する述語はsubstitute.

これは SWI-Prolog で機能します。どうすれば改善できるかについて誰かコメントはありますか？DCG の & 差分リストの使い方を学んでいます。Findたとえば、 を見つけた後、プロローグがバックトラックしてそれを通常の文字として解釈しないように、カットを入れました[ C ]。これは必要ですか、それとももっと宣言的な方法がありますか?

もう 1 つの質問 - 代用と同じことを行うための述語がすでに利用可能ですか? おそらくアトム上で?

前もって感謝します。

次のコードは、Findw / Replaceinのすべての出現を置き換えRequest、答えをに入れるDCGResultです。この質問のコードについては、matに感謝します。

SWI-Prologでは、これは次のように拡張されます。

このコードは末尾再帰ですか？述語の2番目の定義のphraseへの再帰呼び出しの後にへの呼び出しがあります。の3番目の定義には、への再帰呼び出しの後にもあります。再帰呼び出しが最後に行われた場合、コードは末尾再帰になると思いました。生成されたコードが末尾再帰でない場合、Prologに末尾再帰コードを生成させる方法はありますか？前もって感謝します。replacereplaceE=[F|G]replacereplace

1. リストの逆を返すreverseと呼ばれる2つの引数を持つ再帰的なProlog述語を取得できますか？

   サンプルクエリと期待される結果：

   /li>

2. 呼び出された2つの引数の再帰的Prolog述語はpalindrome、指定されたリストが回文である場合にtrueを返します。

   期待される結果を含むサンプルクエリ：

   /li>

Prolog の DCG と、特定の文法に適合するすべての可能な構造をいかに迅速に生成できるかに非常に感銘を受けました。

しかし、この検索を他の制約と組み合わせたいと思います。たとえば、複雑な文法を定義し、Prolog に 10 語以下のすべての文を生成するように依頼します。または、同じ単語を 2 回繰り返さないすべての文。

このような追加の制約を DCG 文法に追加することは可能ですか? それとも、基本的に DCG を通常の Prolog 句に変換して、変更を開始する必要がありますか?

私が理解していることから、Prologでは次のように解析しながら機能をキャプチャします:

これは DCG を設計するときによくあることですか?

phrase_from_file文法規則を使用して整数行を含むファイルを解析しようとしています

したがって：phrase_from_file(line,'input.txt').

それは失敗し、私はそれを追跡しようとするとすぐに迷子になりました。印刷しようとしたIのですが、うまくいきません。

編集::以下の解決策はどれも私のニーズに本当に合わないので（read/1用語を読んでいると仮定し、DCGを書くのに時間がかかりすぎる場合があります）、グーグルでこのコードを共食いしました。主な変更点は次のとおりです。