素朴な自作言語のコンパイラをLibreOffice Basicに移植した

これは [LibreOffice Advent Calendar 2020](https://adventar.org/calendars/5258) の14日目の記事です。

1つ前は @parpy さんの [PHPからODFドキュメントを書き換えてみた - Qiita](https://qiita.com/parpy/items/0754a5ba10ef6d6da79f) です。

----

こんにちは。素朴な自作言語のコンパイラをいろんな言語に移植するぞおじさんです。
素朴な自作言語のコンパイラをいろんな言語に移植しています。

----

素朴な自作言語のコンパイラというのは、以前作ったこれです。

- [Rubyで素朴な自作言語のコンパイラを作った](https://memo88.hatenablog.com/entry/2020/05/04/155425)
- [RubyでオレオレVMとアセンブラとコード生成器を2週間で作ってライフゲームを動かした話](https://memo88.hatenablog.com/entry/2019/05/04/232236)

これのコンパイラ部分だけいろんな言語に移植するということをやっていまして、今年は9つの言語に移植しました。下記に一覧があります。

<!--
元の Ruby 版だと全部合わせて 1500行くらいの、■
-->


- [vm2gol-v2 移植まとめ](https://memo88.hatenablog.com/entry/2020/08/30/132314)

その一環として今回 LibreOffice Basic に移植しました。
いつもはコンパイラだけ移植しているのですが、Calc を使えばセルで簡易グラフィックみたいなことができるのと、せっかくの Advent Calendar なのでアセンブラとVMも移植して、コンパイル〜アセンブル〜VMでの実行まですべて Calc 上で行えるようにしてみました。

----

……という話をすると、こういうのを作ったことがない方は「なんだかすごそうなことをやっている」と思われるかもしれませんが、意外とそんなことはありません。



いろんなものを削ぎ落として手抜きしまくっているため、 元の Ruby 版だとコンパイラからVMまで全部合わせても（割と冗長に書いて） 1500行くらいです（[一番最初に書いたVM](https://memo88.hatenablog.com/entry/2019/05/04/235252) は30行程度）。扱っているデータ型も整数だけで、配列も構造体もポインタもないですし、ライフゲームがコンパイルできて動けばOKというものです。
というのは、自分がコンパイラ実装初心者だったからです。作るのに何ヶ月もかかるような本格的なものではなく、短期間で作れて、ブラックボックスがなく何をやっているのか全部分かる簡単なものが欲しくてこうなりました。


<!--
（配列はないのですが、VRAM を実質的に1つのグローバルな配列のように扱っていて、そこもズルしている感じです）
ほんとうにほんとうにしょぼいコンパイラなのです。
-->

難しいアルゴリズムや Ruby の高度な言語機能なども使っていなくて、それで気軽に移植できています。




# できたもの

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





# 実行の例

<!--
サンプルとしてライフゲームを用意しました……というかこれは元の Ruby版からそのまま持ってきたものです。

----
-->

※ ファイル内の Basic マクロを実行する都合上セキュリティの設定をゆるめる必要があります。
ツールバーから ツール＞オプション
＞LibreOffice＞セキュリティ＞マクロセキュリティ

※ 矩形要素に長いテキストを入れるとパフォーマンスが悪化するようで、環境によってはシートの切り替えやページのスクロールで数秒待たされる場合があります :confounded:

---

以下の手順でライフゲームをコンパイル〜実行できます。

1. Calc でファイル（ `vm2gol-v2.fods` ）を開く
2. 字句解析: 「src」シートを開き、 `[tokenize]` ボタンを押す
3. 構文解析: 「tokens」シートを開き、 `[parse]` ボタンを押す
4. コード生成:  「tree」シートを開き、 `[codegen]` ボタンを押す
4. アセンブル:  「asm」シートを開き、 `[assemble]` ボタンを押す
4. VMで実行:  「vm」シートを開き、
    5. `[reset]` ボタンを押す（レジスタとメモリをリセット）
    6. `[load]` ボタンを押す（プログラム＝機械語コードをメモリにロード）
    7. `[step N]` ボタンを押す（複数ステップを連続して実行）

<!--
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/234055/b74a69fb-c4a1-6d88-6fe3-57ce9c51d5db.png)
-->

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/234055/222bf338-0c22-c24e-864e-d46405ebcf41.png)
ライフゲームの1ターンを実行するのに50秒くらいかかります [^1] :sweat_smile:
[^1]: ひとまず富豪的に作ったので、高速化の余地はあると思います。

<br />

処理に時間がかかりすぎていて途中で中断したいといった場合は
ツール＞マクロ＞マクロの編集
実行＞停止（Shift+F5）
で止められます。


# 変換の流れ

<!--
具体例として足し算するだけの関数でプログラムの変換の流れを示します。
-->

具体例として足し算関数を呼び出して結果を受け取るだけのプログラムで変換の流れを示します。

----

高水準言語のコード。

```javascript
// コメント

func add(a, b) {
  var c = a + b;
  return c;
}

func main() {
  var result;
  call_set result = add(1, 2);
}
```

パッと見では JavaScript っぽい感じですね。独自の機能とか最近の流行りの要素とかは何もなくてよくて、ベタなやつでOKというたいへん志の低い言語です。

C言語のように、エントリポイントとして main という名前の関数を必須としています。

↓ 字句解析してトークン列に変換

```
kw    func
ident add
sym   (
ident a
sym   ,
ident b
sym   )
sym   {
kw    var
ident c
sym   =
ident a
sym   +
ident b
sym   ;
kw    return
ident c
sym   ;
sym   }
kw    func
ident main
sym   (
sym   )
sym   {
kw    var
ident result
sym   ;
kw    call_set
ident result
sym   =
ident add
sym   (
int   1
sym   ,
int   2
sym   )
sym   ;
sym   }
```

↓ パースしてASTに変換

```json
[
  "top_stmts", 
  [
    "func", "add", ["a", "b"],
    [
      ["var", "c", ["+", "a", "b"]],
      ["return", "c"]
    ]
  ],
  [
    "func", "main", [],
    [
      ["var", "c"],
      ["call_set", "c", ["add", 1, 2]]
    ]
  ]
]
```

シリアライズのフォーマットは JSON のサブセット。

↓ コード生成してアセンブリコードに変換

```nasm
  call main
  exit

label add
  push bp
  cp sp bp

  sub_sp 1
  push [bp+2]
  push [bp+3]
  pop reg_b
  pop reg_a
  add_ab
  cp reg_a [bp-1]
  cp [bp-1] reg_a
  cp bp sp
  pop bp
  ret

label main
  push bp
  cp sp bp

  sub_sp 1
  push 2
  push 1
  _cmt call_set~~add
  call add
  add_sp 2
  cp reg_a [bp-1]
  cp bp sp
  pop bp
  ret
```

↓ アセンブルして機械語コードに変換

```
call 16
exit
label add
push bp
cp sp bp
sub_sp 1
push [bp+2]
push [bp+3]
pop reg_b
pop reg_a
add_ab
cp reg_a [bp-1]
cp [bp-1] reg_a
cp bp sp
pop bp
ret
label main
push bp
cp sp bp
sub_sp 1
push 2
push 1
_cmt call_set~~add
call 2
add_sp 2
cp reg_a [bp-1]
cp bp sp
pop bp
ret
```

機械語コードはバイナリフォーマットではなく、見ての通りのプレインテキストです。ここらへんも手抜きしているところ。

元の Ruby 版ではなんとなく可変長風にしていましたが、こだわる必要なかったかなと思って今回ここも簡略化して1行1命令（固定長風？）というフォーマットにしてみました。


# 反復と条件分岐を含むコード例

VRAM の最初のドットを点滅させるだけのプログラム。

```javascript
func main() {
  var x = 0;
  while (1 == 1) {
    set vram[0] = x;
    case {
      (x == 0) { set x = 1; }
      (x == 1) { set x = 0; }
    }
  }
}
```

1ステップごとに再描画させた場合このくらいの速さで動きます。[^2]
[^2]: この GIF画像は 8fps で録画した都合で途中のフレームが抜けています。

（↓Firefox だとアニメgifが再生されない場合があるようです。ファイルをクリックして画像だけ表示すると動くものが見れます。）

![Peek 2020-12-13 11-50_a.gif](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/234055/0b8c53cb-cde2-3ba9-016b-339a2d1b93dd.gif)


----

というわけで、LibreOffice Calc で動かせるコンパイラ・アセンブラ・VM の紹介でした。LibreOffice 自体とあんまり関係ない内容ですみません……「LibreOffice を使ってこんなこともできる」というデモとして見ていただければ幸いです。


----

Advent Calendar 4日目にこんなのも書きました。ご興味あればこちらもどうぞ:

- [LibreOffice BasicでLispインタプリタ（mal）を書いた](https://qiita.com/sonota88/items/501f0efa437bc4d53cc7)

# 他に LibreOffice 関連で書いたもの

https://memo88.hatenablog.com/archive/category/LibreOffice