[B! parsing] zaki1010のブックマーク

pythonでパーサを作る(#4:括弧つき四則演算)｜デジタル忍者ブログ

zaki1010 2021/09/09

リンク

シンプルな数式のパーサー（操車場アルゴリズム） - Fuji Haruka's blog

構文解析にちょこっと興味が出てきたので、単純な数式をパースする関数を Node.js で書いた。参考にしたのは操車場アルゴリズム(Wikipedia) と JavaScript で数式パーサを書いてみた。です。数式の定義できるだけ実装をシンプルにしたいので、数式の定義もシンプルにする。数式を以下のように定義する。 1文字以上の単語構成文字は数式である。(例： 1, 3, a, x, hoge など) s と t が数式のとき、 (s+t), (s-t), (s*t), (s/t) も数式である。上記以外は数式でない。空白文字は入れても良いが無視する。たとえば以下のようなものが数式である。 1 (x + 1) (a + (9 * b)) (1 + (((x / 3) - 6) + (j + (k * n)))) 逆ポーランド記法と抽象構文木与えられた数式に対して、逆ポーランド記

zaki1010 2021/09/09

リンク

操車場アルゴリズムで四則計算の数式をパース - Qiita

以前に簡単な四則計算を再帰下降構文解析でしてみた1ものの、もっと単純で面白い感じのアルゴリズムがあった気がしていた。調べたら「操車場アルゴリズム」（shunting-yard algorithm）と思い出したので、これをRubyで実装してみる。概要詳しい説明や図解はWikipedia参照。中置記法で書かれたよく見る数式を、後置記法（逆ポーランド記法）に変換できる。記号列を入力から出力へ送る際にスタックを用いて並べ替える様子を、列車を並べ替える様子で説明したため、操車場アルゴリズムと呼ばれる。コード以前と同様に「1桁の整数・加算・乗算・括弧のみの数式を解釈して計算結果を返す」パーサを作ってみる。各文字がそのままトークンになるので、字句解析を省いて簡略化する2。エラー処理は不完全なので、前提に合わない数式（例えば2桁の数字）を入力してもエラーにならず変な結果を返すことがある。 cl

zaki1010 2021/09/09

リンク

操車場アルゴリズム - Wikipedia

中置記法からRPNへの変換は、数式を簡単に単純化するのにも使える。そのためにはRPNの式を評価するようにし、値がヌルの変数が出てきたり、値がヌルの演算子が出てきたら、そのパラメータと共に出力に書き込めばよい（これは単純化であり、パラメータが別の演算子だった場合には問題が生じる）。ヌルのパラメータがない演算子の場合は、単にその値を出力に書き込めばよい。この技法は明らかにあらゆる単純化を含んでいるわけではない。それは定数畳み込みの最適化に近い。 C言語での実装例[編集] #include <string.h> #include <stdio.h> #include <stdbool.h> // 演算子 // 優先順位 : 演算子 : 結合性 // 4 : ! : 右結合性 // 3 : * / % : 左結合性 // 2 : + - : 左結合性 // 1 : = : 右結合性 int

zaki1010 2021/09/09

リンク

pythonで数式の構文解析をしてみた - Qiita

ふと数式の簡単な構文解析くらいできないとダメだよなと思ってやってみたんですが、意外と苦戦してしまったので忘れないように書いてみました。今回は再帰降下法と操車場アルゴリズムの2つを試してみます。実装対象今回は+, -, *, /, () をサポートしたものを作ろうと思います。例えば myeval("1+2") では 3 が返ってきてくれるとうれしいです。再帰降下法再帰降下法は再帰的な構造を利用して構文解析を行う手法です。考え方を以下で説明していきます。考え方素朴な考え方今回使用するBNF (Backus-Naur form)を考えます（知らなくても大丈夫です）。数式はこのBFNを用いて以下のように書くことができます。 expr := <term> | <expr> + <term> | <expr> - <term> term := <factor> | <term> * <