素朴な自作言語のコンパイラを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 を併用。

# 記事 リポジトリ 日付
28 Scala github 2024-04-21
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:正確には「リソースの取得にかかる時間+コンパイル時間」を見ているのですが、 コンパイル時間でほとんどを占めていると思われるので、 単に「コンパイル時間」としています。

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


移植一覧に戻る


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

github.com


移植元

memo88.hatenablog.com

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

  • 追記 2021-03-21: Dart のバージョンアップ(2.9.1 => 2.12.0)に合わせて修正
    • null safety まわりを適当に修正
  • 追記 2021-03-21: ステップ56の修正まで適用しました

メモ

  • アセンブラVM は移植対象から外しました。Ruby 版のものを使います。
  • トークナイザとパーサを分けてみた
  • テストのステップを細かくした
  • ファイルを直接まじめに読まなくても、 標準入力が読めればあとはシェルスクリプトでラップしてあげたりすればいいので、 もうそれでいいかなという気持ちになった。

Dart でプログラムを書くのは今回初めてでしたが、JavaScriptJava あたりを知っていればかなりスムーズに書き始められるなーという感想でした。引っかかるところがほとんどなかったです(今回書いた範囲では)。適当にググりながら 1日で書けてしまいました。


今回の実験的な要素としては、パーサをいじって set を不要にしてみました。

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

 func main() {
   var a;
-  set a = 42;
+  a = 42;
 }

文の先頭の set で判別するのをやめて、識別子だったら parseSet_v2() を呼ぶ。 もうちょっとめんどくさいかなと思ってましたが、これだけだったら意外と簡単ですね。

List parseSet_v2() {
  // consume("set"); ... これが不要になる
  final t = peek();
  pos++;
  final varName = t.value;
  consume("=");
  final expr = parseExpr();
  consume(";");
  return ["set", varName, expr];
}

List parseStmt() {
  final t = peek();

  if (t.value == "}") {
    return null;
  }

  if      (t.value == "func"    ) { return parseFunc();      } 
  // ...
  // else if (t.value == "set"     ) { return parseSet();       }
  // ...
  else if (t.value == "_cmt"    ) { return parseVmComment(); }
  else {
    if (t.type == "ident") {
      return parseSet_v2();
    } else {
      throw notYetImpl([ t ]);
    }
  }
}

vm2gol v2 (46) リファクタリング(主にコード生成器)



コード生成器で気になっていた部分を修正しました。

codegen_stmts() まわりの整理

修正前の状況を見てみましょう。 呼び出しの関係が次のようになっています。

呼び出す側    => 呼び出される側
codegen       => codegen_stmts
codegen_case  => codegen_stmts
codegen_while => codegen_stmts

まず codegen_stmtscodegen_top_stmts にリネーム。

リネーム後はこうなります:

codegen       => codegen_top_stmts
codegen_case  => codegen_top_stmts
codegen_while => codegen_top_stmts

codegen => codegen_top_stmts はいいとして、 codegen_casecodegen_while から codegen_top_smtms を呼んでいるのは変ですね。 これだと、たとえば case 文や while 文の中で関数が定義できてしまいます (できるけどそういうコードを書かないようにしていた、という状態)。

リネームによっておかしなところが目立つようになりました。 おかしいので是正していきます。

まずは codegen_func_def 内で関数の処理本体のコード生成を行っていた部分を 改めて codegen_stmts としてメソッド抽出します。 トップレベル以外の場所にある文の連なりの処理です。

(追記 2020-08-25) テストが通っていたので雑にやってしまいましたが、 lvar_names の扱いがおかしいことに気付きました。あとで修正します……。

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
  end

  alines
end

こうなりました:

codegen          => codegen_top_stmts
codegen_case     => codegen_top_stmts
codegen_while    => codegen_top_stmts
codegen_func_def => codegen_stmts

あとは codegen_casecodegen_while から codegen_top_smtms ではなく codegen_stmts を呼ぶようにすると、こうなります:

codegen          => codegen_top_stmts
codegen_case     => codegen_stmts
codegen_while    => codegen_stmts
codegen_func_def => codegen_stmts

これで意味的に変だったところがまともになりました。 テストが壊れていないので動作の方も問題なさそうです。 たぶん大丈夫。 ライフゲーム動いてるから。

これで codegen_top_stmts の呼び出し元が codegen だけになりました。 トップレベルに書けるのは今のところ関数定義とコメントだけでよいので、 それ以外の分岐は消してしまいます(上述の修正で不要になったので消してOK)。 これにより引数 fn_arg_names, lvar_names も不要になったのでこれも除去。

--- a/vgcg.rb
+++ b/vgcg.rb
@@ -428,7 +428,7 @@ def codegen_func_def(rest)
   alines
 end
 
-def codegen_top_stmts(fn_arg_names, lvar_names, rest)
+def codegen_top_stmts(rest)
   alines = []
 
   rest.each do |stmt|
@@ -436,16 +436,6 @@ def codegen_top_stmts(fn_arg_names, lvar_names, rest)
     case stmt_head
     when "func"
       alines += codegen_func_def(stmt_rest)
-    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 "set"
-      alines += codegen_set(fn_arg_names, 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
@@ -464,7 +454,7 @@ def codegen(tree)
 
   head, *rest = tree
   # assert head == "stmts"
-  alines += codegen_top_stmts([], [], rest)
+  alines += codegen_top_stmts(rest)
 
   alines
 end

第38回codegen_stmts()codegen_func_def() の共通化 について触れたときは、なんか変だなとは思っていたもののこの形がまだ見えていませんでした。 慌てていじらずに寝かせておいてよかった気がします。

codegen_exp()

codegen_exp() が長くて(106行……)ちょっと辛いのと、 二項演算の左右の項をスタックに push する処理が重複していたので、 メソッド抽出して整理して、最終的に次のようになりました。すっきり。

def codegen_exp(fn_arg_names, lvar_names, exp)
  alines = []
  operator, *args = exp

  arg_l = args[0]
  arg_r = args[1]

  alines += _codegen_exp_push(fn_arg_names, lvar_names, arg_l)
  alines += _codegen_exp_push(fn_arg_names, lvar_names, arg_r)

  case operator
  when "+"
    alines += _codegen_exp_add()
  when "*"
    alines += _codegen_exp_mult()
  when "eq"
    alines += _codegen_exp_eq()
  when "neq"
    alines += _codegen_exp_neq()
  else
    raise not_yet_impl("operator", operator)
  end

  alines
end

その他

  • codegen_set(): caseの分岐を他の箇所に揃えた
    • 他の箇所に揃えて、まず型で分岐させる書き方に
  • Vm#copy: 記述位置の移動のみ
  • vgparser.rb: tokenize() の記述位置の移動のみ
    • パーサのコードを調べてるとき、末尾に tokenize() があると邪魔くさかったので


Pythonでシンプルな自作言語のコンパイラを書いた


移植一覧に戻る


Python で書いてみました。やっつけなので汚いです。Python よく知らないけどライフゲームが動いたのでヨシ、という程度の雑なものです。

github.com

移植元

github.com

<自作言語処理系(Ruby版)の説明用テンプレ>

自分がコンパイラ実装に入門するために作った素朴なトイ言語とその処理系です。

何ヶ月もかけてCコンパイラを作るのが「100 の労力で 100 を得る」だとしたら、このプロジェクトは「まず 5 の労力で 20 を得よう」みたいな方向性です。得られるものは 100 ではありませんが短期間で完成させることができます。

<説明用テンプレおわり>

ベースになっているバージョン: ステップ45 のあたり
(追記 2023-11-19 ステップ66 まで反映しました)

動かし方の例

$ echo '
  func add(a, b) {
    return a + b;
  }

  func main() {
    call add(1, 2);
  }
' | python3 mrcl_lexer.py | python3 mrcl_parser.py | python3 mrcl_codegen.py


# ↓アセンブリが出力される

  call main
  exit

label add
  push bp
  mov bp sp

  # 関数の処理本体
  mov reg_a [bp:2]
  push reg_a
  mov reg_a [bp:3]
  push reg_a
  pop reg_b
  pop reg_a
  add reg_a reg_b

  mov sp bp
  pop bp
  ret

  mov sp bp
  pop bp
  ret

label main
  push bp
  mov bp sp

  # 関数の処理本体
  mov reg_a 2
  push reg_a
  mov reg_a 1
  push reg_a
  _cmt call~~add
  call add
  add sp 2

  mov sp bp
  pop bp
  ret

(snip)

ステージごとに動かしてみる

上記の例ではパイプでつなげてコンパイル処理全体を一気に実行していますが、字句解析・構文解析・コード生成それぞれを単独で実行することもできます。

以下、空の main 関数( func main() {} )だけをコンパイルするケースで各ステージの動作例を示します。

字句解析

echo 'func main() {}' | python3 mrcl_lexer.py

出力:

[1, "kw", "func"]
[1, "ident", "main"]
[1, "sym", "("]
[1, "sym", ")"]
[1, "sym", "{"]
[1, "sym", "}"]

func main() {} という単なる文字列をトークンの並びに変換します。ここは簡単。素朴な文字列処理なので mrcl_lexer.py も100行以下に収まっています(2024-04-30 時点)。

文字列処理のプログラミングの経験がある程度ある人なら入出力を見ただけで「こうすればできそうだ」というイメージが湧くのではないでしょうか。

構文解析

echo '
[1, "kw", "func"]
[1, "ident", "main"]
[1, "sym", "("]
[1, "sym", ")"]
[1, "sym", "{"]
[1, "sym", "}"]
' | python3 mrcl_parser.py

出力:

[
  "top_stmts",
  [
    "func",
    "main",
    [],
    []
  ]
]

構文解析ではトークンの並びを入力として受け取り、抽象構文木に変換します。

1次元の情報から構造(木構造)を持つデータへ変換するわけで、やり方を知らないとここはちょっと魔法っぽいですよね。

構文解析処理の実装手法はさまざまありますが、Mini Ruccola ではサードパーティライブラリを使わずなるべく自前で書く方針なので 再帰下降構文解析 という方法を使っています。

知らないと魔法っぽく見えるところですし、「再帰下降構文解析」という名前がちょっと怖そうに聞こえるかもしれませんが、初歩的な部分であれば半日もかからず入門できると思います。別の記事に書きましたのでこちらを参照してください。

qiita.com

基本的な部分が分かってしまえば、あとは肉付けです。肉付けしていけばパーサができあがります。

コード生成

echo '
[
  "top_stmts",
  [
    "func",
    "main",
    [],
    []
  ]
]
' | python3 mrcl_codegen.py

出力:

  call main
  exit

label main
  push bp
  mov bp sp

  # 関数の処理本体

  mov sp bp
  pop bp
  ret

(snip)

コンパイラ実装のコア部分です。 抽象構文木を入力として受け取り、アセンブリコード(Mini Ruccola では機械語コードと大体同じ)を出力します。

コンパイル処理全体を通して眺めると、1次元のデータ(ソースコード)を一度扱いやすい構造(抽象構文木)に変換し、それから目的とする出力の形に合わせて1次元のデータ(機械語と対応する命令の列)に変換する、という流れになっていますね。

ここは詳しく書き始めると長くなるので以下を参照してください。私はこういう流れで入門しました、というメモです。

memo88.hatenablog.com


VM機械語の初歩

アセンブラ

関数呼び出し

関数の引数・ローカル変数・関数の返り値

ライフゲームコンパイルして実行

(2024-01-06 追記)

run_game_of_life.sh を追加しました。 ライフゲームのプログラムをコンパイルアセンブルし、VM で実行します。

他の人によって書かれた Python 版移植

ご興味ある方はぜひどうぞ!

github.com

メモ

アセンブラVM は移植対象から外しました。Ruby 版のものを使います。

(2024-01-06 追記)Python で書いたアセンブラVM も追加しました。


トークナイザは今のところ大した量もないのでパーサと同じファイルに書いていますが、やっぱり分けようかなという気分になりました。


移植版は今後も継続してメンテするわけではなくババッと作って気が済んだら終わりというものなので、 Ruby 版にそのうち入れるかもしれない修正を気軽に・実験的に試してみようかと。

高水準言語部分の文法をやっぱり Ruby っぽくしようかなと考えていて、今回はそれを一部試してみました。

(2021-06-05 追記: その後の修正を加えるために以下の修正はいったん取り消しましたが、一応 trial ブランチに残してあります。)

funcdef に変えて、 { ... }... end に変えて、行コメントの開始文字を # に変えて……と修正していって、下記のような怪しい見た目になりました。varset なんかはまだ残っています。

def calc_next_gen(current_val, count)
  # 注目しているセルの次世代の生死
  var next_val = 0;

  case
  when (current_val == 0)
    case
    when (count == 3)
      set next_val = 1;
    end
  when (0 == 0)
    case
    when (count == 2)
      set next_val = 1;
    when (count == 3)
      set next_val = 1;
    end
  end
  
  return next_val;
end

怪しいですが ruby -c test/*.vg.txt で文法チェックすると OK と出ます。

Ruby で実行するとさすがに何かしらエラーになるだろう……と思って試してみたら正常終了しました。 最初は意外な感じがしましたが、メソッドの定義しかしてない(実行していない)ため実行時エラーも出ない、ということのようです。なるほど。