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

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/234055/9ebeab7b-e274-4b72-4c9a-1a69b3c3c2c9.png)

[かんたんな自作言語のコンパイラをいろんな言語で書いてみるシリーズ](https://memo88.hatenablog.com/entry/2020/08/30/132314) 21番目の言語はシェルスクリプト（Bashスクリプト）です。

~~Bashがある環境ならどこでも自作言語で書いたプログラムをコンパイルできるようになりました。~~

:::note

2022-09-11 追記: すみません、いいかげんなことを書いてしまいましたが、普通に awk やら od やらを使っているので環境によってはそのままでは動かない可能性がありますね。

FreeBSD で動かしたい方は masakeida さんのフォーク版（ありがとうございます :pray:）を参照してください。

masakeida/vm2gol-v2-bash: toy compiler
https://github.com/masakeida/vm2gol-v2-bash

:::






# できたもの

https://github.com/sonota88/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 合計
```



# 動かし方の例

```bash
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)
```






# 移植元

https://github.com/sonota88/vm2gol-v2


Bashスクリプト版のベースになっているバージョンは [tag:62](https://github.com/sonota88/vm2gol-v2/tree/62) のあたり

<!--
（追記 2021-09-18: [ステップ60](https://memo88.hatenablog.com/entry/20210911_vm2gol_v2_60_pass_stmt) の修正まで適用しました）
-->

＜自作言語処理系の説明用テンプレ＞

自分がコンパイラ実装に入門するために作った素朴なトイ言語とその処理系です。簡単に概要を書くと下記のような感じ。

<!--
入門者（＝自分）にやさしく、難しいことをせずに短期間でババッと作れることを重視してる感じの仕様・実装です。
- リポジトリ: [github.com/sonota88/vm2gol-v2](https://github.com/sonota88/vm2gol-v2)
-->

- 小規模: コンパイラ部分は 1,000 行程度
- pure Ruby / 標準ライブラリ以外のライブラリ不要
- x86風の自作VM向けにコンパイルする
- ライフゲームのために必要な機能だけ
  - 変数宣言、代入、反復、条件分岐、関数定義
  - 演算子: `+`, `*`, `==`, `!=` のみ（優先順位は `(` `)` で明示）
  - 型なし（値は符号付き整数のみ）
- 作ったときに書いた備忘記事
  - [RubyでオレオレVMとアセンブラとコード生成器を2週間で作ってライフゲームを動かした話](https://qiita.com/sonota88/items/f9cb3fc4a496b354b729)
  - [Rubyでかんたんな自作言語のコンパイラを作った](https://qiita.com/sonota88/items/2b95378b43a22109513c)
- [本体には含めていない後付けの機能など](https://memo88.hatenablog.com/entry/vm2gol_v2_additional_features)
    - 真偽値リテラル / break / if/else / 単項マイナス / Racc などを使って書いたパーサの別実装
- [Ruby 以外の言語への移植](https://memo88.hatenablog.com/entry/2020/08/30/132314)
    - コンパイラ部分のみ
    - Python, Java, TypeScript など、2021-12-19 の時点では 20言語
- [セルフホスト版](https://qiita.com/sonota88/items/1e683276541cf1b87b76)
- 製作過程を知りたい場合は[製作メモ](https://memo88.hatenablog.com/entry/2019/05/04/234516)を見てください

＜説明用テンプレおわり＞



# メモ

## 文字列

<!--
Bashスクリプトだと文字列を素直に扱えなくて面倒なのですが、
-->

下記の記事のおかげでなんとかなりました。ありがとうございます :pray:

<!-- シェルスクリプトはバイナリを扱えない。さてどうしよう…… - Qiita -->
https://qiita.com/richmikan@github/items/6b763519a28b4ce40031

バイト単位で16進数表現との相互変換さえできてしまえば、あとは煮るなり焼くなり思いのまま、です。







## データ構造

```json
[
  123, "fdsa",
  [
    11, "FDSA",
    []
  ]
]
```

<!--
（今回作ったコンパイラでは）
あと、そのままだと整数と文字列の区別ができません。

のような、リストの要素として整数、文字列、リストを持たせることができる再帰的なデータ構造が必要です。Bashスクリプトには配列はあり、単純な値を入れる分にはいいのですが、普通のやりかたではネストしたリストに相当するデータを扱うことができなさそうでした。
-->

のような、リストの要素として整数、文字列、リストを持たせることができる再帰的なデータ構造が必要です。


<!--
ここは自前でなんとかする必要があり、ひとまず下記のようにしました。もっと良いやり方がある気がします。
-->
Bashスクリプトの配列は単純な値を入れる分にはいいのですが、ネストしたリストを扱うことができなさそうでした。そこで、下記のようにしました。「とりあえず最初に思いついた方法でやってみた」というもので、もっと良いやり方がある気がします。

（※ いつもならこういうことをやりたくなった段階で別の言語で書くことを検討しますが、今回は Bashスクリプトで書くこと自体が目的です）

まず、リストの要素にあたるデータの表現はこんな感じ。

<!--
配列には文字列は入れられるので、文字列で表現します。
以下、このデータ構造のことを *ノード* と呼ぶことにします。
-->

```bash
# 整数
"int:-123"

# 文字列
"str:fdsa"

# リスト
"list:1"
```

<!--
レキサ～コード生成の過程で扱う
-->

- 先頭に型を表すタグを付けた1行の文字列
- 文字列の値（`str:...` の `...` の部分）は改行を含まない（レキサで捨てる）ため、改行についての考慮は不要
- `list:` の後に続く数字はリストID

たとえば `["+", 1, -2]` というリストは次のように3行の文字列で表せます。1行がリストの要素1つに対応します。

```bash
"str:+
int:1
int:-2
"
```

この文字列をグローバルな配列変数に入れて管理する形にしました。要素のインデックスがリストIDに対応します。

たとえば、入れ子のあるリスト `["+", 1, ["*", 2, 3]]` は次のようになります。

```bash
# GLOBAL[0]
"str:*
int:2
int:3
"

# GLOBAL[1]
"str:+
int:1
list:0
"
```

<!--
というわけで、足回りとしてここらへんが用意できればコンパイラが作れることが知られています（私の中で）。

パフォーマンスの問題は別途ありますが、要するに下記のような操作ができるインターフェイスが用意できればよくて、実装は（とりあえずは）なんでもいいのです。

-->

パフォーマンスの問題は別途ありますが、要するに下記のような操作ができるインターフェイスが用意できればOK。

- リストの要素数を求める
- リストのn番目の要素を読み書きする
- リストの要素の型を判別する
- リストに要素を追加する



## 関数からの値の返却

関数 `myfunc` から標準出力に出力して `result="$(myfunc)"` のようにコマンド置換で受け取る方法だと不都合な点が2つあります。




- (1) 末尾の改行の有無を制御しにくい
    - [シェルスクリプトにはコマンド出力を変数に入れると末尾の改行が全部消えてしまう罠がある！ - Qiita](https://qiita.com/ko1nksm/items/7c4040c6b6f3fac14db7) に書かれている通り
- (2) 呼び出した関数内でグローバル変数を更新できない
    - コマンド置換だとサブシェルになるので

ちょっと悩みましたが、結局下記の方式に落ち着きました。

- 関数からの戻り値の受け渡し用のグローバル変数 `RV1` を用意する
- `$(...)` で囲まずに普通に関数を呼び出す
- 関数側では、返したい値を `RV1` に代入する
- 呼び出し元では、関数呼び出しの直後に `RV1` から移し替える

単純な例として、文字列を２つ受け取って連結した文字列を返す関数。

```bash
# return value
RV1=

myfunc() {
  RV1="${1}${2}"
}

myfunc "foo" "bar"
retval="$RV1"
```

<!--
このコンパイラでは
計測してないですけど、たぶん
-->

こうですね。単にこのパターンで書けばよいだけなので頭は使わなくてよいです。無心に書いていくとコンパイラができあがります。並行処理とかやってないですし、関数から戻った直後で受け取る約束さえ守っていれば問題は起こりません。

全然スマートじゃなくてなんじゃこりゃって感じのソリューションですけど、この方法にも良いところがあって、`RV2`, `RV3`, ... と増やすことで複数の値をいくらでも返すことができます。あと、コマンド置換よりはオーバーヘッドが小さいかもしれません（未確認）。


<!--
これで立派に「戻り値の受け渡しの要件」を満たせます。
-->

関数の中でグローバル変数を書き換える実際の例としてはリストの生成処理があります。ヒープにリスト用の領域を確保して、リストを指し示すポインタを返すようなイメージです。

```bash
new_list() {
  new_gid
  local self_=$RV1
  GLOBAL[$self_]=""

  RV1=$self_
}

new_list
list1_=$RV1
```

<!--
これは、たとえば JavaScript で書くと下記に対応します。

 ```javascript
function newList() {
  const self_ = newGid();
  g[self_] = ""; // グローバルな配列を更新
  return self_;
}

const list1_ = newList();
 ```
-->

Ruby で書くとしたらこんな感じ。

```ruby
def new_list
  self_ = new_gid() # 新しいインデックスを採番
  $GLOBAL[self_] = ""
  return self_
end

list_ = new_list()
```




----

というわけで、かんたんなコンパイラを書くことにより、Bashスクリプトにおける

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

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




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

<!-- Perlでかんたんな自作言語のコンパイラを書いた - Qiita -->
https://qiita.com/sonota88/items/1482e236054ad3edfdf5

<!-- なでしこ3でかんたんな自作言語のコンパイラを書いた - Qiita -->
https://qiita.com/sonota88/items/54c65e97aa563009137e

<!-- 素朴な自作言語のコンパイラをLibreOffice Basicに移植した - Qiita -->
https://qiita.com/sonota88/items/31c127c42a9722892aa8

<!-- シェルスクリプトにコンパイルする言語3つ - memo486 -->
https://memo88.hatenablog.com/entry/languages_compiled_to_shell_script