Qiita の方に書きました。
LibreOffice BasicでLispインタプリタ(mal)を書いた
Qiita の方に書きました。
Ruby/Racc: パースに失敗した位置(行、桁)を得る
Qiita の方に書きました。
素朴な自作言語のコンパイラをGoに移植した
やっつけなので汚いです。ライフゲームのコンパイルが通ったのでヨシ、というレベルのものです。
移植元
ベースになっているバージョン: tag:50 のあたり
(2021-06-20 追記) ステップ60 の修正まで反映しました
メモ
今回の実験コーナー。
これまで Dart への移植 のときに set を不要にし、 Java への移植 のときに call を不要にし、 Perl への移植 のときに call_set を不要にしてきました。
今回はこれらを全部適用して、さらに Python への移植 のときにやった、 Ruby っぽい見た目への変更も加えました。
trial ブランチ でやってみました。
vgコードはこんな感じ。
var
を除けばこれはもう Ruby ですね。
def calc_next_gen(current_val, count) # 注目しているセルの次世代の生死 var next_val = 0; case when (current_val == 0) case when (count == 3) next_val = 1; end when (0 == 0) case when (count == 2) next_val = 1; when (count == 3) next_val = 1; end end return next_val; end def main() var w = 5; # 盤面の幅 var h = 5; # 盤面の高さ # 初期状態の設定 vram_set(w, 1, 0, 1); vram_set(w, 2, 1, 1); vram_set(w, 0, 2, 1); vram_set(w, 1, 2, 1); vram_set(w, 2, 2, 1); var gen_limit = 0; var gen = 1; while (gen != gen_limit) make_next_gen(w, h); replace_with_buf(); gen = gen + 1; end end
Zig: コマンドライン引数を受け取って整数(i32)に変換する
Zig 昨日触りはじめたばかりでまだぜんぜん分かってません。
まずは std.os.argv
でコマンドライン引数を取得します。
pkv
は確認用のユーティリティ関数で、 print key value のつもり。
// arg_to_i_v1.zig const std = @import("std"); fn pkv(k: []const u8, v: var) !void { std.debug.warn("{} ({})\n", .{k, v}); } pub fn main() !void { try pkv("std.os.argv", std.os.argv); try pkv("std.os.argv type", @TypeOf(std.os.argv) == [][*:0]u8); const arg1: [*:0]u8 = std.os.argv[1]; try pkv("arg1", arg1); }
$ zig-0.6.0 run arg_to_i_v1.zig -- 42 std.os.argv ([*:0]u8@7ffc55805dd8) std.os.argv type (true) arg1 (42)
コマンドライン引数が文字列(というかバイト列)の配列として取得できたので、次はこれを i32 に変換します。
標準ライブラリに std.fmt.parseInt
という関数があったので適当に使ってみました。
// arg_to_i_v2.zig const std = @import("std"); pub fn main() !void { const arg1: [*:0]u8 = std.os.argv[1]; const n: i32 = try std.fmt.parseInt( i32, // 変換後の型 arg1, // 変換元の文字列 10 // 基数 ); }
これは型が違うためエラーになります。
./arg_to_i_v2.zig:14:5: error: expected type '[]const u8', found '[*:0]u8' arg1, // 変換元の文字列
ここで詰まったので、一度落ち着いて、型について見てみることにしました。
std.os.argv
の型は [][*:0]u8
、
その要素(それぞれの引数)の型は [*:0]u8
。
[]Foo
は Foo のスライス。
この表記はスライスだ、と丸呑みしてもよいですが、
これが出てきたら []
の中が空なのでコンパイル時には要素数(長さ)が決まらない(実行時に決まる)
……みたいなことを考えればいいんでしょうか。
[*]Foo
は Foo の配列へのポインタ型。
うーん、この表記は覚えるしかなさそう。
Cの配列のように先頭と要素の型に関する情報は持っているが、要素数の情報は持たない。
[A:B]Foo
は要素数が A で終端の要素(sentinel)が B である Foo の配列を表す型。
たとえば、[4:0]u8
は要素数が 4 で、終端の要素が 0 である u8 の配列の型、となる。
[ 11, 22, 33, 44, 0 ] ^ ここ(xs[要素数])が 0
で、 [*:0]Foo
は何なのか。
要素数が *
とは??
と思ってしまいましたが、
これは「終端が0である配列」へのポインタ型、と読めばいいようです。たぶん。
終端が 0 であることは分かっているが要素数は分からない配列の先頭を差すポインタの型。
[len:sentinel]
のパターンに当てはめるのではなく、この場合は
[*]Foo
に終端の情報 :0
が加わっている、と捉えればよいのでしょうか。
あと残っているのは []const u8
の const
ですね。
const
を外して []u8
だけだったら何かというと、えーとこれは「u8
のスライス」ですね。
ただの []Foo
だと要素を書き換えられるスライスですが、
[]const Foo
だと要素を書き換えられないスライスになるようです。
var xs: [3]u8 = [3]u8{ 'a', 'b', 'c' }; const slice: []u8 = xs[0..xs.len]; slice[0] = 'A'; const unmodifiable_slice: []const u8 = xs[0..xs.len]; unmodifiable_slice[0] = 'A'; //=> error: cannot assign to constant
std.fmt.parseInt
が []const u8
を要求しているということは、つまり
「std.fmt.parseInt
では渡されたスライスの内容を変更しません(できません)よ」
ということを引数の型で表明しているのだと思います。
std.fmt.parseInt
を使う側は「呼び出した関数の中で引数で渡したものの内容が書き換えられたりしないか?」という心配をしなくて済む、ありがたい、ということでしょう。
他の例としては、たとえば OutStream の write 関数や print 関数に渡す文字列の型も []const u8
になっています。
https://github.com/ziglang/zig/blob/0.6.0/lib/std/io/out_stream.zig
pub fn write(self: Self, bytes: []const u8) Error!usize { ... } pub fn print(self: Self, comptime format: []const u8, args: var) Error!void { ... }
ここまで分かったので、次にすべきなのは [*:0]u8
から []const u8
への変換です。
// こういう形に持っていきたい: const slice: []const u8 = ??? // [*:0]u8 から変換する const n: i32 = try std.fmt.parseInt(i32, slice, 10);
枝葉を無視して「配列からスライスへの変換」と考えてみます。
配列からスライスを作る基本的な方法はこう。
const xs: [3]u8 = [3]u8{ 'a', 'b', 'c' }; const slice: []u8 = xs[0..xs.len];
ですが、今必要なのは [*:0]u8
から []const u8
への変換なので、
その形に持って行きたい。
変換後は []const u8
にしたいので、とりあえず const
を付けてみます。
const xs: [3]u8 = [3]u8{ 'a', 'b', 'c' }; const slice: []const u8 = xs[0..xs.len]; // ^^^^^
えーとそれから次は……この例だと変換元が [3]u8
と要素数を指定していますが、これを [*:0]u8
にしたいので…… :0
を付けてみましょうか。
const xs: [3:0]u8 = [3:0]u8{ 'a', 'b', 'c' }; const slice: []const u8 = xs[0..xs.len];
ここから [*:0]u8
にすると、スライスに変換するときに必要な xs.len
が取れなくなります。
const xs: [*:0]u8 = ...; const slice: []const u8 = xs[0..???];
[*:0]u8
ということは、要素数は分からないけれど終端が 0 であることは分かっています。
なので、要素数を知りたければ 0 の位置を探せばいいんじゃないでしょうか。
次のような関数を書いてみました。
fn countChars(chars: [*:0]u8) usize { var i: usize = 0; while (true) { if (chars[i] == 0) { return i; } i += 1; } }
これを使って、 [*:0]u8
な配列を作って []const u8
に変換するサンプルコードを書いてみました。
// arg_to_i_v3.zig // ... snip ... pub fn main() !void { var xs: [5:0]u8 = [5:0]u8{ 'a', 'b', 'c', 0, 'd' }; try pkv("xs", xs); try pkv("xs.len", xs.len); const xs2: [*:0]u8 = &xs; try pkv("xs2", xs2); // try pkv("xs2.len", xs2.len); // => error: type '[*:0]u8' does not support field access const slice = xs2[0..countChars(xs2)]; try pkv("slice", slice); try pkv("slice.len", slice.len); }
$ zig-0.6.0 run arg_to_i_v3.zig xs (abcd) xs.len (5) xs2 (abc) slice (abc) slice.len (3)
できました。
ためしに途中の要素 xs[3]
を 0 にしてみたため abc
までで打ち切られていますが、
終端が 0 だということになっているのでこれはこれでよいでしょう。
ここまでできたらあとは parseInt に渡すだけです。 まとめると下記のようになりました。
// arg_to_i_v4.zig const std = @import("std"); fn pkv(k: []const u8, v: var) !void { std.debug.warn("{} ({})\n", .{k, v}); } fn countChars(chars: [*:0]u8) usize { var i: usize = 0; while (true) { if (chars[i] == 0) { return i; } i += 1; } } pub fn main() !void { const arg1: [*:0]u8 = std.os.argv[1]; const arg1_unmodifiable_slice: []const u8 = arg1[0..countChars(arg1)]; const n: i32 = try std.fmt.parseInt( i32, arg1_unmodifiable_slice, 10 ); try pkv("n", n); }
$ zig-0.6.0 run arg_to_i_v4.zig -- 42 n (42)
上記の countChars
に相当する関数は標準ライブラリにあるんじゃないかと思って調べてみましたが、ちょっと分かりませんでした。
が、テストコードの中に strlen
という関数があるのは見つけました。
https://github.com/ziglang/zig/blob/0.6.0/test/stage1/behavior/const_slice_child.zig#L35
fn strlen(ptr: [*]const u8) usize { var count: usize = 0; while (ptr[count] != 0) : (count += 1) {} return count; }
だいたい同じことやってますね。
参考
- (2019-07-23) オープンソースプログラミング言語zigまとめ - Qiita
- たいへん参考になりました
- v0.4.0 時点
この記事を読んだ人は(ひょっとしたら)こちらも読んでいます
Zig: 1バイトごとに読み書きするだけのcatコマンドを書いてみた
Zig(ziglang) で標準入力から1バイト読んで標準出力に書くのを繰り返すだけの素朴な cat コマンドを書いてみました。
Zig はさっき触り始めたばかりで右も左も分からない状態です。
<追記 2022-07-17>
v0.8.0 で InStream, OutStream がそれぞれ reader, writer という名前に変わりました。
Proposal: Rename InStream and OutStream · Issue #4917 · ziglang/zig
この変更にあわせて、下記のように修正する必要があります。v0.9.1 でコンパイル+実行できることを確認しました。
- const outstream = std.io.getStdOut().outStream(); + const outstream = std.io.getStdOut().writer(); - const instream = std.io.getStdIn().inStream(); + const instream = std.io.getStdIn().reader();
<追記おわり>
const std = @import("std"); pub fn main() !void { const outstream = std.io.getStdOut().outStream(); const instream = std.io.getStdIn().inStream(); while (true) { const byte = instream.readByte() catch |err| switch (err) { error.EndOfStream => { break; }, else => |e| { return e; }, }; try outstream.writeByte(byte); } }
実行。
$ head -5 cat.zig | zig-0.6.0 run cat.zig | cat -A const std = @import("std");$ $ pub fn main() !void {$ const outstream = std.io.getStdOut().outStream();$ const instream = std.io.getStdIn().inStream();$
リファレンスの探し方がよく分かってなくて GitHub でソースとコメントを見た方が速かった。
zig/in_stream.zig at 0.6.0 · ziglang/zig
https://github.com/ziglang/zig/blob/0.6.0/lib/std/io/in_stream.zig
0.6.0 では in_stream.zig
だったのが master(現在は 4fbf9f7f79c8e0df
)では reader.zig
に変わっていたりします。
2020-09-21 追記
関数呼び出しや条件分岐などの要素が加わったサンプルとして、 CR, LF, タブ, EOF を分かりやすく表示するバージョンを書いてみました。 入力が UTF-8 である想定です。
const std = @import("std"); const outstream = std.io.getStdOut().outStream(); fn printByte(byte: u8) !void { if (byte == '\t') { try outstream.print("<TAB>", .{}); } else if (byte == '\r') { try outstream.print("<CR>", .{}); } else if (byte == '\n') { try outstream.print("<LF>", .{}); try outstream.writeByte(byte); } else { try outstream.writeByte(byte); } } pub fn main() !void { const instream = std.io.getStdIn().inStream(); while (true) { const byte = instream.readByte() catch |err| switch (err) { error.EndOfStream => { break; }, else => |e| { return e; }, }; try printByte(byte); } try outstream.print("<EOF>\n", .{}); }
実行例:
$ export PS1='--------\n\n$ ' -------- $ cat sample.txt ab cd あいうえお 0123-------- $ cat -A sample.txt ab^Icd^M$ M-cM-^AM-^BM-cM-^AM-^DM-cM-^AM-^FM-cM-^AM-^HM-cM-^AM-^J^M$ 0123-------- $ cat sample.txt | zig-0.6.0 run cat_v2.zig ab<TAB>cd<CR><LF> あいうえお<CR><LF> 0123<EOF> --------
この記事を読んだ人は(ひょっとしたら)こちらも読んでいます
cat コマンドを改造して育てていくとコンパイラが作れます。
素朴な自作言語のコンパイラをPHPに移植した
Zenn に引っ越しました。
vm2gol v2 (50) コード生成処理の変更にあわせたパーサの修正など
- 目次ページに戻る / 前 / 次
- 前回からの差分をまとめて見る
変数宣言周りの修正(パーサ編)
第48回 変数宣言のコード生成処理の改善など で変数宣言まわりを変更したときは特に考えてなかったんですが、これはパーサも合わせておいた方が良さそうに思えます。
まずは var文が書ける場所を関数の直下のみに限定する変更。
--- a/vgparser.rb +++ b/vgparser.rb @@ -185,7 +185,20 @@ class Parser consume ")" consume "{" - stmts = parse_stmts() + + stmts = [] + loop do + t = peek() + break if t.value == "}" + + stmts << + if t.value == "var" + parse_var() + else + parse_stmt() + end + end + consume "}" [:func, func_name, args, stmts] @@ -434,7 +447,6 @@ class Parser case t.value when "func" then parse_func() - when "var" then parse_var() # parse_stmt() からは削除 when "set" then parse_set() when "call" then parse_call() when "call_set" then parse_call_set()
これにより while文やcase文の中で var文が使えなくなってテストが壊れるので適宜 set文に変えるなどしました。
--- a/test/test_vgparser.rb +++ b/test/test_vgparser.rb @@ -286,14 +286,16 @@ class ParserTest < Minitest::Test def test_while_2 src = <<-EOS + var a; while (a == 1) { - var b; + set a = 2; } EOS tree_exp = [ + [:var, "a"], [:while, [:eq, "a", 1], [ - [:var, "b"]]]] + [:set, "a", 2]]]]
次いで top_stmt(s) 関連の修正。
parse_top_stmt()
,parse_top_stmts()
を追加parse()
からparse_top_stmts()
を呼び出すように切り替えparse_stmt()
から関数定義の分岐を削除
--- a/vgparser.rb +++ b/vgparser.rb @@ -446,7 +446,6 @@ class Parser return nil if t.value == "}" case t.value - when "func" then parse_func() when "set" then parse_set() when "call" then parse_call() when "call_set" then parse_call_set() @@ -474,8 +473,31 @@ class Parser stmts end + def parse_top_stmt + t = peek() + + case t.value + when "func" then parse_func() + else + raise ParseError, "Unexpected token (#{t.inspect})" + end + end + + def parse_top_stmts + stmts = [] + + loop do + break if end?() + + stmts << parse_top_stmt() + end + + stmts + end + def parse - stmts = parse_stmts() + stmts = parse_top_stmts() [:stmts, *stmts] end end
これで、 関数定義の中に関数定義を書くのはダメ、などのルールがパーサのコードで表現できている状態になりました。 今まで結構いい加減にやっていたところが多少はマシになった気がします。
vgtコードのルート要素の名前を変更
いい機会なのでこれも今回あわせて変更しました。 地味に気になっていた。
// before [ "stmts", ... ] // after [ "top_stmts", ... ]
ちなみに Ruby でも top_stmts
という名前になっています。
https://github.com/ruby/ruby/blob/v2_7_1/parse.y#L1208
codegen_return で出力する命令を変更
整数の即値を return で返却する場合は
set_reg_a {値}
というアセンブリコードを出力していましたが、他との統一性のため
cp {値} reg_a
のように cp を使うように変えました。 こうしておいた方が都合が良さそうなのです。 出力されるアセンブリコード、機械語コードが変わりますが動作は何も変わりません。
Perl に移植 していたときに気付いて Ruby版にフィードバック。
peek
parse_var()
では先読みのため @tokens[@pos + 1]
としていて、
ここだけ peek に置き換えられていなかったんですが、
offset という引数を追加して peek(1)
とすると
現在位置の1個先を覗き見できるようにしました。
--- a/vgparser.rb +++ b/vgparser.rb @@ -87,8 +87,8 @@ class Parser .map { |t| format("%s<%s>", t.type, t.value) } end - def peek - @tokens[@pos] + def peek(offset = 0) + @tokens[@pos + offset] end def dump_state(msg = nil)
これも移植版で先行して試していたものをそろそろいいかなと思って取り込んだ形。
その他
- メソッドの位置の変更
- ParseError のメッセージを改善
- テストまわりの改善
素朴な自作言語のコンパイラをC♭に移植した
やっつけなので汚いです。ライフゲームのコンパイルが通ったのでヨシ、というレベルのものです。
C♭は書籍 『ふつうのコンパイラをつくろう』の題材として作られた、C によく似た言語です。コンパイラ cbc は Java製。
移植元
ベースになっているバージョン: 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 環境で動かしているせいかもしれません。