Ruby Parser開発日誌 (12) - LR parser generatorの提供する文法の健全性

LR parser generatorを難しいと感じるのはおそらくShift/Reduce ConflictやReduce/Reduce Conflictに遭遇したときでしょう。 嫌われがちなこれらのConflictが、実はわかりにくい文法を生み出すことを防いでいるというのが今日のお話です。

Bugs にあがった2つのチケット

https://bugs.ruby-lang.org/1 で最近文法に関する議論を2つ行ないました。その両者においてConflictが議論において重要な示唆を与えたので紹介します。

Bug #17925 (caseによるパターンマッチを1行で書いた時)

bugs.ruby-lang.org

Issueの内容は簡潔でcase ... whenの場合はセミコロンをいれることにより1行で書くことができるが、case ... inの場合はできないというものです。

# Syntax OK
case expression when 42; end

# syntax error
case expression in 42; end

これはcaseのあとにexpression in 42という1行パターンマッチ(expr)を書くことができるためです。つまりcase (expression in 42); endとパースされるので、その後にinないしwhenを書いていないものはsyntax errorになります。

なので例えば次のような書き方は通ります。

# Syntax OK
case expression in 42; in true; :t end

ちなみにこのexprというのは他には例えばifの後や、後置whileの後ろなどにも書ける要素と同じです。

いまのparse.yを変更してcase (expression) in 42; endと解釈するようにすることも可能です2。 expression in 42はtrueもしくはfalseの値しか返さないのでcaseに渡すというユースケースはあまり多くないとも考えられます。なのでこの部分だけ特別に解釈を変えることも選択肢のひとつだと思います。

ではこれを変更したときの影響にはどのようなものがあるのでしょうか。すでにリリースしている機能なので変更時の影響範囲を把握することは大切です。

当然case ... inは影響を受けます。例えば

expression = 42

case expression in 42
in true
  p :t
in false
  p :f
end
#=> :t

expression = 421

case expression in 42
in true
  p :t
in false
  p :f
end
#=> :f

というコードは以下のように挙動が変わります。

expression = 42

case expression in 42
in true
  p :t
in false
  p :f
end
#=> nothing printed, because body for 42 is empty

expression = 421

case expression in 42
in true
  p :t
in false
  p :f
end
#=> 421 (NoMatchingPatternError)
# because nothing matches

それ以外にも影響を受ける箇所があります。そうですcase ... whenですね。

case expression in 42
when true
  p :t
when false
  p :f
end

というコードはsyntax errorを起こすようになります。

case expression in 42
when true
  p :t
when false
  p :f
end

# test2.rb:2: syntax error, unexpected `when' (SyntaxError)
# when true
# ^~~~

case expression inまで読んだ時点でcase ... inの構文だと解釈するので、その後にwhenがくるとエラーになります。おなじcaseから始まる構文なので片方の変更がもう一方にも影響します。

なおこの影響はShift/Reduce Conflictとして観測できます。case ... inだけをexpr_value0という1行パターンマッチを除いたルールで置き換えると以下のようなConflictがレポートされます(見やすいように一部編集)3。

State 394

    shift/reduce conflict on token "`in'":
       60 expr0: arg •
       71 expr: arg • "`in'" @7 @8 p_top_expr_body
      First example: $@1 k_case arg • "`in'" @7 @8 p_top_expr_body opt_terms @19 case_body k_end "=>" @5 @6 p_top_expr_body opt_terms
      Shift derivation

       ↳ 358: k_case expr_value                                     opt_terms @19 case_body k_end
                     ↳ 78: expr
                           ↳ 71: arg • "`in'" @7 @8 p_top_expr_body

      Second example: $@1 k_case arg • opt_terms "`in'" @38 @39 p_top_expr then $@40 compstmt p_cases k_end '[' opt_call_args rbracket "operator-assignment" lex_ctxt command_rhs opt_terms "end-of-input"
      Reduce derivation

       ↳ 361: k_case expr_value0       opt_terms p_case_body                                                 k_end
                     ↳ 77: expr0                 ↳ 500: "`in'" @38 @39 p_top_expr then $@40 compstmt p_cases
                           ↳ 60: arg •

Bug #18080 (メソッド呼び出しに対する1行パターンマッチ)

bugs.ruby-lang.org

こちらもIssueの内容は簡潔でブロック付きのメソッド呼び出しを1行パターンマッチの左に置くことができるケースと、できないケースがあるというものです。具体的には引数がないケースやカッコで引数を囲んでいる場合は通りますが、カッコで囲まないケースではsyntax errorになってしまいます。

p(1) do
end => a
# OK

p 1 do
end => a
# syntax error

これもparse.yを変更して通すことは可能です4。

こちらにも実は一つ問題があって、以下の組み合わせのときは思った挙動になりません。

  • ブロックがない
  • 引数をカッコで囲まない
  • pattern matchの記号が =>
[].append => a
[].append in a
[].append(1) => a
[].append(1) in a
# このケースだけはpattern matchingにならない
[].append 1 => a
[].append 1 in a

#appendを{1 => a}というhashを引数として呼び出すという、すでにある記法になってしまうからです。

このような一貫性のなさもShift/Reduce Conflictとして観測できます。今回のpatchではConflictをさけるために=>のときはblock_callを、inのときはcommand_callを許可するように変更しましたが、=>のときもcommand_callを許可すると以下のようなConflictがレポートされます(見やすいように一部編集)5。

State 223

    shift/reduce conflict on token "=>":
      308 args: arg_value •
      759 assoc: arg_value • "=>" arg_value
      First example: $@1 k_return arg_value • "=>" arg_value opt_block_arg "=>" @7 @8 p_top_expr_body opt_terms "end-of-input"
      Shift derivation

       ↳ 65: command                                                                      "=>" @7 @8 p_top_expr_body
             ↳ 97: k_return call_args
                            ↳ 299: assocs                                   opt_block_arg
                                   ↳ 757: assoc
                                          ↳ 759: arg_value • "=>" arg_value
      Second example: $@1 k_return arg_value • opt_block_arg "=>" @7 @8 p_top_expr_body opt_terms "end-of-input"
      Reduce derivation

       ↳ 65: command_call                                                 "=>" @7 @8 p_top_expr_body
             ↳ 82: command
                   ↳ 97: k_return call_args
                                  ↳ 298: args               opt_block_arg
                                         ↳ 308: arg_value •

手書きパーサーで検出できるのか

手書きパーサーの場合はどうなるでしょうか。手書きパーサーはこれらの点を発見・指摘してくれません。ということは実装する人が把握する必要がありますが、毎回見落としなく行うのはかなり困難だと思います。困難な理由はいくつかあります。

1. あらゆる組み合わせを考慮する必要がある

文法の要素というのは1つからなるのではありません。例えば1も1 + 2も1..2も見た目は異なりますがRubyではargという同じグループに属しています。またp 1, 2 do endとp 1, 2のように一部を省略したものが同じグループのこともあります(これらはともにcommand_call)。文法の一貫性を考えるうえではp 1, 2 do endという個別具体的なコードだけを議論、検証するのではなくarg全体、expr全体など、あるグループに注目して議論をする必要があります。さらにargはexpr、exprはstmtのような置き換えもあるのでargを議論するときはそれがexprやstmtとして扱われる状況も考慮する必要があります。

2. コンフリクトはつねにReduceとともにある

Shift/Reduce ConflictもReduce/Reduce ConflictもReduceが関係します6。Reduceというのはそこまでをひとまとめにして、別の生成規則のなかに入れるという操作です。これは今注目しているルールが他のルールのどこで使われているかに関係するので、大局的な視点が必要になります。

1つめのBug #17925の例でいうとexpression in 42というexprはcase ... inだけでなくcase ... whenのなかにも書くことができます。そのためcase ... whenのほうのルールも調整しないとcase expression in 42 ...をcase (expression) in 42 ...とcase (expression in 42) ...のどちらに解釈していいか定まらなくなってしまうのでした。

3. 文法に関する議論や実装は局所的である

これらのチケットでの議論もそうですが、文法の議論は対象となる最小のものを中心に行われることが多々あります。議論の対象が絞られるという点で最小ケースについて議論すること自体はよいことだと思います。しかしここまでみてきたように、文法の曖昧性というのはある構文をほかの構文と組み合わせた時に発生します。

またパーサーの実装も局所的な実装の組み合わせからなります。LR parser generatorであれば個別ルールの組み合わせで全体が実装されていますし、手書きパーサー(再帰下降パーサー)の場合であってもparse_stmt、parse_exprなどの関数の組み合わせでパーサー全体を構成することになります。

[].append 1 => aの例でいうと、パターンマッチをパースする部分と引数をパースする部分の間で衝突が起きています。しかし実装をするときは以下のようにそれぞれを局所化して実装します。

// pattern matching
expr: arg tASSOC p_top_expr_body ;

// 引数の一部
assoc: arg_value tASSOC arg_value ;

言い方をかえればLR parser generatorの報告するConflictというのは、実装を局所化した時に全体として不都合が起きてないかをチェックしてくれる機構ともいえます。そしてそのようなチェック機構があるから実装を局所化することができるといえます。

4. Rubyの文法の特徴

以上の点に加えて、Rubyの文法の特徴のうちConflictを起こしやすい特徴が2つあると思っています。

1つは小さな単位に多くのルールがあることです。Rubyの文法構造は大きく4つに分けることができ、大きいものから順に以下のような並びになります。

  • stmt (statement / 文)
  • expr (expression / 式)
  • arg (argument / 引数)
  • primary (primary / 項)

このうちprimaryとargに関するルールはexprやstmtよりも多いです。より小さな要素が多いということはそれだけ組み合わせが多くなります。

もう1つは省略記法があるということです。p 1のようにメソッド呼び出しのカッコは省略可能ですし、def add(i, j) = i + jのようにendを省略した記法もあります。このように自明な終端がない構文はどこまでを読んでいいのか不明確になりやすく、結果としてConflictを起こしやすくなります7。

これらの特徴を考えるに、計算機科学の助けを借りず人力で文法の一貫性を担保していくのは無理があると思います。 新しい文法の追加や文法の変更の影響を把握するために、人間がRubyの文法を全部頭にのせたうえで議論する必要があるという状況はよくないでしょう。今後の構文の変更や追加の際のコストが高くなりますし、そもそも議論に参加できる人が極めて限られてしまいます。

LR parser generatorは完璧なのか

LR parser generatorのレポートしてくるConflictは文法全体の健全性を担保するチェック機構であるという話をしました。ではいまのLR parser generatorのレポートは十分なのでしょうか? 十分ではないのでLR parser generatorを触った人の多くがConflictに抵抗感を持っているのだと思います。最近はBisonもLramaもCounterexamplesを実装したので、どういったケースでConflictが起きているかわからないというのは減ったと思います。次に改善すべきはShift/Reduceのどちらにするか決めた時に簡単にそれを指示できるような機能でしょう。RustのコンパイラやGCC, Clangのようにエラーメッセージをもとにどう修正すればよいか分かるようなparser generatorを目指していきたいです。

まとめ

  • 文法の追加や変更をする際には文法全体の一貫性を考慮する必要がある
  • 文法の変更をする際には他の構文への影響範囲を把握できる仕組みがあると変更の是非を議論しやすい
  • これらは組み合わせの問題と大局的な検証が必要なことから人間が行うのは難しい
  • LR parser generatorのレポートするConflictは文法全体の健全性を担保するチェック機構である

ところで世界で最も成功している手書きパーサーの1つがRoslynだとおもうのですが、C#の構文の追加時などにはどのようにして文法全体の一貫性や曖昧性がないことをチェックしているのでしょうか、ご存知の方がいたら教えてください8。

  1. Rubyのissue tracker↩
  2. https://github.com/yui-knk/ruby/tree/bugs_17925↩
  3. Comparing ruby:master...yui-knk:bugs_17925_2 · ruby/ruby · GitHub↩
  4. https://github.com/yui-knk/ruby/tree/bugs_18080↩
  5. Comparing ruby:master...yui-knk:bugs_18080 · ruby/ruby · GitHub↩
  6. ShiftとShiftであればShiftすればだけなのでShift/Shift Conflictにはならない↩
  7. Lookahead-setによって切れ目を決めることになるが、Lookahead-setはReduceした場合に来うるtokenのlistのことなので文法全体に対する大局的な理解が必要↩
  8. アンダース・ヘルスバーグの力とMicrosoftの資本力でなんとかしているという可能性もなきにしもあらず...↩