/
chapter10.txt
1960 lines (1581 loc) · 69.9 KB
/
chapter10.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
$comment(-*- coding: utf-8 -*- vim:set encoding=utf-8:)$
Translated by Robert GRAVINA
h1. Chapter 10: Parser
h2. Outline of this chapter
h3. Parser construction
The parser is defined in the `yacc` source file `parse.y`, which `yacc` uses to
produce a working parser, `parse.c`.
Although one would expect `lex.c` to contain the scanner this is not the case.
This file is created by `gperf`, taking the file `keywords` as input, and
defines the reserved word hashtable. This tool-generated `lex.c` is `#include`d
in (the also tool-generated) `parse.c`. The details of this process is somewhat
difficult to explain at this time, so we shall return to this later.
Figure 1 shows the parser construction process. For the benifit of those readers
using Windows who may not be aware, the `mv` (move) command creates a new copy
of a file and removes the original. `cc` is, of course, the C compiler and `cpp`
the C pre-processor.
!images/ch_parser_build.png(Parser construction process)!
h3. Disecting `parse.y`
Let's now look at `parse.y` in a bit more detail. The following figure presents
a rough outline of the contents of `parse.y`.
▼ parse.y
<pre class="longlist">
%{
header
%}
%union ....
%token ....
%type ....
%%
rules
%%
user code section
parser interface
scanner (character stream processing)
syntax tree construction
semantic analysis
local variable management
ID implementation
</pre>
Previously we briefly mentioned the rules and user code sections. With this
chapter we begin to study the parser in some detail and so turn our attention to
these sections.
There is a considerable number of support functions defined in the user code
section, however roughly speaking they can be divided into the six parts
previously mentioned. The following table shows where each of parts are
explained in this book.
|Category|Chapter|Section|
|Parser interface|This chapter|Section 3 "Scanning"|
|Scanner|This chapter|Section 3 "Scanning"|
|Syntax tree construction|Chapter 12 "Syntax tree construction"|Section 2 "Syntax tree construction"|
|Semantic analysos|Chapter 12 "Syntax tree construction"|Section 3 "Semantic analysis"|
|Local variable management|Chapter 12 "Syntax tree construction"|Section 4 "Local variables"|
|`ID` implementation|Chapter 3 "Names and name tables"|Section 2 "`ID` and symbols"|
h2. General remarks about grammar rules
h3. Coding rules
The grammar of `ruby` conforms to a coding standard and is thus easy to read
once you are familiar with it.
Firstly, regarding symbol names, all non-terminal symbols are written in lower
case characters. Terminal symbols are prefixed by some lower case character and
then followed by upper case. Reserved words (keywords) are prefixed with the
character `k`. Other terminal symbols are prefixed with the character `t`.
▼ Symbol name examples
|Token|Symbol name|
|(non-terminal symbol)|`bodystmt`|
|`if`|`kIF`|
|`def`|`kDEF`|
|`rescue`|`kRESCUE`|
|`varname`|`tIDENTIFIER`|
|`ConstName`|`tCONST`|
|1|`tINTEGER`|
The only exceptions to these rules are `klBEGIN` and `klEND`. These symbol names
refer to the reserved words for "BEGIN" and "END", respectively, and the `l`
here stands for `large`. Since the reserved words `begin` and `end` already
exist (naturally, with symbol names `kBEGIN` and `kEND`), these non-standard
symbol names were required.
h3. Important symbols
`parse.y` contains both grammar rules and actions, however for now I would like
to concentrate on the grammar rules alone. The script sample/exyacc.rb can be
used to extract the grammar rules from this file. Aside from this, running `yacc
-v` will create a logfile `y.output` which also contains the grammar rules,
however it is rather difficult to read. In this chapter I have used a slighty
modified version of `exyacc.rb`\footnote{modified `exyacc.rb`:`tools/exyacc2.rb`
located on the attached CD-ROM} to extract the grammar rules.
▼ `parse.y`(rules)
<pre class="longlist">
program : compstmt
bodystmt : compstmt
opt_rescue
opt_else
opt_ensure
compstmt : stmts opt_terms
:
:
</pre>
The output is quite long - over 450 lines of grammar rules - and as such I have
only included the most important parts in this chapter.
Which symbols, then, are the most important? Symbols such as `program`, `expr`,
`stmt`,`primary`, `arg` etc. represent the more general grammatical elements of
a programming language and it is to these which we shall focus our attention.
The following table outlines these general elements and the symbol names used
to represent them.
|Syntax element|Relevant symbol names|
|Program|`program prog file input stmts whole`|
|Sentence|`statement stmt`|
|Expression|`expression expr exp`|
|Smallest element|`primary prim`|
|Left hand side of an expression|`lhs`(left hand side)|
|Right hand side of an expression|`rhs`(right hand side)|
|Function call|`funcall function_call call function`|
|Method call|`method method_call call`|
|Argument|`argument arg`|
|Function definition|`defun definition function fndef`|
|Declarations|`declaration decl`|
In general, programming lanaguages tend to have the following symbol heiarchy.
|Program element|Properties|
|Statement|Can not be combined with other symbols. A syntax tree trunk.|
|Expression|Can be combined with itself or be part of other
expressions. A syntax tree interal node.|
|Primary|An element which can not be further decomposed. A syntax tree leaf node.|
C function definitions and Java class definitions are examples of statements in
other languages. An expression can be a procedure call, an arithmetic expression
etc. while a primary usually refers to a string literal or number. Some languages
do not contain all of these symbol types, however they generally contain some
kind of hierarchy of symbols such as `program`→`stmt`→`expr`→`primary`.
It is often the case that symbol types lower in this heirarchy can be promoted
to higher levels and vice versa. For example, in C function calls are expressions
yet can be may also be statements.
Conversely, when surrounded in parenthesis expressions become primaries.
Scoping rules differ considerably between programming languages. Consider
substitution. In C, the value of expressions can be used in substitutions
whereas in Pascal substitution occurs only at the statement level. Also,
function and class definitions are typically statements however in languages
such as Lisp and Scheme, since everything is an expression, they too are
expressions. Ruby follows Lisp's design in this regard.
h3. Program structure
Now let's turn our attention to the grammer rules of `ruby`. Firstly,
`yacc` will begin by examining the first rule defined in `parse.y`, and as
we can see from the following table, this is `program`. From here we can see
the ruby grammar unfold and the existance of the `program stmt expr primary`
heierarchy mentioned earlier. However there is an extra rule here for `arg`.
Let's now take a look at this.
▼ `ruby` grammar (outline)
<pre class="longlist">
program : compstmt
compstmt : stmts opt_terms
stmts : none
| stmt
| stmts terms stmt
stmt : kALIAS fitem fitem
| kALIAS tGVAR tGVAR
:
:
| expr
expr : kRETURN call_args
| kBREAK call_args
:
:
| '!' command_call
| arg
arg : lhs '=' arg
| var_lhs tOP_ASGN arg
| primary_value '[' aref_args ']' tOP_ASGN arg
:
:
| arg '?' arg ':' arg
| primary
primary : literal
| strings
:
:
| tLPAREN_ARG expr ')'
| tLPAREN compstmt ')'
:
:
| kREDO
| kRETRY
</pre>
If you look at each of the final alternatives for each of the rules you should
be able to clearly make out a hierarchy of `program`→`stmt`→`expr`→`arg`→
`primary`.
I'd like to focus on the rule for `primary`.
<pre class="emlist">
primary : literal
:
:
| tLPAREN_ARG expr ')' /* here */
</pre>
The name `tLPAREN_ARG` comes from `t` for terminal symbol, `L` for left and
`PAREN` for parentheses - it is the open parenthesis. Why this isn't `'('`
is covered in the next section "Context-dependent scanner". The purpose of this
rule is demote an `expr` to a `primary`, and is shown in Figure 2. This creates
a cycle which can the seen in Figure 2, and the arrow shows how this rule is
reduced during parsing.
!images/ch_parser_exprloop.png(`expr` demotion)!
The next rule is also particularly interesting.
<pre class="emlist">
primary : literal
:
:
| tLPAREN compstmt ')' /* here */
</pre>
A `compstmt`, which represents code for an entire program, can be demoted to
a `primary` with this rule. The next figure illustrates this rule in action.
!images/ch_parser_progloop.png(`program`の縮退)!
This means that for any syntax element in Ruby, if we surround it with
parenthesis it will become a `primary` and can be passed as an argument to a
function, be used as the right hand side of an expression etc. It helps to
see an example of this to grasp what this truly means.
<pre class="emlist">
p((class C; end))
p((def a() end))
p((alias ali gets))
p((if true then nil else nil end))
p((1 + 1 * 1 ** 1 - 1 / 1 ^ 1))
</pre>
If we invoke `ruby` with the `-c` option (syntax check), we get the following
output.
<pre class="screen">
% ruby -c primprog.rb
Syntax OK
</pre>
Although it might look surprising at first, yes you really can do this in Ruby!
The details of this are covered when we look at semantic analysis (in Chaper 12
"Syntax tree construction") however it is important to note there are exceptions
to this rule. For example passing a `return` statement as an argument to a
function will result in an error. For the most part, however, the "surrounding
anything in parenthesis means it can be passed as an argument to a function"
rule does hold.
In the next section I will cover the most important grammar rules in some detail.
h3. `program`
▼ `program`
<pre class="longlist">
program : compstmt
compstmt : stmts opt_terms
stmts : none
| stmt
| stmts terms stmt
</pre>
As mentioned earlier, `program` represents an entire program in the grammar.
For all intents and purposes `compstmts` is equivilent to `program`.
前述の通り`program`は文法全体、即ちプログラム全体を表している。その
`program`は`compstmts`と同じであり、`compstmts`は`stmts`とほぼ同じである。
その`stmts`は`terms`区切りの`stmt`のリストである。つまりプログラム全体は
`terms`区切りの`stmt`のリストである。
`terms`はもちろんterminatorsの略で、文を終端する記号、セミコロンだとか
改行のことだ。`opt_terms`はOPTional `terms`(省略可能な`terms`)だろう。
定義は次のようになっている。
▼ `opt_terms`
<pre class="longlist">
opt_terms :
| terms
terms : term
| terms ';'
term : ';'
| '\n'
</pre>
`terms`は`';'`か`'\n'`の後に任意の数だけ`';'`が続く並びなので、
この規則だけから考えると二個以上の改行があるとまずいように
思える。実際に試してみよう。
<pre class="emlist">
1 + 1 # 改行一つめ
# 改行二つめ
# 改行三つめ
1 + 1
</pre>
再び`ruby -c`を使う。
<pre class="screen">
% ruby -c optterms.rb
Syntax OK
</pre>
おかしい。通ってしまった。実を言うと、連続した改行はスキャナのレベルで
捨てられてしまってパーサには最初の一つしか渡らないようになっているのだ。
ところで、`program`と`compstmt`は同じものだと言ったが、それならこの規則は
何のために存在するのだろう。実はこれはアクションを実行するためだけにあ
るのだ。例えば`program`ならプログラム全体について一度だけ必要な処理を実
行するために用意されている。純粋に文法のことだけ考えるなら`program`は省
略しても全く問題ない。
これを一般化すると、規則には見ための解析のために必要なものと、アクショ
ンを実行するために必要なものの二種類があるということになる。`stmts`のと
ころにある`none`もアクションのために必要な規則の一つで、空リストに対して
(`NODE*`型の)`NULL`ポインタを返すために用意されている。
h3. `stmt`
次に文、`stmt`だ。`stmt`の規則はわりと量があるので、少しずつ見ていく
ことにする。
▼ `stmt`(1)
<pre class="longlist">
stmt : kALIAS fitem fitem
| kALIAS tGVAR tGVAR
| kALIAS tGVAR tBACK_REF
| kALIAS tGVAR tNTH_REF
| kUNDEF undef_list
| stmt kIF_MOD expr_value
| stmt kUNLESS_MOD expr_value
| stmt kWHILE_MOD expr_value
| stmt kUNTIL_MOD expr_value
| stmt kRESCUE_MOD stmt
| klBEGIN '{' compstmt '}'
| klEND '{' compstmt '}'
</pre>
なんとなくわかる。最初にいくつかあるのは`alias`だし、
次が`undef`、その後にいくつか並ぶ「なんたら`_MOD`」は
modifier(修飾子)のことだろうから、後置系構文だと想像が付く。
`expr_value`や`primary_value`はアクションのために用意されている規則である。
例えば`expr_value`なら値(value)を持つ`expr`であることを示す。値
を持たない`expr`とは`return`や`break`、あるいはそういうものを含む`if`文
などのことだ。「値を持つ」の詳しい定義は
第12章『構文木の構築』で見る。
`primary_value`も同じく「値を持つ」`primary`である。
`klBEGIN`と`klEND`は説明した通り`BEGIN`と`END`のこと。
▼ `stmt`(2)
<pre class="longlist">
| lhs '=' command_call
| mlhs '=' command_call
| var_lhs tOP_ASGN command_call
| primary_value '[' aref_args ']' tOP_ASGN command_call
| primary_value '.' tIDENTIFIER tOP_ASGN command_call
| primary_value '.' tCONSTANT tOP_ASGN command_call
| primary_value tCOLON2 tIDENTIFIER tOP_ASGN command_call
| backref tOP_ASGN command_call
</pre>
この規則は全部くくって見るのが正しい。
共通点は右辺に`command_call`が来る代入であることだ。
`command_call`は引数括弧を省略したメソッド呼び出しである。
新しく出てきた記号は以下に表を置いておくので対照しながら確かめてほしい。
|`lhs`|代入の左辺(Left Hand Side)|
|`mlhs`|多重代入の左辺(Multiple Left Hand Side)|
|`var_lhs`|代入の左辺、ただし変数系のみ(VARiable Left Hand Side)|
|`tOP_ASGN`|`+=`や`*=`など組み合わせ代入記号(OPerator ASsiGN)|
|`aref_args`|`[]`メソッド呼び出しの引数に使える表現(Array REFerence)|
|`tIDENTIFIER`|ローカル変数に使える識別子|
|`tCONSTANT`|定数に使える識別子(一文字目が大文字)|
|`tCOLON2`|`::`|
|`backref`|`$1 $2 $3...`|
ちなみにarefはLisp用語だ。対になるasetというのもあって、そちらは
array setの略。この略語は`ruby`のソースコードのいろいろなところで
使われている。
▼ `stmt`(3)
<pre class="longlist">
| lhs '=' mrhs_basic
| mlhs '=' mrhs
</pre>
この二つは多重代入である。`mrhs`は`mlhs`と同じ作りで、multipleな
`rhs`(右辺)。
こう見てくると、名前の意味を知るだけでもかなりわかりやすいということが
わかる。
▼ `stmt`(4)
<pre class="longlist">
| expr
</pre>
最後に、`expr`へ連結する。
h3. `expr`
▼ `expr`
<pre class="longlist">
expr : kRETURN call_args
| kBREAK call_args
| kNEXT call_args
| command_call
| expr kAND expr
| expr kOR expr
| kNOT expr
| '!' command_call
| arg
</pre>
式。`ruby`の式は文法上はかなり小さい。なぜなら普通は`expr`に入るものがほと
んど`arg`に行ってしまっているからだ。逆に言うと、ここには`arg`に行けなかっ
たものが残っているということになる。では行けなかったものはなにかと言う
と、これまたメソッド呼び出し括弧の省略組である。`call_args`は剥き出しの
引数リストで、`command_call`は先程言ったとおり括弧省略メソッドのこと。こ
ういうものを「小さい」単位に入れると衝突しまくることになる。
ただし以下の二つだけは種類が違う。
<pre class="emlist">
expr kAND expr
expr kOR expr
</pre>
`kAND`は「`and`」で`kOR`は「`or`」。この二つは制御構造としての役割があ
るので、`command_call`以上に「大きい」構文単位に入れなければならない。
そして`command_call`は`expr`にある。だから最低でも`expr`にしてやらない
とうまくいかない。例えば次のような使いかたが存在するのだが……
<pre class="emlist">
valid_items.include? arg or raise ArgumentError, 'invalid arg'
# valid_items.include?(arg) or raise(ArgumentError, 'invalid arg')
</pre>
もし`kAND`の規則が`expr`でなくて`arg`にあったとすると、次のように
連結されてしまうことになる。
<pre class="emlist">
valid_items.include?((arg or raise)) ArgumentError, 'invalid arg'
</pre>
当然パースエラーだ。
h3. `arg`
▼ `arg`
<pre class="longlist">
arg : lhs '=' arg
| var_lhs tOP_ASGN arg
| primary_value '[' aref_args ']' tOP_ASGN arg
| primary_value '.' tIDENTIFIER tOP_ASGN arg
| primary_value '.' tCONSTANT tOP_ASGN arg
| primary_value tCOLON2 tIDENTIFIER tOP_ASGN arg
| backref tOP_ASGN arg
| arg tDOT2 arg
| arg tDOT3 arg
| arg '+' arg
| arg '-' arg
| arg '*' arg
| arg '/' arg
| arg '%' arg
| arg tPOW arg
| tUPLUS arg
| tUMINUS arg
| arg '|' arg
| arg '^' arg
| arg '&' arg
| arg tCMP arg
| arg '>' arg
| arg tGEQ arg
| arg '<' arg
| arg tLEQ arg
| arg tEQ arg
| arg tEQQ arg
| arg tNEQ arg
| arg tMATCH arg
| arg tNMATCH arg
| '!' arg
| '~' arg
| arg tLSHFT arg
| arg tRSHFT arg
| arg tANDOP arg
| arg tOROP arg
| kDEFINED opt_nl arg
| arg '?' arg ':' arg
| primary
</pre>
規則の数は多いが、文法の複雑さは規則の数には比例しない。単に場合分けが
多いだけの文法は`yacc`にとっては非常に扱いやすく、むしろ規則の深さである
とか再帰のほうが複雑さに影響する。
そうすると演算子のところで`arg OP arg`という形で再帰しているのが気になる
のだが、これらの演算子には全て演算子優先順位が設定されているため
実質上ただの列挙にすぎない。
そこで`arg`の規則からそういう「ただの列挙」を併合して削ってしまおう。
<pre class="emlist">
arg: lhs '=' arg /* 1 */
| primary T_opeq arg /* 2 */
| arg T_infix arg /* 3 */
| T_pre arg /* 4 */
| arg '?' arg ':' arg /* 5 */
| primary /* 6 */
</pre>
終端記号および終端記号のリストは区別する意味がないので全部まとめて`T_`の
付く記号で表現した。`opeq`は`operator + equal`、`T_pre`は`'!'`や`'~'`の
ような前置型演算子、`T_infix`は`'*'`や`'%'`と言った二項演算子を表す。
この構造で衝突しないためには以下のようなことが重要になる
(ただしこれが全てではない)。
* `T_infix`が`'='`を含まないこと
`arg`は`lhs`と部分的に重なるので`'='`があると規則1と3が区別できない。
* `T_opeq`と`T_infix`が共通項を持たないこと
`arg`は`primary`を含むから共通項を持つと規則2と3が区別できない。
* `T_infix`の中に`'?'`がないこと
もし含むと規則3と5がshift/reduce conflictを起こす。
* `T_pre`が`'?'`や`':'`を含まない
もし含むと規則4と5がかなり複雑に衝突する。
結論としては全ての条件が成立しているので、この文法は衝突しない。
当然と言えば当然だ。
h3. `primary`
`primary`は規則が多いので最初から分割して示す。
▼ `primary`(1)
<pre class="longlist">
primary : literal
| strings
| xstring
| regexp
| words
| qwords
</pre>
リテラル類。`literal`は`Symbol`リテラル(`:sym`)と数値。
▼ `primary`(2)
<pre class="longlist">
| var_ref
| backref
| tFID
</pre>
変数類。`var_ref`はローカル変数やインスタンス変数など。
`backref`は`$1 $2 $3`……。
`tFID`は`!`や`?`が付いた識別子、例えば`include? reject!`など。
`tFID`はローカル変数ではありえないので、
それ単独で出てきたとしてもパーサレベルでメソッド呼び出しになる。
▼ `primary`(3)
<pre class="longlist">
| kBEGIN
bodystmt
kEND
</pre>
`bodystmt`が`rescue`や`ensure`も含んでいる。
つまりこれは例外制御の`begin`である。
▼ `primary`(4)
<pre class="longlist">
| tLPAREN_ARG expr ')'
| tLPAREN compstmt ')'
</pre>
既に説明した。構文縮退。
▼ `primary`(5)
<pre class="longlist">
| primary_value tCOLON2 tCONSTANT
| tCOLON3 cname
</pre>
定数の参照。`tCONSTANT`は定数名(大文字で始まる識別子)。
`tCOLON2`は`::`と`tCOLON3`は両方とも`::`なのだが、`tCOLON3`はトップレベルを
意味する`::`だけを表している。つまり`::Const`という場合の`::`である。
`Net::SMTP`のような`::`は`tCOLON2`だ。
同じトークンに違う記号が使われているのは括弧省略メソッドに対応する
ためである。例えば次の二つを見分けるためだ。
<pre class="emlist">
p Net::HTTP # p(Net::HTTP)
p Net ::HTTP # p(Net(::HTTP))
</pre>
直前にスペースがあるか、あるいは開き括弧などの境界文字がある場合は
`tCOLON3`でそれ以外では`tCOLON2`になる。
▼ `primary`(6)
<pre class="longlist">
| primary_value '[' aref_args ']'
</pre>
インデックス形式の呼び出し、例えば`arr[i]`。
▼ `primary`(7)
<pre class="longlist">
| tLBRACK aref_args ']'
| tLBRACE assoc_list '}'
</pre>
配列リテラルとハッシュリテラル。こちらの`tLBRACK`も`'['`を表して
いるのだが、`'['`は`'['`でも前に空白のない`'['`のこと。この区別が必要
なのもメソッド呼び出し括弧の省略の余波だ。
それにしてもこの規則の終端記号は一文字しか違わないので非常にわかりずらい。
以下の表に括弧の読みかたを書いておいたので対照しながら読んでほしい。
▼ 各種括弧の英語名
|記号|英語名|日本語名(の一例)|
|`( )`|parentheses|丸括弧、括弧|
|`{ }`|braces|ヒゲ括弧、中括弧|
|`[ ]`|brackets|角括弧、大括弧|
▼ `primary`(8)
<pre class="longlist">
| kRETURN
| kYIELD '(' call_args ')'
| kYIELD '(' ')'
| kYIELD
| kDEFINED opt_nl '(' expr ')'
</pre>
メソッド呼び出しと形式が似ている構文。
順番に、`return`、`yield`、`defined?`。
`yield`には引数が付いているのに`return`に引数がないのはどうしてだろう。
根本的な原因は、`yield`はそれ自体に返り値があるのに対し`return`には返り値が
ないことである。ただし、ここで引数がないからといって値を渡せないわけでは、
もちろんない。`expr`に次のような規則があった。
<pre class="emlist">
kRETURN call_args
</pre>
`call_args`は剥き出しの引数リストなので`return 1`や`return nil`には対
処できる。`return(1)`のようなものは`return (1)`として扱われる。という
ことは、次のように引数が二個以上ある`return`には括弧が付けられないはず
だ。
<pre class="emlist">
return(1, 2, 3) # return (1,2,3)と解釈されてパースエラー
</pre>
このあたりは次章『状態付きスキャナ』を読んでから
もう一度見てもらうとよくわかるだろう。
▼ `primary`(9)
<pre class="longlist">
| operation brace_block
| method_call
| method_call brace_block
</pre>
メソッド呼び出し。`method_call`は引数あり(括弧もある)、`operation`は
括弧も引数もなし。`brace_block`は`{`〜`}`か`do`〜`end`で、それがついて
いるメソッドとはつまりイテレータだ。`brace`なのになぜ`do`〜`end`が入る
のか……ということにはマリアナ海溝よりも深淵な理由があるのだが、これも
やはり次章『状態付きスキャナ』を読んでもらうしかない。
▼ `primary`(10)
<pre class="longlist">
| kIF expr_value then compstmt if_tail kEND # if
| kUNLESS expr_value then compstmt opt_else kEND # unless
| kWHILE expr_value do compstmt kEND # while
| kUNTIL expr_value do compstmt kEND # until
| kCASE expr_value opt_terms case_body kEND # case
| kCASE opt_terms case_body kEND # case(形式2)
| kFOR block_var kIN expr_value do compstmt kEND # for
</pre>
基本制御構造。ちょっと意外なのは、こんなデカそうなものが`primary`という
「小さい」ものの中にあることだ。`primary`は`arg`でもあるのでこんなこと
もできるということになる。
<pre class="emlist">
p(if true then 'ok' end) # "ok"と表示される
</pre>
Rubyの特徴の一つに「ほとんどの構文要素が式」というのがあった。
`if`や`while`が`primary`にあることでそれが具体的に表現されている。
それにしてもどうしてこんな「大きい」要素が`primary`にあって大丈夫なのだ
ろう。それはRubyの構文が「終端記号Aで始まり終端記号Bで終わる」
という特徴があるからに他ならない。この点については次の項で改めて
考えてみる。
▼ `primary`(11)
<pre class="longlist">
| kCLASS cname superclass bodystmt kEND # クラス定義
| kCLASS tLSHFT expr term bodystmt kEND # 特異クラス定義
| kMODULE cname bodystmt kEND # モジュール定義
| kDEF fname f_arglist bodystmt kEND # メソッド定義
| kDEF singleton dot_or_colon fname f_arglist bodystmt kEND
# 特異メソッド定義
</pre>
定義文。クラス文クラス文と呼んできたが、本当はクラス項と呼ぶべきで
あったか。これらも全て「終端記号Aで始まりBで終わる」パターンなので、
いくら増えたところで一向に問題はない。
▼ `primary`(12)
<pre class="longlist">
| kBREAK
| kNEXT
| kREDO
| kRETRY
</pre>
各種ジャンプ。このへんはまあ、文法的にはどうでもいい。
h3. 衝突するリスト
先の項では`if`が`primary`なんかにあって大丈夫なのだろうか、という疑問を
提示した。厳密に証明するにはなかなか難しいのだが、感覚的にならわりと
簡単に説明できる。ここでは次のような小さい規則でシミュレーション
してみよう。
<pre class="emlist">
%token A B o
%%
element : A item_list B
item_list :
| item_list item
item : element
| o
</pre>
`element`がこれから問題にしようとしている要素だ。例えば`if`について考える
なら`if`だ。`element`は終端記号`A`で始まり`B`で終わるリストである。
`if`で言うなら`if`で始まり`end`で終わる。内容物の`o`はメソッドや
変数参照やリテラルである。リストの要素には、その`o`か、または`element`が
ネストする。
この文法に基くパーサで次のような入力をパースしてみよう。
<pre class="emlist">
A A o o o B o A o A o o o B o B B
</pre>
ここまでネストしまくっていると人間にはインデントなどの助けがないとちょっ
とわかりにくい。だが次のように考えればわりと簡単である。いつか必ず
`A`と`B`が`o`だけを狭んで現れるので、それを消して`o`に変える。それを繰り
返すだけでいい。結論は図4のようになる。
!images/ch_parser_ablist.png(Aで始まりBで終わるリストのリストをパース)!
しかしもし終端の`B`がなかったりすると……
<pre class="emlist">
%token A o
%%
element : A item_list /* Bを消してみた */
item_list :
| item_list item
item : element
| o
</pre>
これを`yacc`で処理すると2 shift/reduce conflictsと出た。つまりこの文法は
曖昧である。入力は、先程のものから単純に`B`を抜くと次のようになってしまう。
<pre class="emlist">
A A o o o o A o A o o o o
</pre>
どうにもよくわからない。しかしshift/reduce conflictはシフトしろ、とい
うルールがあったので、試しにそれに従ってシフト優先(即ち内側優先)でパー
スしてみよう(図5)。
!images/ch_parser_alist.png(Aで始まるリストのリストをパース)!
とりあえずパースできた。しかしこれでは入力と意図が全く違うし、どうやっ
ても途中でリストを切ることができなくなってしまった。
実はRubyの括弧省略メソッドはこれと似たような状態にある。わかりにくいが、
メソッド名と第一引数が合わせて`A`だ。なぜならその二つの間にだけカンマが
ないので、新しいリストの始まりだと認識できるからである。
他に「現実的な」HTMLもこのパターンを含む。例えば``や``が省略され
たときはこうなる。そういうわけで`yacc`は普通のHTMLにはまるで通用しない。
h2. スキャナ
h3. パーサ概形
スキャナに移る前にパーサの概形について説明しておこう。
図6を見てほしい。
!images/ch_parser_interf.png(パーサインターフェイス(コールグラフ))!
パーサの公式インターフェイスは`rb_compile_cstr()`、
`rb_compile_string()`、
`rb_compile_file()`の三つである。それぞれCの文字列、Rubyの文字列オブジェク
ト、Rubyの`IO`オブジェクトからプログラムを読み込んでコンパイルする。
これらの関数は直接間接に`yycompile()`を呼び出し、最終的に`yacc`が生成した
`yyparse()`に完全に制御を移す。パーサの中心とはこの`yyparse()`に他ならない
のだから、`yyparse()`を中心に把握してやるとよい。即ち`yyparse()`に移る前の
関数は全て前準備であり、`yyparse()`より後の関数は`yyparse()`にこき使われ
る雑用関数にすぎない。
`parse.y`にある残りの関数は`yylex()`から呼び出される補助関数群だが、こちらも
また明確に分類することができる。
まずスキャナの最も低レベルな部分には入力バッファがある。`ruby`はソースプ
ログラムをRubyの`IO`オブジェクトか文字列のどちらからでも入力できるように
なっており、入力バッファはそれを隠蔽して単一のバイトストリームに見せか
ける。
次のレベルはトークンバッファである。入力バッファから1バイト
ずつ読んだらトークンが一つ完成するまでここにまとめてとっておく。
従って`yylex`全体の構造は図7のように図示できる。
!images/ch_parser_scanner.png(スキャナの全体像)!
h3. 入力バッファ
まず入力バッファから見ていこう。インターフェイスは
`nextc()`、`pushback()`、`peek()`の三つだけだ。
しつこいようだがまずデータ構造を調べるのだった。
入力バッファの使う変数はこうだ。
▼ 入力バッファ
<pre class="longlist">
2279 static char *lex_pbeg;
2280 static char *lex_p;
2281 static char *lex_pend;
(parse.y)
</pre>
バッファの先頭と現在位置、終端。どうやらこのバッファは単純な一列の
文字列バッファらしい(図8)。
!images/ch_parser_ibuffer.png(入力バッファ)!
h4. `nextc()`
ではこれを使っているところを見てみる。まずは一番オーソドックスと
思われる`nextc()`から。
▼ `nextc()`
<pre class="longlist">
2468 static inline int
2469 nextc()
2470 {
2471 int c;
2472
2473 if (lex_p == lex_pend) {
2474 if (lex_input) {
2475 VALUE v = lex_getline();
2476
2477 if (NIL_P(v)) return -1;
2478 if (heredoc_end > 0) {
2479 ruby_sourceline = heredoc_end;
2480 heredoc_end = 0;
2481 }
2482 ruby_sourceline++;
2483 lex_pbeg = lex_p = RSTRING(v)->ptr;
2484 lex_pend = lex_p + RSTRING(v)->len;
2485 lex_lastline = v;
2486 }
2487 else {
2488 lex_lastline = 0;
2489 return -1;
2490 }
2491 }
2492 c = (unsigned char)*lex_p++;
2493 if (c == '\r' && lex_p <= lex_pend && *lex_p == '\n') {
2494 lex_p++;
2495 c = '\n';
2496 }
2497
2498 return c;
2499 }
(parse.y)
</pre>
最初の`if`で入力バッファの最後まで行ったかどうかテストしているようだ。そ
してその内側の`if`は、`else`で`-1`(`EOF`)を返していることから入力全体の
終わりをテストしているのだと想像できる。逆に言えば、入力が終わったときには
`lex_input`が0になる。
ということは入力バッファには少しずつ文字列が入ってきているのだというこ
とがわかる。その単位はと言うと、バッファを更新する関数の名前が
`lex_getline()`なので行に間違いない。
まとめるとこういうことだ。
<pre class="emlist">
if (バッファ終端に到達した)
if (まだ入力がある)
次の行を読み込む
else
return EOF
ポインタを進める
CRを読み飛ばす
return c
</pre>
行を補給する関数`lex_getline()`も見てみよう。
この関数で使う変数も一緒に並べておく。
▼ `lex_getline()`
<pre class="longlist">
2276 static VALUE (*lex_gets)(); /* gets function */
2277 static VALUE lex_input; /* non-nil if File */
2420 static VALUE
2421 lex_getline()
2422 {
2423 VALUE line = (*lex_gets)(lex_input);
2424 if (ruby_debug_lines && !NIL_P(line)) {
2425 rb_ary_push(ruby_debug_lines, line);
2426 }
2427 return line;
2428 }
(parse.y)
</pre>
最初の行以外はどうでもよい。
`lex_gets`が一行読み込み関数へのポインタ、`lex_input`が本当の入力だろう。
`lex_gets`をセットしているところを検索してみると、こう出た。
▼ `lex_gets`をセット
<pre class="longlist">
2430 NODE*