Prolog で統一アルゴリズムがどのように機能するかを理解するために、過去 5 日間を費やしました。今、私はJavaでそのようなアルゴリズムを実装したい..
おそらく最善の方法は、文字列を操作し、スタックなどのデータ構造を使用してその部分を分解することだと思いました..
明確にするために：
ユーザー入力が a(X,c(d,X)) = a(2,c(d,Y)) であるとします。
私はすでにそれを 1 つの文字列として取り、2 つの文字列 ( Expression1 と 2 ) に分割しています。さて、次の文字が変数か定数かなどかどうかをどうやって知ることができますか..ネストされたifでそれを行うことができますが、それは良い解決策ではないようです..継承を使用しようとしましたが、まだ問題があります(どのように読み取られている文字のタイプを知ることはできますか?)
まず、入力を解析して式ツリーを構築する必要があります。次に、ミルナーの統一アルゴリズム (または他の統一アルゴリズム) を適用して、定数と式への変数のマッピングを見つけます。
ミルナーのアルゴリズムの非常に優れた説明は、Dragon Book にあります。Aho、Sethi、および Ullman による「Compilers: Principles, Techniques and Tools」です。(Milners アルゴリズムは巡回グラフの統合にも対応でき、Dragon Book はそれを型推論の方法として提示しています)。その音によって、解析について少し学ぶことで利益が得られる可能性があります...これはドラゴンブックでもカバーされています。
編集: 他の回答では、パーサー ジェネレーターの使用が提案されています。例えばANTLR。それは良いアドバイスですが、(あなたの例から判断すると) あなたの文法は非常に単純なので、StringTokenizer と手書きの再帰降下パーサーを使用することもできます。実際、時間があれば (そして気合があれば)、学習課題としてパーサーを両方の方法で実装する価値があります。
この問題は、特に統合よりも解析に関係しているようです。ANTLRのようなものを使用すると、元の文字列をある種のツリー構造に変換するという点で役立つ場合があります。
(「ネストして実行する」とはどういう意味かはっきりしませんが、式を読み取ろうとして、各「(」に遭遇したときに再帰するようなことをしているのであれば、それは実際には正しい方法の 1 つです。それを行う - これは本質的に、ANTLR が生成するコードが行うことです。)
構文解析よりも物事を統合するメカニズムに関心がある場合は、これを行うための完全に優れた方法の 1 つは、コードで内部表現を直接構築し、構文解析の側面を今のところ延期することです。Prolog スタイルのステートメントはかなり冗長な Java ステートメントのセットになっているため、これは開発中に少し面倒になる可能性がありますが、一度に 1 つの問題に集中できるため、通常は役に立ちます。
(このように構造化すると、適切なパーサーを後で簡単に挿入できるようになります。これにより、それまで手作業で構築していたのと同じ種類のツリーが生成されます。これにより、合理的な方法で 2 つの問題を別々に扱うことができます。きちんとしたファッション）
言語のセマンティクスを理解する前に、テキストを操作しやすい形式に変換する必要があります。このプロセスは構文解析と呼ばれ、意味表現は抽象構文木(AST) と呼ばれます。
Prolog 用の単純な再帰降下パーサーは手書きの場合もありますが、Rats!などのパーサー ツールキットを使用する方が一般的です。またはAntlr
Prolog の AST では、タームのクラスがあり、CompoundTerm、Variable、および Atom はすべてタームです。多態性により、複合項への引数を任意の項にすることができます。
統一アルゴリズムは、複合項の名前を統一し、対応する複合項の各引数の値を再帰的に統一します。