-
Notifications
You must be signed in to change notification settings - Fork 12
/
Copy pathchapter11.txt
2052 lines (1585 loc) · 78.2 KB
/
chapter11.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
h1. 第11章 状態付きスキャナ
h2. 概要
理論のように、スキャナはただひたすらトークンに区切り、パーサはその並び
だけを扱い、両者は完璧に独立している……という段階で済むならば、それは
とてもありがたいことだ。しかし現実はそううまくはいかない。プログラムの
文脈によってトークンの切りかたや記号を変えなければならないということは
よくある。この章ではスキャナとパーサの連携について見ていくことにする。
h3. 具体例
普通のプログラム言語なら、空白は単語の区切りになる以外はたいし
て意味を持たない。しかしRubyは普通ではないので空白のあるなしで全く意味
が変わってしまうことがある。例えば次のような場合だ。
<pre class="emlist">
a[i] = 1 # a[i] = (1)
a [i] # a([i])
</pre>
前者はインデックス代入であり、後者はメソッド呼び出しの括弧を省略して引
数に配列の要素を渡している。
また次のような場合もある。
<pre class="emlist">
a + 1 # (a) + (1)
a +1 # a(+1)
</pre>
このあたりの仕様は一部の地域でやたらと嫌われているようだ。
しかしこのままだとメソッド括弧の省略だけが悪いかのような印象を
与えてしまいそうなので別の例も挙げておこう。
<pre class="emlist">
`cvs diff parse.y` # コマンド呼び出し文字列
obj.`("cvs diff parse.y") # 通常形式のメソッド呼び出し
</pre>
これは、前者がリテラルの形を取ったメソッド呼び出しであるのに対し、
後者は通常形式のメソッド呼び出しである(「```」がメソッド名)。
コンテキストによって随分と扱いが違う。
次の例もかなり激しく働きが変わる。
<pre class="emlist">
print(<<EOS) # ヒアドキュメント
......
EOS
list = []
list << nil # list.push(nil)
</pre>
前者はヒアドキュメントで、後者は演算子形式のメソッド呼び出しである。
このようにRubyの文法には実装するのには不都合なところがたくさん
存在する。とてもではないが丁寧にやっていたら一章で全部紹介しき
れるような量ではない。そこでこの章では根本原理と、難易度の高いところに
限って見ていくことにする。
h3. `lex_state`
`lex_state`という変数がある。`lex`はもちろんlexerのlexだから、これは
スキャナの状態(state)を示す変数だ。
どういう状態があるのだろうか。定義を見てみよう。
▼ `enum lex_state`
<pre class="longlist">
61 static enum lex_state {
62 EXPR_BEG, /* ignore newline, +/- is a sign. */
63 EXPR_END, /* newline significant, +/- is a operator. */
64 EXPR_ARG, /* newline significant, +/- is a operator. */
65 EXPR_CMDARG, /* newline significant, +/- is a operator. */
66 EXPR_ENDARG, /* newline significant, +/- is a operator. */
67 EXPR_MID, /* newline significant, +/- is a operator. */
68 EXPR_FNAME, /* ignore newline, no reserved words. */
69 EXPR_DOT, /* right after `.' or `::', no reserved words. */
70 EXPR_CLASS, /* immediate after `class', no here document. */
71 } lex_state;
(parse.y)
</pre>
プリフィクスの`EXPR_`はexpression、「式」だろう。`EXPR_BEG`なら「式の頭」
だし`EXPR_DOT`は「式の中の、ドットの後」だ。
具体的に説明しよう。`EXPR_BEG`は「式の先頭にいる」ことを示している。
`EXPR_END`は「式の最後にいる」ことを示す。`EXPR_ARG`は「メソッドの引数の前」
を示す。`EXPR_FNAME`は「(`def`などの)メソッド名の前」を示す。説明を飛ば
したものはあとで詳しく解析していく。
ところで、`lex_state`が示しているものは「括弧のあと」「文の頭」というよ
うな情報なのだから、これはスキャナの状態ではなくてパーサの状態のような
気がする。だが普通はスキャナの状態と呼ぶ。なぜだろうか。
実はこの場合の「状態」は普段使う「状態」とちょっと意味が違うのだ。
`lex_state`のような「状態」とは、「スキャナがこういう振舞いをする状態」
という意味である。例えば`EXPR_BEG`を正確に言えば「いまスキャナを働かせ
たら文頭にいるかのように動く状態」である。
また専門用語を使うと、スキャナをステートマシンと見たときの状態、と言え
る。しかしそこまで説明するのはさすがに骨が折れるしあまりに話題が離れす
ぎる。詳しいことはデータ構造に関する教科書を適当に見繕って読んでいただ
きたい。
h3. 状態付きスキャナの読解
状態付きスキャナを読むコツは、一度に全部をつかもうとしないことだ。パー
サを書く人間にとっては、状態付きスキャナはあまり使いたくないものである。
ということは当然、それを処理の本筋にはしたくないはずだ。だからスキャナ
の状態管理というのは「その他の本筋部分に付随したおまけ部分」であること
が多い。つまりスキャナの状態遷移全体の美しい全体像なんてものは最初から
存在しないのである。
ではどうするかというと、徹底的に目的指向で読んでいくのがよい。「これを
解決するためにこの部分がある」「この問題を解消するためのこのコードがあ
る」というふうに、目的に沿ってコードを切り刻む。問題の相互関連なんても
のを考え始めると絶対に行き詰まる。もう一度言うが、そんなものは元からな
いのだ。
とは言えそれにしたってある程度の目標は必要だ。状態付きスキャナを読むと
きの目標は、何よりも各状態がどういう状態かを知ることに置く
べきである。例えば`EXPR_BEG`はどういう状態か。それはパーサが式の頭にい
るということである。というように。
h4. 静的な方法
ではそれはどうやったらわかるだろうか。三通りの方法がある。
* 状態の名前を見る
もっとも簡単であたりまえの方法。例えば`EXPR_BEG`なら当然なにかの先頭
(beginning)なんだろうというのは予測が付く。
* その状態においてどう挙動が変わるか見る
状態によってトークンの切りかたがどう変わるか見る。そして現実の動きと比
べて当たりをつける。
* どういう状態から遷移してくるか見る
どの状態からどういうトークンで遷移してくるか見る。例えば`'\n'`の後に必
ず`HEAD`という状態に遷移しているとしたら、それはきっと行頭を表しているに
違いない。
`EXPR_BEG`を例にして考えてみよう。
`ruby`の場合は状態遷移は全て`lex_state`への代入で表現されているので、ま
ず`EXPR_BEG`の代入を`grep`して洗う。次にそれがどこにあるか書き出す。例えば
`yylex()`の`'#'`と`'*'`と`'!'`と……のように。そして遷移する前の状態を考慮して
それがどういう場合にあてはまるか考える(図1)。
!images/ch_contextual_transittobeg.jpg(`EXPR_BEG`への遷移)!
ああなるほど、これはいかにも文の先頭っぽいな。とわかる。
特に`'\n'`や`';'`のあたりがそれっぽい。そして開き括弧やカンマも
あることから、これは文だけではなくて式の先頭だろうと言える。
h4. 動的な方法
もっとお手軽に現実の挙動を確かめる方法もある。例えばデバッガで
`yylex()`にフックをかけて`lex_state`を見ると簡単だ。
あるいはソースコードを書き換えて状態遷移を出力するようにしてしまっても
いい。`lex_state`の場合は代入や比較が数パターンしかないので、それをテキ
ストのパターンでとらえて遷移を出力するように書き換えればよい。今回は添
付CD-ROMに`rubylex-analyser`というツールを付け
た\footnote{`rubylex-analyser`:添付CD-ROMの`tools/rubylex-analyser.tar.gz`}。
本書でも必要に応じてこのツールを使いつつ説明していく。
全体的な手順としては、まずデバッガやツールを使ってなんとなくの動きを
確認する。そしてその情報をソースコードを見て確認・敷衍していくという
のがよいだろう。
h3. 各状態について
`lex_state`の状態について簡単に説明しておく。
* `EXPR_BEG`
式の先端。`\n ( { [ ! ? : ,` 演算子 `op=`などの直後。
最も一般的な状態である。
* `EXPR_MID`
予約語の`return break next rescue`の直後。
二項演算子の`*`や`&`が無効になる。
挙動は`EXPR_BEG`と似ている。
* `EXPR_ARG`
メソッド呼び出しのメソッド名部分である可能性がある要素の直後、
または`'['`の直後。
ただし`EXPR_CMDARG`である場所を除く。
* `EXPR_CMDARG`
通常形式のメソッド呼び出しの最初の引数の前。
詳しくは「`do`の衝突」の節を参照。
* `EXPR_END`
文が終端可能なところ。例えばリテラルや括弧のあと。ただし`EXPR_ENDARG`で
ある場所は除く。
* `EXPR_ENDARG`
`EXPR_END`の特殊版。`tLPAREN_ARG`に対応する閉じ括弧の直後。
「括弧でくくられた第一引数」の項を参照。
* `EXPR_FNAME`
メソッド名の前。具体的には`def`・`alias`・`undef`・シンボルの`':'`の
直後である。「```」が単独で名前になる。
* `EXPR_DOT`
メソッド呼び出しのドットのあと。`EXPR_FNAME`と扱いは似ている。
あらゆる予約語がただの識別子として扱われる。
`'`'`が単独で名前になる。
* `EXPR_CLASS`
予約語`class`の後ろ。この状態だけはかなり限定的である。
まとめると、
* `BEG MID`
* `END ENDARG`
* `ARG CMDARG`
* `FNAME DOT`
はそれぞれ似たような状況を表す。`EXPR_CLASS`だけはちょっと特殊だが、
出てくる場所が非常に限定されているのでそもそもあまり考えなくて済む。
h2. 改行の制御
h3. 問題
Rubyの文には必ずしも終端が必要なかった。例えばCやJavaでは必ず文末に
セミコロンを置かないといけないが、Rubyではそういうものは必要ない。
一行一文が基本なので、行末で勝手に文が終わるのである。
ところがその一方で「明らかに続きがある」場合は自動的に文が継続すること
になっている。「明らかに続きがある」状態とは、
* カンマのあと
* インフィックス演算子のあと
* 括弧がバランスしていない
* 予約語`if`の直後
などである。
h3. 実装
このような文法を実現するためにはどうしたらいいのだろう。単にスキャナで
改行を読み飛ばすだけではだめである。Rubyのように文の両端が予約語で区切
られている文法ならC言語ほどは衝突しないが、軽く試してみたところ、`return`、
`next`、`break`、メソッド呼び出しの括弧省略は全て削らないと通らなかった。
そういうものを残しておくには文末にはなんらかの終端記号がないといけない。
それが`\n`であるか`';'`であるかは問わないが、とにかくなんらかの終端記号は
必要なのだ。
そこで解決策は二つある。即ちパーサで解決するかスキャナで解決するかだ。
パーサで解決するとしたら、`\n`が許されるところ全てにオプションで`\n`を置
けるような文法を書いてしまえばよい。スキャナで解決するなら、`\n`に意味の
あるところでだけ`\n`をパーサに渡せばよい(その他の場所で読み飛ばす)。
どちらを使うかは趣味の問題だが、普通はスキャナで対応する。そのほうがた
いていコードがコンパクトになるし、どうでもいい記号で規則がぐちゃぐちゃ
になってしまったらパーサジェネレータを使う意味がなくなってしまうからだ。
そういうわけで結論から言うと`ruby`でも改行にはスキャナで対応する。行を継
続したいときは`\n`を読み飛ばし、終端したいときは`\n`をトークンとして送る。
それが`yylex()`のここだ。
▼ `yylex()`-`'\n'`
<pre class="longlist">
3155 case '\n':
3156 switch (lex_state) {
3157 case EXPR_BEG:
3158 case EXPR_FNAME:
3159 case EXPR_DOT:
3160 case EXPR_CLASS:
3161 goto retry;
3162 default:
3163 break;
3164 }
3165 command_start = Qtrue;
3166 lex_state = EXPR_BEG;
3167 return '\n';
(parse.y)
</pre>
`EXPR_BEG`・`EXPR_FNAME`・`EXPR_DOT`・`EXPR_CLASS`では`goto retry`、
つまり意味がないので読み飛ばす。ラベル`retry`は`yylex()`の巨大`switch`の
前にある。
その他のところでは改行が意味を持つのでパーサに渡し、ついでに
`lex_state`を`EXPR_BEG`に戻す。改行が意味のあるところは即ち`expr`の切れめ
だからだ。
また`command_start`は当面無視しておくべきである。最初に言ったように、
一度にいろいろなところを追うと必ず混乱する。
具体的な例を少し見てみよう。さっそく添付の解析ツール
`rubylex-analyser`を使う。
<pre class="screen">
% rubylex-analyser -e '
m(a,
b, c) unless i
'
+EXPR_BEG
EXPR_BEG C "\nm" tIDENTIFIER EXPR_CMDARG
EXPR_CMDARG "(" '(' EXPR_BEG
0:cond push
0:cmd push
EXPR_BEG C "a" tIDENTIFIER EXPR_CMDARG
EXPR_CMDARG "," ',' EXPR_BEG
EXPR_BEG S "\n b" tIDENTIFIER EXPR_ARG
EXPR_ARG "," ',' EXPR_BEG
EXPR_BEG S "c" tIDENTIFIER EXPR_ARG
EXPR_ARG ")" ')' EXPR_END
0:cond lexpop
0:cmd lexpop
EXPR_END S "unless" kUNLESS_MOD EXPR_BEG
EXPR_BEG S "i" tIDENTIFIER EXPR_ARG
EXPR_ARG "\n" \n EXPR_BEG
EXPR_BEG C "\n" ' EXPR_BEG
</pre>
いろいろ出力が出ているが、ここで必要なのは左と真ん中の欄だけである。左
の欄は`yylex()`に入るの前の`lex_state`を示し、真ん中の欄はトークンとそ
の記号を示す。
まず最初のトークン`m`の前と第二引数`b`の前では、改行しているが`\n`がトー
クンの前にくっついていて終端記号として出てきていない。`lex_state`が
`EXPR_BEG` だからだ。
しかし下から二行目では`\n`が終端記号としても出てきている。`EXPR_ARG`だ
からだ。
というように、使っていけばいい。もうちょっとだけ例を見てみる。
<pre class="screen">
% rubylex-analyser -e 'class
C < Object
end'
+EXPR_BEG
EXPR_BEG C "class" kCLASS EXPR_CLASS
EXPR_CLASS "\nC" tCONSTANT EXPR_END
EXPR_END S "<" '<' EXPR_BEG
+EXPR_BEG
EXPR_BEG S "Object" tCONSTANT EXPR_ARG
EXPR_ARG "\n" \n EXPR_BEG
EXPR_BEG C "end" kEND EXPR_END
EXPR_END "\n" \n EXPR_BEG
</pre>
予約語`class`のあとは`EXPR_CLASS`なので改行が無視される。
しかしスーパークラス式`Object`のあとは`EXPR_ARG`なので`\n`が出てきた。
<pre class="screen">
% rubylex-analyser -e 'obj.
class'
+EXPR_BEG
EXPR_BEG C "obj" tIDENTIFIER EXPR_CMDARG
EXPR_CMDARG "." '.' EXPR_DOT
EXPR_DOT "\nclass" tIDENTIFIER EXPR_ARG
EXPR_ARG "\n" \n EXPR_BEG
</pre>
`'.'`の後は`EXPR_DOT`なので`\n`が無視された。
ところで、`class`は予約語のはずなのに、なんで`tIDENTIFIER`になるのだろう。
次の節に続く。
h2. 予約語と同じメソッド名
h3. 問題
Rubyでは予約語をメソッド名に使うことができる。ただしメソッド名に使える
と一口に言ってもコンテキストがいくつかあって、
* メソッド定義(`def xxxx`)
* 呼び出し(`obj.xxxx`)
* シンボルリテラル(`:xxxx`)
という三つが考えられる。Rubyではこの全てが可能である。以下それぞれに
考えてみよう。
まずメソッド定義は、専用の予約語`def`が先行するのでなんとかなりそうだ。
メソッド呼び出しについては、レシーバを省略されるとかなり面倒なことにな
るのだが、実はさらに仕様が限定されていて、そういうのは許可されない。つ
まりメソッド名が予約語の場合は決してレシーバを省略できないのだ。あるい
は、ちゃんとパースできるようにそういう仕様になっていると言うべきかもし
れない。
そしてシンボルの場合は、やはり終端記号`':'`が先行するのでなんとか通せそう
である。ただしこの場合は予約語とは関係なく`':'`が`a?b:c`のコロンと衝突する
という問題がある。これさえ解決できればなんとかなる。
いずれのケースにしてもやはり方法は二つ考えられる。即ちスキャナで解決す
るかパーサで解決するかだ。スキャナで解決する場合、`def`や`.`や`:`の次に来る
予約語を`tIDENTIFIER`(など)にすればよい。パーサで解決するなら、そうい
う規則を書けばよい。`ruby`では三つそれぞれに両方を使い分けている。
h3. メソッド定義
メソッド定義の名前部分。ここではパーサ側で対処する。
▼ メソッド定義の規則
<pre class="longlist">
| kDEF fname
f_arglist
bodystmt
kEND
| kDEF singleton dot_or_colon fname
f_arglist
bodystmt
kEND
</pre>
メソッド定義を表す規則は二つだけで、それぞれ通常のメソッド定義と特異メ
ソッド定義に対応する。いずれも`fname`が名前部分で、その`fname`は次のように
定義されている。
▼ `fname`
<pre class="longlist">
fname : tIDENTIFIER
| tCONSTANT
| tFID
| op
| reswords
</pre>
`reswords`が予約語で`op`が二項演算子だ。どちらの規則も単に終端記号を全部並
べてあるだけなので省略する。それから`tFID`は`gsub!`や`include?`のように語尾
に記号が付くものである。
h3. メソッド呼び出し
予約語と同名のメソッド呼び出しに対してはスキャナで対処する。
予約語のスキャンのコードはこうなっていた。
<pre class="emlist">
識別子をスキャン
result = (tIDENTIFIERまたはtCONSTANT)
if (lex_state != EXPR_DOT) {
struct kwtable *kw;
/* See if it is a reserved word. */
kw = rb_reserved_word(tok(), toklen());
予約語を処理する
}
</pre>
`EXPR_DOT`がメソッド呼び出しドットの後を表す。`EXPR_DOT`のときには無条件で
予約語の処理を抜かすから、ドットの後の予約語の記号は`tIDENTIFIER`か
`tCONSTANT`になる。
h3. シンボル
予約語のシンボルはパーサとスキャナの両方で対処される。
まず規則から。
▼ `symbol`
<pre class="longlist">
symbol : tSYMBEG sym
sym : fname
| tIVAR
| tGVAR
| tCVAR
fname : tIDENTIFIER
| tCONSTANT
| tFID
| op
| reswords
</pre>
このように、パーサで明示的に予約語(`reswords`)を通すようにしている。こ
うできるのはあくまで`tSYMBEG`という専用の終端記号が前にあるからで、記号
が`':'`だったりしたらこううまくはいかない。条件演算子(`a?b:c`)と衝突して
おしまいだ。つまりスキャナレベルで`tSYMBEG`を見分けるのがポイントである
ことに変わりはない。
ではその区別はどうやっているのだろうか。スキャナの実装を見てみよう。
▼ `yylex`-`':'`
<pre class="longlist">
3761 case ':':
3762 c = nextc();
3763 if (c == ':') {
3764 if (lex_state == EXPR_BEG || lex_state == EXPR_MID ||
3765 (IS_ARG() && space_seen)) {
3766 lex_state = EXPR_BEG;
3767 return tCOLON3;
3768 }
3769 lex_state = EXPR_DOT;
3770 return tCOLON2;
3771 }
3772 pushback(c);
3773 if (lex_state == EXPR_END ||
lex_state == EXPR_ENDARG ||
ISSPACE(c)) {
3774 lex_state = EXPR_BEG;
3775 return ':';
3776 }
3777 lex_state = EXPR_FNAME;
3778 return tSYMBEG;
(parse.y)
</pre>
前半の`if`は`':'`が二つ続いた場合。このときは最左最長一致原則で
優先的に`'::'`をスキャンする。
その次の`if`は先程言った条件演算子の`':'`だ。`EXPR_END`と`EXPR_ENDARG`は
どちらも式の終わりだから、引数が来ない……つまりシンボルはありえないので
条件演算子の`':'`にする。
また次の文字がスペースだった(`ISSPACE(c)`)ときもシンボルでは
なさそうなので条件演算子だ。
そして上記のどちらでもない場合は全てシンボルである。そのときは
`EXPR_FNAME`に遷移してあらゆるメソッド名に備える。パースではなんでも困ら
ないのだが、これを忘れるとスキャナが予約語に対して値を渡してくれないの
で値の計算が変になる。
h2. 修飾子
h3. 問題
例えば`if`には通常の記法と後置修飾するものがある。
<pre class="emlist">
# 通常記法
if cond then
expr
end
# 後置
expr if cond
</pre>
これも衝突の原因になる。なぜかというと、これまたやっぱりメソッド括弧の
省略が原因である。例えばこんな場合だ。
<pre class="emlist">
call if cond then a else b end
</pre>
この式は`if`まで読んだところで次の二通りに解釈できる。
<pre class="emlist">
call((if ....))
call() if ....
</pre>
よくわからなければものは試しで、衝突するかどうかやってみよう。文法の中
の`kIF_MOD`を`kIF`に変えて`yacc`で処理してみる。
<pre class="screen">
% yacc parse.y
parse.y contains 4 shift/reduce conflicts and 13 reduce/reduce conflicts.
</pre>
目論見通り衝突しまくっている。興味があれば`yacc`に`-v`オプションを
付けてログを取り、中を読んでみよう。どう衝突したのか詳細に書いてある。
h3. 実装
さてどうしたらいいだろうか。`ruby`では普通の`if`を`kIF`、後置の`if`を
`kIF_MOD`というように記号レベルで(つまりスキャナレベルで)区別してし
まう。他の後置系演算子も全く同じで、
`kUNLESS_MOD kUNTIL_MOD kWHILE_MOD` `kRESCUE_MOD`に`kIF_MOD`の
合わせて五種類がある。この判断を行っているのは次のところだ。
▼ `yylex`-予約語
<pre class="longlist">
4173 struct kwtable *kw;
4174
4175 /* See if it is a reserved word. */
4176 kw = rb_reserved_word(tok(), toklen());
4177 if (kw) {
4178 enum lex_state state = lex_state;
4179 lex_state = kw->state;
4180 if (state == EXPR_FNAME) {
4181 yylval.id = rb_intern(kw->name);
4182 }
4183 if (kw->id[0] == kDO) {
4184 if (COND_P()) return kDO_COND;
4185 if (CMDARG_P() && state != EXPR_CMDARG)
4186 return kDO_BLOCK;
4187 if (state == EXPR_ENDARG)
4188 return kDO_BLOCK;
4189 return kDO;
4190 }
4191 if (state == EXPR_BEG) /*** ここ ***/
4192 return kw->id[0];
4193 else {
4194 if (kw->id[0] != kw->id[1])
4195 lex_state = EXPR_BEG;
4196 return kw->id[1];
4197 }
4198 }
(parse.y)
</pre>
これがあるのは`yylex`の末尾、識別子をスキャンしたあとだ。最後の(一番内
側の)`if`〜`else`が修飾子を扱う部分である。`EXPR_BEG`かどうかで返り値を
変えていることがわかる。ここが修飾子かどうかの判定だ。つまり変数`kw`が
カギである。そして`kw`は……とずっと上を見ていくと、`struct kwtable`だと
わかる。
`struct kwtable`は`keywords`内で定義されている構造体で、
ハッシュ関数`rb_reserved_word()`は`gperf`が作ってくれるということは
前章で話した。もう一度構造体を紹介しよう。
▼ `keywords `- `struct kwtable`
<pre class="longlist">
1 struct kwtable {char *name; int id[2]; enum lex_state state;};
(keywords)
</pre>
`name`と`id[0]`については説明済みである。予約語名とその記号だ。
今回は残りのメンバについて話す。
まず`id[1]`がいま問題の修飾子に対応する記号である。例えば`if`なら
`kIF_MOD`だ。
修飾子版がない予約語だと`id[0]`と`id[1]`には同じものが入っている。
そして`state`は`enum lex_state`だから、予約語を読んだあとに遷移すべき状態だ。
とりあえずその組み合わせを一覧しておく。この出力は筆者の自作
ツール`kwstat.rb`で得られる。これも添付CD-ROMに収録し
た\footnote{`kwstat`:添付CD-ROMの`tools/kwstat.rb`}。
<pre class="screen">
% kwstat.rb ruby/keywords
---- EXPR_ARG
defined? super yield
---- EXPR_BEG
and case else ensure if module or unless when
begin do elsif for in not then until while
---- EXPR_CLASS
class
---- EXPR_END
BEGIN __FILE__ end nil retry true
END __LINE__ false redo self
---- EXPR_FNAME
alias def undef
---- EXPR_MID
break next rescue return
---- modifiers
if rescue unless until while
</pre>
h2. `do`の衝突
h3. 問題
イテレータの書式には`do`〜`end`と`{`〜`}`の二種類があるのだった。この二つの
違いは優先順で、`{`〜`}`のほうがずっと高い。優先順位が高いということは
文法として単位が「小さい」ということで、より小さい規則に入れることが
できる。例えば`stmt`でなく`expr`や`primary`に入れることができる。例えば
昔は`{`〜`}`イテレータが`primary`で`do`〜`end`イテレータが`stmt`にあった。
ところが途中で次のような式に対する要求が出てきた。
<pre class="emlist">
m do .... end + m do .... end
</pre>
これを許すには`do`〜`end`イテレータを`arg`や`primary`に入れればいい。
ところが`while`の条件式は`expr`、つまり`arg`や`primary`を含むので、
ここで`do`が衝突してしまう。具体的には次のようなときだ。
<pre class="emlist">
while m do
....
end
</pre>
ちょっと見では`do`は`while`の`do`になるのが正しそうである。しか
しよくよく見ると`m do`〜`end`というくくりも考えられる。人間が混同でき
るということは`yacc`なら確実に衝突する。実際にやってみよう。
<pre class="emlist">
/* doの衝突の実験 */
%token kWHILE kDO tIDENTIFIER kEND
%%
expr: kWHILE expr kDO expr kEND
| tIDENTIFIER
| tIDENTIFIER kDO expr kEND
</pre>
`while`、変数参照、イテレータだけに問題を単純化した。この規則は条件式の
冒頭に`tIDENTIFIER`が来るとshift/reduce conflictを起こす。`tIDENTIFIER`を
変数参照にして`do`を`while`に付けるのが還元、イテレータの`do`にするのが
シフトだ。
悪いことにshift/reduce conflictはシフト優先なので放置しておくと`do`はイ
テレータの`do`になる。かと言って演算子優先順位その他で還元に倒すと`do`が全
くシフトされなくなり、`do`それ自体が使えなくなる。つまり全ての問題を矛
盾なく解決するには、`do`〜`end`イテレータを`expr`にすることなく演算子が使え
る規則を書くか、スキャナレベルで解決するしかない。
しかし`do`〜`end`イテレータを`expr`に入れないというのはとても非現実的である。
`expr`のための規則(ということは`arg`と`primary`もだ)を全て繰り返さないと
いけなくなる。従ってこの問題はスキャナで解決するのが適切だ。
h3. 規則レベルの解決
以下に関連規則を簡約化したものを示す。
▼ `do`の記号
<pre class="longlist">
primary : kWHILE expr_value do compstmt kEND
do : term
| kDO_COND
primary : operation brace_block
| method_call brace_block
brace_block : '{' opt_block_var compstmt '}'
| kDO opt_block_var compstmt kEND
</pre>
見てのとおり、`while`の`do`とイテレータの`do`で終端記号が違う。
`while`が`kDO_COND`、イテレータが`kDO`だ。あとはスキャナでこの
区別をすればよい。
h3. 記号レベルの解決
以下は、何度も見てきた`yylex`の予約語の処理部分の一部である。
`do`の処理をしているのはここだけなので、ここのコードを
調べれば判断基準がわかるはずだ。
▼ `yylex`-識別子-予約語
<pre class="longlist">
4183 if (kw->id[0] == kDO) {
4184 if (COND_P()) return kDO_COND;
4185 if (CMDARG_P() && state != EXPR_CMDARG)
4186 return kDO_BLOCK;
4187 if (state == EXPR_ENDARG)
4188 return kDO_BLOCK;
4189 return kDO;
4190 }
(parse.y)
</pre>
ぐちゃぐちゃとあるが、`kDO_COND`に関係するところだけ見ればよい。なぜなら、
`kDO_COND`と`kDO`/`kDO_BLOCK`という比較、`kDO`と`kDO_BLOCK`という
比較は意味があるが、それ以外の比較は意味がないからだ。いまは条件の
`do`さえ区別できればよいのであって、他の条件を一緒に追ってはいけない。
つまり`COND_P()`が鍵となる。
h3. `COND_P()`
h4. `cond_stack`
`COND_P()`は`parse.y`の先頭近くで定義されている。
▼ `cond_stack`
<pre class="longlist">
75 #ifdef HAVE_LONG_LONG
76 typedef unsigned LONG_LONG stack_type;
77 #else
78 typedef unsigned long stack_type;
79 #endif
80
81 static stack_type cond_stack = 0;
82 #define COND_PUSH(n) (cond_stack = (cond_stack<<1)|((n)&1))
83 #define COND_POP() (cond_stack >>= 1)
84 #define COND_LEXPOP() do {\
85 int last = COND_P();\
86 cond_stack >>= 1;\
87 if (last) cond_stack |= 1;\
88 } while (0)
89 #define COND_P() (cond_stack&1)
(parse.y)
</pre>
型`stack_type`は`long`(32ビット以上)か`long long`(64ビット以上)だ。
`cond_stack`はパース開始時に`yycompile()`で初期化され、後は常にマクロ
経由で扱われるので、そのマクロを把握すればよい。
そのマクロ`COND_PUSH`/`POP`を見ると、どうやら整数をビット単位のスタック
として使うようである。
<pre class="emlist">
MSB← →LSB
...0000000000 初期値0
...0000000001 COND_PUSH(1)
...0000000010 COND_PUSH(0)
...0000000101 COND_PUSH(1)
...0000000010 COND_POP()
...0000000100 COND_PUSH(0)
...0000000010 COND_POP()
</pre>
そして`COND_P()`はというと、最下位ビット(LSB)が1かどうか
判定しているから、スタックの先頭が1かどうかの判定ということになる。
残る`COND_LEXPOP()`はちょっと不思議な動きだ。現在の`COND_P()`を
スタック先頭に残したまま右シフトしている。つまり下から2ビットめを
1ビットめで踏み潰すようになる。
<pre class="emlist">
MSB← →LSB
...0000000000 初期値0
...0000000001 COND_PUSH(1)
...0000000010 COND_PUSH(0)
...0000000101 COND_PUSH(1)
...0000000011 COND_LEXPOP()
...0000000100 COND_PUSH(0)
...0000000010 COND_LEXPOP()
</pre>
これがどういう意味を持つのかは後で説明しよう。
h4. 目的の調査
ではこのスタックの目的を調べるために、
`COND_PUSH() COND_POP()`を使っているところを全部リストアップしてみよう。
<pre class="emlist">
| kWHILE {COND_PUSH(1);} expr_value do {COND_POP();}
--
| kUNTIL {COND_PUSH(1);} expr_value do {COND_POP();}
--
| kFOR block_var kIN {COND_PUSH(1);} expr_value do {COND_POP();}
--
case '(':
:
:
COND_PUSH(0);
CMDARG_PUSH(0);
--
case '[':
:
:
COND_PUSH(0);
CMDARG_PUSH(0);
--
case '{':
:
:
COND_PUSH(0);
CMDARG_PUSH(0);
--
case ']':
case '}':
case ')':
COND_LEXPOP();
CMDARG_LEXPOP();
</pre>
ここから次のような法則を発見できる。
* 条件式の最初で`PUSH(1)`
* 開き括弧で`PUSH(0)`
* 条件式の終わりで`POP()`
* 閉じ括弧で`LEXPOP()`
とすると、なんとなく
使い道が見えてくる。`cond_stack`という名前も考えると、条件式と同じレベルに
いるかどうか判定するマクロに違いない(図2)。
!images/ch_contextual_condp.jpg(`COND_P()`の移り変わり)!
この仕掛けによって次のような場合にもうまく対処できるようになる。
<pre class="emlist">
while (m do .... end) # doはイテレータのdo(kDO)
....
end
</pre>
ということは、32ビットマシンで`long long`がない場合には括弧か条件式が
32レベルネストしたあたりで変なことになる可能性がある。とはいえ普通は
そんなにネストしないから実害は出ない。
また`COND_LEXPOP()`の定義がちょっと不思議なことになっていたのは、どうやら
先読み対策らしい。ただ現在はうまいこと先読みが起こらないような規則に
なっているために`POP`と`LEXPOP`を分ける意味がなくなっている。つまり
現時点では「`COND_LEXPOP()`は無意味」という解釈が正しい。
h2. `tLPAREN_ARG`(1)
h3. 問題
この問題は、非常にややこしい。これが通るようになったのは`ruby` 1.7に
なってから、それもごく最近の話である。どういうことかというと……
<pre class="emlist">
call (expr) + 1
</pre>
を
<pre class="emlist">
(call(expr)) + 1
call((expr) + 1)
</pre>
のどちらに解釈するか、という話だ。以前は全て前者のように処理されてい
た。つまり括弧は常に「メソッド引数の括弧」だった。しかし
`ruby` 1.7では後者のように処理されるようになったのである。
つまり空白が入ると括弧は「`expr`の括弧」になる。
なぜ解釈が変わったのか、例を紹介しておこう。まず次のような文を書いた。
<pre class="emlist">
p m() + 1
</pre>
ここまでなら問題はない。しかし`m`の返す値が実は小数で、桁数が多す
ぎたとしよう。そこで表示するときは整数にしてしまうことにする。
<pre class="emlist">
p m() + 1 .to_i # ??
</pre>
しまった、括弧が必要だ。
<pre class="emlist">
p (m() + 1).to_i
</pre>
これはどう解釈されるだろうか? 1.6までなら、これは
<pre class="emlist">
(p(m() + 1)).to_i
</pre>
となる。つまりせっかく付けた`to_i`が何の意味もなくなってしまう。これは困る。
そこで括弧との間に空白がある場合だけは特別扱いして`expr`の括弧にすることに
したのである。
自分で調査してみたい人のために書いておくと、
この変更が実装されたのは`parse.y`のリビジョン1.100(2001-05-31)である。
だから1.99との差分を見ていくと比較的わかりやすい。
差分を取るコマンドはこうだ。
<pre class="screen">
~/src/ruby % cvs diff -r1.99 -r1.100 parse.y
</pre>
h3. 調査
まず現実に仕組みがどう動いているか見てみることにしよう。添付の
ツール`ruby-lexer`\footnote{`ruby-lexer`:添付CD-ROMの`tools/ruby-lexer.tar.gz`}を
使うとプログラムに対応する記号列を調べられる。
<pre class="screen">
% ruby-lexer -e 'm(a)'
tIDENTIFIER '(' tIDENTIFIER ')' '\n'
</pre>
`-e`は`ruby`と同じくプログラムをコマンドラインから直接渡すオプションだ。
これを使っていろいろ試してみよう。
まず問題の、第一引数が括弧でくくられている場合。
<pre class="screen">
% ruby-lexer -e 'm (a)'
tIDENTIFIER tLPAREN_ARG tIDENTIFIER ')' '\n'
</pre>
スペースを入れたら開き括弧の記号が`tLPAREN_ARG`になった。
ついでに普通の式括弧も見ておこう。
<pre class="screen">
% ruby-lexer -e '(a)'
tLPAREN tIDENTIFIER ')' '\n'
</pre>
普通の式括弧は`tLPAREN`らしい。
まとめるとこうなる。