IchigoJam で簡易的な電卓コンパイラ (入力された計算式を計算して計算結果を返すM0マシン語を出力するプログラム) を作ってみた。
※IchigoJamはjig.jpの登録商標です。
仕様
以下の要素が使える。
- 32767までの整数リテラル
- 変数
A(マシン語呼び出し時の第1引数R0の値が入る、小文字のaも使用可) - 二項演算子
+(加算)、-(減算)、*(乗算) - カッコ
()(カッコ内を先に計算する)
二項演算子は左結合である。
* の優先度は + および - より高く、+ と - の優先度は同じである。
入力は、以下のBNFの <expr> が有効である。空白を含め余計な文字を入れてはいけない。
<expr> ::= <add>
<add> ::= <mult> | <add> <add-op> <mult>
<add-op> ::= "+" | "-"
<mult> ::= <value> | <mult> <mult-op> <value>
<mult-op> ::= "*"
<value> ::= <number> | <var> | "(" <add> ")"
<number> ::= <digit> | <number> <digit>
<digit> ::= "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"
<var> ::= "A" | "a"
入力の計算式は INPUT コマンドにより読み込む。
IchigoJam の INPUT コマンドの仕様により、文字列を入力ため最初に " をつけなければならない。
また、入力時にスクロールが発生すると、うまく入力を認識できなくなる点に注意すること。
出力先は、仮想アドレス #700 固定である。
変換が完了した場合、変換結果の長さを画面に出力する。
エラーが発生した場合、エラーメッセージを画面に出力する。
プログラム
10 ' ﾃﾞﾝﾀｸ ｺﾝﾊﾟｲﾗ
20 INPUT">",E:POKE#700,#F1,#B5:P=#702:[0]=E:[1]=E+LEN(E):[2]=0:S=2:GOSUB@A:IFE<AGOTO@S:ELSEPOKEP,#01,#B0,#F0,#BD:?P-#6FC;" Bytes":END
30 @S:?"Syntax error":END
40 @A:S=S+4:[S-2]=[S-6]:[S-1]=[S-5]:[S]=[S-4]:GOSUB@M:IFA=[S-6]GOTO60
50 O=PEEK(A-1):IFO=#2BORO=#2D[S-3]=O=#2D:[S-1]=A-1:[S]=[S-4]+1:GOSUB@A:R=[S-4]*#41|[S]<<3:POKEP,R,#18|[S-3]*2|R>>8:P=P+2
60 S=S-4:RETURN
70 @M:S=S+3:[S-2]=[S-5]:[S-1]=[S-4]:[S]=[S-3]:GOSUB@V:IFA=[S-5]GOTO90
80 IFPEEK(A-1)=#2A[S-1]=A-1:[S]=[S-3]+1:GOSUB@M:POKEP,#40|[S-3]|[S]<<3,#43:P=P+2
90 S=S-3:RETURN
100 @V:IF[S]>7?"Too complex":END
110 IF[S-2]=[S-1]GOTO@S
120 A=[S-1]-1:C=PEEK(A):IFC=#41ORC=#61POKEP,#00,#98|[S]:P=P+2:RETURN
130 IFC<>#29GOTO160
140 S=S+3:[S-2]=[S-5]:[S-1]=[S-4]-1:[S]=[S-3]:GOSUB@A:IFA=[S-5]GOTO@S
150 A=A-1:IFPEEK(A)<>#28GOTO@S:ELSES=S-3:RETURN
160 V=C-#30:D=10:IFV<0OR9<VGOTO@S
170 IFA=[S-2]GOTO190
180 C=PEEK(A-1)-#30:IF0<=CANDC<=9A=A-1:V=V+D*C:D=D*10:GOTO170
190 IFV>255POKEP,V>>8,#20|[S],[S]*9,#02,V,#30|[S]:P=P+6ELSEPOKEP,V,#20|[S]:P=P+2
200 RETURN
このプログラムは、CC BY 4.0 でライセンスする。
このプログラム (改造したものを含む) を公開の場で利用する際は、出典を示していただけると嬉しい。
これは、Qiitaの利用規約に基づくプログラムの利用を禁止するものではない。
実行結果例
演算子の優先順位やカッコを考慮した計算、および引数の使用ができている。
解説
呼び出し規約・引数と戻り値
今回のプログラムで使用したパース用のサブルーチン @A、@M、@V は、共通で以下の仕様になっている。
- スタックポインタとして変数
Sを用いる。 - スタックは配列の小さい添字から大きい添字に向かって伸び、スタックポインタは有効な値が入っている最後の要素を表す。
- パース開始アドレス (最初の文字のアドレス)、パース終了アドレス (最後の文字の次のアドレス)、結果を出力するレジスタの番号、をこの順にスタックに積んだ状態で呼び出す。
- 出力する計算処理は、渡された「結果を出力するレジスタ」およびそれより番号が大きいレジスタのみを用いて行う。
- スタックポインタ以外の変数は自由に使用してよい。呼ばれた時点で積まれているスタックの内容は、引数を含め変更してはいけない。
- 戻る際、返り値としてパース済みアドレス (後ろからパースを行った最後 (メモリ上で一番前) の文字のアドレス) を変数
Aに格納する。
前からパースしようとすると、add や mult の最初に同じ add や mult が配置されているので、無限ループになりやすい。
そこで、異なる要素が配置された後ろからパースすることで、処理をしやすくした。
コンパイラの作成では、トークンの分割・構文解析 (ASTの作成)・マシン語の生成をそれぞれ分けて行うことが多い。
しかし、今回は、容量を節約するためこれらを全て一気に行う。
10行目：タイトル
FILES 対応のタイトル行である。
20行目：入力受付、expr のパース、プロローグとエピローグの出力
INPUT">",E
入力の計算式を E に受け取る。
POKE#700,#F1,#B5:P=#702
出力先 P を初期化し、プロローグとして
PUSH {R0,R4,R5,R6,R7,LR}
を出力する。
これにより、callee-save レジスタの値および戻り用の LR を保存するとともに、引数 R0 をスタックに積む処理である。
[0]=E:[1]=E+LEN(E):[2]=0:S=2:GOSUB@A
- パース開始位置、パース終了位置、計算結果出力先レジスタ (
R0) をスタックに積む。 - スタックポインタ
Sを初期化する。 - add をパースするサブルーチンを呼び出す。
IFE<AGOTO@S:ELSEPOKEP,#01,#B0,#F0,#BD:?P-#6FC;" Bytes":END
返り値のパース済み位置が先頭でない場合は、余計な文字があったということなので、コンパイルエラーとする。
そうでない場合は、エピローグ
SP += 1
POP {R4,R5,R6,R7,PC}
を出力する。
これは、スタックに積んだ引数 R0 をポップし、callee-save レジスタの値を復元して呼び出し元に戻る処理である。
最後に、出力したバイト数を画面に出力し、終了する。
容量節約のため、最後の出力分 P に4を足すかわりに、容量の計算で P から引く値からあらかじめ4を引いている。
30行目：構文エラー表示
「Syntax error」を出力し、終了する。
40～60行目：add をパースする処理
40 @A:S=S+4
スタックにサブルーチンを呼び出す際の引数などの作業領域を確保する。
[S-2]=[S-6]:[S-1]=[S-5]:[S]=[S-4]:GOSUB@M
パース対象範囲を渡された範囲すべて、計算結果出力先レジスタを渡された計算結果出力先レジスタとして、mult をパースする処理を行う。
mult は、add 全体を置き換えるか、add の演算子の右側を置き換える。
IFA=[S-6]GOTO60
処理を行った結果、対象範囲全体がパースされた場合は、パース処理を完了する。
50 O=PEEK(A-1):IFO=#2BORO=#2D
パース済範囲の1文字前 (すなわち、演算子) を読み込み、+ または - であるかを判定する。
どちらでもない場合、このまま処理を完了する。
[S-3]=O=#2D
サブルーチン呼び出しによる変数の破壊に備え、演算子の種類をスタックに保存する。
[S-1]=A-1:[S]=[S-4]+1:GOSUB@A
パース対象範囲を演算子の左側、結果出力先レジスタを渡された結果出力先レジスタの1個次のレジスタとして、add をパースする処理を行う。
R=[S-4]*#41|[S]<<3:POKEP,R,#18|[S-3]*2|R>>8:P=P+2
結果出力先レジスタ (=右辺の計算結果が格納されたレジスタ) を Rd、左辺の計算結果が格納されたレジスタを Rm として、演算子に応じて
Rd = Rm + Rd
または
Rd = Rm - Rd
を出力する。
スタックに保存しておいた演算子情報を用いる。
60 S=S-4:RETURN
スタックの確保した領域を開放し、呼び出し元に戻る。
70～90行目：mult をパースする処理
add をパースする処理と同様である。
ただし、以下の点が異なる。
- 右辺 (または全体) のパースは value、左辺のパースは mult として行う。
- 演算子は
*であるかをチェックする。 - 有効な演算子がある場合、左辺のパース後
Rd *= Rmを出力する。 - 演算子が1種類なので、種類は保存しない。そのため、スタックの確保量も add より少ない。
100～200行目：value をパースする処理
100～110行目：チェック処理
100 @V:IF[S]>7?"Too complex":END
計算結果出力先レジスタが R7 を超えている場合、レジスタ不足なので「Too complex」を出力して処理を中断する。
110 IF[S-2]=[S-1]GOTO@S
パース対象が空の場合、「Syntax error」を出して処理を中断する。
120行目：var をパースする処理
120 A=[S-1]-1:C=PEEK(A):IFC=#41ORC=#61POKEP,#00,#98|[S]:P=P+2:RETURN
パース対象の最後の文字が A または a の場合、計算結果出力先レジスタを Rd として
Rd = [SP + 0]L
を出力し、戻る。文字を取得する際にパース済み範囲も設定している。
130～150行目：カッコをパースする処理
130 IFC<>#29GOTO160
パース対象の最後の文字が ) かをチェックする。違う場合は、カッコの処理を飛ばす。
140 S=S+3:[S-2]=[S-5]:[S-1]=[S-4]-1:[S]=[S-3]:GOSUB@A
カッコの中身を add としてパースする。
IFA=[S-5]GOTO@S
パースの結果入力の最後まで消費していた場合、「Syntax error」を出して処理を中断する。
150 A=A-1:IFPEEK(A)<>#28GOTO@S:ELSES=S-3:RETURN
パースされたカッコの中身の1個前の文字を取得する。
それが ( であれば、戻る。
そうでなければ、「Syntax error」を出して処理を中断する。
160～200行目：number をパースする処理
160 V=C-#30:D=10:IFV<0OR9<VGOTO@S
number のパースを開始する。
最後の文字が数字でない場合、「Syntax error」を出して処理を中断する。
文字列から数値へ変換する際に用いる係数 D と変換結果 V を初期化する。
V には、1文字目を変換した結果を入れておく。
170 IFA=[S-2]GOTO190
パース対象範囲の最後 (最初) まで変換を行った場合、変換を終了して次の処理に進む。
180 C=PEEK(A-1)-#30:IF0<=CANDC<=9A=A-1:V=V+D*C:D=D*10:GOTO170
次の文字を取得する。それが数字ならば、変換結果に反映し、係数を更新し、変換を続行する。
数字でない場合は、次の処理に進む。
190 IFV>255POKEP,V>>8,#20|[S],[S]*9,#02,V,#30|[S]:P=P+6
変換結果の数値が 255 を超えている場合は、変換結果の上位バイトを VH、下位バイトを VL、計算結果出力先レジスタを Rd として
Rd = VH
Rd = Rd << 8
Rd += VL
を出力する。
ELSEPOKEP,V,#20|[S]:P=P+2
変換結果の数値が 255 以下の場合は、変換結果を V、計算結果出力先レジスタを Rd として
Rd = V
を出力する。
200 RETURN
処理を完了し、戻る。
プログラム (改良版)
計算式の入力時、最初に " を入力するのは面倒で、忘れがちであった。
そこで、最初の INPUT の前にキーバッファをいじって " を自動入力する処理を追加した。
10 ' ﾃﾞﾝﾀｸ ｺﾝﾊﾟｲﾗ 2
20 N=PEEK(4099):POKE4100+N,34:POKE4099,N+1:INPUT">",E:P=#702:POKEP-2,#F1,#B5:[0]=E:[1]=E+LEN(E):[2]=0:S=2:GOSUB@A:IFE=APOKEP,1,#B0,#F0,#BD:?P-#6FC;" Bytes":END
30 @S:?"Syntax error":END
40 @A:S=S+4:[S-2]=[S-6]:[S-1]=[S-5]:[S]=[S-4]:GOSUB@M:IFA=[S-6]GOTO60
50 O=PEEK(A-1):IFO=43ORO=45[S-3]=O=45:[S-1]=A-1:[S]=[S-4]+1:GOSUB@A:R=[S-4]*65|[S]*8:POKEP,R,24|[S-3]*2|R>>8:P=P+2
60 S=S-4:RETURN
70 @M:S=S+3:[S-2]=[S-5]:[S-1]=[S-4]:[S]=[S-3]:GOSUB@V:IFA=[S-5]GOTO90
80 IFPEEK(A-1)=42[S-1]=A-1:[S]=[S-3]+1:GOSUB@M:POKEP,64|[S-3]|[S]*8,#43:P=P+2
90 S=S-3:RETURN
100 @V:IF[S]>7?"Too complex":END
110 IF[S-2]=[S-1]GOTO@S
120 A=[S-1]-1:C=PEEK(A):IFC|32=97POKEP,0,#98|[S]:P=P+2:RETURN
130 IFC-41GOTO160
140 S=S+3:[S-2]=[S-5]:[S-1]=[S-4]-1:[S]=[S-3]:GOSUB@A:IFA=[S-5]GOTO@S
150 A=A-1:IFPEEK(A)-40GOTO@S:ELSES=S-3:RETURN
160 V=C-48:D=10:IFV<0OR9<VGOTO@S
170 IFA=[S-2]GOTO190
180 C=PEEK(A-1)-48:IF0<=CANDC<=9A=A-1:V=V+D*C:D=D*10:GOTO170
190 IFV>255POKEP,V>>8,32|[S],[S]*9,2,V,48|[S]:P=P+6ELSEPOKEP,V,32|[S]:P=P+2
200 RETURN
このプログラムは、CC BY 4.0 でライセンスする。
このプログラム (改造したものを含む) を公開の場で利用する際は、出典を示していただけると嬉しい。
これは、Qiitaの利用規約に基づくプログラムの利用を禁止するものではない。