かんたんな自作言語のコンパイラをいろんな言語で書いてみるシリーズ 21番目の言語はシェルスクリプト（Bashスクリプト）です。
Bashがある環境ならどこでも自作言語で書いたプログラムをコンパイルできるようになりました。
2022-09-11 追記: すみません、いいかげんなことを書いてしまいましたが、普通に awk やら od やらを使っているので環境によってはそのままでは動かない可能性がありますね。
FreeBSD で動かしたい方は masakeida さんのフォーク版（ありがとうございます 
）を参照してください。
masakeida/vm2gol-v2-bash: toy compiler
https://github.com/masakeida/vm2gol-v2-bash
できたもの
いろいろと雑なのですが、アドベントカレンダーの期日があるのでとりあえず公開します。
サイズはこんな感じ。
$ wc -l {lexer,parser,codegen}.sh lib/*.sh
220 lexer.sh
655 parser.sh
525 codegen.sh
42 lib/common.sh
193 lib/json.sh
284 lib/utils.sh
1919 合計
動かし方の例
echo '
func add(a, b) {
return a + b;
}
func main() {
var one = 1;
var result;
call_set result = add(one, 2);
}
' | ./lexer.sh | ./parser.sh | ./codegen.sh
# ↓アセンブリが出力される
call main
exit
label add
push bp
cp sp bp
cp [bp:2] reg_a
push reg_a
cp [bp:3] reg_a
push reg_a
pop reg_b
pop reg_a
add_ab
cp bp sp
pop bp
ret
label main
push bp
cp sp bp
sub_sp 1
cp 1 reg_a
cp reg_a [bp:-1]
sub_sp 1
cp 2 reg_a
push reg_a
cp [bp:-1] reg_a
push reg_a
_cmt call~~add
call add
add_sp 2
cp reg_a [bp:-2]
cp bp sp
pop bp
ret
# (snip)
移植元
Bashスクリプト版のベースになっているバージョンは tag:62 のあたり
＜自作言語処理系の説明用テンプレ＞
自分がコンパイラ実装に入門するために作った素朴なトイ言語とその処理系です。簡単に概要を書くと下記のような感じ。
- 小規模: コンパイラ部分は 1,000 行程度
- pure Ruby / 標準ライブラリ以外のライブラリ不要
- x86風の自作VM向けにコンパイルする
- ライフゲームのために必要な機能だけ
- 変数宣言、代入、反復、条件分岐、関数定義
- 演算子:
+,*,==,!=のみ（優先順位は()で明示） - 型なし（値は符号付き整数のみ）
- 作ったときに書いた備忘記事
-
本体には含めていない後付けの機能など
- 真偽値リテラル / break / if/else / 単項マイナス / Racc などを使って書いたパーサの別実装
-
Ruby 以外の言語への移植
- コンパイラ部分のみ
- Python, Java, TypeScript など、2021-12-19 の時点では 20言語
- セルフホスト版
- 製作過程を知りたい場合は製作メモを見てください
＜説明用テンプレおわり＞
メモ
文字列
下記の記事のおかげでなんとかなりました。ありがとうございます
バイト単位で16進数表現との相互変換さえできてしまえば、あとは煮るなり焼くなり思いのまま、です。
データ構造
[
123, "fdsa",
[
11, "FDSA",
[]
]
]
のような、リストの要素として整数、文字列、リストを持たせることができる再帰的なデータ構造が必要です。
Bashスクリプトの配列は単純な値を入れる分にはいいのですが、ネストしたリストを扱うことができなさそうでした。そこで、下記のようにしました。「とりあえず最初に思いついた方法でやってみた」というもので、もっと良いやり方がある気がします。
（※ いつもならこういうことをやりたくなった段階で別の言語で書くことを検討しますが、今回は Bashスクリプトで書くこと自体が目的です）
まず、リストの要素にあたるデータの表現はこんな感じ。
# 整数
"int:-123"
# 文字列
"str:fdsa"
# リスト
"list:1"
- 先頭に型を表すタグを付けた1行の文字列
- 文字列の値（
str:...の...の部分）は改行を含まない（レキサで捨てる）ため、改行についての考慮は不要 -
list:の後に続く数字はリストID
たとえば ["+", 1, -2] というリストは次のように3行の文字列で表せます。1行がリストの要素1つに対応します。
"str:+
int:1
int:-2
"
この文字列をグローバルな配列変数に入れて管理する形にしました。要素のインデックスがリストIDに対応します。
たとえば、入れ子のあるリスト ["+", 1, ["*", 2, 3]] は次のようになります。
# GLOBAL[0]
"str:*
int:2
int:3
"
# GLOBAL[1]
"str:+
int:1
list:0
"
パフォーマンスの問題は別途ありますが、要するに下記のような操作ができるインターフェイスが用意できればOK。
- リストの要素数を求める
- リストのn番目の要素を読み書きする
- リストの要素の型を判別する
- リストに要素を追加する
関数からの値の返却
関数 myfunc から標準出力に出力して result="$(myfunc)" のようにコマンド置換で受け取る方法だと不都合な点が2つあります。
- (1) 末尾の改行の有無を制御しにくい
- (2) 呼び出した関数内でグローバル変数を更新できない
- コマンド置換だとサブシェルになるので
ちょっと悩みましたが、結局下記の方式に落ち着きました。
- 関数からの戻り値の受け渡し用のグローバル変数
RV1を用意する -
$(...)で囲まずに普通に関数を呼び出す - 関数側では、返したい値を
RV1に代入する - 呼び出し元では、関数呼び出しの直後に
RV1から移し替える
単純な例として、文字列を２つ受け取って連結した文字列を返す関数。
# return value
RV1=
myfunc() {
RV1="${1}${2}"
}
myfunc "foo" "bar"
retval="$RV1"
こうですね。単にこのパターンで書けばよいだけなので頭は使わなくてよいです。無心に書いていくとコンパイラができあがります。並行処理とかやってないですし、関数から戻った直後で受け取る約束さえ守っていれば問題は起こりません。
全然スマートじゃなくてなんじゃこりゃって感じのソリューションですけど、この方法にも良いところがあって、RV2, RV3, ... と増やすことで複数の値をいくらでも返すことができます。あと、コマンド置換よりはオーバーヘッドが小さいかもしれません（未確認）。
関数の中でグローバル変数を書き換える実際の例としてはリストの生成処理があります。ヒープにリスト用の領域を確保して、リストを指し示すポインタを返すようなイメージです。
new_list() {
new_gid
local self_=$RV1
GLOBAL[$self_]=""
RV1=$self_
}
new_list
list1_=$RV1
Ruby で書くとしたらこんな感じ。
def new_list
self_ = new_gid() # 新しいインデックスを採番
$GLOBAL[self_] = ""
return self_
end
list_ = new_list()
というわけで、かんたんなコンパイラを書くことにより、Bashスクリプトにおける
- 文字列処理
- データ構造（入れ子のあるリスト）
- 関数からの値の返却
についてのノウハウが新たに得られました。めでたしめでたし。
この記事を読んだ人は（たぶん）こちらも読んでいます