[解決済み] 式（エクスプレッション）パーサー（優先順位付き）？

質問

二項演算子（+, -, |, &, *, /, etc）、単項演算子（！）、括弧を処理する簡単なスタックアルゴリズムを使って、数式パーサーを開発しました。

しかし、この方法を使用すると、すべてのものが同じ優先順位を持つことになります。優先順位は括弧を使用して強制することができますが、演算子に関係なく左から右へ評価されます。

つまり、今現在 "1+11*5" は 60 を返し、期待される 56 ではありません。

これは現在のプロジェクトに適していますが、私は後のプロジェクトで使用できる汎用ルーチンを持ちたいと考えています。

わかりやすくするために編集しました。

優先順位を持つ方程式を解析するための良いアルゴリズムは何ですか？

私は、利用可能なコードのライセンス問題を避けるために、私自身がコーディングできる、実装と理解が簡単なものに興味があります。

文法です。

文法の質問は理解できない - 私はこれを手で書きました。 YACC や Bison の必要性を感じないほど単純なものです。 私は単に "2+3 * (42/13)" のような方程式を持つ文字列を計算する必要があるだけです。

言語。

私はこれをCでやっていますが、私はアルゴリズムに興味があるのであって、言語固有の解決策ではありません。 C言語は十分に低レベルなので、必要であれば他の言語に変換するのは簡単でしょう。

コード例

を投稿しました。 のテストコードを投稿しました。 を投稿しました。 プロジェクトの要件が変更されたため、プロジェクトに組み込まれなかったので、パフォーマンスやスペースのためにコードを最適化する必要はありませんでした。 これは元の冗長な形式であり、容易に理解できるはずです。 演算子の優先順位の観点からこれ以上何かするとしたら、私はおそらく次のものを選ぶでしょう。 マクロハック を選ぶと思う。 しかし、実際のプロジェクトでこれを使用する場合は、よりコンパクトでスピーディなパーサーを使用することになるでしょう。

関連する質問

数学パーサーのスマートな設計？

-アダム

どのように解決するのですか？

難しい方法

あなたは 再帰的降下パーサ .

優先順位を得るには、例えばサンプルの文字列を使って再帰的に考える必要があります。

1+11*5

を手作業で行うには、このように 1 で始まる全く新しい再帰的な解析 "セッション" を開始する必要があります。 11 ... そして、必ず 11 * 5 をそれ自身の要素にパースして、パースツリーを生成します。 1 + (11 * 5) .

これは説明するのも大変なことで、特にC言語の無力さを痛感します。 11を解析した後、もし*が実際には+だった場合、用語を作るのをやめて、代わりに 11 を因子として解析しなければならないのです。もう、頭が爆発しそうです。再帰的ディセント戦略で可能ですが、もっといい方法があるのでは...。

簡単な（正しい）方法

Bison のような GPL ツールを使用する場合、bison が生成する C コードは GPL の対象外なので、おそらくライセンスの問題を心配する必要はありません (IANAL ですが、GPL ツールは生成されたコード/バイナリに GPL を強制しないと確信しています。たとえば Apple は Aperture といったコードを GCC でコンパイルし、そのコードを GPL する必要なく販売します。) 。

Bison のダウンロード (または同等のもの、ANTLRなど)。

通常、bison を実行するだけで、この 4 つの関数電卓を実証する希望の C コードが得られるようなサンプル コードがいくつかあります。

http://www.gnu.org/software/bison/manual/html_node/Infix-Calc.html

生成されたコードを見て、これが言うほど簡単でないことを見てください。また、Bisonのようなツールを使う利点は、1）何かを学ぶことができる（特にDragonの本を読んで文法について学ぶ場合）、2）以下を避けることができる。 国立医薬品食品衛生研究所 車輪の再発明を試みる 本物のパーサー生成ツールがあれば、後でスケールアップして、パーサーがパーシング ツールの領域であることを他の人に示すことができます。

更新しました。

ここの人々は多くの適切なアドバイスを提供してくれました。解析ツールをスキップしたり、Shunting Yard アルゴリズムや手製の再帰的なまともな解析器を使用することに対する私の唯一の警告は、小さなおもちゃの言語である ¹ は、いつか関数（sin、cos、log）や変数、条件、forループを持つ大きな実際の言語に変わるかもしれません。

しかし、一回限りのパーサーと評価器は、変更が必要になったとき、または機能が追加されたときに、問題を引き起こすかもしれません。あなたの状況はさまざまで、あなたの判断が必要でしょう。 自分の罪のために他人を罰する ^[2] というように、十分とは言えないツールを構築する。

解析のための私のお気に入りのツール

この仕事に最適なツールは パーセク ライブラリ（再帰的なまともなパーサー用）で、プログラミング言語 Haskell に付属しています。見た目は BNF のように見えますが（サンプルコード [3]）、実際には Haskell の通常のライブラリです。つまり、残りの Haskell コードと同じビルドステップでコンパイルされ、任意の Haskell コードを書いてパーサ内でそれを呼び出すことができ、他のライブラリとの混在も可能です。 を混在させることができます。 . (ところで、このような解析言語をHaskell以外の言語に埋め込むと、構文上の無駄が多くなってしまいます。私はこれをC#で行いましたが、非常にうまく動作しますが、あまりきれいで簡潔ではありません)。

メモです。

1 リチャード・ストールマンは、以下のように言っています。 なぜ Tcl を使ってはいけないか

Emacsの主要な教訓は、以下の通りです。 拡張のための言語であってはならない 単なる拡張言語であってはならないということです。 それは 本当のプログラミング言語であるべきだということです。 実質的なプログラムを書き、維持するために設計された 本物のプログラミング言語であるべきです。なぜなら、人々は なぜなら、人々はそうしたいと思うからです。

[2] そうです、私はその言葉を使ったことで一生心に傷を負っています。

また、このエントリーを投稿したとき、プレビューは正しかったのですが、次のことに注意してください。 SO の適切でないパーサーは、最初の段落にある私のクローズ アンカー タグを食べました。 というのも、正規表現とワンオフのハックを使うと を使えば、おそらく何か微妙で小さな間違いを犯すでしょう。 .

[指数、括弧、乗算のための空白、定数（円周率やeなど）で拡張された4関数電卓です。）

aexpr   =   expr `chainl1` toOp
expr    =   optChainl1 term addop (toScalar 0)
term    =   factor `chainl1` mulop
factor  =   sexpr  `chainr1` powop
sexpr   =   parens aexpr
        <|> scalar
        <|> ident

powop   =   sym "^" >>= return . (B Pow)
        <|> sym "^-" >>= return . (\x y -> B Pow x (B Sub (toScalar 0) y))

toOp    =   sym "->" >>= return . (B To)

mulop   =   sym "*" >>= return . (B Mul)
        <|> sym "/" >>= return . (B Div)
        <|> sym "%" >>= return . (B Mod)
        <|>             return . (B Mul)

addop   =   sym "+" >>= return . (B Add) 
        <|> sym "-" >>= return . (B Sub)

scalar = number >>= return . toScalar

ident  = literal >>= return . Lit

parens p = do
             lparen
             result <- p
             rparen
             return result