5÷(8−3)×2+1を正しく計算できる？
というやつだ
答えは3なんだけど、
LRで構文木を作ると
まず、Rを探しに行く
右端は+ 1
PLUS
/ \
5/(8-3)*2 1
続いて、LからまたRを探すと、* 2
PLUS
/ \
MUL 1
/ \
5/(8-3) 2
さらにLの5/(8-3)にRを探すと/ (8-3)
PLUS
/ \
MUL 1
/ \
DIV 2
/ \
5 8-3
んで、今度はR側にまだ再帰できるところがあるので
PLUS
/ \
MUL 1
/ \
DIV 2
/ \
5 MINUS
/ \
8 3
これで構文木が完成
そんで、答えを出すには最下層から上に上がっていく
8-3=5なので
PLUS
/ \
MUL 1
/ \
DIV 2
/ \
5 5
続いて
5/5=1なので
PLUS
/ \
MUL 1
/ \
1 2
さらに続けて
1*2=2となり
PLUS
/ \
2 1
最後は
2+1=3
という事で、答えの3が導ける
ここで、数式とプログラミング言語を比べると、C言語なんて関数なので、
例えばif文
if (a==b) {
proc();
}
if
/ \
== proc()
/ \
a b
のようになるし、forも代入も似たようなもんで、構文木を作って解釈して行くことになる
このやり方はクヌース大先生が考案したもので、その後多くのアイデアが出てくるのだけど、基本はやはり構文木を作るというやり方になっている
そして、lexやyaccが生まれ、
構文木を自動生成するためにBNF記法が生まれ、C言語などのプログラミング言語が出来た
C++では構文定義をC++の記法で置き換えたboost::spiritsなども生まれ、すぐにこの変態的実装はなくなるかと思ったが、C++17でも残ってる
lexやyaccは
flexやbisonになったが
わたしが最近触っているANTLRは構文定義からGoやSwiftのコードも出力できる
好みの言語で新しい言語を作ることができるようになってきた
