パソコン活用研究5番街（Visual Basic、Excel(VBA)、BASIC　プログラミング研究）

計算機を作ってみる〜後置記法　（準備中）
〜program言語を作ってみるシリーズ

CPUを自作する、OSを自作する、プログラム言語を自作するという一連の自作の試み(*)のなかで、
プログラム言語を自作シするリーズのとっかかりとして計算機を作ってみる。
(*)自作の試みについては、BLOG 開発とお客様の狭間で　プログラミング言語を作る　などに書いてます。

字句解析までは、計算機を作ってみる-字句解析に書きましたのでそちらをご参照下さい。
構文解析については計算機を作ってみる-構文解析に書いてます・
計算機を作ってみる-完成形では、式の中に( )を使えなかったので、( )を含めた処理が
できるようにしてみる。
計算機を作ってみる-完成形の延長線上で( )の処理を追加していくと、ぐちゃぐちゃなプログラム
になりそうなので、方針を転換して後置記法（逆ポーランド記法）にいったん置き換えて処理する
方法をとってみる。

トークン化するところまでは、ほぼ同じ処理をしているが、( )のための処理を65,66行目に追加している。
実際の( )の処理はサブルーチンで飛んだ2100行目〜、2150行目〜で行っている。
変数としては左括弧の個数をlparenに保持し、右括弧の個数をrparenに保持


2100行〜　左括弧の処理のサブルーチン
ひとつ前の文字が演算子でない（数字や負号）場合はエラーとし、演算子ならlparen=lparen+1する。

2150行〜　右括弧の処理。
ひとつ前の文字が数字でない（式の先頭や演算子、負号）の場合はエラーとし
数字なら rparen=rparen+1する

110行で、左括弧と右括弧の数を比較し、等しくなければエラーとしている。

トークン化したあとの処理は全く別の方法をとっている。
式は中置記法で与えられるので、まずこれを後置記法（逆ポーランド記法）に書き換える

今回は、list$という配列とstack$という配列を用意しました。
最終的にlist$のほうに後置記法に書き換えられた式が保存され、実際の演算に使われます。
stack$のほうは文字通り一時的な処理のためのスタックとして使います。

まず、置き換え作業用に式の中に出てくる数値や演算子の優先順位を以下の通りとします。

置き換えのルールは以下の通りです。
�@トークンを１つ取ってくる
�A　
(a) �@で取ってきたトークンが数値ならlist$に入れる

(b) �@で取ってきたトークンが(ならstack$に入れる
(c) �@で取ってきたトークンが)なら、(に出会うまでstack$から順番に取り出しlist$に入れる。
　　（は捨てる。取ってきた)もそのまま捨てる。
(d) �@で取ってきたトークンが"*"または"/"の場合、stack$の一番上と比較し、stack$の一番上がトークンの優先順位
　　と同じか優先順位が高ければstack$から取り出しlist$に入れる。これを繰り返し、最後に取ってきたトークンを
　　stack$に入れる。
　　stack$の一番上がトークンの優先順位より低ければ、取ってきたトークンをそのままstack$に入れる。
　　言葉で説明するとわかりにくいが、要するにstack$の一番上が"*"または"/"ならstack$からlist$に移し、
　　"+"や"-"や"("ならそのままということ。
(e) 　　�@で取ってきたトークンが"+"または"-"の場合も(d)と同様、stack$の一番上と比較し、stack$の一番上がトークンの優先順位
　　と同じか優先順位が高ければstack$から取り出しlist$に入れる。これを繰り返し、最後に取ってきたトークンを
　　stack$に入れる。
　　stack$の一番上がトークンの優先順位より低ければ、取ってきたトークンをそのままstack$に入れる。
　　言葉で説明するとわかりにくいが、要するにstack$の一番上が"*","/","+","-"ならstack$からlist$に移し、
　　"("ならそのままということ。
�B全てのトークンの処理をしたら、stack$に残っているものを順に取り出して、list$に入れる。

このルールの�A(a)
150行　トークンが数値の場合は2500行のサブルーチンで処理。
2500行では、リストにそのまま保存し、リストトップの値を1つ加算

ルール�A(d)の処理
160行　トークンが乗算または除算（"*"または"/"）の場合は2600行のサブルーチンで処理

�Bの処理　210〜240行




後置記法のlist$から実際の演算をするのは
300〜360行
演算子があったら、１つ前と２つ前の数値をとってきて演算し、演算結果は２つ前に保存する。
そして１つ前の数値と演算子は取り除いて、それ以降を前につめるという処理をしています。


5 dim token$(20),list$(50),stack$(50)
10 input a$
15 n=0:type=0:ng=0:lparen=0:rparen=0:topl=1:tops=1:ng=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
65 if moji$="(" then gosub 2100
66 if moji$=")" then gosub 2150
70 next
80 for i=1 to n
90 print "token";i;":";token$(i)
100 next
110 if lparen<>rparen then print"parentheses mismatch":ng=1
120 if ng=1 then goto 500

130 for i=1 to n
140 'stack$(tops)=token$(i):
150 if token$(i)<>"(" and token$(i)<>")" and token$(i)<>"+" and token$(i)<>"-" and token$(i)<>"*" and token$(i)<>"/" then gosub 2500
160 if token$(i)="*" or token$(i)="/" then gosub 2600
170 if token$(i)="+" or token$(i)="-" then gosub 2700
180 if token$(i)="(" then stack$(tops)=token$(i):tops=tops+1
190 if token$(i)=")" then gosub 2800
195 gosub 5000:gosub 5100
200 next
210 for i=tops-1 to 1 step -1
220 list$(topl)=stack$(i)
230 topl=topl+1
240 next

250 for i=1 to topl
260 print list$(i);" ";
270 next
280 print
290 list$(topl)="="
300 i=1
310 while list$(2)<>"="
320 if list$(i)="+" then gosub 6000
330 if list$(i)="-" then gosub 6100
340 if list$(i)="*" then gosub 6200
350 if list$(i)="/" then gosub 6300
355 i=i+1
360 wend
370 print "=";val(list$(1))


500 end
1000 if type=0 or type=2 or type=4 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":ng=1:return '先頭やoperatorに続いた時はエラー
2010 if type=1 or type=4 then n=n+1
2020 token$(n)=moji$
2030 type=2 'operator
2035 print moji$;":type:";type
2040 return
2100 if type=1 or type=3 then print"error":ng=1:return 'numberやminus signに続いた時はエラー
2110 lparen=lparen+1:n=n+1:token$(n)=moji$:type=4 'parentheses
2120 print moji$;":type:";type: return
2150 if type=0 or type=2 or type=3 then print"error":ng=1:return '先頭、operatorrやminus signに続いた時はエラー
2160 rparen=rparen+1:n=n+1:token$(n)=moji$:type=4 'parentheses
2170 print moji$;":type:";type: return
2500 list$(topl)=token$(i)
2510 topl=topl+1
2530 return
2600 j=tops-1
2610 while J>=1
2620 if stack$(j)="*" or stack$(j)="/" then list$(topl)=stack$(j):topl=topl+1:stack$(j)="":j=j-1:tops=tops-1 else j=0
2630 wend
2640 stack$(tops)=token$(i)::tops=tops+1:return
2700 j=tops-1
2710 while J>=1
2720 if stack$(j)="*" or stack$(j)="/" or stack$(j)="+" or stack$(j)="-" then list$(topl)=stack$(j):topl=topl+1:stack$(j)="":j=j-1:tops=tops-1 else j=0
2730 wend
2740 stack$(tops)=token$(i):tops=tops+1:return
2800 j=tops-1
2810 while stack$(j)<>"("
2820 list$(topl)=stack$(j):topl=topl+1:stack$(j)="":j=j-1
2830 wend
2840 stack$(j)="": tops=j
2850 return
5000 print token$(i);" : ";
5005 for m=1 to tops
5010 print stack$(m)+" ";
5020 next
5030 print " : ";
5040 return
5100 for m=1 to topl
5110 print list$(m)+" ";
5120 next
5130 print
5140 return

6000 list$(i-2)=str$(val(list$(i-2))+val(list$(i-1)))
6010 gosub 7000
6020 return
6100 list$(i-2)=str$(val(list$(i-2))-val(list$(i-1)))
6110 gosub 7000
6120 return
6200 list$(i-2)=str$(val(list$(i-2))*val(list$(i-1)))
6210 gosub 7000
6220 return
6300 list$(i-2)=str$(val(list$(i-2))/val(list$(i-1)))
6310 gosub 7000
6320 return
7000 for m=i+1 to topl
7010 list$(m-2)=list$(m)
7020 next
7025 i=i-2
7030 return





ここでひとまず、BASICで計算機を作るシリーズは終了して、VB.Netで再帰下降パースを使った
プログラムを作ってみることにします。

★VB.NETで計算機を作る〜自作コンパイラシリーズ
VB.Netで計算機を作る（字句解析）
VB.Netで計算機を作る（足し算・引き算）
VB.Netで計算機を作る（乗算・除算）