3
Help us understand the problem. What are the problem?

posted at

updated at

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

これは LibreOffice Advent Calendar 2020 の14日目の記事です。

1つ前は @parpy さんの PHPからODFドキュメントを書き換えてみた - Qiita です。


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


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

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

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


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

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

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

できたもの

実行の例

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

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


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

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

image.png
ライフゲームの1ターンを実行するのに50秒くらいかかります 1 :sweat_smile:


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

変換の流れ

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


高水準言語のコード。

// コメント

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に変換

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

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

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

  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 の最初のドットを点滅させるだけのプログラム。

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

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

Peek 2020-12-13 11-50_a.gif


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


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

他に LibreOffice 関連で書いたもの

  1. ひとまず富豪的に作ったので、高速化の余地はあると思います。

  2. この GIF画像は 8fps で録画した都合で途中のフレームが抜けています。

Register as a new user and use Qiita more conveniently

  1. You can follow users and tags
  2. you can stock useful information
  3. You can make editorial suggestions for articles
What you can do with signing up
3
Help us understand the problem. What are the problem?