～program言語を作ってみるシリーズ
CPUを自作する、OSを自作する、プログラム言語を自作するという一連の自作の試み(*)のなかで、
プログラム言語を自作シするリーズのとっかかりとして計算機を作ってみる。
(*)自作の試みについては、BLOG 開発とお客様の狭間で プログラミング言語を作る などに書いてます。
プログラミング言語（コンパイラ）を作ってみようと思った時に、ひとつ手にとってみる本としては、
情報系の学生がプログラミング言語を作る（コンパイラを作る）というような講義で使いそうなテキストがある。
それらのテキストを見てみると、そもそも”コンパイラとは”というところから説明が始まり、次にだいたい
「文脈自由文法」のあたりの説明が続く。
そこには、
「書き換えを行う対象となる非終端記号の集合Ｎ、書き換えを行うことができない終端記号の称号Ｔ，
書き換え（生成）規則の集合Ｐ，そして書き換えを開始する最初の非終端記号となる開始記号Ｓによって
定義される」云々
というような説明があって、これは正面玄関の入口には違いないが、ここから入ってコンパイラ自作まで
行きつける人が果たして何人いるんだろうかと思わざるを得ない説明がえんえんと続く。
こういう風に基礎理論からちゃんと勉強してから、コンパイラ作成を始めるというのもひとつのアプローチではあるし、
基礎理論はちゃんと勉強するにこしたことはないのだが、こういう説明が続くと最初のところで果てちゃいそう（ですよね）。
ということで、理論は後で勉強することにして、とりあえず四則演算の計算機でも実際に作ってみることにする。
たかが、四則演算の計算機とはいえ、
いずれにせよ、インプットされた式（文字列）に対して、
字句解析（トークン化する） －＞ 構文解析 －＞解析に基づいて演算を実行
という流れを実装することになる。
計算機を作って見る時に、大別して
(A) YACCとLEXを使う
(B) イチからスクラッチで作る
の２通りある。
プログラム言語を作るとなると、(A)が王道のやり方。
YACC(Yet another compiler compilerの略らしい）は構文解析用のプログラムを生成してくれる
プログラム、LEXはレキシカルアナライザと呼ばれるもので、こちらは字句解析を行うプログラムを
生成してくれるもの。
YACCとLEXを使うと計算機レベルのものなら自分が記述する部分は数行の記述でできちゃったりするのだが、
①YACCとLEXが生成してくれたソースコードは馬鹿でかい。たかが四則演算の計算機にどんだけ余計な脂肪が
ついてんだろ、という無駄な感覚
②その中で何を行っているのかがBlackBOXで気持ちが落ちつかない。（これは吐き出されたソースコードを解析すれば
わからなくもないが）
③YACCやLEX用の記述はBNF記法とか正規表現をきちんと理解していないと書けない。
BNF記法や正規表現はちゃんと勉強したほうがいいに決まってんだけど・・
(正規表現については->「正規表現と有限オートマトン」参照）
という、あれやこれやの理由で、まずは(B)スクラッチで作ってみることにする。
いずれ、別の回でYACCやLEXを使った作り方もやりたいとは思いますが。
いずれ、最終的にはCやPythonなどの再帰呼び出しのできる言語や、その他の言語で作ることにしますが、
とりあえずアルゴリズムの確認やらなにやらのためのプロトタイプは旧型BASICでやることにします。
（BASICなんて、とバカにする人が多いですが、この程度のプログラムのアルゴリズムの検証ならBASICが楽）
（＊）BASICで無理やり再帰コールのまねごとをしてみる －＞「BASICで再帰呼び出しもどきをやってみる」
最初は、入力された式（文字列）を字句解析してトークン化する部分をやってみる。
最初に作ってみたのはこれ（token.bas)。N88互換BAIS for Winで作成。
とりあえず動けばいいという試作レベルなので、エラーチェックもほとんどしてないし、コードも動けばいいレベルなので
無駄なコードがあったり、まだバグがあったりするかもしれません。
今回のプログラムの前段階として作ったのが、空白を区切りとして入力された文字列から整数だけを抜き出す
プログラム。（－＞「入力データが整数かどうか判定する」）
今回はそこに、演算子（+, -, *, /)の判定を付け加えたものになる。
そこでも書いたのですが、今回作るような字句解析（レキシカルアナライザー）みたいな機能は、正規表現
の使えるプログラム言語ならあっさり解決（「正規表現と有限オートマトン」参照）なのですが、旧BASICでは
ゴリゴリ解析するコードを書くことになります。
入力の規則として
数値とオペレータ（演算子）は空白で区切るルールにしている。空白は連続していても構わない。
00,000,001という0だけが連続する表記は許容していない。+0,-0という表記も許容しない。
0～9,+,=,*,/と空白以外の文字は読み飛ばすので、aとかｂとか#などが文字列にあってもエラーにせず
読み飛ばしてく。
なお、N88互換BASICの特色として、10行目 input文で文字列を入力するとき、空白もいっしょに取り込む。
元祖N88BASICやF=BASICは空白を含んだ文字列を入力するときは、"This is a pen."のようにコーテーションマーク
で文字列を囲んでやる必要がある。
プログラムの全体的な流れ、
30～90行 文字列を1字づつ取り出して、文字のタイプ（数字か演算子かetc.）を判定（変数typeに文字のタイピを格納）。
100～120行 数値、演算子などのかたまりとしてトークン化
変数は以下の通り
type １字づつ取り出した字のタイプの判定
0・・初期状態 1・・１文字目が0 2・・１文字目0以外の数値 3・・１文字目が-（負の数） 5・・演算子 10・・エラー
n トークンの個数
１字取り出し
20行 入力された文字列の長さを変数 l に保存
30～90行 最初の文字から終わりの文字までfor ループで取り出し、type判定処理を回す
40行 mid$で1字づつ取り出し
85行 エラー判定（type=10)の場合は、1字判定処理を終了し次の処理（トークン化）に移る
具体的なtypeの判定処理は以下のサブルーチンをコールして処理している。
最初の1文字、または空白の後の最初の1文字は1000行目からのサブルーチンで処理
1010行 ascで字のアスキーコードを取得。数字（1～9 = アスキーコードは&H31～&H39） ならType=2（0以外の数値）
1020行 先頭に"-"が来た場合はマイナス記号（負の数）かどうかの判定（1100行目）をコール。符号としてのマイナス記号ならtype=5 とする。
演算子のマイナス（引き算）の記号と判定した場合はtype=3とする。
1030行 先頭に0がきた場合の判定処理（1200行）をコール。正しい0（単独の0）ならType=1、そうでなければエラー（type=10）とする。
このプログラムでは00,001,のような記述は許容していないため。
1040行 演算子としての、+,*,/の判定処理。1300行をコールし演算子としての正しい使い方ならtype=5とする。
ここまでの1000～1040行で正しい表記として判定された場合は、新しいトークンの始まりとして認識し、n=n+1している。
1045行 空白の場合はtype=0 とする。
1050行 正しい表記として認識された場合（type>0 and type<10）は新しいトークンに書き込む。
ここでトークン化の作業も行っていることになる。
2文字目以降の処理
前の文字が0以外の数値だった場合（Type=2)は、2000行をコール
2000行 数値の場合（0～9）は、type=2を継続。今のトークンに続けて書き込む。
空白の場合はType=0とする。
前の文字がマイナス記号（負の符号）（Type=3）だった場合は、2500行をコール
0以外の数値(1～9）の場合はType=2として、今のトークンに続けて書き込む。
0だったり、演算記号だった場合はエラーとし、Type=10とする。
このプログラムでは-0という書き方は許容しないので、0が続いた場合はエラーにしている。
トークン化とトークンの表示
上記の1字取り出しての判定処理において既にトークン化はやってしまｌっているので、
100～120行は トークンを表示して7みせているだけ。
<token.bas>
5 dim token$(20)
10 input a$
14 'type 0・・初期状態 1・・１文字目0 2・・１文字目0以外の数値 3・・１文字目- 5・・演算子 10・・エラー
15 n=0:type=0
20 l=len(a$)
30 for i=1 to l
40 moji$=mid$(a$,i,1)
50 if type=3 then gosub 2500: goto 85
60 if type=2 then gosub 2000: goto 85
70 if type=0 then gosub 1000
80 if moji$=" " then type=0 : print moji$;":type:";type '空白が連続していてもtype=0を継続
85 if type=10 then goto 100
90 next
100 for i=1 to n
110 print "token";i;":";token$(i)
120 next
130 if type=10 then print "error"
500 end
1000 type=10 'いったん全てerror type=10 としておく
1010 if (asc(moji$)>=&H31 and asc(moji$)<=&H39) then n=n+1: type=2
1020 if moji$="-" then n=n+1: gosub 1100
1030 if moji$="0" then n=n+1: gosub 1200
1040 if (moji$="+" or moji$="*" or moji$="/") then n=n+1: gosub 1300
1045 if moji$=" " then type=0: goto 1070 '空白文字の出力は80行で行うのでここではパス
1050 if type>0 and type<10 then token$(n)=token$(n)+moji$
1060 print moji$;":type:";type
1070 return
1100 if (i<l and mid$(a$,i+1,1)=" ") or i=l then type=5 else if i<l and (asc(mid$(a$,i+1,1))>=&H31 and asc(mid$(a$,i+1,1))<=&H39) then type=3 else type=10 'この-が演算子か符号か
1110 return
1200 if mid$(a$,i+1,1)=" " or i=l then type=1 else type=10 'type=10 はエラーにする
1210 return
1300 if mid$(a$,i+1,1)=" " or i=l then type=5 else type=10 'type=10 はエラーにする
1310 return
2000 if (asc(moji$)>=&H30 and asc(moji$)<=&H39) then type=2:token$(n)=token$(n)+moji$ else if moji$=" " then type=0 else type=10
2020 if type=2 or type =0 then print moji$;":type:";type
2030 return
2500 if (asc(moji$)>=&H31 and asc(moji$)<=&H39) then type=2 else type=10
2510 token$(n)=token$(n)+moji$: print moji$;"type:";type
2520 return
特に字句解析（トークン化）のプログラムに難しいところはないが、
0やマイナス符号の処理では、次に続く1字まで読み込んで判定する必要があるのが少々面倒なところ。
10 - 12 * 5
と入力したところ。
まず式（文字列）を１文字づつ解析し、数字はまとめて数値としてトークン化している。
ということでひとまず、式（文字列）の字句解析（トークン化）の基本的な部分はこんな感じ。