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


移植まとめに戻る


やっつけなので汚いです。ライフゲームコンパイルが通ったのでヨシ、というレベルのものです。

github.com

C♭は書籍 『ふつうのコンパイラをつくろう』の題材として作られた、C によく似た言語です。コンパイラ cbcJava製。


移植元

memo88.hatenablog.com

ベースになっているバージョン: tag:49 のあたり

  • (追記 2022-03-27)Docker 化しました

ただ、実質的にはC言語版 からの移植です。 そのままコピーしてきて、cbcコンパイルできるように修正しました。

メモ

  • cbcコンパイルについては前回書いたとおり
  • ほぼC言語なので細かい部分の直しだけで済み、 ライフゲームのコードをコンパイルできるところまで2日程度で持っていけた
  • いろいろあって適当なプリプロセッサを作り、 必要なファイルを全部1ファイルにまとめて cbc に渡すようにした
    • 行番号が変わってしまうのでこれはこれでめんどくさいのですが……
    • 単純なマクロの置換もここで処理
  • substring (lib/utils.cb) のバグというか実装が雑だったので ちゃんと文字列終端を見て止めるように修正。 まあそもそもがやっつけなのでそういうのあるだろうなと思ってました。 やっぱりあった。
  • sscanf がなかったため 文字列から int に変換する処理だけ自前で追加
  • ためしに Names だけ連結リストにしてみた

以下、移植で変更が必要だった部分についてのメモ。 Cの仕様にも詳しくないので「そもそもCでもダメだけどたまたま動いていた」みたいなパターンもある気がします。


引数がない関数の場合は void が必須。

int foo_func(void) {
  // snip
}

// foo_func() とした場合のエラーメッセージ:
//=> cbc: error: Encountered " ")" ") "" at line 849, column 34.

for 文でイテレータ変数の変数宣言はダメ。 C89/90 だとそうなんでしたっけ……(記憶がうっすら)。

  for (int i = 0; i < 10; i++) {
    // snip
  }

//=> cbc: error: Encountered " "int" "int "" at line 767, column 35.

for (;;) ... はダメ。 これは while (1) ... に書き換えればOK。


ポインタの配列の宣言の書式はこう。

Foo*[1024] foo_array;

文字の比較

int main(void) {
  char* str = "fdsa";

  if (str[0] == 'f') {
    printf("equal\n");
  } else {
    printf("not equal\n");
  }

  return 0;
}

//=> not equal

(int)str[0] == 'f' のように int にキャストすると equal になる。 詳しく調べていませんが、 64bit 環境で動かしているせいかもしれません。

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

memo88.hatenablog.com

memo88.hatenablog.com

memo88.hatenablog.com

memo88.hatenablog.com

「ふつうのコンパイラをつくろう」のcbcをUbuntu18.04(64bit)でビルドする

こちらの2つの記事を参考にさせてもらいました。ありがとうございます。以下の内容はこれらの記事で書かれていることとほぼ同じです。


ホスト側で適当な作業用ディレクトリを用意。 以下 WORK_DIR

cd {WORK_DIR}

cbc を用意:

git clone https://github.com/aamine/cbc.git

ブランチを 1.0.1 に合わせておきます:

(
  cd cbc
  git checkout 1.0.1 -b ubuntu1804_64bit
)

クリーンな環境で確認したいので Docker コンテナで作業します。

{WORK_DIR}/Dockerfile

FROM ubuntu:18.04

RUN apt update \
  && apt install -y --no-install-recommends \
       make \
       openjdk-8-jdk-headless

とりあえず最低限のものだけ。

この時点でのディレクトリ・ファイル階層はこう:

- WORK_DIR/
  - cbc/
  - Dockerfile

build と run:

# (作り直す場合)
# docker rmi cbc_ubuntu1804_64bit

docker build -t cbc_ubuntu1804_64bit .

dk run --rm -it \
  -v"$(pwd)/cbc:/root/cbc" \
  cbc_ubuntu1804_64bit

以下、コンテナ内での作業。 ただし、ファイルの編集はホスト側で行っています。

コンテナ内なので root で作業していますが、一般ユーザで実行する場合は適宜 sudo apt などに読み替えてください。


まずは GCC, JavaCC, Ant をインストール:

apt install -y --no-install-recommends gcc javacc ant

apt だと JavCC 5.0 が入るようです。

ちなみに、 openjdk の前に ant をインストールすると依存パッケージとして openjdk 11 がインストールされます。


cd /root/cbc

cbc のビルド手順に従う場合ここで build.properties を修正しないといけないのですが、 apt で JavaCC をインストールした場合 /usr/share/java/javacc.jar が配置されるので、今回はこの手順はスキップします。

ちなみに、このディレクトリ指定が間違っていると次のようなメッセージを出して失敗します。

# make
ant compile
Buildfile: /root/cbc/build.xml

init:

parser:

BUILD FAILED
/root/cbc/build.xml:9: JavaCC home must be a valid directory.

Total time: 0 seconds
Makefile:8: recipe for target 'lib/cbc.jar' failed
make: *** [lib/cbc.jar] Error 1

make を実行:

make clean
make

コンパイルエラーになります。

    [javac]   both class java.lang.reflect.Parameter in java.lang.reflect and class net.loveruby.cflat.entity.Parameter in net.loveruby.cflat.entity match

これは Parser.jj に import 文を1行追加すれば消えます。

--- a/net/loveruby/cflat/parser/Parser.jj
+++ b/net/loveruby/cflat/parser/Parser.jj
@@ -11,6 +11,7 @@ PARSER_BEGIN(Parser)
 package net.loveruby.cflat.parser;
 import net.loveruby.cflat.ast.*;
 import net.loveruby.cflat.entity.*;
+import net.loveruby.cflat.entity.Parameter;
 import net.loveruby.cflat.type.*;
 import net.loveruby.cflat.asm.Label;
 import net.loveruby.cflat.utils.ErrorHandler;

再度 make:

$ make

...snip...

compile:
    [javac] /root/cbc/build.xml:16: warning: 'includeantruntime' was not set, defaulting to build.sysclasspath=last; set to false for repeatable builds
    [javac] Compiling 193 source files to /root/cbc/build/classes
      [jar] Building jar: /root/cbc/lib/cbc.jar

BUILD SUCCESSFUL
Total time: 2 seconds
cd lib; make libcbc.a
make[1]: Entering directory '/root/cbc/lib'
../bin/cbc -O -fPIC -c stdarg.cb -o stdarg.o
stdarg.s: Assembler messages:
stdarg.s:6: Error: invalid instruction suffix for `push'
stdarg.s:14: Error: invalid instruction suffix for `pop'
stdarg.s:20: Error: invalid instruction suffix for `push'
stdarg.s:43: Error: invalid instruction suffix for `pop'
cbc: error: as failed. (status 1)
cbc: error: compile error
Makefile:14: recipe for target 'stdarg.o' failed
make[1]: *** [stdarg.o] Error 1
make[1]: Leaving directory '/root/cbc/lib'
Makefile:11: recipe for target 'lib/libcbc.a' failed
make: *** [lib/libcbc.a] Error 2

Javaコンパイルは通って、今度は lib/ 内での make で失敗します。

lib/Makefile を修正:

--- a/lib/Makefile
+++ b/lib/Makefile
@@ -11,9 +11,9 @@ AR_CREATE = ar crs
 .SUFFIXES: .cb .s .o
 
 .cb.o:
-  $(CBC) $(CBFLAGS) -c $< -o $@
+   $(CBC) $(CBFLAGS) -Wa,"--32" -c $< -o $@
 .s.o:
-  $(CBC) -c $<
+   $(CBC) -Wa,"--32" -c $<
 
 $(TARGET): $(OBJS)
    $(AR_CREATE) $(TARGET) $(OBJS)

再度 make:

root@9aee3742173e:~/cbc# make
cd lib; make libcbc.a
make[1]: Entering directory '/root/cbc/lib'
../bin/cbc -O -fPIC -Wa,"--32" -c stdarg.cb -o stdarg.o
../bin/cbc -Wa,"--32" -c alloca.s
ar crs libcbc.a stdarg.o alloca.o
make[1]: Leaving directory '/root/cbc/lib'

root@9aee3742173e:~/cbc# echo $?
0

成功しました。


ビルドが成功したのでインストールしてみます。 ちなみにインストール先を変えたい場合は 引数で指定してやれば良いようです。

root@9aee3742173e:~/cbc# ./install.sh 
prefix=/usr/local/cbc
mkdir -p /usr/local/cbc/bin
install -m755 bin/cbc /usr/local/cbc/bin
mkdir -p /usr/local/cbc/lib
cp lib/cbc.jar lib/libcbc.a /usr/local/cbc/lib
rm -rf /usr/local/cbc/import
cp -r import /usr/local/cbc/import
cbc successfully installed as /usr/local/cbc/bin/cbc

とりあえずヘルプを表示してみます。

root@9aee3742173e:~/cbc# /usr/local/cbc/bin/cbc --help
Usage: cbc [options] file...
Global Options:
  --check-syntax   Checks syntax and quit.
  --dump-tokens    Dumps tokens and quit.

... snip ...

動かせますね。


サンプルコードを用意して、

int main (int argc, char** argv) {
  return 42;
}

インストールした cbcコンパイルしてみます。

root@9aee3742173e:~/cbc# /usr/local/cbc/bin/cbc sample.cb 
sample.s: Assembler messages:
sample.s:6: Error: invalid instruction suffix for `push'
sample.s:12: Error: invalid instruction suffix for `pop'
cbc: error: as failed. (status 1)
cbc: error: compile error

cbc のオプションで -Wa,"--32" -Wl,"-melf_i386" を指定して実行してみます。

root@9aee3742173e:~/cbc# /usr/local/cbc/bin/cbc -Wa,"--32" -Wl,"-melf_i386" \
>   sample.cb
/usr/bin/ld: cannot find /usr/lib/crt1.o: No such file or directory
/usr/bin/ld: cannot find /usr/lib/crti.o: No such file or directory
/usr/bin/ld: cannot find -lc
/usr/bin/ld: cannot find /usr/lib/crtn.o: No such file or directory
cbc: error: /usr/bin/ld failed. (status 1)
cbc: error: compile error

メッセージが変わりました。


crt1.o などが必要なので、 libc6-dev-i386 をインストールします。

これら(Cランタイム)が何かということについては p574, 575 で解説されています。

apt install -y --no-install-recommends libc6-dev-i386

/usr/lib32/ にインストールされました。

root@9aee3742173e:~/cbc# ls /usr/lib32/ | grep crt
Mcrt1.o
Scrt1.o
crt1.o
crti.o
crtn.o
gcrt1.o
grcrt1.o
rcrt1.o

これらを参照している箇所を修正:

--- a/net/loveruby/cflat/sysdep/GNULinker.java
+++ b/net/loveruby/cflat/sysdep/GNULinker.java
@@ -10,10 +10,10 @@ class GNULinker implements Linker {
     // #@@range/vars{
     static final private String LINKER = "/usr/bin/ld";
     static final private String DYNAMIC_LINKER      = "/lib/ld-linux.so.2";
-    static final private String C_RUNTIME_INIT      = "/usr/lib/crti.o";
-    static final private String C_RUNTIME_START     = "/usr/lib/crt1.o";
-    static final private String C_RUNTIME_START_PIE = "/usr/lib/Scrt1.o";
-    static final private String C_RUNTIME_FINI      = "/usr/lib/crtn.o";
+    static final private String C_RUNTIME_INIT      = "/usr/lib32/crti.o";
+    static final private String C_RUNTIME_START     = "/usr/lib32/crt1.o";
+    static final private String C_RUNTIME_START_PIE = "/usr/lib32/Scrt1.o";
+    static final private String C_RUNTIME_FINI      = "/usr/lib32/crtn.o";
     // #@@}
 
     ErrorHandler errorHandler;

再度 make + install:

make clean
make
./install.sh

サンプルコードをコンパイル:

/usr/local/cbc/bin/cbc -Wa,"--32" -Wl,"-melf_i386" sample.cb

コンパイルが成功して実行ファイル sample が作られました。 実行してみます。

root@9aee3742173e:~/cbc# ./sample
root@9aee3742173e:~/cbc# echo $?
42

正しく動いているようです。


毎回 -Wa,"--32" -Wl,"-melf_i386" を付けるのは煩雑なので bin/cbc に追加してしまいます。

--- a/bin/cbc
+++ b/bin/cbc
@@ -9,4 +9,5 @@ srcdir_root="$(dirname "$(dirname "$cmd_path")")"
         net.loveruby.cflat.compiler.Compiler \
         -I"$srcdir_root/import" \
         -L"$srcdir_root/lib" \
+        -Wa,"--32" -Wl,"-melf_i386" \
         "$@"

再度インストール:

./install.sh

次のように使えるようになりました。

root@9aee3742173e:~/cbc# /usr/local/cbc/bin/cbc sample.cb 
root@9aee3742173e:~/cbc# ./sample 
root@9aee3742173e:~/cbc# echo $?
42

cbc に加えた変更をまとめて見る場合はこちら:

https://github.com/sonota88/cbc/compare/1.0.1...sonota88:ubuntu1804_64bit

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

qiita.com

memo88.hatenablog.com

memo88.hatenablog.com

memo88.hatenablog.com

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


移植一覧に戻る


20年ぶりくらいにC言語のコードを書きました。 かなり忘れてます。 やっつけなので汚いです。ライフゲームコンパイルが通ったのでヨシ、というレベルのものです。

github.com


移植元

memo88.hatenablog.com

ベースになっているバージョン: tag:49 のあたり
(追記 2021-05-18: tag:58 の修正まで反映しました)

ただ、Ruby 版より主に Java版 を見ながら書き写してました。

メモ

  • ほとんど忘れてたので、すごく初心者っぽいできあがりになってると思います
    • 「あー、そうだそうだ、こうだったわ」ではなく「そういえばこんなだったっけ……思い出せない……」「えっ、これいちいち範囲チェックしないといけないんだっけか」みたいな感じだった。ほぼ忘れてる。
    • といいつつポインタまわりとか「そもそも構造体とは」とかの概念まで全部忘れているわけでもなく、1週間でなんとか動くところまで持っていけた
  • ひとまず C89/C90 あたりの、20年前に書いていたスタイルで書いてみた
    • #pragmra once は使ってみた。便利。
    • 気が向いたら他の C99/C11 な要素も取り入れて書き直すなどしてみたい
  • パース処理を最初に書き始めるところが重い
    • 最初は入力トークン列を全部無視して固定文字列を出力する
    • 次はツリーを手書きで組み立てて print。 ここでもまだ入力トークン列は全部無視。
    • その次にやっと入力をパースしてツリーを組み立てて置き換えていく
    • みたいな流れにすると1ステップを小さくできる
  • コード生成に入る前の JSON も重い
    • ので、コード生成の前に JSON の読み書きだけのテストも追加した。
    • 肩慣らしでこれを最初に持ってきてもよいかも
      • 規模縮小版のパーサにもなっているので
    • フルセットではなく制限のあるJSONなので割と簡単
      • 要素は入れ子の配列と文字列と数のみ
      • トップレベルは必ず配列
      • 文字列のバックスラッシュエスケープはなし
  • やっぱり一番最初にトークナイズからコード生成まで通すところが重くて、 そこができてしまえば後は割と楽
    • ここをどんどん小さなステップに分解して簡単にしていきたい
  • 文字列操作の関数とか個別にテストしてないのでたぶんいろいろおかしい
    • サイズ指定・範囲のチェックはかなり雑
  • free してないのはめんどくさかったからだけど、一応意図的。 低レイヤを知りたい人のためのCコンパイラ作成入門 の「コラム: 9ccにおけるメモリ管理」も参照。
  • 連結リストを動的に確保したりせずに大きめの固定サイズの配列にしてたりして、かなり無駄が多い
    • 気が向いたら連結リストで書き直したい
  • 正規表現を使わなくてもプリミティブな文字列操作だけでなんとかなると分かった
    • 気が向いたらこれを組み込んだりしてみたい
  • コード生成時にその場ですぐ printf で出力する方式にしたら case の処理がやりにくかったので、生成されるコードを変更して簡単に書けるようにした
  • 今回は疲れたので実験的な要素はひとまずなし。気が向いたら後で。

行数はこんな感じです。

$ wc -l *.c lib/*.{c,h}
  694 vgcg.c
  746 vgparser.c
  223 vgtokenizer.c
  178 lib/json.c
   18 lib/test_json.c
  323 lib/types.c
   96 lib/utils.c
    5 lib/json.h
   86 lib/types.h
   15 lib/utils.h
 2384 合計

パーサの別実装

qiita.com

vm2gol v2 (49) codegen_case を移植しやすいように変更



まずはしょぼいミスを修正……。

--- a/vgparser.rb
+++ b/vgparser.rb
@@ -478,7 +478,7 @@ if $PROGRAM_NAME == __FILE__
 
   begin
     tree = parser.parse()
-  rescue ParseError => e
+  rescue Parser::ParseError => e
     parser.dump_state()
     raise e
   end

codegen_case の変更

C言語に移植しているところなのですが、 生成したアセンブリコードを alines に溜めて受け渡していくのをめんどくさがって printf() でその都度出力するスタイルで書き進めていたら codegen_case() の実装でひっかかりました。

Cのコーディングをがんばる方向も考えましたが、 そもそも then_bodies が文字列の配列の配列となる時点で 若干複雑で、もうちょいどうにかならんかなという気がします。 それに、 then_bodies なんてものが出てくる時点で ここだけちょっと例外的なんですよね(気にはなっていた)。

というわけで、移植元の Ruby版の方から変えて、移植しやすくすることにしました。

case の動作としては等価で、 出力されるアセンブリコード(と機械語コード)の表現が変わる形です。


これはアセンブリコードで変更を見た方が分かりやすいと思います。

# 変更前:

  {条件式1の評価}
  compare
  jump_eq then_1

  {条件式2の評価}
  compare
  jump_eq then_2

label then_1
  {then_1 の場合の処理}
  jump end_case

label then_2
  {then_2 の場合の処理}
  jump end_case

label end_case

これまでは、このように各条件式が真になった場合のコードを then_bodies に溜めておいて、 後ろの方でまとめて出力していました。

まあ急いで作っていてその時パッと思いついたのをそのまま書いたというものです。 深い理由があってこのようになっているわけではありません。 変えてもいいでしょう。

で、どうするか。 jump_neq (比較結果が偽の場合にジャンプする)という VM 命令を追加して、 次のようなアセンブリコードを出力するのはどうかと考えました

# 案1(没):

  {条件式1の評価}
  compare
  jump_neq end_when_1
  {条件式1が真の場合の処理}
  jump end_case            # 最後までスキップ
label end_when_1           # 偽だった場合ここにジャンプ
                           # → 次の式の評価へ進む
  {条件式2の評価}
  compare
  jump_neq end_when_2
  {条件式2が真の場合の処理}
  jump end_case
label end_when_2

label end_case

すっきりしてていい感じなのですが、 VMアセンブラまで修正が必要になるのと、 今回のこれだけのために命令を追加するのも大げさ (せっかく命令を追加してもここだけでしか使われない)かなと思って、 結局 jump_eq でなんとかする次の方式にしました。

# 案2(採用):

  {条件式1の評価}
  compare
  jump_eq when_1
  jump end_when_1
label when_1               # 真だった場合ここにジャンプ
  {条件式1が真の場合の処理}
  jump end_case            # 最後までスキップ
label end_when_1           # 偽だった場合ここにジャンプ
                           # → 次の式の評価へ進む
  {条件式2の評価}
  compare
  jump_eq when_2
  jump end_when_2
label when_2
  {条件式2が真の場合の処理}
  jump end_case
label end_when_2

label end_case

というわけで差分がこう。 then_bodies に加えて then_alines も不要になりました。

--- a/vgcg.rb
+++ b/vgcg.rb
@@ -36,10 +36,10 @@ def codegen_case(fn_arg_names, lvar_names, when_blocks)
   label_id = $label_id
 
   when_idx = -1
-  then_bodies = []
 
   label_end = "end_case_#{label_id}"
   label_when_head = "when_#{label_id}"
+  label_end_when_head = "end_when_#{label_id}"
 
   when_blocks.each do |when_block|
     when_idx += 1
@@ -56,24 +56,24 @@ def codegen_case(fn_arg_names, lvar_names, when_blocks)
       alines << "  set_reg_b 1"
 
       alines << "  compare"
-      alines << "  jump_eq #{label_when_head}_#{when_idx}"
+      alines << "  jump_eq #{label_when_head}_#{when_idx}"  # 真の場合
+      alines << "  jump #{label_end_when_head}_#{when_idx}" # 偽の場合
+
+      # 真の場合ここにジャンプ
+      alines << "label #{label_when_head}_#{when_idx}"
+
+      alines += codegen_stmts(fn_arg_names, lvar_names, rest)
+
+      alines << "  jump #{label_end}"
+
+      # 偽の場合ここにジャンプ
+      alines << "label #{label_end_when_head}_#{when_idx}"
 
-      then_alines = ["label #{label_when_head}_#{when_idx}"]
-      then_alines += codegen_stmts(fn_arg_names, lvar_names, rest)
-      then_alines << "  jump #{label_end}"
-      then_bodies << then_alines
     else
       raise not_yet_impl("cond_head", cond_head)
     end
   end
 
-  # すべての条件が偽だった場合
-  alines << "  jump #{label_end}"
-
-  then_bodies.each {|then_alines|
-    alines += then_alines
-  }
-
   alines << "label #{label_end}"
 
   alines

出力されるアセンブリコードがちょっとだけ複雑になり、 一方でコード生成器の複雑さは少し減りました。 悪くはないんじゃないかなと思います。 少なくとも移植はしやすくなりました。



vm2gol v2 (48) 変数宣言のコード生成処理の改善など



Java版 を書いているときに codegen_stmts() の微妙なところに気付いてしまいました。

def codegen_stmts(fn_arg_names, lvar_names, stmts)
  alines = []

  stmts.each do |stmt|
    stmt_head, *stmt_rest = stmt

    case stmt_head
    when "call"
      alines += codegen_call(fn_arg_names, lvar_names, stmt_rest)
    when "call_set"
      alines += codegen_call_set(fn_arg_names, lvar_names, stmt_rest)
    when "var"
      lvar_names << stmt_rest[0] # ★ここ
      alines << "  sub_sp 1"
      if stmt_rest.size == 2
        alines += codegen_set(fn_arg_names, lvar_names, stmt_rest)
      end
    when "set"
      # ...

メソッドの引数 lvar_names を変更しています。 なんでこうなってるかというと、 以前リファクタリングしたとき(第46回) に雑にやってしまっていたからですね……。


Ruby の場合は参照渡し的な挙動になるので、 うまく動いてテストも通っていて(だからすぐ気づかなかったのですが)、特別まずいというわけでもないと思います。

def foo(arg_xs)
  arg_xs << 2
end

xs = [1]
foo(xs)
foo(xs)
p xs #=> [1, 2, 2]

とはいえ、呼び出し先で変更すると挙動が把握しにくかったりしますし、もうちょっといい感じにできないかなと。


というわけで修正します。

まず、codegen_stmts() のループ内で行っている1つの文の処理を codegen_stmt() に抽出。これは単純なリファクタリング

--- a/vgcg.rb
+++ b/vgcg.rb
@@ -415,38 +415,44 @@ def codegen_comment(comment)
   ]
 end
 
+def codegen_stmt(fn_arg_names, lvar_names, stmt)
+  stmt_head, *stmt_rest = stmt
+
+  case stmt_head
+  when "call"
+    codegen_call(fn_arg_names, lvar_names, stmt_rest)
+  when "call_set"
+    codegen_call_set(fn_arg_names, lvar_names, stmt_rest)
+  when "var"
+    alines = []
+    lvar_names << stmt_rest[0]
+    alines << "  sub_sp 1"
+    if stmt_rest.size == 2
+      alines += codegen_set(fn_arg_names, lvar_names, stmt_rest)
+    end
+    alines
+  when "set"
+    codegen_set(fn_arg_names, lvar_names, stmt_rest)
+  # when "eq"
+  #   alines += codegen_exp(fn_arg_names, lvar_names, stmt)
+  when "return"
+    codegen_return(lvar_names, stmt_rest)
+  when "case"
+    codegen_case(fn_arg_names, lvar_names, stmt_rest)
+  when "while"
+    codegen_while(fn_arg_names, lvar_names, stmt_rest)
+  when "_cmt"
+    codegen_comment(stmt_rest[0])
+  else
+    raise not_yet_impl("stmt_head", stmt_head)
+  end
+end
+
 def codegen_stmts(fn_arg_names, lvar_names, stmts)
   alines = []
 
   stmts.each do |stmt|
-    stmt_head, *stmt_rest = stmt
-
-    case stmt_head
-    when "call"
-      alines += codegen_call(fn_arg_names, lvar_names, stmt_rest)
-    when "call_set"
-      alines += codegen_call_set(fn_arg_names, lvar_names, stmt_rest)
-    when "var"
-      lvar_names << stmt_rest[0]
-      alines << "  sub_sp 1"
-      if stmt_rest.size == 2
-        alines += codegen_set(fn_arg_names, lvar_names, stmt_rest)
-      end
-    when "set"
-      alines += codegen_set(fn_arg_names, lvar_names, stmt_rest)
-    # when "eq"
-    #   alines += codegen_exp(fn_arg_names, lvar_names, stmt)
-    when "return"
-      alines += codegen_return(lvar_names, stmt_rest)
-    when "case"
-      alines += codegen_case(fn_arg_names, lvar_names, stmt_rest)
-    when "while"
-      alines += codegen_while(fn_arg_names, lvar_names, stmt_rest)
-    when "_cmt"
-      alines += codegen_comment(stmt_rest[0])
-    else
-      raise not_yet_impl("stmt_head", stmt_head)
-    end
+    alines += codegen_stmt(fn_arg_names, lvar_names, stmt)
   end
 
   alines

次に、codegen_stmt() で変数宣言を処理するのをやめます。

それだけだと変数宣言できなくなってしまうので、ではどうするかというと、 変数宣言だけ codegen_func_def() で処理してしまうことにしました。 これで変数名を lvar_names に追加する処理が codegen_func_def() に戻りました。

これが今回の修正のメインとなるコミットです。

--- a/vgcg.rb
+++ b/vgcg.rb
@@ -423,14 +423,6 @@ def codegen_stmt(fn_arg_names, lvar_names, stmt)
     codegen_call(fn_arg_names, lvar_names, stmt_rest)
   when "call_set"
     codegen_call_set(fn_arg_names, lvar_names, stmt_rest)
-  when "var"
-    alines = []
-    lvar_names << stmt_rest[0]
-    alines << "  sub_sp 1"
-    if stmt_rest.size == 2
-      alines += codegen_set(fn_arg_names, lvar_names, stmt_rest)
-    end
-    alines
   when "set"
     codegen_set(fn_arg_names, lvar_names, stmt_rest)
   # when "eq"
@@ -475,7 +467,18 @@ def codegen_func_def(rest)
 
   lvar_names = []
 
-  alines += codegen_stmts(fn_arg_names, lvar_names, body)
+  body.each do |stmt|
+    if stmt[0] == "var"
+      _, *stmt_rest = stmt
+      lvar_names << stmt_rest[0]
+      alines << "  sub_sp 1"
+      if stmt_rest.size == 2
+        alines += codegen_set(fn_arg_names, lvar_names, stmt_rest)
+      end
+    else
+      alines += codegen_stmt(fn_arg_names, lvar_names, stmt)
+    end
+  end
 
   alines << ""
   alines << "  cp bp sp"

codegen_stmt()codegen_while()codegen_case() からも呼ばれているため、 この変更により while 文や case 文の中で変数宣言できなくなってしまいます。 が、その点は特に困らないからいいだろうという判断にしました。

昔のC言語だと関数の先頭でしかローカル変数宣言できませんでしたし、 大丈夫なんじゃないかな……。


あとは変数宣言のコード生成処理を codegen_var() に抽出して、 関数の body を処理する部分が次のようになりました。

  body.each do |stmt|
    if stmt[0] == "var"
      _, *stmt_rest = stmt
      lvar_names << stmt_rest[0]
      alines += codegen_var(fn_arg_names, lvar_names, stmt_rest)
    else
      alines += codegen_stmt(fn_arg_names, lvar_names, stmt)
    end
  end

その他

移植のときに気付いたもののフィードバックなど。

  • codegen_while() などで出てくるラベル名を変数化して DRY に
  • 式関連の変数名などがパーサでは expr、コード生成器では exp となっていて 不揃いだったので expr に統一
  • comment → vm_comment にリネーム
  • Token#type の値を変更
    • :reserved:kw など


Mini Ruccola(vm2gol-v2)移植一覧

機能を減らしてハードルを下げまくった、初心者・入門者(=自分)向けの、かんたん・素朴で割といいかげんな自作言語のコンパイラ Mini Ruccola(vm2gol-v2) の移植です。

移植元の Ruby版のコンパイラ部分だけだと 1000行くらい、という素朴さ。

  • ノリとしては zick さんの LISP Implementation Advent Calendar : ATND hatebu (2014年、 Wayback Machine )に近い感じ(のつもり)
  • mal (Make a Lisp) の影響もちょっとあると思います
  • 基本的にやっつけ、ものによっては殴り書きです。 動いたら(コンパイルできたら)そこで終わりで、気が向けば多少はきれいにしたりして、次の言語へGO。細かいことを気にしだすと無限に時間がかかるので割と意図的に気にしないようにしています。
  • それぞれの言語に詳しくなることよりも、とにかく作って動かすことを優先しています
    • 「その言語らしい書き方」にするようがんばらない。できる範囲で。気が向いたらやる。
    • 「習うよりも慣れろ」スタイルで
  • Java 以外はエディタ(Emacs)と print デバッグで。 ものによっては language server を併用。

# 記事 リポジトリ 日付
27 R github 2023-12-25
26 Elixir github 2023-12-11
25 C# github 2023-07-02
24 V github 2023-04-23
23 Forth(Gforth) github 2023-03-12
22 Tcl github 2021-12-26
21 シェルスクリプト(Bashスクリプト) github 2021-12-20
20 なでしこ3 github 2021-12-13
19 Haskell github 2021-06-28
18 OCaml github 2021-06-26
17 Pascal github 2021-05-22
16 Julia github 2021-05-03
15 Rust github 2021-04-07
14 Crystal github 2021-03-27
13 Ruccola(セルフホスト) github 2021-02-21
12 Kotlin github 2021-01-14
11 Zig github 2021-01-07
10 LibreOffice Basic github 2020-12-14
9 Go github 2020-09-25
8 PHP github 2020-09-18
7 C♭ github 2020-09-13
6 Perl github 2020-09-08
5 C github 2020-09-06
4 Java github 2020-08-30
3 Dart github 2020-08-22
2 Python github 2020-08-19
1 TypeScript (Deno) github 2020-08-15

他の人が書いてくれたもの

他の人に使っていただけると、作った甲斐があった! という気持ちになりますね。ありがとうございます。

関連リポジトリ

他の人に使ってもらうことを意識した整備などはしていないですが、参考までに。

参考

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


移植一覧に戻る


Java で書いてみました。やっつけなので汚いです。ライフゲームが動いたのでヨシ、というレベルのものです。

github.com


移植元

memo88.hatenablog.com

ベースになっているバージョン: tag:47 のあたり

メモ

  • アセンブラVM は移植対象から外しました。Ruby 版のものを使います。
  • テストのステップをさらに細かくした
    • トークナイザの最初のテストを通すときが重い(一番最初に無から作り始める段階なので重い)ので、 最初のテストの入力を最低限のもの(func + 半角スペース だけ)にしたりとか
  • 例外まわりが雑

今回はパーサをいじって call を不要にしてみました。

(追記 2021-03-31: この修正はいったん revert しましたが、一応 trial ブランチに残してあります。)

 func main() {
-  call my_func();
+  my_func();
 }

set のとき と同じです。 文の先頭の call で判別するのをやめて、識別子だったら parseCall_v2() を呼ぶ。

    private NodeList parseStmt() {
        Token t = peek();

        if (t.is(Token.Type.SYM, "}")) {
            return NodeList.empty();
        }

        switch (t.getStr()) {
        case "func"    : return parseFunc();
        case "var"     : return parseVar();
        case "set"     : return parseSet();
        // case "call"    : return parseCall();
        case "call_set": return parseCallSet();
        case "return"  : return parseReturn();
        case "while"   : return parseWhile();
        case "case"    : return parseCase();
        case "_cmt"    : return parseVmComment();
        default:
            if (t.type == Token.Type.IDENT &&
                    peek(1).is(Token.Type.SYM, "(")
            ) {
                return parseCall_v2();
            } else {
                throw unexpected("Unexpected token");
            }
        }
    }

vm2gol v2 (47) 引数のパースの厳密化など



パーサが結構いいかげんなので、直します。

引数のパースの厳密化

一番適当なのが引数のパースです。 現状だと my_func(1 2 a) のように区切りのカンマがなくても文法エラーになりません。

というわけで、 1つ目の引数と2個目以降の引数をパースする下請けメソッドをそれぞれ用意し、 次のように書き直しました。

  def _parse_arg
    t = peek()

    if t.type == :ident
      @pos += 1
      t.value
    elsif t.type == :int
      @pos += 1
      t.value
    else
      raise ParseError
    end
  end

  def _parse_args_first
    return nil if peek().value == ")"

    _parse_arg()
  end

  def _parse_args_rest
    return nil if peek().value == ")"

    consume(",")

    _parse_arg()
  end

  def parse_args
    args = []

    first_arg = _parse_args_first()
    if first_arg.nil?
      return args
    else
      args << first_arg
    end

    loop do
      rest_arg = _parse_args_rest()
      if rest_arg.nil?
        break
      else
        args << rest_arg
      end
    end

    args
  end

2個目以降の引数は カンマとセットにして見ていく形です。 BNF っぽく書くと下記のような感じでしょうか。

args:
    引数なし
  | arg (',' arg)*

これでカンマがない場合にエラーにできるようになりました。

※ 追記: 細かくメソッドを分けすぎたので ステップ58 であらためて整理しました。


他に似たように反復になっている構文をチェックしてみると…… stmts (文の連なり)と case文の when句の部分が似ているのですが、 これらの場合は引数リストのカンマに当たる区切りトークンが必要ないため修正不要です。

peek()

上記のコードにも含まれてしまっていますが、 現在のトークンを取得するためにこれまで @tokens[@pos] としていたところを、 peek() というメソッドに置き換えました。

出現頻度が高めなのでメソッド化したい気持ちはありつつも current_token とかだとちょっと野暮ったいな……と思っていたところ、 こういう場合は peek という名前が使われるらしいと分かったので今回採用しました。

この peek という単語は「(一部だけを)ちらっと見る・覗き見る」のような意味だそうです。 「流行のピーク」などという場合は peak で、これは別の単語。

その他

  • パース中に例外が発生した場合、その場で dump_state() を呼ぶのをやめて 大元に集約
  • when句のないcase文を文法エラーとみなすようにした (parse_case)
  • refactor: when句の処理を _parse_when_clause() に抽出 (Parser)
  • vgcg.rb
    • vram[...] のマッチ処理をメソッドに抽出して共通化


kairo-gokko (39) コンパイル時間短縮のために data.rb をスリム化



require_remote にかかる時間がさすがに長すぎるので、なんとかしたい……。 開発効率的にも辛いですし、他の人に見てもらうときもなるべく待たせないようにしたい。


というわけで調べてみました。 ネックになっているのは data.rbコンパイル時間のようです。

今までのデータでサイズが一番大きいのは step 36 のものなので、今回はこのファイルを使って比較します。

data.rbコンパイルにどのくらい時間がかかっているのか *1 測ってみると、 Firefox で 5回の平均が 22.8 秒でした。うーん、これはひどい

サイズを見てみます。

  • 741 KiB
  • 行数: 35,163

うーむ。Opal もこんなものを渡されて大変ですね。


ちなみにこの data.rb を CRuby で実行してみるとこんな感じでした。

$ ruby -v
ruby 2.7.0p0 (2019-12-25 revision 647ee6f091) [x86_64-linux]

$ time ruby data.rb 

real    0m0.192s
user    0m0.107s
sys     0m0.095s

単純に大きいので小さくしましょう。

以下は data.rb の内容の一部です。

      {
        "edges": [
          {
            "pos1": {
              "x": 59,
              "y": 9
            },
            "pos2": {
              "x": 60,
              "y": 22
            },
            "wfs": [
              {
                "pos1": {
                  "x": 59,
                  "y": 9
                },
                "pos2": {
                  "x": 60,
                  "y": 9
                }
              },
              {
                "pos1": {
                  "x": 60,
                  "y": 9
                },
                "pos2": {
                  "x": 61,
                  "y": 9
                }
              },

Point オブジェクトが大量にあります。 まずは これをコンパクトにしましょう。

オブジェクトのフォーマット { ... } になっていたところをただの文字列にします。 フォーマットの変更なので、 step 38 までのデータとは互換性がなくなりますが、やむなし。

--- a/unit.rb
+++ b/unit.rb
@@ -9,17 +9,12 @@ module Unit
     end
 
     def to_plain
-      {
-        x: @x,
-        y: @y
-      }
+      [@x, @y].join(",")
     end
 
     def self.from_plain(plain)
-      Point.new(
-        plain["x"],
-        plain["y"]
-      )
+      x, y = plain.split(",").map { |s| s.to_f }
+      Point.new(x, y)
     end
 
     def hash

たとえば上に挙げた箇所がこんな感じでコンパクトになります:

      {
        "edges": [
          {
            "pos1": "59,9",
            "pos2": "60,22",
            "wfs": [
              {
                "pos1": "59,9",
                "pos2": "60,9"
              },
              {
                "pos1": "60,9",
                "pos2": "61,9"
              },

これで 11.4 秒になりました。


それから、JSON の整形でもかなりサイズが水増しされているので、 整形をやめることに。

--- a/preprocess.rb
+++ b/preprocess.rb
@@ -21,6 +21,6 @@ circuits =
 plain = circuits.map { |circuit| circuit.to_plain }
 
 puts "$data_json = <<EOB"
-print JSON.pretty_generate(plain)
+print JSON.generate(plain)
 print "\n"
 puts "EOB"

もちろん整形されている方がデバッグ時などに見やすいわけで、 整形をやめるかどうかちょっと悩みました。

しかし、デバッグのために data.rb を調べなければいけない場面は今までそんなになかったですし、 整形したければまた JSON.pretty_generate に戻せばよいだけだと考え、やってしまうことにしました。


最終的な前後比較です。

所要時間: requrie_remote "./data.rb" の所要時間
サイズ: data.rb のサイズ

before:
  所要時間: 22.8 秒
  サイズ:   740.8 KiB

after:
  所要時間: 2.6 秒    ... 88%減
  サイズ:   109.6 KiB ... 85%減

かなり縮みました。元がひどかったですね……。


デモ用に 1bit CPU だけのデータを作り直しました。

https://sonota88.github.io/kairo-gokko/pages/39/index.html



*1:正確には「リソースの取得にかかる時間+コンパイル時間」を見ているのですが、 コンパイル時間でほとんどを占めていると思われるので、 単に「コンパイル時間」としています。