C++ 四則演算を再帰下降構文解析する

C++で再帰下降構文解析してみた。

オブジェクト指向はしてない。STL使いたかっただけ。

四則演算をどうやって解析して出力するのかよく分かっていなかった。

基本中の基本・・のはず。お勉強のためのメモ。

メモ

文脈自由文法(CFG)であれば、BMF記法で表現できる。

CFGとプッシュダウン・オートマトンは等価である。

正規表現　∈　CFG　であるため　正規表現をCFGで表現可能。

なお、正規表現は決定性有限オートマトンと等価である。

CFGを受理する言語を考える場合は、BMF記法を使用すると良いようだ。

※BMFを使わなくてもCFGの定義に基づいて四則演算の文法を記述すれば良い。

基本的な流れ。

[1] BMF記法に基づいて書きたい言語の文法を表現する。

[2] コードに落とし込む

-- > 構文解析器は構文木を出力するの一般的。

-- > 四則演算であれば、その場で計算して出力しても問題ない？

-- > 字句解析 -> 構文解析　の流れが一般的。　数字と演算子のみからなる式であるため、構文解析中に一緒にやる。

開発環境

Windows

Visual Studio 2013 pro

CODE

参考

http://dai1741.github.io/maximum-algo-2012/docs/parsing/
http://www.prefield.com/algorithm/string/parser.html

再帰下降構文解析 - Wikipedia