素朴な再帰下降パーサをRubyで書いてみる

再帰下降パーサとは？

Wikipediaを引用すると、

再帰下降構文解析 - Wikipedia

再帰下降構文解析（さいきかこうこうぶんかいせき、英語: Recursive Descent Parsing）は、相互再帰型の手続き（あるいは再帰的でない同等の手続き）で構成されるLL法のトップダウン構文解析であり、各プロシージャが文法の各生成規則を実装することが多い。従って、生成されるプログラムの構造はほぼ正確にその文法を反映したものとなる。そのような実装の構文解析器を再帰下降パーサ（Recursive Descent Parser）と呼ぶ。

なるほど分からん。

Rubyにまつわる再帰下降パーサ実装をいくつか眺めてみる

Prism

Ruby のデフォルトになった手書きパーサ。

github.com

lexer の実装も parser の実装も全部 prism.c の中に書かれていそう。

• prism/src/prism.c at 7ae3f03840359e611099bd505be84a3e4337f6ea · ruby/prism · GitHub

Ruby の文法がシンプルではない方の部類だと認識しており、いきなりハードルが高すぎたようだ。次。

Herb

Kaigi on Rails 2025 で（少なくとも自分の中で）注目だったやつ。

github.com

erb/html をパースして AST を作成しているところが再帰下降パーサの実装になっている。

• herb/src/lexer.c at c2611f595e729eee1322e6bfd3022417b0663e6a · marcoroth/herb · GitHub
• herb/src/parser.c at c2611f595e729eee1322e6bfd3022417b0663e6a · marcoroth/herb · GitHub

パース処理は herb_parser_parse 関数からスタートして、parser_parse_document → parser_parse_in_data_state → parser_parse_html_element → parser_parse_html_regular_element → parser_parse_in_data_state ... みたいな感じで HTML 要素の階層で再帰呼び出しで処理されていそうな雰囲気を掴んだ。

RBS

Ruby の型を記述するやつ。RBS も内部で AST を作成しており再帰下降パーサな実装になっている。

github.com

lexer の実装は re2c というツールを使って正規表現から生成されているみたい。

• rbs/src/lexer.re at 4482ed2c4a3faca78b3c332480b956e99ab9788c · ruby/rbs · GitHub
• rbs/src/parser.c at 4482ed2c4a3faca78b3c332480b956e99ab9788c · ruby/rbs · GitHub

rbs_parse_signature 関数がパースのエントリーポイントのように見える。rbs_parse_signature → parse_decl → parse_class_decl → parse_class_decl0 → parse_module_members → parse_member_def あたりを辿ると処理の雰囲気を掴める。

TinyGQL

tenderlove 氏による experimental な GraphQL パーサらしい。「recursive descent parser ruby」みたいなキーワードで GitHub 検索してたら見つけた。これまでのものが全てC言語実装だったので Ruby 実装のものも見ておきたいなということで引用。

github.com

• tinygql/lib/tinygql/lexer.rb at 72fc14e74160ed72c8b224b7c8072a29eccd03dc · tenderlove/tinygql · GitHub
• tinygql/lib/tinygql/parser.rb at 72fc14e74160ed72c8b224b7c8072a29eccd03dc · tenderlove/tinygql · GitHub

case で分岐しながら各生成規則に対したメソッド呼び出しを再帰しているようだ。大体分かった。

ruby/json

Ruby 組み込みの JSON パーサ。JSON パーサを書きたくなったのでついでに見ておく。

github.com

• json/ext/json/ext/parser/parser.c at 9e6067bb55d60d893fb95dafa777af880459c7c2 · ruby/json · GitHub

json_parse_any 関数が全てを司っているように見える。なるほど。

頻出語彙の整理

パーサ実装でよく見かける語彙たち。ニュアンス分からないやつは LLM にも聞いてみた。

• lexer ... 字句解析器、文字列をトークンに分解する
• parser ... 構文解析器、トークンから AST （構文木）を構築する
• token ... トークン、意味を持つ最小単位、キーワードとか識別子とか数値・記号など
• AST ... Abstract Syntax Tree、構文木
• node ... AST の構成要素、メタファーが「木」だからね
• advance ... 現在の解析位置を先に進める関数に使われがち、lexerだったら文字位置、parserだったらトークン位置が進むイメージ
• peek ... 解析位置を先に進めずに先の文字やトークンをチェックする時に使われがち、英単語の語源としては「ちらっとのぞく」

素朴な再帰下降パーサをRubyで書いてみる

ようやく本題。雰囲気が掴めたところで実際に書いてみる。

文法が巨大＆複雑ではなく、かつ部分的に対応してもそれなりに動作確認可能なものということで JSON をパースする何かを目指す。あと JSON であれば AST を作る必要もなく Ruby で表現される何かしらの値 (e.g. true, false, nil, String, Integer|Flaot, {}, []) を生成すれば良い。

JSON の文法は以下ページに記載の通り。

www.json.org

バッカスナウア記法のようでバッカスナウア記法ではない、でも少しバッカスナウア記法なもので表現したのが以下の通り。

json ::= element
value ::= object | array | string | number | "true" | "false" | "null"
object ::= '{' ws '}' | '{' members '}'
members ::= member | member ',' members
member ::= ws string ws ':' element
array ::= '[' ws ']' | '[' elements ']'
elements ::= element | element ',' elements
element ::= ws value ws
string ::= '"' characters '"'
characters ::= "" | character characters
character ::= '0020' . '10FFFF' - '"' - '\' | '\' escape
escape ::= '"' | '\' | '/' | 'b' | 'f' | 'n' | 'r' | 't' | 'u' hex hex hex hex
hex ::= digit | 'A' . 'F' | 'a' . 'f'
number ::= integer | fraction | exponent
integer ::= digit | onenine digits | '-' digit | '-' onenine digits
digits ::= digit | digit digits
digit ::= '0' | onenine
onenine ::= '1' . '9'
fraction ::= "" | '.' digits
exponent "" | 'E' sign digits | 'e' sign digits
sign ::= "" | '+' | '-'
ws ::= "" | '0020' ws | '000A' ws | '000D' ws | '0009' ws

さて、ここから true と false だけパースできる文法を定義するならばこうなる。 ws も潔く対応しない。

json ::= element
value ::= "true" | "false"
element ::= value

初期実装

最初の実装はこう。

require "strscan"

class Lexer
  def initialize(string)
    @scan = StringScanner.new string
    @token = nil
  end

  attr_reader :token

  def advance
    @token = case
             when @scan.scan(/true/)
               :TRUE
             when @scan.scan(/false/)
               :FALSE
             end
  end
end

class Parser
  def initialize(string)
    @lexer = Lexer.new string
  end

  def parse_json
    @lexer.advance
    parse_element
  end

  def parse_element
    parse_value
  end

  def parse_value
    v = case @lexer.token
        when :TRUE
          true
        when :FALSE
          false
        end
    @lexer.advance
    v
  end
end

puts Parser.new(%|true|).parse_json.inspect
puts Parser.new(%|false|).parse_json.inspect

動かしてみる。

$ ruby parser.rb 
true
false

要素数が 0 or 1 な Array に対応する

つまり繰り返しがまだ要らない。文法はこんな感じか。

json ::= element
value ::= array | "true" | "false"
array ::= '[' ']' | '[' elements ']'
elements ::= element
element ::= value

実装差分。

diff --git a/parser.rb b/parser.rb
index f282c4f..0283cea 100644
--- a/parser.rb
+++ b/parser.rb
@@ -14,6 +14,10 @@ class Lexer
                :TRUE
              when @scan.scan(/false/)
                :FALSE
+             when @scan.scan(/\[/)
+               :LBRACKET
+             when @scan.scan(/\]/)
+               :RBRACKET
              end
   end
 end
@@ -38,11 +42,31 @@ class Parser
           true
         when :FALSE
           false
+        when :LBRACKET
+          parse_array
         end
     @lexer.advance
     v
   end
+
+  def parse_array
+    array = []
+    @lexer.advance # consume LBRACKET
+    case @lexer.token
+    when :RBRACKET
+      array
+    else
+      array.concat parse_elements
+    end
+  end
+
+  def parse_elements
+    [parse_element]
+  end
 end
 
 puts Parser.new(%|true|).parse_json.inspect
 puts Parser.new(%|false|).parse_json.inspect
+puts Parser.new(%|[]|).parse_json.inspect
+puts Parser.new(%|[true]|).parse_json.inspect
+puts Parser.new(%|[[[]]]|).parse_json.inspect

実行。なんとネストした Array がパースできている。これは再帰している。

$ ruby parser.rb 
true
false
[]
[true]
[[[]]]

要素数が複数の Array に対応する

繰り返し処理が必要になってくる。

json ::= element
value ::= array | "true" | "false"
array ::= '[' ']' | '[' elements ']'
elements ::= element | element ',' elements
element ::= value

差分は以下の通り。

diff --git a/parser3.rb b/parser3.rb
index 0283cea..0542c8b 100644
--- a/parser3.rb
+++ b/parser3.rb
@@ -18,6 +18,8 @@ class Lexer
                :LBRACKET
              when @scan.scan(/\]/)
                :RBRACKET
+             when @scan.scan(/,/)
+               :COMMA
              end
   end
 end
@@ -61,7 +63,13 @@ class Parser
   end
 
   def parse_elements
-    [parse_element]
+    elements = []
+    elements << parse_element
+    while @lexer.token == :COMMA
+      @lexer.advance # consume COMMA
+      elements << parse_element
+    end
+    elements
   end
 end
 
@@ -70,3 +78,5 @@ puts Parser.new(%|false|).parse_json.inspect
 puts Parser.new(%|[]|).parse_json.inspect
 puts Parser.new(%|[true]|).parse_json.inspect
 puts Parser.new(%|[[[]]]|).parse_json.inspect
+puts Parser.new(%|[true,false]|).parse_json.inspect
+puts Parser.new(%|[true,false,[[],[true],[[true,false]]]]|).parse_json.inspect

$ ruby parser.rb 
true
false
[]
[true]
[[[]]]
[true, false]
[true, false, [[], [true], [[true, false]]]]

最終ソースコード

require "strscan"

class Lexer
  def initialize(string)
    @scan = StringScanner.new string
    @token = nil
  end

  attr_reader :token

  def advance
    @token = case
             when @scan.scan(/true/)
               :TRUE
             when @scan.scan(/false/)
               :FALSE
             when @scan.scan(/\[/)
               :LBRACKET
             when @scan.scan(/\]/)
               :RBRACKET
             when @scan.scan(/,/)
               :COMMA
             end
  end
end

class Parser
  def initialize(string)
    @lexer = Lexer.new string
  end

  def parse_json
    @lexer.advance
    parse_element
  end

  def parse_element
    parse_value
  end

  def parse_value
    v = case @lexer.token
        when :TRUE
          true
        when :FALSE
          false
        when :LBRACKET
          parse_array
        end
    @lexer.advance
    v
  end

  def parse_array
    array = []
    @lexer.advance # consume LBRACKET
    case @lexer.token
    when :RBRACKET
      array
    else
      array.concat parse_elements
    end
  end

  def parse_elements
    elements = []
    elements << parse_element
    while @lexer.token == :COMMA
      @lexer.advance # consume COMMA
      elements << parse_element
    end
    elements
  end
end

puts Parser.new(%|true|).parse_json.inspect
puts Parser.new(%|false|).parse_json.inspect
puts Parser.new(%|[]|).parse_json.inspect
puts Parser.new(%|[true]|).parse_json.inspect
puts Parser.new(%|[[[]]]|).parse_json.inspect
puts Parser.new(%|[true,false]|).parse_json.inspect
puts Parser.new(%|[true,false,[[],[true],[[true,false]]]]|).parse_json.inspect

これは JSON パーサと言えるのか？

やはり object がパースできないと JSON パーサに見えないが、一応この段階でも JSON のサブセットをパースできる何かにはなっているはず。

素朴すぎないか？

Yes.

ホワイトスペースの対応とか、string や number といったリテラル値の抽出とか、終了判定とか、文法エラーの検出など実装すべきものはたくさんあるけど、全部あえて無視した。あと処理の効率化（ @scan.scan あたりの文字列処理の効率化）も意識的にやっていない。あくまで「再起下降パーサの雰囲気を掴む」ということを第一目的に実装してみた。

再起下降パーサの実装として本当に合ってる？

ぶっちゃけ分からない。分からないので誰か有識者の方がいたら教えてほしい。

まとめ

素朴な再起下降パーサを Ruby で書いてみた。合ってるかどうかは分からない。

宣伝コーナー

というわけでこの続き的なことは 10/23(木) に開催する Kashiwa.rb #16 ワイガヤグループワーク会 で取り組むつもりです。

自分は「Rubyで素朴な再帰下降パーサーを実装して理解する」というテーマで取り組むつもり https://t.co/j5SQrUJ0OP

— Koji NAKAMURA (@kozy4324) 2025年10月17日

パーサに限らず、Rubyに関すること（Rubyに関さないことも）で興味あればぜひ勉強会に足を運んでみてください。それでは。