Ruby Parser開発日誌 (7) - doについて考える

前回のあらすじ

Ruby Parser開発日誌 (6) - parse.yのMaintainabilityの話 - かねこにっき

Rubyのparserの複雑さを分析し、parserとlexerの密結合を解消に挑戦しました。Practical LR Parser Generationという論文を参考に条件付き生成規則をLramaに実装し、Rubyのparserに適用してみましたが一部でconflictが発生してしまいました。

今回は引き続きdoを中心に密結合を解消できないか考えていきましょう。

問題を整理する

doについて理解を深める

doの何が問題なのかもう一度考えてみましょう。Rubyにおいてdoは複数の箇所で使われます。

# lambdaのdo (keyword_do_LAMBDA)
-> do e1 end

# whileのdo (keyword_do_cond)
while true do e1 end

# 引数の括弧なしでのメソッド呼び出しのdo (keyword_do_block)
cmd a1, a2 do e1 end

# 引数の括弧ありでのメソッド呼び出しのdo (keyword_do)
m(a1, a2) do e1 end

このような文法をサポートするうえで問題になるのがS/R conflictやR/R conflictです。 たとえばwhileの条件の部分にメソッド呼び出しが書かれたとき、

# while (m(a1, a2)) do e1 end と解釈される。つまりdoはwhileにくっつく
while m(a1, a2) do e1 end

もしくは引数の括弧なしでのメソッド呼び出しの引数に、引数の括弧ありでのメソッド呼び出しが書かれたとき、

# cmd a1, (m(a1, a2)) do e1 end と解釈される。つまりdoはcmdのblockになる
cmd a1, m(a1, a2) do e1 end

こういったケースでdoがどこにくっつくのかを決めておく必要があります。 Rubyではこれらを4種類の異なるトークンに分け、優先順位を決めています。優先度の高い方から順位に

keyword_do_LAMBDA > keyword_do_cond > keyword_do_block > keyword_do

となっています。具体的にはlexerのロジックとして実装されています。 各種doの間には優先度があるので、whileの条件式にlambdaを書くことはできますが、一方でwhileの条件式にdoブロックを伴うメソッド呼び出しを書くことはできません。

# OK
while -> do e1 end do e2 end

# NG
while cmd a1, a2 do e1 end do e2 end
-e:1: syntax error, unexpected `do', expecting end-of-input # "do e2 end"のdoでSyntaxError
while cmd a1, a2 do e1 end do e2 end
-e: compile error (SyntaxError)

doに関するその他の特徴として、括弧のなかに入ると外側に関係なく再びdoを書くことが可能になるという特徴があります。

#  NG
cmd a1, m(a1, a2) do e1 end do e2 end

# OK
cmd a1, (m(a1, a2) do e1 end) do e2 end

# OK
cmd a1, [m(a1, a2) do e1 end] do e2 end

# OK
cmd a1, {m(a1, a2) do e1 end => 1} do e2 end

parserの気持ちになって考える

前回、条件付き生成規則を単純に利用しただけではうまくいきませんでした。しかし冷静に考えてみると今のRubyのparseは全ての局面でどう振る舞うべきか(shiftするべきかreduceするべきか)わかっているわけです1。見方を変えればparserをメンテナンスしている人もまたどう振る舞うべきかわかっているわけです。

具体例をいくつかあげると以下のようなケースでそれぞれshfit/reduceを判断できているわけです。

m(a1, a2) do e1 end
          ~~ ここではshiftする

cmd a1, m(a1, a2) do e1 end
                  ~~ ここではreduceする

cmd a1, (m(a1, a2) do e1 end)
                   ~~ ここではshiftする

ということは何かしらの方法で我々の意図をparser generatorに教えてあげることができれば、その通りに振る舞ってくれるparserを作ることができるかもしれません。

これまでの分析でわかっている要件を整理してみましょう。

  1. 同じにみえるdoに対してどのくらい結びついているかという強さのようなものを宣言したい。lambdaのdoは一番強いなど優先度がある。
  2. その強さは常に一定ではなく、外側の構文によって変化する。whileのなかのメソッド呼び出しと、メソッド呼び出しの中のwhileで許可されるかどうかが変わってくる。

Nonterminal attributesを拡張する

じつは私たちはこの2つの要件を満たすことができそうなテクニックにすでに出会っています。 まず一つ目の結びつきの強さのようなものといえばPrecedenceが思い浮かぶことでしょう。Bisonに限らず多くのparser generatorで実装されていると思います2*/+-よりも優先されるということをparserの定義ファイルで宣言することで、本来であればconflictしてしまうようなルールを書くことができます。

%left  '+' '-'
%left  '*' '/' '%'

arg : ...
      | arg '+' arg
      | arg '-' arg
      | arg '*' arg
      | arg '/' arg

parser generatorがstateとその遷移を計算するときに、直前のtokenと次のtokenの優先度を比較することでconflictを解消してくれます3

arg '+' arg '*' arg
            ~~~ '*' は '+'よりも強いのでshiftする

arg '*' arg '+' arg
            ~~~ '+' は '*'よりも弱いのでreduceする

つぎに二つ目の外側の構文によって変化するという点ですが、これは前回紹介したNonterminal attributesが使えそうです。

C++やRustで<...>のなかで比較演算子Greater Thanの>が出てきて欲しくないとか、Golangでif ... {}の条件のexpressionのところで{}が末尾にきて欲しくないという例があげられています。これってまさしく「この条件のときはこのルールを適用しない」という話ではないですか。

Nonterminal attributesはいわゆる状態をルール間で受け渡すことができる仕組みと言えます。

Let's 実装

さっそくLramaに実装したものがこちらになります4

github.com

今回の拡張のポイントを見ていきましょう。アクションなどは一部省略しています。

/*
 * keyword_do:
 *   do_LOWEST  = 0.
 *   do_BLOCK   = 1. keyword_do_block  (CMDARG_P)
 *   do_COND    = 2. keyword_do_cond   (COND_P)
 *   do_LAMBDA  = 3. keyword_do_LAMBDA (lambda_beginning_p)
 *   do_HIGHEST = 4.
 */
%int-attr keyword_do do_LOWEST do_BLOCK do_COND do_LAMBDA do_HIGHEST -- (1)

lambda      : tLAMBDA f_larglist(do_LOWEST) lambda_body(do_LAMBDA)  -- (2)

expr_value_do   : expr_value(do_LOWEST) do(do_COND)

block_call  : command do_block(do_BLOCK)

command_args    :  call_args(do_LOWEST)

primary     | tLPAREN compstmt(do_HIGHEST) ')' -- (3)

program     :  top_compstmt(do_HIGHEST) -- (4)
  1. 特定のtoken(ここではkeyword_do)に対してAttributeを宣言する。今回はkeyword_do以外に3つのtokenが必要だったのでdo_BLOCK, do_COND, do_LAMBDAを優先度の低い順に定義し、他に最も優先度の低いdo_LOWESTと最も高いdo_HIGHESTを定義している。
  2. lambdaの解析、whileなどの条件式の解析、コマンド呼び出しの解析の箇所でそれぞれ優先度を指定する。これらはいずれも右側のdoの方が優先される。例えばlambda_bodyの中にlambdaのdoが宣言されており、その優先度は他のどのdoよりも高いので左側(f_larglist)のdoの優先度を最低にしている。
  3. 括弧のなかでは再びdoの結合の仕方がもとに戻るため、括弧で囲まれた非終端記号では再度優先度を最大にする。
  4. スクリプトの解析をはじめたときの初期値は優先度最大にする。

実際にRubyのparse.yに応用してみる

RubyにLramaをインストールし、parse.yも書き換えたものはこちらです。

github.com

test-allも通っています

Lramaの実装について

parser generator側ではどういう実装になっているのかも気になるところだと思います。 端的にいうとLR parserの状態を細かく分けることでこの機能を実現しています。

そもそもLR parserの状態というのはいまどのルールのどこを解析しているのかを示すものでした5。例えばifに関する1つのルールを細かく分類して状態にしています。

primary: k_if expr_value then compstmt if_tail k_end
• k_if expr_value then compstmt if_tail k_end # ifの直前にいる
k_if • expr_value then compstmt if_tail k_end # ifの直後にいる
k_if expr_value • then compstmt if_tail k_end # thenの直前にいる
...

Attributesの機能を実装するときにはこれらの状態に加えてAttributesの値も含めて状態を作っています。前回の例でいえばDO_ALLOWEDがtrueかfalseか、今回の例でいえばkeyword_doの値がdo_LOWEST (0)からdo_HIGHEST (4)のどれであるかを考慮した状態を管理しています。

片方はshift、もう片方はreduceを期待する2つのスクリプトがあったとします。

# (1) doはメソッド呼び出しのdoなのでshiftしてほしい
m(a1, a2) do e1 end

# (2) doはwhileのdoなので"m(a1, a2)"でreduceしてほしい
while m(a1, a2) do e1 end

いままではどちらも同じ状態 105として管理していました。全く同じ状態でdoが来たときに一方ではshift、一方ではreduceをしてほしいと言えばそれはconflictなので、"do""do for condition"のようにtokenを分けてあげる必要がありました。分けた以上はlexerがどのタイミングでどちらのtokenとして切り出すか知っている必要があり、それがparserとlexerの密結合につながっていたのでした。

$ ruby -v
ruby 3.2.0 (2022-12-25 revision a528908271) [arm64-darwin21]

$ ruby --dump=y -e 'm(a1, a2) do e1 end'
Stack now 0 2 105
Reading a token
...
Next token is token "`do'" (1.10-1.12: )

$ ruby --dump=y -e 'while m(a1, a2) do e1 end'

Stack now 0 2 95 385 105
Reading a token
...
Next token is token "`do' for condition" (1.16-1.18: )

Attributesの機能を使うことでwhileなどの条件式の解析中であるという状態を状態 544という別の状態として管理することで、同じ"do"であっても片方ではshiftをし、もう片方ではreduceをすることができるようになりました。

$ ./miniruby -v
ruby 3.3.0dev (2023-04-08T08:51:29Z lrama-attributes_1 c26bd5ab28) [arm64-darwin21]

$ ./miniruby --dump=y -e 'm(a1, a2) do e1 end'
Stack now 0 2 105
Reading a token
...
Next token is token "`do'" (1.10-1.12: )

$ ./miniruby --dump=y -e 'while m(a1, a2) do e1 end'
Stack now 0 2 95 385 544
...
Next token is token "`do'" (1.16-1.18: )

Lramaの生成するreportも見ておきましょう。一見同じにみえる状態ですが一方はdo_HIGHEST、もう一方はdo_LOWESTになっています。またdo_HIGHESTの場合はrule 343のlookahead setよりも優先度が高くなっているのでshift、逆にdo_LOWESTの場合はrule 343のlookahead setが優先されるのでreduceするようになっています。

State 105  -- 'm(a1, a2) do e1 end'の場合はこっち

  343 primary: method_call •  ["end-of-input", "`rescue'", "`ensure'", "`end'", "`then'", "`elsif'", "`else'", "`when'", "`in'", "`and'", "`or'", "`if' modifier", "`unless' modifier", "`while' modifier", "`until' modifier", "`rescue' modifier", "dummy end", '.', "**", "<=>", "==", "===", "!=", ">=", "<=", "&&", "||", "=~", "!~", "..", "...", "<<", ">>", "&.", "::", "=>", "{ arg", "'}'", tLAMBEG, '?', ':', '>', '<', '|', '^', '&', '+', '-', '*', '/', '%', '}', '[', ',', ')', ']', ';', '\n'] (keyword_do: 4)
  344        | method_call • brace_block (keyword_do: 4)
  381 k_do: • "`do'" (keyword_do: 4)
  473 brace_block: • '{' brace_body '}' (keyword_do: 4)
  474            | • k_do do_body k_end (keyword_do: 4)

    "`do'"  shift, and go to state 329
    '{'     shift, and go to state 330

    $default  reduce using rule 343 (primary)

    k_do         go to state 333
    brace_block  go to state 427

    Conflict between rule 343 and token "`do'" resolved as shift ( < "`do'").

State 544 -- 'while m(a1, a2) do e1 end'の場合はこっち

  343 primary: method_call •  ["end-of-input", "`rescue'", "`ensure'", "`end'", "`then'", "`elsif'", "`else'", "`when'", "`in'", "`do'", "`and'", "`or'", "`if' modifier", "`unless' modifier", "`while' modifier", "`until' modifier", "`rescue' modifier", "dummy end", '.', "**", "<=>", "==", "===", "!=", ">=", "<=", "&&", "||", "=~", "!~", "..", "...", "<<", ">>", "&.", "::", "=>", "{ arg", "'}'", tLAMBEG, '?', ':', '>', '<', '|', '^', '&', '+', '-', '*', '/', '%', '}', '[', ',', ')', ']', ';', '\n'] (keyword_do: 0)
  344        | method_call • brace_block (keyword_do: 0)
  381 k_do: • "`do'" (keyword_do: 0)
  473 brace_block: • '{' brace_body '}' (keyword_do: 0)
  474            | • k_do do_body k_end (keyword_do: 0)

    '{'  shift, and go to state 1032

    $default  reduce using rule 343 (primary)

    k_do         go to state 1035
    brace_block  go to state 1141

    Conflict between rule 343 and token "`do'" resolved as reduce ("`do'" < ).

既存の機能との関係

Bisonに詳しい人の中にはprecedence declarationsRuleへのprecedenceとどう違うのか疑問に思う方もいると思います。

前者は以下のような設定でトークン間に優先度(と結合の方向)を設定する機能です。今回のAttributesの機能はひとつの同じtoken doに対して複数の優先度を設定したいという点が異なります。

...
%left  '+' '-'
%left  '*' '/' '%'
%right tUMINUS_NUM tUMINUS
...

後者は生成規則に優先度を設定できるものですが、これだけでは"whileの条件式のなかでは優先度を下げる"といった細かい指定ができません。指定しようとすると生成規則を分割する必要がありますが、前回議論したようにそれでは煩雑すぎます。

command_rhs  : command_call   %prec tOP_ASGN

まとめ

Nonterminal attributesだけではRubyの文法を整理しきれないことがわかったので、1つのtokenに対して経路に応じて複数の優先度を設定することでconflictを解消する方法を新しく考案しました。この方法を使うことで4つに分かれていたRubydo関連のtokenを1つに統合できることがわかりました。またこの方法は既存のprecedence機能が解決している問題と異なる問題に有効であることを確認しました。

ちなみにこの手法、Practical LR Parser GenerationのNonterminal attributesに対しても新規性があるかもしれないと思っています。論文のなかでNonterminal attributesをprecedenceにも応用できることは触れられていますが、私の理解が正しければそれは既存のBisonなどが提供している機能を別の方法でも実現できるということまでしか言っていないはずです。また既存のBisonのprecedenceアルゴリズムの延長に実装可能ということも今回示すことができたのではないかと思います。

parse.yのMaintainabilityの話はdoだけではないので、次回も引き続き別のMaintainability上の問題を見ていきたいと思います。

最後に宣伝ですが、RubyKaigi 2023ではRuby Parserの未来の話をします。parserに興味をお持ちの方、当日お会いしましょう!

rubykaigi.org


  1. Rubyのparserはconflictが0になるようにチェックが入っています
  2. Bisonの場合はContextual Precedence (Bison 3.8.1)を参照
  3. How Precedence (Bison 3.8.1)が詳しい
  4. Branchだと今後コミットが変わる可能性があるので、Commitでいうと https://github.com/yui-knk/ruby/commit/7f8e1ea91434a2793ea4f26ab709de6942e49f55
  5. 詳しくはRuby Parser開発日誌 (3) - かねこにっきを参照