Javacc/jjtreeを使用して方程式/式を簡略化

Question

方程式ファイルを読み込んで各ルールのASTノードを作成するための文法を作成しました。私の質問は、パーサーが可能な方程式正しく読んでください。どの段階？ ASTノードを作成する前または後に？ 私に次のアイデアやチュートリアルを提供してください。

ありがとうございます。

Answer 1

私はあなたが、少なくとも1つの方程式のためのASTを持つ開始二つの異なる問題に二つの異なるソリューションを求めるあなたの式はX^2+3*Y^2

のように、実数値変数の上に簡単な多項式のようなものと仮定しています：

• の式に「代替値」とは、上記の式のためのASTにXの== 3及びY = 2、代替のために得られた値、例えば、計算し、計算方法3^2+3*2^2 - >21
• 簡素化の仕方：代数系簡略化を意味すると思います。

yuoが既にASTを持っている場合、値を代入する最初の問題はかなり簡単です。 （そうでない場合、最初にASTを生成するために方程式を解析してください）次に、変数名を含むすべてのリーフノードを対応する値に置き換えて、ASTを歩いてから、子プロセスが発生したすべての親ノードに対して算術演算を行います数字になる。これ以上ノードが算術的に評価されなくなるまでこれを繰り返します。基本的に単純な算術をツリー評価スキームに結び付けます。

この例のように評価するとツリーが1つの値に縮小され、数値結果My SO answer shows how do that in detailを印刷できます。 JavaCC/JJTreeを適切に適用しても、小さなプロジェクトで簡単に実装できます。

数式がそれ以上の演算ができない状態になることがあります。たとえば、x == 0でyがわからない1+x+yなどです。そのような置換/算術評価プロセスの結果は1+yになります。残念ながら、あなたはASTとしてしか持っていないでしょう...今結果を見るために結果のASTを印刷する必要があります。これはより困難です。 see my SO answer on how to prettyprint a tree。これははるかに多くの作業です。式をに制限しても式の上ではの多項式に制限しても、小さなプロジェクトでもこれを行うことができます。 JavaCCは解析するのに役立ちますが、プレタイピングを助けることはありません。

上記のように変数の置換と算術評価を行うだけでなく、代数の法則の知識をコード化し、その法則を複雑なツリーにマッチさせる必要があるため、2番目の問題ははるかに難しくなります。 1つまたは2つの代数の法則（例えば、x+0 - >x; y-y - >0）をハードワイヤリングするかもしれませんが、このように多くの法則をハードワイヤリングすることで、相互作用する方法が不可能になります。

JavaCCはそのような回答の一部を形成するかもしれませんが、小さな部分だけです。ソリューションの残りの部分は十分に難しいので、JavaCCの上にすべてを構築しようとするのではなく、代替案を探す方が良いです。 これにはより組織化されたアプローチが必要です：Program Transformation System (PTS)。典型的なPTSは の任意の言語（場合によっては多項式）の文法を指定することができます。 は自動的にインスタンスをASTに解析し、ASTから有効なテキストを再生成することができます。A 良い PTSでは、PTSがインスタンスASTを自動的に適用するソースからソースへの変換ルールを記述できます。あなたの場合、代数法をソース・ツー・ソース規則として書き留め、PTSがすべての作業を行います。

例があまりにも長いため、ここでは説明できません。しかし、here I describe how to define formulas suitable for early calculus classes, and how to define algebraic rules that simply such formulas including applying some class calculus derivative laws。

JavaCC/JJTreeの上に自分のPTSを作成することができます。これには数年かかるだろう。すべての作業を繰り返すのではなく、PTSを簡単に取得できます。