katsyoshi/arpaka - GitHub

前回は、Ruby のソースを Parser に渡し、 Class や Module、それに含まれる Method の定義を木構造として返すところまで進めました。 コードの中ではその結果を AST と呼んでいますが、この時点では Ruby の構文全体を 表すことよりも、Parser を使える入口と、必要な定義を返すことを優先しています。

今回は、入力を Ruby のソースコード一式ではなく parse.y だけにして、同じ Parser を 動かすために何が必要なのかを整理します。

What parse.y Doesn’t Include

最初は、parse.y が文法そのものなのだから、これを Lrama に渡せば Parser ができると 考えました。実際、文法を読み込んで解析表を作るところまでは parse.y だけで進められます。

でも、できあがった Parser が Ruby のソースを受け取って結果を返すには、それだけでは足りません。 parse.y が決めているのは、どの token の並びを受け付けるかと、reduce のときにどの Action を実行するかです。Ruby のソースを token に変換する処理や、Action が組み立てる 値の入れ物までは parse.y の中にありません。

Ruby source
    ↓
  Lexer
    ↓
  Parser generated from parse.y
    ↓
  Action / Builder
    ↓
  Parser result

parse.y だけで動かすというのは、周辺の実装をなくすことではありません。呼び出し側が Ruby のソースコード一式を用意しなくてもよくし、文法の入力を parse.y に限定した上で、必要な 周辺部品は Arpaka 側に持つ、という意味になります。

token 名を解決

Ruby の parse.y には、RUBY_TOKEN(tIDENTIFIER) のような記述があります。Ruby の ビルドでは defs/id.def と tool/id2token.rb を使って、これを Parser が扱う token 番号へ展開しています。

parse.y だけを受け取る場合、この展開に必要な Ruby のソースコード一式はありません。そこで Arpaka は RUBY_TOKEN(NAME) を token 名へ置き換えてから Lrama に渡します。token 番号を 呼び出し側に要求するのではなく、文法の中にある名前を使って Parser を生成するためです。

ただし、これは token の名前を解決しているだけです。Lexer が Ruby の文字列を読み、 その token を返す処理は別に必要です。

Combining the Lexer with the Parser

Lrama が生成するのは token 列を読む Parser です。Ruby の parse.y を渡しても、文字列や コメント、正規表現、heredoc、補間などを Ruby の token 列へ変換する Lexer までは生成されません。

そのため、Arpaka では Parser とは別に Lexer を用意します。Lexer はソースを読み、 parse.y が期待する token と値を返します。さらに、do や { のように前後の状態で 意味が変わる token については、Parser や Action と状態を共有する必要があります。

ここを省略して token 列を手で渡すだけなら、Lrama の Parser の動作確認はできます。でも、 それは Ruby の Parser としてソースを読む入口にはなりません。

parse.y の外側にあるもの

parse.y には文法規則と Action が書かれています。ただし、Parser を動かすために必要な ものがすべて入っているわけではありません。

Ruby の parse.y は、次のような外側の仕組みに依存しています。

  • token 名や token 番号の展開
  • Ruby のソースを token に変換する Lexer
  • Action から呼ばれるマクロや補助関数
  • Parser と Lexer が共有する状態
  • Action の値を受け取り、結果の木を組み立てる Builder

Ruby のビルドでは、これらが C の Parser や Lexer、生成スクリプトの中で組み合わされます。 parse.y だけを Lrama に渡しても、文法から解析表を作れるだけで、Ruby のソースを読んで 結果を返すところまではできません。

Action だけでは足りない

文法認識だけなら Action は必須ではありません。しかし Arpaka のように Parser の結果を 木構造として返す場合は、規則を適用したときに値を組み立てる Action が必要です。

それでも、Action の本文だけを Ruby に書き換えれば動くわけではありません。$$ や $1 を Ruby の値へ変換し、Action から呼ばれる処理を Builder として用意し、Parser や Lexer の 状態を共有する仕組みも必要です。

Arpaka の生成処理では、文法規則に対応する Action mapping と、Lexer、Builder、Parser の runtime を一つの standalone frontend にまとめます。

parse.y だけを入力にする

必要な部品が揃ったので、呼び出し側の入力を parse.y だけにできます。

frontend = Arpaka.compile(
  parse_y: "/path/to/parse.y",
  class_name: "RubyParser"
)

tree = frontend.parse(
  "class Example\n  def call\n  end\nend\n",
  filename: "example.rb"
)

ここで parse_y: に渡しているのは文法の入力だけです。token 名の前処理、Action mapping、 Lexer、Builder、runtime は Arpaka が持っているものを使います。つまり、parse.y だけで Parser を動かすために必要なのは、parse.y の内容を増やすことではなく、文法の外側に あった依存を切り出して、生成時に組み合わせることでした。

このモードは、どの Ruby の parse.y でも自動的に互換性が得られるという意味ではありません。 文法の変更に合わせて Action mapping や runtime が変わることもあります。Ruby のソースコード一式 を渡すモードでは、その版の parse.y と周辺ファイルをまとめて確認できますが、parse.y だけ のモードでは、Arpaka が対応している範囲を明示しておく必要があります。

まとめ

parse.y だけで Arpaka の Parser を動かすために必要だったのは、次の部品でした。

  • RUBY_TOKEN を解決して文法を Lrama に渡す前処理
  • Ruby のソースを token 列へ変換する Lexer
  • Action の値を組み立てる Builder と runtime
  • 文法規則と Ruby 側の処理を対応付ける Action mapping
  • それらを standalone frontend としてまとめる生成処理

parse.y は Parser の中心ですが、Parser 全体ではありません。文法だけを入力にできるように するには、文法から外に出ている token、Action、Lexer、値の構築を別々に見つけて、最後に 一つの入口へ戻す必要がありました。

これで parse.y だけから Parser を生成する道具はできました。次は、異なる Ruby の文法を 受け取ったときに、どこまで同じ結果を保証するのかを考えることになります。