〜program言語を作ってみるシリーズ
CPUを自作する、OSを自作する、プログラム言語を自作するという一連の自作の試み(*)のなかで、
プログラム言語を自作シするリーズのとっかかりとして計算機を作ってみる。
(*)自作の試みについては、BLOG 開発とお客様の狭間で プログラミング言語を作る などに書いてます。
字句解析までは、計算機を作ってみる-字句解析に書きましたのでそちらをご参照下さい。
Token化できたら、次は構文解析になります。構文解析のアプローチもいろいろあります。
C言語のように再帰プログラムが可能な言語では、再帰下降パーサという方法で洗練された
構文解析プログラムヲかけます。
が、今回は旧BASICで始めたので再帰プログラムが書けません。
なので、手始めに地道に一番オーソドックスに解析木を作ってみることにします。
例えば、5+2*3 という式は、次のような解析木になります。
（図１）最初にプログラム実行画面をみてみます。
（画面１）まず5+2*3をトークン化します。
token1 : 5
token2 : +
token3 : 2
token4 : *
token5 : 3
次に、
上のような木の構造にはしていませんが、解析をします。
tree 1 + token2, 5 token1, * token4
という部分は、「+(token2)は5(token1)と*(token4)とに枝分かれしている」という解析結果になります。
tree2 * token4, 2 token3, 3 token5
の部分は、「*は2と3に枝分かれしている」
という解析結果を表示しています。
字句解析のプログラム（−＞計算機を作ってみる-字句解析）にこのプログラムで追加したのは
110〜140行目、実質的には3000行番台と4000行番台です。
トークンの種類が+または-の場合は3000行番台、*または/の場合は4000行番台で処理します。
以下、3000行番台、4000行番台の処理について説明します。
変数
tree$ 結節点のデータ
treer$ 左の子ノードのデータ
treel$ 右の子ノードのデータ
tree,treer,treelにはtokenのナンバーを保存
t treeの番号
変数はいろいろ出てきてわかりにくいので、「計算機を作ってみる-完成形(1)変数」もご参照下さい。
*, /の処理の方が簡単なので、先に4000行台を見てみることにします。
具体例でまず処理の仕方をなぞってみます。
5/2*3 の場合、以下のようにトークン化されます。
token1 : 5
token2 : /
token3 : 2
token4 : *
token5 : 3
左から演算していくという数学のルールにのっとれば分析木で表すと、図２のようになります。
（図２）最初の演算子である/（割り算）については、左ノードは一つ手前のトークンである5、右ノードには一つ後ろのトークンである2を
もってくればよい。
２つ目の演算子である*の時はどう処理すればよいか。
２つ前のトークンを調べ、/なのでこれを左ノードに入れる。右ノードは一つ後ろのトークンである3をもってくる。
もし、この式が5+2*3だと、演算の優先順位は掛け算・割り算が上なので、図１のような解析木になります。
この場合のように２つ前の演算子が+または-なら、左の子ノードにはひとつ前のトークンを、右の子ノードには一つ後ろのトークンを
入れることになります。（図１の*の解析木の部分を参照）
4010〜4030行は上記で説明したような作業を行っています。
・右の子ノード
右の子ノードにはいずれにせよひとつ後ろのトークンを入れる（4040行）。
・左の子ノード
左の子ノード（treer$)に入れるデータが複数パターンに分かれるので、4010〜4030行はその処理をしている
t=1の場合、すなわち式の中に最初に出てきた演算子の場合は、１つ前のトークンを左の子ノード（treer$)に入れる。
t>2、すなわち２つめ以降の演算子の場合は、２つ前のトークン（つまり１つ前の演算子）が*または/ならその演算子を
左の子ノード（treer$)に入れる。
t>2で２つ前のトークン（つまり前の演算子）が+または-なら、ひとつ前のトークン（数値）を左の子ノード（treer$)に入れる。
演算子 +, -の処理
+, -の処理は3000行台になります。
+,-の場合は、左の子ノードも右の子ノードもいくつかのパターンに分かれます。
具体例で考えてみます。
2*3*4+5 は分析木で表すと以下の図3のようになります。
（図３）+の左の子ノードにはひとつ前の演算子である*、右の子ノードにはひとつ後ろのトークンである5が入ります。
次に、1+2*3*4+5 という式を分析木で表してみます（図4）。
（図4)+の左の子ノードにはひとつ前の演算子である*ではなくて、ずっと前のほうに出現している+が入ります。
演算子の優先順位を考慮していくと、左の子ノードはなかなかに複雑な判定が必要になります。
一応、ルールとしては例えば以下のような解析パターンで解決できそうです。
+または-の演算子の左の子ノードの解析
・+または-の演算子が式の最初の演算子（一番左にある演算子）なら、左の子ノードにはひとつ前のトークン（数値）を入れる。
・式の左側を順（左側に向かって）に分析していき、+または-の演算子があったら、その演算子を左の子ノードに入れる。
・式の左側を順に分析していき、+または-の演算子がなければ、ひとつ手前の演算子を左の子ノードに入れる。
以下、プログラムの全体です。
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
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