前回のあらすじ
Ruby Parser開発日誌 (5) - Lrama LALR (1) parser generatorを実装した - かねこにっき
Error Recoveryを実装するためにLrama LALR (1) parser generatorを実装しました。 Error Recoveryについては目処がたったので今回はparse.yのMaintainabilityをいかにして改善するか考えたいと思います。
parse.yの難しさ
Rubyのparse.yの難しさについては聞く人によって異なる回答が返ってくるところですが、おおよそ以下のようにまとめることができると思います。
- ファイルの行数が多い
- shift/reduce conflictやreduce/reduce conflict時に何が起きているか分かりにくい
- Bisonが原始的な記法しか提供していないので全ての規則を書く必要がある1
- Ripperとコードベースを共有していて見通しが悪い
- parserとlexerが密結合している
RubyのparserのMaintainabilityに関する発表といえばstable branch maintainerのnagachikaさんによるkeynote All bugfixes are incompatibilities - RubyKaigi 2019があります。このkeynoteでは"Fixing SyntaxError caused another SyntaxError"という話で3つの具体例をあげてnagachikaさんが直面した問題を説明しています2。これらの問題は5番目の"parserとlexerが密結合している"という点が原因だと思うので、parserとlexerがなぜ密結合しているのか、密結合がどのような問題を引き起こしているのか、どのようにして解消するかについて見ていきましょう。
parserとlexerがなぜ密結合しているのか
ruby/parse.y at v3_2_0 · ruby/ruby · GitHub をみるとわかるようにRubyのparserに関する構造体には結構な数のメンバが定義されています。なかでも特に以下のメンバはlexerが切り出すtokenの種類をコントロールするのに使われます
enum lex_state_e state: 現在13種類の状態が定義されている。いろいろなtokenの切り出しに影響するint paren_nest:(,[,{の現時点での深さをカウントしている。lambda (-> {})のparseに使われるint lpar_beg: lambda (-> {})のparse開始時点のparen_nestを保持している。これもまたlambda (-> {})のparseに使われるint brace_nest:{の現時点での深さをカウントしている。string interpolation ("#{var}")のparseに使われるstack_type cond_stack;:while ... doなどのdoのparseに使われるstack_type cmdarg_stack:foo 1, 2 doなどのdoのparseに使われる
これらの状態はlexer(parser_yylex関数)で更新されることもありますし、parserのアクション内部で更新されることもあります。参照に関してはlexerからの参照が圧倒的に多いです(見落としがなければparserでは参照してないはず)。というのもLALR parserはtokenの種類によって遷移が変化することはあってもその他の方法で遷移を変更することはできないので、parserの中でlexerの状態をみても役に立たないことがほとんどだからです。
ではなぜこのように複数の状態を管理する必要があるのでしょうか。その役割は大きく3つに分けられると思います。
1. shift/reduce conflictやreduce/reduce conflictを解消するため
これについてはdoが有名でしょう。たとえばwhile m do ... end ...という入力があり、mまでshiftをして次のtokenがdoであるときにshiftをするかreduceをするかを決めなくてはいけません。shiftをするのであればwhile (m do ... end) ...と解釈することになりますし、reduceするのであればwhile (m) do ... end ...と解釈することになります。Rubyではwhileの条件部分にはdoを書けないという仕様(つまりreduceする)なのでwhile (m) do ... end ...となります。
Matzにっき(2004-04-26) に書いてあるように、
という方法が現在のRubyで採用されています。具体的にはm do endのdoをkeyword_doというtokenにし、while 1 do endのdoをkeyword_do_condというtokenにして生成規則を定義します。そしてwhileをshiftしたときにparserのアクションでフラグをたてて(COND_PUSH(1)して)"do"という文字列からtokenを生成するときには、そのフラグをみて生成するtokenを変えます。違うtokenなのでconflictしなくなるということですね。
2. 特定の生成規則をある条件下では無効するため
先ほどの例を"whileのなかの条件式にはdoが書けない"例と捉えることもできます。ほかの例として"lambdaの仮引数には ... がきてはいけない"という例があります。
-> (a) {}や-> (a=1) {}と書くことはできますが、-> (...) {}とは書けません。一方で生成規則を書く時はlambdaの引数(f_larglist)であれ、メソッド定義の引数(f_arglist)であれ基本的には同じルール(f_args)を使いわましたいものです。
ちなみにこの差分の実装のためにlambdaの場合はtDOT3を返すことでsyntax errorにするという方法が採用されています3。
3. tokenの長さを場所によって調整するため
lexerを素直に実装すると貪欲にマッチさせるような実装になるでしょう。例えば|から始まるtokenを切り出す時は以下のtokenに該当するかどうかを上から順に確かめていくことになるでしょう
||=(tOP_ASGN)||(tOROP)|('|')
しかしRubyではこれでうまくいかないケースがあって、例えば m do || end のようにblock parameterを省略したときには||とふたつの|が連続して出現します。かつては素直にtOROPを受け取るようにしていましたが、文法を定義するときには"|と|の間に省略可能なparameterがある"と定義したいものです。なので現在はlexerの方で調整をしています。doのあとはEXPR_BEGのstate bitがたつのでそれをみて切り出すtokenを変えています。
密結合が引き起こす問題
端的にいうと見通しが悪くなるというのが問題です。見通しが悪い理由は大きく2つに分類できます。
1. lexerの状態がどの範囲で影響するのかがわかりにくい
All bugfixes are incompatibilities - RubyKaigi 2019 の3番目の例がわかりやすいかと思います4。 もともとのチケットBug #11107は以下のコードが通らないというものでした。
-e:1: syntax error, unexpected keyword_do_block, expecting keyword_end
p ->() do a(1) do end end
^
全体はp argsという引数の括弧を省略したメソッドの呼び出しになっていて、その場合はkeyword_do_blockというtokenを切り出すようにlexerの状態が設定されます。一方でa(1) do endのdoは括弧付きのメソッド呼び出しなのでkeyword_doを期待しています。チケットが報告された時点ではp ->() doの前後でdoに関する状態が変わらないようになっていて、lambdaのbodyのなかにも影響するようになっていたため上記のコードがsyntax errorになっていたのでした5。
このようにある時点で設定したlexerの状態がその後どこまで影響するか把握しにくく、また把握するためにはparseとlexerの両方を理解しないといけないのが現状です。
2. ある時点でのlexerの状態がパッとみたときにわからない
lex stateの更新の仕方にもいくつかパターンがあります
- tokenの種類から一意に決まるパターン。たとえば
tOROP(||)なら次はEXPR_BEGになるといったケースです - tokenの種類と現在のstateから決まるパターン。
tCMP(<=>)は通常はEXPR_BEG、defや.(メソッド呼び出しのドット)のあとなどの一部の状況ではEXPR_ARGになるといったケースです - parserのactionで更新するパターン。たとえばシングルトンメソッドの定義時(
def obj.m; end)に.のあとはEXPR_FNAMEでないといけないので、その調整をparserのアクションで行っています。lexerは常に.のときにEXPR_DOTを設定するので、その効果をparserがわで調整する必要があります。
これらが絶妙に絡まり合った結果、parse中の各地点で結局lex stateがどうなっているのかを理解するのが難しくなっています。
問題の解消に向けて
yaccの宣言的な文法は条件が書けない。 「この条件のときはこのルールを適用しない」というような文法はありえない。
Matzにっき(2004-04-26) に書いてあるこの指摘はその通りで、確かにBisonにはそのような機能はありません。しかしBisonにないからといってそれが不可能とは限らないのです。 2022年に発表されたPractical LR Parser Generationという論文をみてみましょう。
However, the prevailing consensus is that automatic parser generation is not practical for real programming languages: ... As a result, virtually all modern languages use recursive-descent parsers written by hand, a lengthy and error-prone process that dramatically increases the barrier to new programming language development.
という嘆きから始まるこの論文は、LR parser generatorへの5つの改善を加えることでより便利で効率のよいparser generatorを提案しています。また論文の筆者は具体的な実装として https://github.com/jzimmerman/langcc を実装し、GolangおよびPythonのparserを生成できることを示しています。
Nonterminal attributes
複数の異なる技法が紹介されていますが、なかでも今回のケースで有効な技法がNonterminal attributesです。C++やRustで<...>のなかで比較演算子Greater Thanの>が出てきて欲しくないとか、Golangでif ... {}の条件のexpressionのところで{}が末尾にきて欲しくないという例があげられています。これってまさしく「この条件のときはこのルールを適用しない」という話ではないですか。
Nonterminal attributesが具体的にどういった機能かというと
- 非終端記号にattributes(属性)を持たせられるようにする
- attributeはbinary-valued(二値)もしくはinteger-valued(数値)を指定できる
- 各生成規則ではattributeを用いた制約を書くことができる
Rubyのdoに注目してbinary-valuedのケースをみていきましょう。さっそくLramaに実装したので、簡略化した以下のようなparse.yを渡して各状態を確認していきます。
%{
// Prologue
%}
%union {
int i;
}
%token <i> k_while
%token <i> k_do
%token <i> k_end
%token <i> tSTRING
%token <i> tIDENTIFIER
%attr DO_ALLOWED -- (1)
%%
program: stmt(DO_ALLOWED) ; -- (2)
stmt : k_while expr(!DO_ALLOWED) k_do stmt k_end -- (2)
| expr
;
expr : tSTRING
| command_call
;
command_call: tIDENTIFIER
| @lhs(DO_ALLOWED) tIDENTIFIER k_do stmt k_end -- (3)
;
%%
通常のparse.yとの主な差分は
%attr DO_ALLOWEDでattributeを宣言。このattributeがtrueのときはその中でdoを含むルールが出現してよいという意味@lhs(DO_ALLOWED) tIDENTIFIER k_do stmt k_endのように特定のルールに対してDO_ALLOWEDなときのみこのルールを使うことができるという指定をしているstmt(DO_ALLOWED)やk_while expr(!DO_ALLOWED) k_do stmt k_endのように右辺の非終端記号に対してattributeを指定して値を書き換えている。whileの条件部分ではdoを含むルールは禁止するという意味
この文法ファイルからレポートをつくると確かにk_whileを経由してexprのparseをしているとき(State 1)ではcommand_callのルールが1つになっていて、そうでないとき(State 3)はcommand_callのルールが2つになっています。普段はdoが来ていいけどwhileの条件式の部分ではdoは来てはいけないというのが表現できています。
State 1 # こちらは command_call の2つめのルールがなく、doが禁止されている
2 stmt: k_while • expr k_do stmt k_end (DO_ALLOWED: true)
4 expr: • tSTRING (DO_ALLOWED: false)
5 | • command_call (DO_ALLOWED: false)
6 command_call: • tIDENTIFIER (DO_ALLOWED: false) -- ここが1つしかない
tSTRING shift, and go to state 8
tIDENTIFIER shift, and go to state 9
expr go to state 10
command_call go to state 11
State 3 # こちらは command_call の2つめのルールがあり、doが許可されている
6 command_call: tIDENTIFIER • ["end of file", k_end] (DO_ALLOWED: true)
7 | tIDENTIFIER • k_do stmt k_end (DO_ALLOWED: true) -- doを含むルールがある
k_do shift, and go to state 12
$default reduce using rule 6 (command_call)
実際にRubyのparse.yに応用してみる
whileなどのdoの統合
keyword_do_condをkeyword_doに統合したものがこちらになります。
whileなどの条件の箇所(expr_value_do)を処理するときはdoの出現を禁止する。doが出現するルール(brace_block)ではDO_ALLOWEDをチェックする。COND_PUSH(0)を呼んでいる箇所を探して、その後ではDO_ALLOWEDを渡すという修正です。これはconflictなしでいけました。
-expr_value_do : {COND_PUSH(1);} expr_value do {COND_POP();} +expr_value_do : {COND_PUSH(1);} expr_value(!DO_ALLOWED) do {COND_POP();} { $$ = $2; } ; @@ -4301,7 +4301,7 @@ brace_block : '{' brace_body '}' nd_set_line($$, @1.end_pos.lineno); /*% %*/ } - | k_do do_body k_end + | @lhs(DO_ALLOWED) k_do do_body k_end
コマンド呼び出しのdoの統合
続いてkeyword_do_blockをkeyword_doに統合したものがこちらになります。
これは括弧なしのメソッド呼び出しの引数のdoに関するルールです。以下のように引数の中にはdoが書けないというものです(Syntaxとしては正しいけど外側のcmdのブロックとして扱われる)。
cmd a1 do e1 end # こうではなく cmd (a1 do e1 end) # こう解釈される cmd(a1) do e1 end
コマンドの引数を処理するときは(command_call)blockに関係するルールでDO_ALLOWEDをチェックするようにする。コマンドの引数を処理が始まったら(command_args)doの出現を禁止する。CMDARG_PUSH(0)を呼んでいる箇所を探して、その後ではDO_ALLOWEDを渡すという修正です。
command_call : command - | block_command + | @lhs(DO_ALLOWED) block_command ; @@ -3086,7 +3086,7 @@ command_args : { CMDARG_PUSH(1); if (lookahead) CMDARG_PUSH(0); } - call_args + call_args(!DO_ALLOWED) {
今回はconflictが発生しました。ためしにBisonでcounterexamples6を計算させると、returnが絡む入力でShift/Reduce conflictする様子がわかります。
これまでは普通のdo(k_do)ならshift、コマンドのdo(k_do_block)ならreduceと棲み分けができていたので衝突していなかったのですが、今回その2つを統合したので衝突するようになってしまいました7。
shift/reduce conflict on token "`do'":
341 primary: method_call •
379 k_do: • "`do'"
Example: k_return method_call • "`do'" do_body k_end call_op operation2 command_args
Shift derivation
command_call
↳ 75: command
↳ 89: k_return call_args
↳ 288: command
↳ 83: primary_value call_op operation2 command_args
↳ 368: primary
↳ 342: method_call brace_block
↳ 472: k_do do_body k_end
↳ 379: • "`do'"
Reduce derivation
command_call
↳ 76: block_command
↳ 78: block_call call_op2 operation2 command_args
↳ 458: command do_block ↳ 766: call_op
↳ 89: k_return call_args ↳ 457: k_do_block do_body k_end
↳ 289: args opt_block_arg ↳ 380: "`do'"
↳ 299: arg_value ↳ 289: ε
↳ 271: arg
↳ 263: primary
↳ 341: method_call •
LALRパーサーから踏み出した実装をしたため、知らないうちに意図しないエッジケースが生まれてしまっています8。もしくは知らないうちに仮定するルールが増えているとも考えられます。どちらにせよこれは困ったことになりました。
まとめ
Rubyのparseの複雑さはparserとlexerが密結合していることが原因の一つであるという分析をし、そのなかでもとくにdoに関する問題をみてきました。
2022年に発表されたPractical LR Parser Generationという論文を参考に「この条件のときはこのルールを適用しない」という文法を導入してみた結果、一部では有効ですがある部分ではconflictが発生することがわかりました。どうしたものでしょうか...
-
例えばMenhirには
optionやnonempty_listといった便利機能があります。http://gallium.inria.fr/~fpottier/menhir/manual.html#sec32↩ - 動画の36:16あたりから↩
-
p->lex.lpar_beg >= 0 && p->lex.lpar_beg+1 == p->lex.paren_nestかつIS_lex_state_for(last_state, EXPR_LABEL)をみて-> (の中にいる状態だと初見で理解するのはちょっと難しいと思います。ちなみにIS_lex_state_for(last_state, EXPR_LABEL)のチェックをせずtDOT3を返すようにすると今度は-> (a = ...2) {}が通らなくなります。こういう絶妙なバランスがこの分岐で実装されているわけですね↩ - 動画の43:31あたり↩
-
ちなみに
while ->() do a(1) do end end do endは3.2でも通りません。これはlambdaのf_larglistのあとでCMDARG_PUSH(0)はしているけどCOND_PUSH(0)はしていないためです。特に報告もあがっていないので、このままでいいと思います↩ - 便利なのでLramaにもほしいです。Finding Counterexamples from Parsing Conflicts参照↩
-
既存の文法が壊れるのを覚悟で
k_return call_args(!DO_ALLOWED)というように禁止してもまだだめで、endless method definitionの中のargでのdoを禁止する必要があります。cmd a1, def m = obj.m1 do e1 endみたいなケースです。cmd a1, return a2 do e1 endはvoid value expressionでSyntaxErrorになるので別途returnなどが出現できる位置を制御するattributeを定義するという手もありますが煩雑になります↩ - Practical LR Parser GenerationではAddendumでGoの型パラメーターの構文やPythonのパターンマッチングの構文に曖昧さがあるという指摘をしています↩
