-
Notifications
You must be signed in to change notification settings - Fork 12
/
Copy pathchapter12.txt
1623 lines (1312 loc) · 60.9 KB
/
chapter12.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. 第12章 構文木の構築
h2. ノード
h3. `NODE`
既に書いたようにRubyプログラムはいったん構文木に変換される。
そして構文木とは具体的に何かと言うと、「ノード(node)」と呼ばれる
構造体で作られるツリー構造である。`ruby`ではノードは全て`NODE`型で
表わされる。
▼ `NODE`
<pre class="longlist">
128 typedef struct RNode {
129 unsigned long flags;
130 char *nd_file;
131 union {
132 struct RNode *node;
133 ID id;
134 VALUE value;
135 VALUE (*cfunc)(ANYARGS);
136 ID *tbl;
137 } u1;
138 union {
139 struct RNode *node;
140 ID id;
141 int argc;
142 VALUE value;
143 } u2;
144 union {
145 struct RNode *node;
146 ID id;
147 long state;
148 struct global_entry *entry;
149 long cnt;
150 VALUE value;
151 } u3;
152 } NODE;
(node.h)
</pre>
構造体名`RNode`から推測できるかもしれないが、ノードはRubyオブジェクト
である。つまりノードの生成と解放は`ruby`のガーベージコレクタが面倒をみる。
だから当然`flags`にはまずオブジェクト構造体の`basic.flags`と同じ役割がある。
つまり構造体の型`T_NODE`や`FL_FREEZE`などのフラグを記録している。
`NODE`の場合はこれに加えてノードのタイプも`flags`に格納している。
どういうことだろうか。プログラムには`if`や`while`、`def`などいろいろな
要素があるので、それに対応してノードにもたくさん種類がある。それが
ノードのタイプである。`NODE`には複雑な共用体が三つ用意されているが、
この共用体の使いかたはそのノードのタイプによってただ一つに決定する。
例えば`if`のノード`NODE_IF`ならこうだ。
|メンバ|共用体メンバ|役割|
|`u1`|`u1.node`|条件式|
|`u2`|`u2.node`|真の本体|
|`u3`|`u3.node`|偽の本体|
また`node.h`ではこの共用体メンバにアクセスするためのマクロも用意されて
いる。
▼ `NODE`アクセス用マクロ
<pre class="longlist">
166 #define nd_head u1.node
167 #define nd_alen u2.argc
168 #define nd_next u3.node
169
170 #define nd_cond u1.node
171 #define nd_body u2.node
172 #define nd_else u3.node
173
174 #define nd_orig u3.value
:
:
(node.h)
</pre>
例えばこんなふうに使う。
<pre class="emlist">
NODE *head, *tail;
head->nd_next = tail; /* head->u3.node = tail */
</pre>
ソース中ではほぼ間違いなくこのマクロのほうが使われる。そのごくわずかな
例外は`parse.y`で`NODE`を生成しているところと`gc.c`で`NODE`をマークする
ところの二カ所だけである。
ところでこのようなマクロを使うのはなぜだろうか。一つは、`u1`のようにそれ
自体何も意味のない数字を覚えるのは面倒だからだろう。しかしそれ以上に重
要なのは、対応する数字は変わっても問題ないし、実際に変わる可能性がある
ことだ。例えば`if`の条件節が`u1`に入っている必然性はないので、なんらかの理
由で`u2`に変えたくなるかもしれない。しかし`u1`を直接使っていたらソースコー
ドのあちこちを直してまわらないとならず、不便である。ノードは全部`NODE`で
宣言されるから、`if`を表すノードを探すのは大変だ。アクセス用のマクロを用
意しておけばそんなことはなくなるし、逆にマクロからノードの種類を判定す
ることもできるようになる。
h3. ノードタイプ
`NODE`構造体の`flags`にはノードの種類が記憶されていると言った。
この情報の記憶方法を見ておこう。ノードタイプは`nd_set_type()`で
セット、`nd_type()`で取得できる。
▼ `nd_type nd_set_type`
<pre class="longlist">
156 #define nd_type(n) (((RNODE(n))->flags>>FL_USHIFT)&0xff)
157 #define nd_set_type(n,t) \
158 RNODE(n)->flags = ((RNODE(n)->flags & ~FL_UMASK) \
| (((t)<<FL_USHIFT) & FL_UMASK))
(node.h)
</pre>
▼ `FL_USHIFT FL_UMASK`
<pre class="longlist">
418 #define FL_USHIFT 11
429 #define FL_UMASK (0xff<<FL_USHIFT)
(ruby.h)
</pre>
`nd_type`あたりに注目していけばたいして苦労しない。
ようするに図1のようになっているらしい。
!images/ch_syntree_flagUsage.jpg(RNode.flagsの使われかた)!
それから、マクロだとデバッガで使えないので関数の`nodetype()`も
用意されている。
▼ `nodetype`
<pre class="longlist">
4247 static enum node_type
4248 nodetype(node) /* for debug */
4249 NODE *node;
4250 {
4251 return (enum node_type)nd_type(node);
4252 }
(parse.y)
</pre>
h3. ファイル名と行番号
`NODE`の`nd_file`にはこのノードに対応するテキストが存在していたファイル名
(へのポインタ)が保持されている。ファイル名があれば行番号もありそうだが
対応するメンバは見あたらない。実は行番号は以下のマクロによって`flags`に
埋めこまれているのである。
▼ `nd_line nd_set_line`
<pre class="longlist">
160 #define NODE_LSHIFT (FL_USHIFT+8)
161 #define NODE_LMASK (((long)1<<(sizeof(NODE*)*CHAR_BIT-NODE_LSHIFT))-1)
162 #define nd_line(n) \
((unsigned int)((RNODE(n)->flags >> NODE_LSHIFT) & NODE_LMASK))
163 #define nd_set_line(n,l) \
164 RNODE(n)->flags = ((RNODE(n)->flags & ~(-1 << NODE_LSHIFT)) \
| (((l)&NODE_LMASK) << NODE_LSHIFT))
(node.h)
</pre>
`nd_set_line()`などはなかなか壮観だ。だが、名前からして`nd_set_line()`と
`nd_line`が対称の働きをすることは間違いないので、簡単な`nd_line()`を調べて
パラメータの関係をつかんでしまえば`nd_set_line()`はそもそも解析する必要
がない。
まず`NODE_LSHIFT`だが、これは前項のノードタイプの話を見てくれば想像
できる通り、`flags`の使われているビット数だ。`FL_USHIFT`が`ruby`のシステム
予約分(11ビット、`ruby.h`)、8がノードタイプ分である。
次に`NODE_LMASK`。
<pre class="emlist">
sizeof(NODE*) * CHAR_BIT - NODE_LSHIFT
</pre>
は残っているビット数。これを`restbits`とでも置いてみよう。すると
かなり簡単になる。
<pre class="emlist">
#define NODE_LMASK (((long)1 << restbits) - 1)
</pre>
つまり図2のようなことらしい。
1を引くとくり下がりが起こるところがポイントだ。
最終的に`NODE_LMASK`はまだ使えるビット分の1の並びだとわかる。
!images/ch_syntree_lmask.jpg(`NODE_LMASK`)!
では改めて`nd_line()`を見てみよう。
<pre class="emlist">
(RNODE(n)->flags >> NODE_LSHIFT) & NODE_LMASK
</pre>
右シフトで未使用ビット領域をLSBまで落とす。bit andでその未使用ビット領
域だけを残す。つまり`flags`の使われかたをまとめると図3のよう
になる。`FL_USHIFT`は11だったから、32ビットマシンでは 32-(10+8)=13 ビッ
ト分が行番号に使えるということだ。
!images/ch_syntree_flags.jpg(`NODE`での`flags`の使いかた)!
……ということは、行番号が 2^13=8192 を超えると行番号表示が
おかしくなるはずである。試そう。
<pre class="emlist">
File.open('overflow.rb', 'w') {|f|
10000.times { f.puts }
f.puts 'raise'
}
</pre>
筆者の686マシンでは`ruby overflow.rb`でキッチリ1809行と表示された。成
功である。ただし64ビットマシンではもう少しファイルを大きくしないとうま
く失敗できないだろう。
h3. `rb_node_newnode()`
最後に、ノードを生成する関数`rb_node_newnode()`を見よう。
▼ `rb_node_newnode()`
<pre class="longlist">
4228 NODE*
4229 rb_node_newnode(type, a0, a1, a2)
4230 enum node_type type;
4231 NODE *a0, *a1, *a2;
4232 {
4233 NODE *n = (NODE*)rb_newobj();
4234
4235 n->flags |= T_NODE;
4236 nd_set_type(n, type);
4237 nd_set_line(n, ruby_sourceline);
4238 n->nd_file = ruby_sourcefile;
4239
4240 n->u1.node = a0;
4241 n->u2.node = a1;
4242 n->u3.node = a2;
4243
4244 return n;
4245 }
(parse.y)
</pre>
`rb_newobj()`は第5章『ガ-ベージコレクション』で見た。空いている`RVALUE`を一つ取得する
関数である。これに構造体型フラグ`T_NODE`を付けたところで`VALUE`として
の初期化は完了。`u1 u2 u3`にはもちろん`NODE*`以外の値を受けることもあ
るのだが、とりあえず`NODE*`でまとめて受けておく。`ruby`の構文木には
`double`などは入らないのでポインタで受けておけばサイズが小さすぎるといっ
た心配はない。
ここまでわかったら、あとは細部は忘れて、`NODE`とは
* `flags`
* `nodetype`
* `nd_line`
* `nd_file`
* `u1`
* `u2`
* `u3`
の七つのメンバを持つ構造体だと思っていればよい。
h2. 構文木の構築
パーサの役割はバイト列であるソースコードを構文木に変換することだった。
文法が通るだけではその仕事の半分もこなせていないのであって、ノードを組
み立てて木を作らなければならない。この節ではその構文木の構築過程を見て
いこう。
h3. `YYSTYPE`
本章はようするにアクションの話だから、`$$`や`$1`の型である
`YYSTYPE`が重要になってくる。そこでまず`ruby`の`%union`を見てみよう。
▼ `%union`宣言
<pre class="longlist">
170 %union {
171 NODE *node;
172 ID id;
173 int num;
174 struct RVarmap *vars;
175 }
(parse.y)
</pre>
`struct RVarmap`は評価器の構造体で、ブロックローカル変数を格納する。
あとはいいだろう。一番使うのはもちろん`node`である。
h3. 構文木のある風景
まず事実を見る、というのがコード読みのセオリーであった。今はどういう構
文木ができるのかを知りたいわけだから、まずその答え(構文木)を見ること
から始めるべきだ。
いちいちデバッガで見てみるのでもよいが、添付CD-ROMに収録したツール
`nodedump`\footnote{`nodedump`:添付CD-ROMの`tools/nodedump.tar.gz`}を
使うともっと手軽に構文木を視覚化することができる。このツールは
Pragmatic Programmers\footnote{Pragmatic Programmers ^http://www.pragmaticprogrammers.com}作の
NodeDumpを本書用に改造したものだ。
オリジナルはかなり説明的な出力をしてくれるのだが、こちらの改造版では
構文木の姿を徹底的にダイレクトに出力するようにしている。
例えば`m(a)`という単純な式をダンプするにはこうすればいい。
<pre class="screen">
% ruby -rnodedump -e 'm(a)'
NODE_NEWLINE
nd_file = "-e"
nd_nth = 1
nd_next:
NODE_FCALL
nd_mid = 9617 (m)
nd_args:
NODE_ARRAY
nd_alen = 1
nd_head:
NODE_VCALL
nd_mid = 9625 (a)
nd_next = (null)
</pre>
`-r`オプションでロードするライブラリを指定し、`-e`でプログラムを渡す。
するとそのプログラムの構文木表現がダンプされる。
中身の見かたを簡単に説明しよう。`NODE_NEWLINE`や`NODE_FCALL`というのが
ノードタイプだ。それと同じインデントに書いてあるものがそのノードのメン
バの内容である。例えばルートには`NODE_NEWLINE`があり、そのメンバは
`nd_file nd_nth nd_next `の三つ。`nd_file`はCの文字列`"-e"`を指し、
`nd_nth`はCの整数1を指し、`nd_next `には次のノード`NODE_CALL`が格納さ
れている。と言葉で言ってもわかりにくいだろうから、図4と対照
してみてほしい。
!images/ch_syntree_stree.jpg(構文木)!
各ノードの意味を説明すると、`NODE_FCALL`はFunction CALL。
`NODE_ARRAY`はその名前の通り配列のノードで、ここでは引数のリストを
表している。`NODE_VCALL`はVariable or CALLで、未定義のローカル変数を
参照するとこれになる。
では`NODE_NEWLINE`はなんだろう。これは、実行時に実行中のファイル名と行
番号を合わせるためのノードで、`stmt`一つにつき一つセットされる。だから
実行の意味を考えるうえではこのノードは無視してもよい。また`nodedump`の
かわりに`nodedump-short`を`require`するとそもそも`NODE_NEWLINE`のよ
うな邪魔なものは省略して表示してくれる。単純なほうが見やすいから、今後
は特に書かない限り`nodedump-short`を使う。
以下では構文木全体の様子をとらえるために三つのタイプの構成要素を
見ていく。まず最初に構文木の葉(leaf)。次にその組み合わせである式、
即ち構文木の枝。最後に、文を並べるためのリストつまり構文木の幹だ。
h3. 葉
まずは末端、構文木の葉の部分から見よう。
リテラルや変数参照など、
規則で言うと`primary`の中の特に単純なものがこれに当たる。
<pre class="screen">
% ruby -rnodedump-short -e '1'
NODE_LIT
nd_lit = 1:Fixnum
</pre>
数値の1。なんのヒネリもない。ただしここでノードに入っているのは
Cの1ではなくてRubyの1(`Fixnum`の1)であることには注意。なぜかと
言うと……
<pre class="screen">
% ruby -rnodedump-short -e ':sym'
NODE_LIT
nd_lit = 9617:Symbol
</pre>
このように、`Symbol`も構文木になると同じ`NODE_LIT`で表現されるからだ。
こうやって常に`nd_lit`に`VALUE`を入れるようにしておけば、`Symbol`だろ
うと`Fixnum`だろうと実行するときには全く同じように扱うことができる。つ
まり、`nd_lit`の値を取り出して返すだけでよくなる。構文木というのは
実行するために作るものなのだから、実行に都合がいいように作るのが正しい。
<pre class="screen">
% ruby -rnodedump-short -e '"a"'
NODE_STR
nd_lit = "a":String
</pre>
文字列。これもRubyの文字列である。
文字列リテラルは実際に使うときにはコピーする。
<pre class="screen">
% ruby -rnodedump -e '[0,1]'
NODE_NEWLINE
nd_file = "-e"
nd_nth = 1
nd_next:
NODE_ARRAY
nd_alen = 2
nd_head:
NODE_LIT
nd_lit = 0:Fixnum
nd_next:
NODE_ARRAY
nd_alen = 1
nd_head:
NODE_LIT
nd_lit = 1:Fixnum
nd_next = (null)
</pre>
配列。これは葉とは言えないが、リテラルつながりなのでよしとしよう。
`NODE_ARRAY`のリストに各要素のノードがぶらさがっている感じだろうか。
これだけ`nodedump-short`を使わない理由は……この節を最後まで読めばわかる。
h3. 枝
次は枝にあたる部分……「組み合わせ」に注目する。
例に取るのは`if`だ。
h4. `if`
なにかと言うと`if`ばかり例にしているような気がするが、それはなにしろ構造
が単純だし、`if`を知らない読者はいないので書くほうからすると便利なのだ。
それはともあれ`if`の例。例えばこんなコードを構文木化してみよう。
▼ ソースプログラム
<pre class="longlist">
if true
'true expr'
else
'false expr'
end
</pre>
▼ その構文木表現
<pre class="longlist">
NODE_IF
nd_cond:
NODE_TRUE
nd_body:
NODE_STR
nd_lit = "true expr":String
nd_else:
NODE_STR
nd_lit = "false expr":String
</pre>
ここでは前述の`nodedump-short`を使っているので`NODE_NEWLINE`が消えてい
る。`nd_cond`が条件、`nd_body`が真の場合の本体、`nd_else`が偽
の場合の本体である。
では今度はこれを作っているコードを見てみよう。
▼ `if`の規則
<pre class="longlist">
1373 | kIF expr_value then
1374 compstmt
1375 if_tail
1376 kEND
1377 {
1378 $$ = NEW_IF(cond($2), $4, $5);
1379 fixpos($$, $2);
1380 }
(parse.y)
</pre>
`NEW_IF()`というのが`NODE_IF`を生成するマクロらしい。記号の値のうち
`$2 $4 $5`を使っているので、規則の記号と`$n`の対応をとってみると
<pre class="emlist">
kIF expr_value then compstmt if_tail kEND
$1 $2 $3 $4 $5 $6
NEW_IF(expr_value, compstmt, if_tail)
</pre>
となった。つまり`expr_value`が条件式、`compstmt`(`$4`)が真の場合、
`if_tail`が偽の場合だろう。
一方ノードを生成するマクロは全て`NEW_xxxx`という名前で、`node.h`で定義され
ている。`NEW_IF()`を見てみよう。
▼ `NEW_IF()`
<pre class="longlist">
243 #define NEW_IF(c,t,e) rb_node_newnode(NODE_IF,c,t,e)
(node.h)
</pre>
パラメータはそれぞれ`c`がcondition、`t`がthen、`e`がelseを表しているようだ。
前節で書いたようにノードではメンバの順番にはあまり意味がないので
こんなところでパラメータ名に凝ってみる必要はない。
またアクションで条件式のノードを処理している`cond()`は意味解析関数である。
これについては後述する。
それと`fixpos()`は行番号の補正を行っている。`NODE`は自分が「生成さ
れたときに」読み込んでいるファイル名と行番号で初期化される。だが`if`を
考えてみると、`NODE_IF`を作るときにはもう`end`までパースしているはずだ。
だからそのままにしておくと行番号がズレる。そこで`fixpos()`で補正すると
いうことになる。
<pre class="emlist">
fixpos(dest, src)
</pre>
で、ノード`dest`の行番号をノード`src`のものにする。`if`で言うなら、
`if`式全体の行番号は条件式の行番号になるということだ。
h4. `elsif`
続いて`if_tail`の規則も見てみよう。
▼ `if_tail`
<pre class="longlist">
1543 if_tail : opt_else
1544 | kELSIF expr_value then
1545 compstmt
1546 if_tail
1547 {
1548 $$ = NEW_IF(cond($2), $4, $5);
1549 fixpos($$, $2);
1550 }
1553 opt_else : none
1554 | kELSE compstmt
1555 {
1556 $$ = $2;
1557 }
(parse.y)
</pre>
まずこの規則は「ゼロ個以上の`elsif`節のあと`opt_else`で終わるリスト」
を表している。なぜなら、`elsif`が続いている限り`if_tail`が再現なく現れ、
`opt_else`が来ると消えるからだ。適当な回数だけ規則を展開してみればわか
る。
<pre class="emlist">
if_tail: kELSIF .... if_tail
if_tail: kELSIF .... kELSIF .... if_tail
if_tail: kELSIF .... kELSIF .... kELSIF .... if_tail
if_tail: kELSIF .... kELSIF .... kELSIF .... opt_else
if_tail: kELSIF .... kELSIF .... kELSIF .... kELSE compstmt
</pre>
そして次にアクションに注目すると、なんと、`elsif`では普通の
`if`と同じ`NEW_IF()`を使っている。つまり、以下の二つのプログラムは
構文木になってしまうと違いがなくなってしまうということだ。
<pre class="emlist">
if cond1 if cond1
body1 body1
elsif cond2 else
body2 if cond2
elsif cond3 body2
body3 else
else if cond3
body4 body3
end else
body4
end
end
end
</pre>
そう言われてみればC言語などは構文レベルでもこの二つの区別がないわけで、
当然と言えば当然かもしれない。他には条件演算子(`a?b:c`)も構文木になる
と`if`文と区別がつかなくなる。
文法上では大きな意味があった優先順位は構文木の構造自体がその情報を含ん
でいるのでもう必要ない。また`if`と条件演算子のような見ための違いに至っ
ては何の意味もなくなり、その意味(振舞い)だけが重要になる。だから`if`
と条件演算子の構文木表現が同じでも全く構わないのだ。
このような例をいくつか挙げてみよう。`and`と`&&`は同じになる。
`or`と`||`も同じだ。`not`と`!`、`if`と修飾`if`、などなども同じである。
h4. 左再帰と右再帰
ところで第9章『速習`yacc`』ではリストを表現するときは常にリストの記号を
左に書いていたが、`if_tail`では逆になっていたことに気付いただろうか。
肝心なところだけ以下に再掲する。
<pre class="emlist">
if_tail: opt_else
| kELSIF ... if_tail
</pre>
間違いなく今までと逆だ。リストの記号`if_tail`が右にある。
実はリストにはもう一つの定石があって、
<pre class="emlist">
list: END_ITEM
| ITEM list
</pre>
と書くと、`ITEM`ゼロ個以上が続き`END_ITEM`で終わるリストになるのだ。
リストの表現としてはどちらだろうとあまり重大な違いはないのだが、アクショ
ンの実行のされかたが致命的に違う。`list`を右に書く形式だと後ろの
`ITEM`から順番にアクションが実行されるのだ。左が`list`の場合のスタッ
クの動きはもうやったから、右に`list`がある場合を試してみよう。入力は
`ITEM`四つと`END_ITEM`である。
||最初は空|
|`ITEM`|`ITEM`をシフト|
|`ITEM ITEM`|`ITEM`をシフト|
|`ITEM ITEM ITEM`|`ITEM`をシフト|
|`ITEM ITEM ITEM ITEM`|`ITEM`をシフト|
|`ITEM ITEM ITEM ITEM END_ITEM`|`END_ITEM`をシフト|
|`ITEM ITEM ITEM ITEM list`|`END_ITEM`→`list`で還元|
|`ITEM ITEM ITEM list`|`ITEM list`→`list`で還元|
|`ITEM ITEM list`|`ITEM list`→`list`で還元|
|`ITEM list`|`ITEM list`→`list`で還元|
|`list`|`ITEM list`→`list`で還元|
||accept.|
「左が`list`」のときにはシフトと還元が交互に行われていたのに、
今回は見ての通りずっとシフト、ずっと還元で解析されている。
なぜ`if_tail`は「右に`list`」にしていたかというと、ボトムアップで構文木を
作るためだ。ボトムアップで作ると最後に`if`のノードが手元に残る。しかしも
し「左が`list`」で`if_tail`を定義すると、最後に手元に`if`のノードを残すため
には`elsif`を見付けるたびに`elsif`のリンクを全部辿っていって末尾に追加しな
ければいけなくなってしまうのだ。これは面倒くさい。ついでに遅い。だから
`if_tail`は「右が`list`」で構築してあるのだ。
最後に見出しの意味だが、文法用語だと
「左が`list`」を左再帰(left recursion)、
「右が`list`」を右再帰(right recursion)と言うのである。
この用語は主に文法処理の論文を読むときや`yacc`の本を書くときに使う。
h3. 幹
葉、枝と来たら最後は幹だ。
文のリストをどうつないでいるのか見よう。
▼ ソースプログラム
<pre class="longlist">
7
8
9
</pre>
これに対応する構文木をダンプすると次のようになる。
これは`nodedump-short`ではなく完全形である。
▼ 対応する構文木
<pre class="longlist">
NODE_BLOCK
nd_head:
NODE_NEWLINE
nd_file = "multistmt"
nd_nth = 1
nd_next:
NODE_LIT
nd_lit = 7:Fixnum
nd_next:
NODE_BLOCK
nd_head:
NODE_NEWLINE
nd_file = "multistmt"
nd_nth = 2
nd_next:
NODE_LIT
nd_lit = 8:Fixnum
nd_next:
NODE_BLOCK
nd_head:
NODE_NEWLINE
nd_file = "multistmt"
nd_nth = 3
nd_next:
NODE_LIT
nd_lit = 9:Fixnum
nd_next = (null)
</pre>
`NODE_BLOCK`のリストができており、それに`NODE_NEWLINE`がヘッダとして
くっついているのがわかる(図5)。
!images/ch_syntree_blocklist.jpg(`NODE_BLOCK`と`NODE_NEWLINE`)!
つまり文(`stmt`)に一つの割合で`NODE_NEWLINE`が付き、それが複数並ぶと
`NODE_BLOCK`でリスト化される。コードも見てみよう。
▼ `stmts`
<pre class="longlist">
354 stmts : none
355 | stmt
356 {
357 $$ = newline_node($1);
358 }
359 | stmts terms stmt
360 {
361 $$ = block_append($1, newline_node($3));
362 }
(parse.y)
</pre>
`newline_node()`で`NODE_NEWLINE`をかぶせ、
`block_append()`でリストをつなぐ。わかりやすい。
`block_append()`だけ中身を見ておこう。
h4. `block_append()`
この関数はド真ん中にエラーチェックがあって邪魔なので
その部分は省略して示す。
▼ `block_append()`(省略版)
<pre class="longlist">
4285 static NODE*
4286 block_append(head, tail)
4287 NODE *head, *tail;
4288 {
4289 NODE *end;
4290
4291 if (tail == 0) return head;
4292 if (head == 0) return tail;
4293
4294 if (nd_type(head) != NODE_BLOCK) {
4295 end = NEW_BLOCK(head);
4296 end->nd_end = end; /*(A-1)*/
4297 fixpos(end, head);
4298 head = end;
4299 }
4300 else {
4301 end = head->nd_end; /*(A-2)*/
4302 }
/* ……省略…… */
4325 if (nd_type(tail) != NODE_BLOCK) {
4326 tail = NEW_BLOCK(tail);
4327 tail->nd_end = tail;
4328 }
4329 end->nd_next = tail;
4330 head->nd_end = tail->nd_end; /*(A-3)*/
4331 return head;
4332 }
(parse.y)
</pre>
先の構文木ダンプによると`NODE_BLOCK`は`nd_next`を使ったリンクリストだった。
それに注意して読むと、「`head`と`tail`のどちらかが`NODE_BLOCK`でなかったら
`NODE_BLOCK`でくるみ、リスト同士を連結する」、と読める。
それと(A-1〜3)では、リスト先頭の`NODE_BLOCK`の`nd_end`が常にリスト末
尾の`NODE_BLOCK`を指すようにしている。こうしておけばいちいちリスト
を全部辿らなくても末尾に要素を連結できるからだろう(図6)。
逆に言えば、リストを追加する必要があるときは`NODE_BLOCK`が
適しているということだ。
!images/ch_syntree_append.jpg(追加が楽)!
h3. 二つのリスト
さて、ここまでで大枠は説明した。構文木の構造については第三部でも
大量に出てくるので、第二部ではこれくらいにしておこう。しかし終わる前に
もう一つだけ話しておきたい。それは二つの汎用リストのことだ。
二つのリストとは、`BLOCK`と`LIST`である。`BLOCK`は先程説明した
`NODE_BLOCK`のリンクリストで、文をつなぐためにある。`LIST`は、
`LIST`と言いつつもその実体は`NODE_ARRAY`のリストだ。配列リテラルに
使われていた奴である。`LIST`はメソッドの引数や多重代入のリストを
格納するために使われている。
この二つのリストの違いはノードの使いかたを見るとわかりやすい。
|`NODE_BLOCK`|`nd_head`|要素を格納する|
||`nd_end`|リスト最後の`NODE_BLOCK`を指す|
||`nd_next`|次の`NODE_BLOCK`を指す|
||||
|`NODE_ARRAY`|`nd_head`|要素を格納する|
||`nd_alen`|このノード以降のリストの長さ|
||`nd_next`|次の`NODE_ARRAY`を指す|
使いかたが違うのは二番目の要素、`nd_end`と`nd_alen`だけだ。
そしてこれがそれぞれの存在意義である。`NODE_ARRAY`はサイズを格納
できるので、頻繁にリストのサイズが必要になる場合は`ARRAY`リストを使う。
そうでない場合は連結が高速な`BLOCK`リストを使う。このへんは
使うほうのコードを見ないと意義がわからないので深くは話さないが、
第三部で登場したら「ああ、長さを使ってる」と思い出してほしい。
h2. 意味解析
第二部の最初で簡単にふれたが、一口にプログラムの解析と言っても見ための
解析と意味の解析の二つがある。見ための解析は`yacc`がほぼやってくれるので、
あとはアクションの中で意味の解析をすればいい。
h3. アクション内でのエラー
意味解析とは具体的にどんなことか。例えば型有り言語なら型の検査がある。
他には、同名の変数を何回も定義していないか、変数を定義前に使っていない
か、使っている手続きが定義されているか、手続きの外で`return`を使っていな
いか、などが意味解析に含まれる。
現在の`ruby`ではどんな意味解析を行っているだろうか。先程の例を見てみると
`ruby`ではエラーチェックが意味解析のほとんどを占めているので、エラーを出
しているところを探してみればよさそうだ。`yacc`のパーサではエラーが起きた
ときには`yyerror()`を呼ぶことになっている……逆に言うと`yyerror()`がある
ところではエラーが起きているということだ。そこでアクション中で
`yyerror()`を呼んでいる場所をリストアップしてみた。
* 値が必要な場所に値を持たない式(void value expression)
* `$n`の`alias`
* メソッド内での`BEGIN`
* メソッド内での`END`
* メソッド外の`return`
* 定数を要求されるところでのローカル変数
* メソッド内での`class`文
* 不適切なパラメータ変数(`$gvar`や`CONST`など)
* 同名のパラメータ変数が二回出てくる
* 不適切な特異メソッドのレシーバ(`def ().method`など)
* リテラルに対する特異メソッド定義
* ハッシュリテラルのリストが奇数
* `self/nil/true/false/__FILE__/__LINE__`への代入
* メソッド内での定数代入
* 条件式内での多重代入
これらのチェックはだいたい以下のような目的に分類できるだろう。
* よりよいエラーメッセージを出す
* 規則を複雑にしすぎない
* それ以外(純粋な意味解析)
例えば「メソッド外の`return`」は規則を複雑にしすぎないためのチェック
である。このエラーは構造の問題なのだから文法で対処できないことはない。
例えばメソッド内と外での文の規則を分割し、許されるものと許されない
ものをそれぞれ全部並べてやればいい。しかしどう考えても面倒だし、アク
ションでハネたほうがよほど簡潔だ。
また「`self`への代入」は、よいエラーメッセージを出すためのチェック
だと考えられる。これは「メソッド外`return`」よりも文法で除外するのは
ずっと簡単だが、パーサで除外すると単に`"parse error"`という出力
で終わってしまう。それよりは今の
<pre class="screen">
% ruby -e 'self = 1'
-e:1: Can't change the value of self
self = 1
^
</pre>
というエラーのほうがずっと親切である。
もちろんキッチリと「この目的」と言えるとは限らない。例えば
「メソッド外`return`」にしても、これはよいエラーメッセージを出すための
チェックだと考えることもできる。目的は重なりあっているものだ。
さて問題は「純粋な意味解析」だが、Rubyではこの分類に当てはまるものがあ
まりない。型付き言語だと型の解析が一大イベントなのだが、Rubyは変数が型
無しなので無意味である。代わりに目立ってくるのが値を持つ式のチェックだ。
値を持つ、を正確に言うと「評価すると値が得られる」となる。`return`や
`break`はそれ自体値を持たない。もちろん`return`先には値を渡すわけだが、
`return`が書いてある場所それ自体には値が残らない。だから例えば次のような
式は変だ。
<pre class="emlist">
i = return(1)
</pre>
こういう式は明らかに勘違い、あるいは単純ミスなのでコンパイル時点で
弾いてしまうほうがよい。以降はこの値を取ることを確認する関数の一つ、
`value_expr()`を見ていくことにする。
h3. `value_expr()`
`value_expr()`は値(value)を持つ`expr`であることをチェックする関数である。
▼ `value_expr()`
<pre class="longlist">
4754 static int
4755 value_expr(node)
4756 NODE *node;
4757 {
4758 while (node) {
4759 switch (nd_type(node)) {
4760 case NODE_CLASS:
4761 case NODE_MODULE:
4762 case NODE_DEFN:
4763 case NODE_DEFS:
4764 rb_warning("void value expression");
4765 return Qfalse;
4766
4767 case NODE_RETURN:
4768 case NODE_BREAK:
4769 case NODE_NEXT:
4770 case NODE_REDO:
4771 case NODE_RETRY:
4772 yyerror("void value expression");
4773 /* or "control never reach"? */
4774 return Qfalse;
4775
4776 case NODE_BLOCK:
4777 while (node->nd_next) {
4778 node = node->nd_next;
4779 }
4780 node = node->nd_head;
4781 break;
4782
4783 case NODE_BEGIN:
4784 node = node->nd_body;
4785 break;
4786
4787 case NODE_IF:
4788 if (!value_expr(node->nd_body)) return Qfalse;
4789 node = node->nd_else;
4790 break;
4791
4792 case NODE_AND:
4793 case NODE_OR:
4794 node = node->nd_2nd;
4795 break;
4796
4797 case NODE_NEWLINE:
4798 node = node->nd_next;
4799 break;
4800
4801 default:
4802 return Qtrue;
4803 }
4804 }
4805
4806 return Qtrue;
4807 }
(parse.y)
</pre>
h4. アルゴリズム
要約。ツリーを順番になめてみて「確実に値がない式」にぶちあたったらその
時点で値を持たないとわかる。`rb_warning()`で警告して`Qfalse`を返す。値のな
い式に当たらないままツリーをなめおわったら値を持つ。`Qtrue`を返す。
ここで、必ずしもツリー全体をチェックする必要はないことに注意してほしい。
例えば`value_expr()`がメソッドの引数に対して呼ばれたと仮定しよう。
ここだ。
▼ `arg`の値を`value_expr()`でチェック
<pre class="longlist">
1055 arg_value : arg
1056 {
1057 value_expr($1);
1058 $$ = $1;
1059 }
(parse.y)
</pre>
この引数`$1`の中にはまたメソッド呼び出しがネストしているかもしれない。し
かしその内側のメソッドの引数は既に`value_expr()`でチェックされているはず
なので、もう一度チェックする必要はない。
もっと一般的に考えよう。とある文法要素`A`があったとして、その全ての構
成要素に対して`value_expr()`を呼んだとしたら、その要素`A`をまたチェックし
なおす必要はなくなる。
では例えば`if`はどうだろうか。無条件に、全要素に対して`value_expr()`を
呼んだものとして扱えるだろうか。結論だけ言うと、そうはいかない。なぜ
なら文である(値を使わない)`if`ならば本体は値を返さなくともよいはずだ
からだ。例えば次のような場合。
<pre class="emlist">
def method
if true
return 1
else
return 2
end
5
end
</pre>
この`if`文には値は必要ない。
しかし次のような場合は値が必要だ。
<pre class="emlist">
def method( arg )
tmp = if arg
then 3
else 98
end
tmp * tmp / 3.5
end
</pre>
だからこの場合は代入文全体をチェックするときに初めて`if`文もチェックする
ようにしなければいけない。そういうものが`value_expr()`の`switch`文に並んで
いるわけである。