読者です 読者をやめる 読者になる 読者になる

ayihiscope

主に情報系の話題が好きな大学生の雑記!

Rubyで四則演算を構文解析してみた

Parsing the parser

大学の課題で文脈自由文法に基づく構文解析の実装ってのがあったので,とっても雑だけど実装してみました.

人生初の自作パーサーなので,超雑な感じですが悪しからず!

あと,デバッグ用のputsが多いけど気にしないで!

あと,いろいろ間違ってるかもしれないのでご指摘よろしくお願いいたします!!

実行環境

ruby 2.3.0p0 (2015-12-25 revision 53290) [x86_64-darwin15]

概要

文字列で入力された数式"1+2-3*(4+5)/6"とかを構文解析して答えを出すプログラムです. ライブラリとか使わずに全部自前で処理します. たぶん,実装したアルゴリズム再帰下降構文解析なのかな・・・?たぶん

文脈自由文法の定義

文脈自由文法 G = (V, T, P, S)を考える

  • V:非終端記号の有限集合
  • T:終端記号の有限集合
  • P:書き換え規則
  • S:開始記号

以下のように定義する

  • V:{ E , D , C } #Eは<式>,Dは<項>,Cは<因子>
  • T:{ <整数> , + , - , * , / , ( , ) }
  • P:E -> D|E+D|E-D # <式> = <項> or <式>+<項> or <式>-<項>
  • D -> C|DC|D/C # <項> = <因子> or <項><因子> or <項>/<因子>
  • C -> <整数>|(E) # <因子> = <整数> or (<式>)

コード

今後の展望

もしまた作る機会あれば,その時は抽象構文木とかちゃんと作ったりしてみたい.

誰かの参考になれば!