ローファイ日記

出てくるコード片、ぼくが書いたものは断りがない場合 MIT License としています http://udzura.mit-license.org/

型付きRubyでパーサを書く(中編)

前編はこちら。

udzura.hatenablog.jp


ここまででスキャナまでは実装し、大体動いたようです(型もちゃんとついたようです)ので、続きの実装をします。

閑話: エディタの型支援を受ける

当方はEmacsなので読者の参考にならないかもしれませんが...。

といっても以下を有効にしたぐらい。

どちらも @ybiquitous さんの力なので、神と崇める他ない。

さらに、RBS有効のプロジェクトだけlspをsteepが用意したものに変えるため、プロジェクトのルートに以下のような .dir-locals.el を用意する。この内容は とんさんのブログ記事 のものを参考にしている。

((ruby-mode . ((lsp-enabled-clients . (steep-ls)))))

これでlspとlsp-uiを有効にすれば、こう言うのが出ます。

「あ、これrust-modeで便利だったやつじゃん!」 って気持ちになれました。イマい言語に追いつく(?)のは嬉しいですね。

閑話休題

パーサの実装

まずはヘルパーメソッドの型をざっくり書きました。

  class Parser
    @tokens: Array[Token]
    @current: Integer
    @node: Node

    def initialize: -> untyped
    def parse: (Array[Token] tokens) -> Root

    private
    def match: (*token_type types) -> bool
    def check: (token_type type_) -> bool
    def succ: -> Token
    def consume: (token_type type_, String message) -> Token
    def at_end?: -> bool
    def peek: -> Token
    def previous: -> Token
  end

型が合うようにヘルパーの実装を書いていきます。

  class Parser
    def initialize
      @tokens = [Token.new(:dummy, "")]
      @current = 0
    end

    def parse(tokens)
      @current = 0

      # まだ書いてないのでダミーの戻り値を置く
      @node = Node.new(:dummy, [], nil)
      Root.new(@node)
    end

    private
    def match(*types)
      types.each do |type|
        if check(type)
          succ()
          return true
        end
      end

      false
    end

    def check(type)
      if at_end?
        false
      else
        peek.type == type
      end
    end

    def succ
      if !at_end?
        @current += 1
      end
      previous
    end

    def consume(type, message)
      if check(type)
        succ()
      else
        raise "#{message} <token: #{peek}>"
      end
    end

    def at_end?
      peek.type == :eof
    end

    def peek
      @tokens[@current] || raise("EOF or out of range")
    end

    def previous
      @tokens[@current - 1] || raise("EOF or out of range")
    end
  end
...
$ bundle exec steep check
# Type checking files:

..............................................................

No type error detected. 🧉

気持ちいい瞬間だね。

あとはBNFに沿って中身を書いていけばいいです。パースの関数は@tokensと@currentを利用してNodeを取り出して返すので () → Node の定義の関数ばかりとなることになります、一部Arrayも返す。実装したら逐一RBSにも追加しつつ進めます。

※ ここ、メソッド本体を実装したら、自動でマージされて欲しいと思いました。typeprof mergeみたいな...。

RBSを漠然と更新していきます。

class Parser
    # ...

    private
    def block: -> Node
    def stats: -> Array[Node]
    def stat: -> Node
    def varstat: -> Node
    def ifstat: -> Node
    def assignstat: -> Node
    def funcallstat: -> Node
    def var: -> Node
    def exp: -> Node
    def binary: -> Node
    def unary: -> Node
    def functioncall: -> Node
    def primary: -> Node
    def args: -> Node
    def binop: -> Node
    def unop: -> Node

    def term: (Token token) -> Node

    def match: (*token_type types) -> bool    # ...
  end

あと :term を追加した方が都合がいい、追加。

type node_type = :block | :stat | :varstat | :assignstat | :funcallstat | :ifstat |
                   :exp | :binary | :unary | :functioncall | :primary | :var |
                   :args | :binop | :unop | :term |
                   :dummy |
                   :root

いったんコード側はダミー実装で埋め、steep checkを通します。

    private
    def block
      Node.new(:dummy, [], nil)
    end

    def stat
      Node.new(:dummy, [], nil)
    end
    #...

こうすると補完が効く、型がわかるなど何かと都合がいい、と。

ガリガリ実装していきます。途中で、token_typeが取るべき値に不足があるねとか、いろいろなことがわかって便利。以下の場合は false という予約語を追加し忘れていました。

lib/klua.rb:331:18: [error] Cannot pass a value of type `::Symbol` as an argument of type `::Klua::token_type`        
│   ::Symbol <: ::Klua::token_type                                                                                    
│     ::Symbol <: (:identifier | :number | :literal_str | :local | :if | :then | :else | :end | :and | :or | :not | :+
 | :- | :* | :/ | :< | :> | :== | :noteq | :assign | :comma | :semicolon | :lbrace | :rbrace | :eof | :dummy)         
│       ::Symbol <: :identifier                                                                                       
│                                                                                                                     
│ Diagnostic ID: Ruby::ArgumentTypeMismatch                                                                           
│                                                                                                                     
└       elsif match(:false)                                                                                           
                    ~~~~~~

あとは、以下の primary メソッドは問題があるんですが、ぱっと見だけでわかりますか?

    def primary
      if match(:nil)
        Node.new(:primary, [term!(:nil)], nil)
      elsif match(:false)
        Node.new(:primary, [term!(:false)], nil)
      elsif match(:true)
        Node.new(:primary, [term!(:true)], nil)
      elsif match(:number)
        Node.new(:primary, [term!(:number)], nil)
      elsif match(:literal_str)
        Node.new(:primary, [term!(:literal_str)], nil)
      elsif match(:lbrace)
        Node.new(:primary, [exp()], nil)
        consume(:identifier, "Expect ) afrer (")
      else
        Node.new(:primary, [var()], nil)
      end
    end

そう、RBSならね。

lib/klua.rb:322:8: [error] Cannot allow method body have type `(::Klua::Node | ::Klua::Token)` because declared as type `::Klua::Node`
│   (::Klua::Node | ::Klua::Token) <: ::Klua::Node
│     ::Klua::Token <: ::Klua::Node
│       ::Object <: ::Klua::Node
│         ::BasicObject <: ::Klua::Node
│
│ Diagnostic ID: Ruby::MethodBodyTypeMismatch
│
└     def primary
          ~~~~~~~

Detected 1 problem from 1 file

ここでした。

    def primary
      if match(:nil)
        # ...
      elsif match(:lbrace)
        r = Node.new(:primary, [exp()], nil)
        consume(:identifier, "Expect ) afrer (")
        r # <- consumeはTokenを返す。Nodeを持ってこないとダメ
      else
        Node.new(:primary, [var()], nil)
      end
    end

いったん、 stat -> varstat の分岐分を実装したのでパースしてみます。

tokens = Klua::Scanner.new.scan "local a = 1 + 1;"
=> 
[<Token type: local value: "local">,
...
p tokens
=> 
[<Token type: local value: "local">,
 <Token type: identifier value: "a">,
 <Token type: assign value: "=">,
 <Token type: number value: "1">,
 <Token type: + value: "+">,
 <Token type: number value: "1">,
 <Token type: semicolon value: ";">,
 <Token type: eof value: "">]
ret = Klua::Parser.new.parse tokens
=> <Node type: root root: <Node type: block nodes: [<Node type: varstat nodes: [<Node type: term nodes: [] term: ...
p ret
<Node type: root root: <Node type: block nodes: [<Node type: varstat nodes: [<Node type: term nodes: [] term: <Token type: identifier value: "a">>, <Node type: exp nodes: [<Node type: binary nodes: [<Node type: unary nodes: [<Node type: primary nodes: [<Node type: term nodes: [] term: <Token type:  value: "">>] term: nil>] term: nil>, <Node type: term nodes: [] term: <Token type: + value: "+">>, <Node type: unary nodes: [<Node type: primary nodes: [<Node type: term nodes: [] term: <Token type:  value: "">>] term: nil>] term: nil>] term: nil>] term: nil>] term: nil>] term: nil>>
=> <Node type: root root: <Node type: block nodes: [<Node type: varstat nodes: [<Node type: term nodes: [] term: <Token type: identifier value: "a">>, <Node type: exp nodes: [<Node type: binary nodes: [<Node type: unary nodes: [<Node type: primary nodes: [<Node type: term nodes: [] term: <Token type:  value: "">>] term: nil>] term: nil>, <Node type: term nodes: [] term: <Token type: + value: "+">>, <Node type: unary nodes: [<Node type: primary nodes: [<Node type: term nodes: [] term: <Token type:  value: "">>] term: nil>] term: nil>] term: nil>] term: nil>] term: nil>] term: nil>>

パース成功しました。これで他のstatの分岐も頑張って実装すれば、パーサも完成です。

ところでこの結果、意図されたパース結果になってるかわかりにくいっすよね...。せめて、インデントぐらいあればね、となります。

Visitorを実装してASTにインデントをつける

一通り他の分岐を実装したことにして、最後にVisitor patternを型付Rubyでやってみます。

ここまで、微妙なエラーを修正し一通り動くようにしたはずのバージョンがこちらです:

github.com

ということでまずVisitorパターンを実装します。突然diff記法になります。

diff --git a/lib/klua.rb b/lib/klua.rb
index 4d8d63e..de26a16 100644
--- a/lib/klua.rb
+++ b/lib/klua.rb
@@ -26,6 +26,10 @@ module Klua
     def inspect
       "<Node type: #{@type} nodes: #{@nodes.inspect} term: #{@term.inspect}>"
     end
+
+    def accept(visirtor)
+      visirtor.visit(self)
+    end
   end
 
   class Root < Node
@@ -484,4 +488,17 @@ module Klua
       @block_level <= 0
     end
   end
+
+  class ASTVisitor
+    def initialize
+      @indent = 0
+    end
+
+    def print_all(node)
+      node.accept(self)
+    end
+
+    def visit(node)
+      # case node.type
+      # when ...
+      # end
+      nil
+    end
+  end
 end

インタフェースが型引数を取れない? ので(間違い: 追記を見よ)ちょっと型付けの情報量が物足りない...。

diff --git a/sig/klua.rbs b/sig/klua.rbs
index 995b65a..45ee5b0 100644
--- a/sig/klua.rbs
+++ b/sig/klua.rbs
@@ -27,6 +27,7 @@ module Klua
 
   class Node
     def initialize: (node_type type_, Array[Node?] nodes, Token? term) -> untyped
+    def accept: (_Visitor visitor) -> untyped
     attr_reader type: node_type
     attr_reader nodes: Array[Node?]
     attr_reader term: Token?
@@ -108,4 +109,13 @@ module Klua
     def previous: -> Token
     def toplevel?: -> bool
   end
+
+  interface _Visitor
+    def visit: (Node node) -> untyped
+  end
+
+  class ASTVisitor
+    include _Visitor
+    @indent: Integer
+    def initialize: -> untyped
+    def print_all: (Node node) -> untyped
+  end
 end

これでsteep checkを通します。

もうちょっとVisitorっぽくしたくなりました。じゃあRootとNodeでメソッドを分けるか、と。

   class ASTVisitor
...
+    def visit_root: (Root root) -> untyped
class Root < Node
@@ -41,6 +45,10 @@ module Klua
     def inspect
       "<Node type: #{@type} root: #{@root.inspect}>"
     end
+
+    def accept(visirtor)
+      visirtor.visit_root(self)
+    end
   end

class ASTVisitor
...
+    def visit_root(root)
+    end

あとは頑張って再帰する。中身を実装しました。

class ASTVisitor
...
+    def visit_root(root)
+      puts "* Root: @type=#{root.type}"
+      @indent += 2
+      visit(root.root)
+      @indent = 0
+    end
+
+    def visit(node)
+      print " " * @indent
+      puts "┗ Node: @type=#{node.type}"
+      @indent += 2
+      if !node.nodes.empty?
+        node.nodes.each do |node_|
+          if node_
+            visit(node_)
+          end
+        end
+      else
+        print " " * @indent
+        puts "[Token: #{node.term&.value} (#{node.term&.type.inspect}) ]"
+      end
+      @indent -= 2
+    end
+  end
 end

ここでも、途中でこう言う箇所があると:

puts "[Token: #{node.term.value} (#{node.term.type.inspect}) ]"

ちゃんと怒られるので便利です。 node.termnilになりうる(分岐を考えると、ならないはずではあるんだけど)ので。

$ bundle exec steep check
# Type checking files:

.............................................................F

lib/klua.rb:524:34: [error] Type `(::Klua::Token | nil)` does not have method `value`
│ Diagnostic ID: Ruby::NoMethod
│
└         puts "[Token: #{node.term.value} (#{node.term.type.inspect}) ]"
                                    ~~~~~

lib/klua.rb:524:54: [error] Type `(::Klua::Token | nil)` does not have method `type`
│ Diagnostic ID: Ruby::NoMethod
│
└         puts "[Token: #{node.term.value} (#{node.term.type.inspect}) ]"
                                                        ~~~~

Detected 2 problems from 1 file

一通り実装したので最後の動作確認。

$ bundle exec irb -rklua
irb(main):001:0" CODE = <<CODE
irb(main):002:0" if a < 1 
irb(main):003:0" then
irb(main):004:0"   a = 1 + 1;
irb(main):005:0"   print(a);
irb(main):006:0"   print("bcdef");
irb(main):007:0" end;
irb(main):008:0> CODE
irb(main):009:0> root = Klua::Parser.parse_through(CODE)[1]
=> <Node type: root root: <Node type: block nodes: [...]>>
irb(main):010:0> a = Klua::ASTVisitor.new
=> #<Klua::ASTVisitor:0x00007f9c81094578 @indent=0>
irb(main):011:0> a.print_all root
* Root: @type=root
  ┗ Node: @type=block
    ┗ Node: @type=ifstat
      ┗ Node: @type=exp
        ┗ Node: @type=binary
          ┗ Node: @type=unary
            ┗ Node: @type=primary
              ┗ Node: @type=term
                [Token: a (:identifier) ]
          ┗ Node: @type=term
            [Token: < (:<) ]
          ┗ Node: @type=unary
            ┗ Node: @type=primary
              ┗ Node: @type=term
                [Token: 1 (:number) ]
      ┗ Node: @type=block
        ┗ Node: @type=assignstat
          ┗ Node: @type=term
            [Token: a (:identifier) ]
          ┗ Node: @type=exp
            ┗ Node: @type=binary
              ┗ Node: @type=unary
                ┗ Node: @type=primary
                  ┗ Node: @type=term
                    [Token: 1 (:number) ]
              ┗ Node: @type=term
                [Token: + (:+) ]
              ┗ Node: @type=unary
                ┗ Node: @type=primary
                  ┗ Node: @type=term
                    [Token: 1 (:number) ]
        ┗ Node: @type=funcallstat
          ┗ Node: @type=functioncall
            ┗ Node: @type=primary
              ┗ Node: @type=term
                [Token: print (:identifier) ]
            ┗ Node: @type=args
              ┗ Node: @type=exp
                ┗ Node: @type=binary
                  ┗ Node: @type=unary
                    ┗ Node: @type=primary
                      ┗ Node: @type=term
                        [Token: a (:identifier) ]
        ┗ Node: @type=funcallstat
          ┗ Node: @type=functioncall
            ┗ Node: @type=primary
              ┗ Node: @type=term
                [Token: print (:identifier) ]
            ┗ Node: @type=args
              ┗ Node: @type=exp
                ┗ Node: @type=binary
                  ┗ Node: @type=unary
                    ┗ Node: @type=primary
                      ┗ Node: @type=term
                        [Token: bcdef (:literal_str) ]

これでも目検は大変ですが少しマシになりました。 パースはうまくいってるようです *1。あとは同じようなVisitorを書いて、インタプリットするなりコンパイルすれば言語の出来上がりです。

そうそう、型付け以外にも、 テストを書く ことを忘れないようにしましょう。


と言うことでRuby + BRS で言語のパーサと、簡単なVisitorまでを書いてみました。

ここまでのコード全体を置いておきます。

github.com

最後にと言うか、後編として、RBSにより型情報が付いたRubyのコードを書いてみての感想などをまとめようと思います。また後日。

早速の追記 @ 2021/11/02 01:00

即で pocke さんにご教示いただき ました。インタフェースが型引数を取ることはできるようです。Ruby 3.0.2 + rbs 1.6.2 では可能でした。

github.com

なのでこのVisitorは、こう言う定義にすれば、そのままインタプリタにも使いまわせるようになると思います。これで steep check も通過します。

diff --git a/lib/klua.rb b/lib/klua.rb
index 115adea..4700b9c 100644
--- a/lib/klua.rb
+++ b/lib/klua.rb
@@ -507,6 +507,7 @@ module Klua
       @indent += 2
       visit(root.root)
       @indent = 0
+      nil
     end
 
     def visit(node)
@@ -524,6 +525,7 @@ module Klua
         puts "[Token: #{node.term&.value} (#{node.term&.type.inspect}) ]"
       end
       @indent -= 2
+      nil
     end
   end
 end

diff --git a/sig/klua.rbs b/sig/klua.rbs
index f22b81f..32316d6 100644
--- a/sig/klua.rbs
+++ b/sig/klua.rbs
@@ -27,7 +27,7 @@ module Klua
 
   class Node
     def initialize: (node_type type_, Array[Node?] nodes, Token? term) -> untyped
-    def accept: (_Visitor visitor) -> untyped
+    def accept: (_Visitor[nil] visitor) -> nil
     attr_reader type: node_type
     attr_reader nodes: Array[Node?]
     attr_reader term: Token?
@@ -110,15 +110,15 @@ module Klua
     def toplevel?: -> bool
   end
 
-  interface _Visitor
-    def visit: (Node node) -> untyped
-    def visit_root: (Root root) -> untyped
+  interface _Visitor[T]
+    def visit: (Node node) -> T
+    def visit_root: (Root root) -> T
   end
 
   class ASTVisitor
-    include _Visitor
+    include _Visitor[nil]
     @indent: Integer
     def initialize: -> untyped
-    def print_all: (Node node) -> untyped
+    def print_all: (Node node) -> nil
   end
 end

untypedが減って嬉しい!


ということで感想などをまとめ、後編を書きました。

udzura.hatenablog.jp

*1:正確なタイムラインとしては、ここまで実装してやっとパーサの間違いをいくつか発見して直した。型は万能じゃないのじゃ〜