〜program言語を作ってみるシリーズ
CPUを自作する、OSを自作する、プログラム言語を自作するという一連の自作の試み(*)のなかで、
プログラム言語を自作シするリーズのとっかかりとして計算機を作ってみる。
(*)自作の試みについては、BLOG 開発とお客様の狭間で プログラミング言語を作る などに書いてます。
字句解析までは、計算機を作ってみる-字句解析に書きましたのでそちらをご参照下さい。
構文解析については計算機を作ってみる-構文解析に書いてます・
今回、最終的に演算の部分を加えて完成です。
ここまで、練習のために 字句解析 → 構文解析 と各工程を地道に進めてきたので。
変数がいろいろでてきてわかりにくくなっているので、一度変数の説明をしておきます。
(1) 変数の説明
5+2*3
という式の例で説明します。
このプログラムに登場する主な変数は、token$, tree$, treer$, treel$ になります。
token$にはトークン化したデータを保存します。token$の配列の個数はnに保存します。
tree$はtree構造に構文解析したときの結節点のノードのデータを保存します。
treer$, treel$には左の子ノードのデータ、右の子ノードのデータを保存します。
結節点の個数はtに保存します。
5+2*3
について、各数値、演算子がどの変数に保存されるかを図示すると以下の通りです。
例えば、* を例にとると、これはtoken$(4)であり、同時にtree$(2)であるとともにTreel$(1)でもあります。
token$(4)ということは、4個目のトークンであり、tree$(2)ということは2個目の結節点（演算子）であり、
treel$(1)ということは、1個目の結節点（演算子、ここでは+演算子）の右の子ノードのデータということを示しています。
5+2*3
を実行した画面で説明すると以下の通りです。
（２） 演算のプログラム
構文解析のプログラムに追加したのは200〜280行目と、5000行以降。
200行〜
230行で、tree$をチェックしながら演算（5000行以降）に飛ばすかどうかを判定している。
tree$（結節点のノード）が演算子であり、かつ左の子ノード、右の子ノードが演算子でないもの（＝左右の子ノードが
両方とも数値のもの）を演算のサブルーチンに飛ばす。
上記の式で言うと、最初（whileループの一回り目）はtree$(1)("+"の演算子）の右の子ノードtreel$(1)は"*"なので、スキップされ、
tree$(2)("*"の演算子）は両方の子ノードが数値なので、演算サブルーチンに飛ばす。
変数jは演算子の数を数えるのに使う変数で、J-=0（全ての演算子の演算が終了）の時に
プログラムは終了します。
上記の式でいうと、whileループの一回り目は、tree$(1)("+"演算子）はスキップされて残っているので、j=1となり
whileループは2廻り目に入ります。
２廻り目では、tree$(1)("+"演算子）も演算処理されるので、J=0となりWhileループが終了します。
これにより、演算子の優先順位（"*","/"を"+2,"-"より優先する）通りの結果を得ています。
5000行〜
演算を行い結果を変数resultに保存して表示します。
演算の優先順位の高いものから演算をしていくので、上記の式の例では、
まず 2*3 を先に演算します。
その演算結果をtree$, token$にも反映させます。
2*3の演算が行われると。
tree$(2)は"*" -> "6" に、
token$(4)も"*" -> "6"に置き換わります。
5050行〜
treer$, treel$も演算結果を反映させます。
上記の式で言うと、
2*3 の演算が行われた後に
treel$(1)のデータは"*" ->"6"に書き換えられます。
5 dim token$(20)
10 input a$
15 n=0:type=0
20 l=len(a$)
30 for i=1 to l
40 moji$=mid$(a$,i,1)
50 if (asc(moji$)>=&H30 and asc(moji$)<=&H39) then gosub 1000
55 if (type=0 or type=2) and moji$="-" then gosub 1000
60 if moji$="+" or (moji$="-" and type=1) or moji$="*" or moji$="/" then gosub 2000
70 next
80 for i=1 to n
90 print "token";i;":";token$(i)
100 next
105 t=0
110 for i=1 to n
120 if token$(i)="+" or token$(i)="-" then gosub 3000
130 if token$(i)="*" or token$(i)="/" then gosub 4000
140 next
150 for i=1 to t
160 print "tree";i;" ";tree$(i);" token";tree(i);",";treer$(i);" token";treer(i);",";treel$(i);" token";treel(i)
170 next
200 j=100
210 while j>0
220 for i=1 to t
230 if (tree$(i)="+" or tree$(i)="-" or tree$(i)="*" or tree$(i)="/") and (treer$(i)<>"+" and treer$(i)<>"-" and treer$(i)<>"*" and treer$(i)<>"/") and (treel$(i)<>"+" and treel$(i)<>"-" and treel$(i)<>"*" and treel$(i)<>"/") then gosub 5000
240 next
245 j=0
250 for i=1 to k
260 if (tree$(i)="+" or tree$(i)="-" or tree$(i)="*" or tree$(i)="/") then j=j+1
265 next
270 wend
280 print result
500 end
1000 if type=0 or type=2 then n=n+1
1005 token$(n)=token$(n)+moji$
1010 type=1 'number
1012 if moji$="-" then type=3 'minus sign
1015 print moji$;":type:";type
1020 return
2000 if type=0 or type=2 then print"error":return
2010 if type=1 then n=n+1
2020 token$(n)=moji$
2030 type=2 'operator
2035 print moji$;":type:";type
2040 return
3000 t=t+1
3005 tree$(t)=token$(i):tree(t)=i
3010 if t=1 then treer$(t)=token$(i-1):treer(t)=i-1
3025 if t>1 then gosub 3050
3030 if token$(i+2)="*" or token$(i+2)="/" then gosub 3100 else treel$(t)=token$(i+1):treel(t)=i+1
3040 return
3050 j=i-2: s=0
3060 while j>0
3070 if (token$(j)="+" or token$(j)="-") then treer$(t)=token$(j):treer(t)=j:j=0:s=1
3075 'if (token$(j)="*" or token$(j)="/") then treer$(t)=token$(j):treer(t)=j
3080 j=j-1
3090 wend
3092 if s=0 then treer$(t)=token$(i-2): treer(t)=i-2
3095 return
3100 j=i+2
3110 while j<n+1
3120 if (token$(j)="+" or token$(j)="-") then j=n+1
3130 if (token$(j)="*" or token$(j)="/") then treel$(t)=token$(j):treel(t)=j
3140 j=j+1
3150 wend
3160 return
4000 t=t+1
4005 tree$(t)=token$(i):tree(t)=i
4010 if t=1 then treer$(t)=token$(i-1):treer(t)=i-1
4020 if t>1 and (token$(i-2)="*" or token$(i-2)="/") then treer$(t)=token$(i-2):treer(t)=i-2
4030 if t>1 and (token$(i-2)="+" or token$(i-2)="-") then treer$(t)=token$(i-1):treer(t)=i-1
4040 treel$(t)=token$(i+1):treel(t)=i+1
4050 return
5000 if tree$(i)="+" then treeval(i)=val(treer$(i))+val(treel$(i))
5010 if tree$(i)="-" then treeval(i)=val(treer$(i))-val(treel$(i))
5020 if tree$(i)="*" then treeval(i)=val(treer$(i))*val(treel$(i))
5030 if tree$(i)="/" then treeval(i)=val(treer$(i))/val(treel$(i))
5035 result =treeval(i)
5038 temp$=tree$(i)
5040 tree$(i)=str$(treeval(i)):token$(tree(i))=tree$(i)
5045 print result;"=";treer$(i);temp$;treel$(i)
5050 for k=1 to t
5060 treer$(k)=token$(treer(k)):treel$(k)=token$(treel(k))
5070 next
5080 return
ここまで頑張ってなんとか完成形にまでこぎつけましたが、まだ( )を扱えません。
ここまで作ってきた方法の延長線上に( )の処理を実装すると、相当にごちゃごちゃした
プログラムになりそうなので、次回は全く方針を変えていったん後置記法に書き変える方法で
( )も使えるようにしてみます。＝＞「計算機を作ってみる（後置記法）」