前編はこちら。
ここまででスキャナまでは実装し、大体動いたようです(型もちゃんとついたようです)ので、続きの実装をします。
閑話: エディタの型支援を受ける
当方はEmacsなので読者の参考にならないかもしれませんが...。
といっても以下を有効にしたぐらい。
どちらも @ybiquitous さんの力なので、神と崇める他ない。
さらに、RBS有効のプロジェクトだけlspをsteepが用意したものに変えるため、プロジェクトのルートに以下のような .dir-locals.el
を用意する。この内容は とんさんのブログ記事 のものを参考にしている。
((ruby-mode . ((lsp-enabled-clients . (steep-ls)))))
これでlspとlsp-uiを有効にすれば、こう言うのが出ます。
うおおlsp-steep動いた、右上にぴょこっと出る奴が動作して嬉しい pic.twitter.com/ZJ4CcaeqvV
— Uchio Kondo🍙 (@udzura) October 28, 2021
「あ、これ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でやってみます。
ここまで、微妙なエラーを修正し一通り動くようにしたはずのバージョンがこちらです:
ということでまず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.term
はnilになりうる(分岐を考えると、ならないはずではあるんだけど)ので。
$ 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までを書いてみました。
ここまでのコード全体を置いておきます。
最後にと言うか、後編として、RBSにより型情報が付いたRubyのコードを書いてみての感想などをまとめようと思います。また後日。
早速の追記 @ 2021/11/02 01:00
即で pocke さんにご教示いただき ました。インタフェースが型引数を取ることはできるようです。Ruby 3.0.2 + rbs 1.6.2 では可能でした。
なのでこの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が減って嬉しい!
ということで感想などをまとめ、後編を書きました。
*1:正確なタイムラインとしては、ここまで実装してやっとパーサの間違いをいくつか発見して直した。型は万能じゃないのじゃ〜