AWK（gawk）でシンプルな自作言語のコンパイラを書いた
かんたんな自作言語のコンパイラをいろんな言語で書いてみるシリーズ 29番目の言語は AWK です。
gawk が使える環境ならどこでも自作言語で書いたプログラムをコンパイルできるようになりました。
（他所に書いていたものを引っ越してきました。元の公開日は 2024-07-21 です。）
できたもの
サイズ
$ LANG=C wc -l mrcl_*.awk lib/*.awk
396 mrcl_codegen.awk
74 mrcl_lexer.awk
406 mrcl_parser.awk
105 lib/json.awk
114 lib/types.awk
31 lib/utils.awk
1126 total
本質的なロジック部分だけならこのくらい:
$ LANG=C wc -l mrcl_*.awk
396 mrcl_codegen.awk
74 mrcl_lexer.awk
406 mrcl_parser.awk
876 total
動作の例
$ echo '
func add(a, b) {
return a + b;
}
func main() {
call add(1, 2);
}
' | gawk -f mrcl_lexer.awk | gawk -f mrcl_parser.awk | gawk -f mrcl_codegen.awk
# ↓アセンブリが出力される
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)
移植元
Ruby 版から移植しています。
自分がコンパイラ実装に入門するために作った素朴なトイ言語とその処理系です。
- コンパクト: コンパイラ部分は 1,000 行程度
- 無理して短く書くようなことはせず、読みやすさ優先で素直に書いてこのくらい
- pure Ruby / 標準ライブラリ以外のライブラリ不要
- ブラックボックスなしですべてを掌握できるように
- x86風の自作VM向けにコンパイルする
- ライフゲームのために必要な機能だけ
- 変数宣言、代入、反復、条件分岐、関数定義
- 演算子:
+,*,==,!=のみ（優先順位は()で明示） - 型なし（値は符号付き整数のみ）
- 作ったときに書いた備忘記事
-
製作メモ
- 作ったときの全過程を書いています
- この通りにやれば誰でも同じものを作れる……のは確かだけど、いろいろ改善点が見えてきたので全体的に改訂したい
- 凝ったことはしていないので Ruby を知らない人でも雰囲気くらいは分かるんじゃないかと
-
本体には含めていない後付けの機能など
- 真偽値リテラル / break / if/else / 単項マイナス / パーサの別実装 / 簡単な静的型検査 / etc.
- これらは後から追加できます
-
他言語への移植
- 最低限の機能だけに絞ってコンパクトにしているので気軽に移植できます
- コンパイラ部分のみ
- Python, TypeScript, Julia, Dart, Haskell, Zig, V, R, Elixir など、2024-07-21 の時点では 29言語
-
セルフホスト版
- さらに育てていってセルフホスト（自作コンパイラで自作コンパイラをコンパイルする）もできました
これは Mini Ruccola 言語で書いたライフゲームをコンパイル＋アセンブルして VM で実行している様子。コンパイルだけなら今回作った gawk 版でも同様に行えます。
メモ
- プログラミング言語としての AWK に触れたのは今回が初めて
- AWK 自体あまり使ったことがなくて、数行程度の簡単な処理を何度か書いたことはあるという程度
- 必要な知識の 8 割くらいはとほほのAWK入門で得られました 🙏
- 構文も見慣れた感じで、思ってたよりは普通のスクリプト言語っぽいという感想
- 多次元配列は使えるけど配列のネストはできないので、 Bash 版の時と同じようにグローバルな配列を 1 個用意してヒープ的に使う方式にした
入力全体を読み込んでから処理をさせたいという都合のため、BEGIN セクションと行ごとのセクションでグローバルな文字列変数に蓄積し、END セクションで入力全体を使って処理するという作りにしています。
BEGIN {
g_src = ""
}
# ...
{
# g_src に蓄積するだけ
g_src = g_src $0 "\n"
}
END {
# 入力全体を処理
do_something(g_src)
}
AWK は行指向の入力を扱うことを意図したツールであり、こういう使い方は本来邪道だと思います。こういうことがしたい場合は AWK を使うべきではないでしょう。
配列のネストはできない
$ echo "" | gawk '
END {
xs1[0] = 1
xs2[0] = xs1
}
'
gawk: cmd. line:4: (FILENAME=- FNR=1) fatal: attempt to use array `xs1' in a scalar context
関数から配列は返せない
$ echo "" | gawk '
function f( xs1) {
xs1[0] = 1
return xs1
}
END {
f()
}
'
gawk: cmd. line:4: (FILENAME=- FNR=1) fatal: attempt to use array `xs1' in a scalar context
関数内で変数宣言するとグローバル変数になる。ここは JavaScript っぽい（JavaScript に受け継がれた？）。
function f() {
x = 1 # グローバル変数になる
}
関数の引数にすることでグローバル変数化を回避する慣習があるそうです。
function f( x) {
x = 1 # グローバル変数にならない
}
JavaScript が作られたときに AWK の構文を参考にした話があって興味深い。
JavaScript 1.0 の構文はプログラミング言語 C の文の構文を忠実に真似て作られており、加えて AWK から影響を受けた装飾もいくつか持っている。
AWK に影響を受けた for-in 文
function 宣言は AWK と同じ構文を採用
この記事を読んだ人は（ひょっとしたら）こちらも読んでいます
Discussion