記事の案内

「このブログには他にどういう記事があるの?」という方向けの案内です。

がんばったもの

memo88.hatenablog.com memo88.hatenablog.com

続き: Rubyで素朴な自作言語のコンパイラを作った - memo88


memo88.hatenablog.com

ごっこ

いわゆる "Build your own 〜 from scratch" 的なもの。

カテゴリ別

Ruby

Ruby カテゴリの記事一覧

LibreOffice

LibreOffice カテゴリの記事一覧

Emacs

Emacs カテゴリの記事一覧

Emacs 関連は一部内容が古くなっている気がします。

Ruby/Racc: パースに失敗した位置(行、桁)を得る

パースに失敗したとき、失敗した位置をたとえば次のように表示したいですよね?

parse error: line 2, col 5
foo bar
    ^

短いのでとりあえず全部貼ります。

# parser.y

class Parser

rule
  program: "a" "b" "c" "d" ";"
  {
    puts "program found"
    result = val
  }
end

---- header

TokenValue = Struct.new(:value, :pos)

---- inner

def initialize(src, tokens)
  @src = src
  @tokens = tokens
end

def next_token
  @tokens.shift
end

def parse
  do_parse
end

def get_lineno_and_range(pos)
  lineno = 1
  line_start = 0
  range = nil

  @src.each_line do |line|
    next_line_start = line_start + line.size
    range = line_start .. (next_line_start - 1)
    break if range.include?(pos)

    line_start = next_line_start
    lineno += 1
  end

  [lineno, range]
end

def on_error(token_id, val, vstack)
  lineno, range = get_lineno_and_range(val.pos)
  colno = val.pos - range.begin + 1
  line = @src[range]

  puts "parse error: line #{lineno}, col #{colno}"

  puts line
  print " " * (colno - 1), "^\n"
end

---- footer

def tokenize(src)
  tokens = []

  pos = 0
  while pos < src.size
    c = src[pos]
    case c
    when /\s/
      pos += 1
    else
      tokens << [c, TokenValue.new(c, pos)]
      pos += 1
    end
  end

  tokens
end

src = File.read(ARGV[0])
tokens = tokenize(src)
parser = Parser.new(src, tokens)
result = parser.parse()
puts "result: " + result.inspect

a b c d ; というトークン列だけを受理するパーサです。

入力となるソースコードではトークン同士をスペースや改行で区切ります。

パースに成功する例:

a
b

c d
;

たとえば dX に置き換えた次のソースコードを与えるとパースに失敗します。

a
b

c X
;

失敗する場合の実行例:

$ racc parser.y -o parser.rb

$ ruby parser.rb sample_ng.txt
parse error: line 4, col 3
c X
  ^
result: nil

短いので上に貼ったコードを読んだ方が早いと思いますが、 一応簡単にメモ。

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


移植一覧に戻る


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

github.com


移植元

memo88.hatenablog.com

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

メモ

  • Go は 3, 4 年前にちょっとしたCLIツールを作った程度
  • C の後だとすごい楽ちん
  • メソッドも便利
  • ほんとは練習のためにもっとスライスを使いたかったけど、あまり使わないままできあがってしまった

今回の実験コーナー。

これまで 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 u8const ですね。

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;
}

だいたい同じことやってますね。

参考

Zig: 1バイトごとに読み書きするだけのcatコマンドを書いてみた

Zig(ziglang) で標準入力から1バイト読んで標準出力に書くのを繰り返すだけの素朴な cat コマンドを書いてみました。

Zig はさっき触り始めたばかりで右も左も分からない状態です。

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>
--------

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


移植一覧に戻る


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

github.com


移植元

memo88.hatenablog.com

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

ただ、実質的には Perl版 からの移植です。

メモ

  • PHP を書くのは今回が初めて
  • さらっと文法を見た感じ Perl に近そうだったので、 Perl版をコピーして書き換えていった
    • 割と機械的に置き換え
      • my を消して
      • sub => function
      • elsif => elseif
      • 正規表現はダブルクォートで囲んで preg_match にして
      • ……などなど
    • PerlPHP という流れで進んだのは良かった
  • Emacsphp-mode を追加するのがめんどくさかったので perl-mode で書いてた
  • クラスも普通に使えるし、 int と string の型の判別もできるし、 Perl より楽ちんという印象。 正直なところあまり書くことがないです……。

今回の実験コーナー。

これまで Dart への移植 のときに set を不要にし、 Java への移植 のときに call を不要にし、 Perl への移植 のときに call_set を不要にしてきました。

これらを全部適用するとどうなるか trial ブランチ でやってみました。

とりあえず parse_stmt() の分岐のとこだけ貼ってみます。

<?php
# ...

    # if     ($t->str_eq("set"     )) { return parse_set();        }
    # if     ($t->str_eq("call"    )) { return parse_call();       }
    # elseif ($t->str_eq("call_set")) { return parse_call_set();   }
    elseif ($t->str_eq("return"  )) { return parse_return();     }
    elseif ($t->str_eq("while"   )) { return parse_while();      }
    elseif ($t->str_eq("case"    )) { return parse_case();       }
    elseif ($t->str_eq("_cmt"    )) { return parse_vm_comment(); }
    else {
        if (
               $t->kind_eq("ident")
            && peek(1)->is("sym", "=")
        ) {
            if (
                   peek(2)->kind_eq("ident")
                && peek(3)->is("sym", "(")
            ) {
                return parse_call_set();
            } else {
                return parse_set();
            }
        } elseif (
               $t->kind_eq("ident")
            && peek(1)->is("sym", "(")
        ) {
            return parse_call();
        } else {
            throw not_yet_impl($t);
        }
    }

個別に試していたときはそれぞれの個別のことだけ考えてやればよかったのが、 3つを同時に満たそうとして else に押し込めてとりあえずこうなった、というものです。 ちょっと野暮ったいですが peek(n) で先読みしてやればなんとかなるようです。

funcall を expr に含めるとかするともうちょっとすっきりする気がします。

vgコードはこんな感じ。 ここまでやるとかなり普通の言語(というか JavaScript)っぽい見た目になりますね。

func 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;
  }
}

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 のメッセージを改善
  • テストまわりの改善