[B! Programming][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) になるし、あるいは抽象構文木を構築したり、数値と四則演算等の算術式のようなものであればその場で直接計算結果を得てしまってもよい。エドガー・ダイクストラが考案したもので、鉄道(車輛)の入れ替えとして説明したことから[1]、操車場という名称がつけられた。初出は、Centrum Wiskunde（オランダ国立数学研究所）のレポート MR 34/61 である（1961年）[2]。データフローとして見ると、このアルゴリズムには、入力と出力の2つの記号の列（ストリーム）があり、その他に1つ、演算子を保持するスタック（LIFO）として使われる

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> * <