シェルスクリプト（Bashスクリプト）でかんたんな自作言語のコンパイラを書いた

かんたんな自作言語のコンパイラをいろんな言語で書いてみるシリーズ 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向けにコンパイルする
• ライフゲームのために必要な機能だけ
  • 変数宣言、代入、反復、条件分岐、関数定義
  • 演算子: +, *, ==, != のみ（優先順位は ( ) で明示）
  • 型なし（値は符号付き整数のみ）
• 作ったときに書いた備忘記事
  • RubyでオレオレVMとアセンブラとコード生成器を2週間で作ってライフゲームを動かした話
  • Rubyでかんたんな自作言語のコンパイラを作った
• 本体には含めていない後付けの機能など
  • 真偽値リテラル / 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) 末尾の改行の有無を制御しにくい
  • シェルスクリプトにはコマンド出力を変数に入れると末尾の改行が全部消えてしまう罠がある！ - Qiita に書かれている通り
• (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スクリプトにおける

• 文字列処理
• データ構造（入れ子のあるリスト）
• 関数からの値の返却

についてのノウハウが新たに得られました。めでたしめでたし。

この記事を読んだ人は（たぶん）こちらも読んでいます