ときどきの雑記帖 RE* (新南口)
parse.y の森の中へ
Syntax rule of Ruby
ruruby: RustでつくっているRuby - Qiita (はてブ [B! Rust] ruruby: RustでつくっているRuby - Qiita)
という記事を読んだ。
- 単一代入、多重代入時の評価順
s[k]=Z*(k=(k2-21)** 2/99)+q79+Z+q2(6-k)のようなコードが最初は正しく動かずかなりハマりました。 これ、配列のインデックスkを右辺式の中で再代入していて、先に右辺を評価してから左辺の配列を評価するとダメなんですね。 確かにそちらの方が自然かもしれないですが、 分かるまではかなり悩みました。で、恐ろしいことに単一代入だと 左辺を評価→右辺を評価→代入 ですが、多重代入（例:a,b,c = 1,2）の場合は 右辺を順に評価→左辺を順に評価→順に代入 という順番になる奇妙な仕様です。
多重代入の謎仕様を何とかしてほしいという市民の訴え
や
- 不思議な代入式
Rubyでは a+b=3が有効な式です （a+(b=3)と解釈される）。こういうのを正しくパースするのも（手書きパーサなので）かなり手間取りました。
には、「あー」(言葉にならない何か)という感想しかないんだけど、後者がちょっと引っかかった。 脚注 には
普通は’+‘の方が’=‘より優先順位が高いので(a+b)=3にパースされてエラーになるはず。でないとa=b+3が(a=b)+3になってしまう。 これも試行錯誤した挙句、アドホックに解決した。
とあるのだけど、そんなへんな優先順位になってたっけとソースコードを見てみる。
演算子の優先順位
ruby/parse.y at ruby_2_7 · ruby/ruby · GitHub
/*
* precedence table
*/
%nonassoc tLOWEST
%nonassoc tLBRACE_ARG
%nonassoc modifier_if modifier_unless modifier_while modifier_until keyword_in
%left keyword_or keyword_and
%right keyword_not
%nonassoc keyword_defined
%right '=' tOP_ASGN
%left modifier_rescue
%right '?' ':'
%nonassoc tDOT2 tDOT3 tBDOT2 tBDOT3
%left tOROP
%left tANDOP
%nonassoc tCMP tEQ tEQQ tNEQ tMATCH tNMATCH
%left '>' tGEQ '<' tLEQ
%left '|' '^'
%left '&'
%left tLSHFT tRSHFT
%left '+' '-'
%left '*' '/' '%'
%right tUMINUS_NUM tUMINUS
%right tPOW
%right '!' '~' tUPLUS
これを見る限りは、’=’ の方が低い優先順位の低いはず。 んが、実際の動作は記事にあるようにどうも逆になっているように見えるのも確か。 そこで、実際どう解釈されているのかを RubyVM::AbstractSyntaxTree.parse (Ruby 2.7.0 リファレンスマニュアル) を使って確かめてみた。
irb(main):001:0> pp RubyVM::AbstractSyntaxTree.parse("a + b = 3")
(SCOPE@1:0-1:9
tbl: [:b]
args: nil
body:
(OPCALL@1:0-1:9 (VCALL@1:0-1:1 :a) :+
(LIST@1:4-1:9 (LASGN@1:4-1:9 :b (LIT@1:8-1:9 3)) nil)))
=> #<RubyVM::AbstractSyntaxTree::Node:SCOPE@1:0-1:9>
確かに + よりも = が優先されて解釈されているようだ。
比較のため、a * b + 3 でやったときの結果はこう。
irb(main):002:0> pp RubyVM::AbstractSyntaxTree.parse("a * b + 3")
(SCOPE@1:0-1:9
tbl: []
args: nil
body:
(OPCALL@1:0-1:9
(OPCALL@1:0-1:5 (VCALL@1:0-1:1 :a) :*
(LIST@1:4-1:5 (VCALL@1:4-1:5 :b) nil)) :+
(LIST@1:8-1:9 (LIT@1:8-1:9 3) nil)))
=> #<RubyVM::AbstractSyntaxTree::Node:SCOPE@1:0-1:9>
解釈の違うことはわかるものの、それが何故なのかという点では情報が得られていない。 やはり構文定義を追いかけるしかないか?
それとこの出力フォーマット(自分には)今一つ読みやすくない印象なのだけど GitHub - whitequark/parser: A Ruby parser. だとどうだったろうか。
コマンドラインオプション
parse.y を追いかけるのはタイヘンなのでどうしたものかと思ったが、 Ruby には便利なコマンドラインオプションがあった。
>ruby --version
ruby 2.7.2p137 (2020-10-01 revision 5445e04352) [x64-mingw32]
>ruby --help
Usage: ruby [switches] [--] [programfile] [arguments]
(省略)
--dump={insns|parsetree|...}[,...]
dump debug information. see below for available dump list
--enable={gems|rubyopt|...}[,...], --disable={gems|rubyopt|...}[,...]
enable or disable features. see below for available features
--external-encoding=encoding, --internal-encoding=encoding
specify the default external or internal character encoding
--verbose turn on verbose mode and disable script from stdin
--version print the version number, then exit
--help show this message, -h for short message
Dump List:
insns instruction sequences
yydebug yydebug of yacc parser generator
parsetree AST
parsetree_with_comment
AST with comments
と、yydebug of yacc parser generator が出せるようになっていた
(いつからあったんだろうこれ?)ので、ありがたく使わせてもらう。
出力を見る
>ruby --dump=yydebug -e "a+b=3"
Starting parse
Entering state 0
Reducing stack by rule 1 (line 1177):
lex_state: NONE -> BEG at line 1178
vtable_alloc:11774: 0x0000000002bafed0
vtable_alloc:11775: 0x0000000002bb0070
cmdarg_stack(push): 0 at line 11788
cond_stack(push): 0 at line 11789
-> $$ = nterm $@1 (1.0-1.0: )
Stack now 0
Entering state 2
Reading a token:
lex_state: BEG -> CMDARG at line 8765
Next token is token "local variable or method" (1.0-1.1: a)
Shifting token "local variable or method" (1.0-1.1: a)
Entering state 35
Reading a token:
lex_state: CMDARG -> BEG at line 9190
Next token is token '+' (1.1-1.2: )
Reducing stack by rule 629 (line 4736):
$1 = token "local variable or method" (1.0-1.1: a)
-> $$ = nterm user_variable (1.0-1.1: )
Stack now 0 2
Entering state 118
(以下略)
期待した出力は得られるようだ。
dump結果を比較する
色分け表示したdiff 結果を使いたいがなんかいい手はあるのだろうか。
という話はさておき、a+b=3 と a+b*3 のそれぞれの場合の出力を比較する
(今回の比較のノイズになる変数の登録情報は削除した上で比較している)。
>diff --side-by-side assign.out mult.out
Starting parse Starting parse
Entering state 0 Entering state 0
Reducing stack by rule 1 (line 1177): Reducing stack by rule 1 (line 1177):
lex_state: NONE -> BEG at line 1178 lex_state: NONE -> BEG at line 1178
cmdarg_stack(push): 0 at line 11788 cmdarg_stack(push): 0 at line 11788
cond_stack(push): 0 at line 11789 cond_stack(push): 0 at line 11789
-> $$ = nterm $@1 (1.0-1.0: ) -> $$ = nterm $@1 (1.0-1.0: )
Stack now 0 Stack now 0
Entering state 2 Entering state 2
Reading a token: Reading a token:
この出だしの部分を含め思った以上に差分が少なくてちょっと驚いた。 まああんまり違いが出ても追いかけるのが大変ではあるのだが。
違いが出るのはこの辺りから
Reading a token: Reading a token:
lex_state: ARG -> BEG at line 9002 | lex_state: ARG -> BEG at line 8949
Next token is token '=' (1.8-1.9: ) | Next token is token '*' (1.8-1.9: )
Reducing stack by rule 629 (line 4736): Reducing stack by rule 629 (line 4736):
$1 = token "local variable or method" (1.7-1.8: b) $1 = token "local variable or method" (1.7-1.8: b)
-> $$ = nterm user_variable (1.7-1.8: ) -> $$ = nterm user_variable (1.7-1.8: )
Stack now 0 2 78 232 217 354 Stack now 0 2 78 232 217 354
Entering state 223 Entering state 223
Next token is token '=' (1.8-1.9: ) | Next token is token '*' (1.8-1.9: )
Reducing stack by rule 111 (line 1918): | Reducing stack by rule 641 (line 4752):
$1 = nterm user_variable (1.7-1.8: ) $1 = nterm user_variable (1.7-1.8: )
-> $$ = nterm lhs (1.7-1.8: ) | -> $$ = nterm var_ref (1.7-1.8: )
Stack now 0 2 78 232 217 354 Stack now 0 2 78 232 217 354
Entering state 216 | Entering state 120
Next token is token '=' (1.8-1.9: ) | Reducing stack by rule 299 (line 2632):
Shifting token '=' (1.8-1.9: ) | $1 = nterm var_ref (1.7-1.8: )
Entering state 423 | -> $$ = nterm primary (1.7-1.8: )
> Stack now 0 2 78 232 217 354
> Entering state 88
> Next token is token '*' (1.8-1.9: )
> Reducing stack by rule 249 (line 2347):
> $1 = nterm primary (1.7-1.8: )
> -> $$ = nterm arg (1.7-1.8: )
> Stack now 0 2 78 232 217 354
> Entering state 557
> Next token is token '*' (1.8-1.9: )
> Shifting token '*' (1.8-1.9: )
> Entering state 356
読み込んだトークンの違いによる差異は当然として、そこからの状態遷移が明らかに異なっているが、 この後は解析スタックの内容の違いはあるものの、また同じような出力になる。
Reading a token: Reading a token:
lex_state: BEG -> END at line 8074 lex_state: BEG -> END at line 8074
lex_state: END -> END at line 7430 lex_state: END -> END at line 7430
Next token is token "integer literal" (1.9-1.10: 3) Next token is token "integer literal" (1.9-1.10: 3)
Shifting token "integer literal" (1.9-1.10: 3) Shifting token "integer literal" (1.9-1.10: 3)
Entering state 41 Entering state 41
Reducing stack by rule 625 (line 4730): Reducing stack by rule 625 (line 4730):
$1 = token "integer literal" (1.9-1.10: 3) $1 = token "integer literal" (1.9-1.10: 3)
-> $$ = nterm simple_numeric (1.9-1.10: ) -> $$ = nterm simple_numeric (1.9-1.10: )
Stack now 0 2 78 232 217 354 216 423 | Stack now 0 2 78 232 217 354 557 356
Entering state 117 Entering state 117
Reducing stack by rule 623 (line 4719): Reducing stack by rule 623 (line 4719):
$1 = nterm simple_numeric (1.9-1.10: ) $1 = nterm simple_numeric (1.9-1.10: )
-> $$ = nterm numeric (1.9-1.10: ) -> $$ = nterm numeric (1.9-1.10: )
Stack now 0 2 78 232 217 354 216 423 | Stack now 0 2 78 232 217 354 557 356
Entering state 116 Entering state 116
Reducing stack by rule 573 (line 4343): Reducing stack by rule 573 (line 4343):
$1 = nterm numeric (1.9-1.10: ) $1 = nterm numeric (1.9-1.10: )
-> $$ = nterm literal (1.9-1.10: ) -> $$ = nterm literal (1.9-1.10: )
Stack now 0 2 78 232 217 354 216 423 | Stack now 0 2 78 232 217 354 557 356
Entering state 103 Entering state 103
Reducing stack by rule 291 (line 2624): Reducing stack by rule 291 (line 2624):
$1 = nterm literal (1.9-1.10: ) $1 = nterm literal (1.9-1.10: )
-> $$ = nterm primary (1.9-1.10: ) -> $$ = nterm primary (1.9-1.10: )
Stack now 0 2 78 232 217 354 216 423 | Stack now 0 2 78 232 217 354 557 356
Entering state 88 Entering state 88
Reading a token: Reading a token:
lex_state: END -> BEG at line 8909 lex_state: END -> BEG at line 8909
Next token is token '\n' (1.10-1.10: ) Next token is token '\n' (1.10-1.10: )
Reducing stack by rule 249 (line 2347): Reducing stack by rule 249 (line 2347):
$1 = nterm primary (1.9-1.10: ) $1 = nterm primary (1.9-1.10: )
-> $$ = nterm arg (1.9-1.10: ) -> $$ = nterm arg (1.9-1.10: )
Stack now 0 2 78 232 217 354 216 423 | Stack now 0 2 78 232 217 354 557 356
Entering state 613 | Entering state 559
Next token is token '\n' (1.10-1.10: ) Next token is token '\n' (1.10-1.10: )
Reducing stack by rule 261 (line 2398): | Reducing stack by rule 223 (line 2244):
$1 = nterm arg (1.9-1.10: ) | $1 = nterm arg (1.7-1.8: )
-> $$ = nterm arg_rhs (1.9-1.10: ) | $2 = token '*' (1.8-1.9: )
Stack now 0 2 78 232 217 354 216 423 | $3 = nterm arg (1.9-1.10: )
Entering state 535 <
Reducing stack by rule 206 (line 2101): <
$1 = nterm lhs (1.7-1.8: ) <
$2 = token '=' (1.8-1.9: ) <
$3 = nterm arg_rhs (1.9-1.10: ) <
-> $$ = nterm arg (1.7-1.10: ) -> $$ = nterm arg (1.7-1.10: )
ここから後は最後までまったく同じ出力となる。
Stack now 0 2 78 232 217 354 Stack now 0 2 78 232 217 354
Entering state 557 Entering state 557
Next token is token '\n' (1.10-1.10: ) Next token is token '\n' (1.10-1.10: )
Reducing stack by rule 221 (line 2236): Reducing stack by rule 221 (line 2236):
$1 = nterm arg (1.5-1.6: ) $1 = nterm arg (1.5-1.6: )
$2 = token '+' (1.6-1.7: ) $2 = token '+' (1.6-1.7: )
$3 = nterm arg (1.7-1.10: ) $3 = nterm arg (1.7-1.10: )
-> $$ = nterm arg (1.5-1.10: ) -> $$ = nterm arg (1.5-1.10: )
Stack now 0 2 78 232 Stack now 0 2 78 232
Entering state 217 Entering state 217
(省略)
Entering state 70 Entering state 70
Reducing stack by rule 2 (line 1177): Reducing stack by rule 2 (line 1177):
$1 = nterm $@1 (1.0-1.0: ) $1 = nterm $@1 (1.0-1.0: )
$2 = nterm top_compstmt (1.0-1.10: ) $2 = nterm top_compstmt (1.0-1.10: )
cmdarg_stack(pop): 0 at line 11810 cmdarg_stack(pop): 0 at line 11810
cond_stack(pop): 0 at line 11811 cond_stack(pop): 0 at line 11811
-> $$ = nterm program (1.0-1.10: ) -> $$ = nterm program (1.0-1.10: )
Stack now 0 Stack now 0
Entering state 1 Entering state 1
Now at end of input. Now at end of input.
Shifting token "end-of-input" (1.10-1.10: ) Shifting token "end-of-input" (1.10-1.10: )
Entering state 3 Entering state 3
Stack now 0 1 3 Stack now 0 1 3
Cleanup: popping token "end-of-input" (1.10-1.10: ) Cleanup: popping token "end-of-input" (1.10-1.10: )
Cleanup: popping nterm program (1.0-1.10: ) Cleanup: popping nterm program (1.0-1.10: )
↑のコード部分の表示幅を(それをそのまま表示できる環境では) 広げたいのだけどどうしたものだろうか
bison でエラー
上記の結果の裏付けのため、yacc でいうところの y.output ファイルを使って動作を追いかけたいと思ったが 配布されている tar 玉には(bison の出力結果としての parse.c はあっても) そんなものは入っていないので、必要なら自分で生成するしかない。
とは言えRubyのビルド環境なんてここ何年も用意していない (使っているPCも何回か変わっているし)ので、 どうしたものかとしばし悩んだものの yacc (bison) の構文ファイルだから特に面倒なことをせんでも bison に tar玉から抜き出した parse.y を食わせれば 生成できるだろうと甘く考えてやってみる。
$ bison -v -g parse.y
parse.y:1098.35: エラー: 無効な文: `('
1098 | %token tUPLUS RUBY_TOKEN(UPLUS) "unary+"
| ^
parse.y:1098.41: エラー: 無効な文: `)'
1098 | %token tUPLUS RUBY_TOKEN(UPLUS) "unary+"
| ^
parse.y:1099.35: エラー: 無効な文: `('
1099 | %token tUMINUS RUBY_TOKEN(UMINUS) "unary-"
| ^
parse.y:1099.42: エラー: 無効な文: `)'
1099 | %token tUMINUS RUBY_TOKEN(UMINUS) "unary-"
| ^
(略)
parse.y:5418.1-5: エラー: 予期しない 識別子:
5418 | terms : term
| ^~~~~
parse.y:5422.1-4: エラー: 予期しない 識別子:
5422 | none : /* none */
| ^~~~
parse.y:5427.3-13222.0: エラー: 予期しない エピローグ
5427 | %%
| ^
ぐはっ。
なにやら大量の(しかし同じ種類の)エラーが。
しかしここで挫けず、エラーの出ている %token の行の記述に違和感があったので調べてみると
どうも実際に bison にかける前に前処理をしているらしく、
それをしていないファイルを食わせてはまずかったらしい。
ruby/common.mk at ruby_2_7 · ruby/ruby · GitHub
{$(srcdir)}.y.c:
$(ECHO) generating $@
$(Q)$(BASERUBY) $(srcdir)/tool/id2token.rb --path-separator=.$(PATH_SEPARATOR)./ --vpath=$(VPATH) id.h $(SRC_FILE) > parse.tmp.y
$(Q)$(BASERUBY) $(srcdir)/tool/pure_parser.rb parse.tmp.y $(YACC)
$(Q)$(YACC) -d $(YFLAGS) -o y.tab.c parse.tmp.y
$(Q)$(RM) parse.tmp.y
$(Q)sed -f $(srcdir)/tool/ytab.sed -e "/^#/s|parse\.tmp\.[iy]|$(SRC_FILE)|" -e "/^#/s!y\.tab\.c!$@!" y.tab.c > $@.new
$(Q)$(MV) $@.new $@
$(Q)sed -e "/^#line.*y\.tab\.h/d;/^#line.*parse.*\.y/d" y.tab.h > $(@:.c=.h)
$(Q)$(RM) y.tab.c y.tab.h
ここでもすでにあるrubyの実行ファイル($(BASERUBY))をつかってたんだねえ。 自分が自力で実行ファイルを作っていたころは まだ BASERUBY を使っていなかったと思うから、 だいぶ「浦島太郎」な状態ですやね。
ということで、(make経由ではなく)手作業で前処理スクリプトを実行してから その結果を bison に食わせると…
文法中の終端が無駄です
"backslash"
"escaped space"
"escaped horizontal tab"
"escaped form feed"
"escaped carriage return"
"escaped vertical tab"
")"
tLAST_TOKEN
文法
0 $accept: program "end-of-input"
1 $@1: %empty
2 program: $@1 top_compstmt
3 top_compstmt: top_stmts opt_terms
4 top_stmts: none
5 | top_stmt
6 | top_stmts terms top_stmt
7 | error top_stmt
8 top_stmt: stmt
9 | "`BEGIN'" begin_block
10 begin_block: '{' top_compstmt '}'
11 $@2: %empty
12 bodystmt: compstmt opt_rescue k_else $@2 compstmt opt_ensure
13 | compstmt opt_rescue opt_ensure
(以下略)
できたできた。
そして
続く(たぶん)。
≪ prev 2020年11月29日
next ≫ 2020年12月5日