このタイプの式はどのように解析するのですか？

Question

私はコンパイラのバックグラウンドを持っていないので、これがその領域のcommmonものなのかどうかわかりません。このような表現を解析する標準的なテクニックはありますか？私は、スタックベースの評価に頼る必要がある場合、私はわからない

((A+B=1) AND (C+D=1) AND ((P+Q=1) OR (K=1)) AND ((Q=1) AND (R=2))) 

：

And 
    A + B = 1 
    C + D = 1 
    Or 
     P + Q = 1 
     K = 1 
    And 
     Q = 1 
     R = 2 

は次のように解析されるべき（例えば、タブは、深さを示しますか）？私は現在、1つを試しています。もし私がそれを稼働させることができれば、動作するコードを投稿します。

これを達成するための簡単な方法についてのご意見はありますか？

Answer 1

あなたは、さまざまな優先順位と関連性を持つ演算子から構築された式をパースする方法について質問していると仮定します。

効果的な手法の1つは「トップダウン演算子優先度」と呼ばれ、「演算子優先度」および「優先度上昇」解析でもあります。

• Pratt parsing（もoriginal paper）

• ダグラス・クロックフォードのtakeその上に

• Pythonistのtakeその上に

• ：ここでは詳細にアプローチを説明するいくつかの素晴らしい情報源でありますJava version

本当にすっきりしたことは、実際に少しのコードしかないことです。

主要概念は、次のとおりです。mixfix

優先対中置対

• 接頭辞：3 + 4 * 5は(3 + 4) * 5または3 + (4 * 5)として解析されますか？

• 連想度：x - y - zは、​​または(x - y) - zと解釈されますか？

偶然、私は最近、このようなものを学び、あなたがhereを見つけることができるオペレータの解析と同様のアプローチ、についての私のブログに記事を書いてしまってきました。私のアプローチでは、接尾辞、接頭辞、接尾辞、およびmixfix演算子（すなわち、? :）を扱います。優先順位と関連性はすべて表で指定されています。私はオペランドがまだ見つからない演算子を追跡するためにスタックを使います。次に、パーサは構文解析ツリーを構築します。各ノードは部分式です。