図1:
EXPR_BEGへの遷移
理論のように、スキャナはただひたすらトークンに区切り、パーサはその並び だけを扱い、両者は完璧に独立している……という段階で済むならば、それは とてもありがたいことだ。しかし現実はそううまくはいかない。プログラムの 文脈によってトークンの切りかたや記号を変えなければならないということは よくある。この章ではスキャナとパーサの連携について見ていくことにする。
普通のプログラム言語なら、空白は単語の区切りになる以外はたいし て意味を持たない。しかしRubyは普通ではないので空白のあるなしで全く意味 が変わってしまうことがある。例えば次のような場合だ。
a[i] = 1 # a[i] = (1) a [i] # a([i])
前者はインデックス代入であり、後者はメソッド呼び出しの括弧を省略して引 数に配列の要素を渡している。
また次のような場合もある。
a + 1 # (a) + (1) a +1 # a(+1)
このあたりの仕様は一部の地域でやたらと嫌われているようだ。
しかしこのままだとメソッド括弧の省略だけが悪いかのような印象を 与えてしまいそうなので別の例も挙げておこう。
`cvs diff parse.y` # コマンド呼び出し文字列
obj.`("cvs diff parse.y") # 通常形式のメソッド呼び出し
これは、前者がリテラルの形を取ったメソッド呼び出しであるのに対し、
後者は通常形式のメソッド呼び出しである（「`」がメソッド名）。
コンテキストによって随分と扱いが違う。
次の例もかなり激しく働きが変わる。
print(<<EOS) # ヒアドキュメント ...... EOS list = [] list << nil # list.push(nil)
前者はヒアドキュメントで、後者は演算子形式のメソッド呼び出しである。
このようにRubyの文法には実装するのには不都合なところがたくさん 存在する。とてもではないが丁寧にやっていたら一章で全部紹介しき れるような量ではない。そこでこの章では根本原理と、難易度の高いところに 限って見ていくことにする。
lex_state
lex_stateという変数がある。lexはもちろんlexerのlexだから、これは
スキャナの状態（state）を示す変数だ。
どういう状態があるのだろうか。定義を見てみよう。
▼enum lex_state
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)
プリフィクスのEXPR_はexpression、「式」だろう。EXPR_BEGなら「式の頭」
だしEXPR_DOTは「式の中の、ドットの後」だ。
具体的に説明しよう。EXPR_BEGは「式の先頭にいる」ことを示している。
EXPR_ENDは「式の最後にいる」ことを示す。EXPR_ARGは「メソッドの引数の前」
を示す。EXPR_FNAMEは「（defなどの）メソッド名の前」を示す。説明を飛ば
したものはあとで詳しく解析していく。
ところで、lex_stateが示しているものは「括弧のあと」「文の頭」というよ
うな情報なのだから、これはスキャナの状態ではなくてパーサの状態のような
気がする。だが普通はスキャナの状態と呼ぶ。なぜだろうか。
実はこの場合の「状態」は普段使う「状態」とちょっと意味が違うのだ。
lex_stateのような「状態」とは、「スキャナがこういう振舞いをする状態」
という意味である。例えばEXPR_BEGを正確に言えば「いまスキャナを働かせ
たら文頭にいるかのように動く状態」である。
また専門用語を使うと、スキャナをステートマシンと見たときの状態、と言え る。しかしそこまで説明するのはさすがに骨が折れるしあまりに話題が離れす ぎる。詳しいことはデータ構造に関する教科書を適当に見繕って読んでいただ きたい。
状態付きスキャナを読むコツは、一度に全部をつかもうとしないことだ。パー サを書く人間にとっては、状態付きスキャナはあまり使いたくないものである。 ということは当然、それを処理の本筋にはしたくないはずだ。だからスキャナ の状態管理というのは「その他の本筋部分に付随したおまけ部分」であること が多い。つまりスキャナの状態遷移全体の美しい全体像なんてものは最初から 存在しないのである。
ではどうするかというと、徹底的に目的指向で読んでいくのがよい。「これを 解決するためにこの部分がある」「この問題を解消するためのこのコードがあ る」というふうに、目的に沿ってコードを切り刻む。問題の相互関連なんても のを考え始めると絶対に行き詰まる。もう一度言うが、そんなものは元からな いのだ。
とは言えそれにしたってある程度の目標は必要だ。状態付きスキャナを読むと
きの目標は、何よりも各状態がどういう状態かを知ることに置く
べきである。例えばEXPR_BEGはどういう状態か。それはパーサが式の頭にい
るということである。というように。
ではそれはどうやったらわかるだろうか。三通りの方法がある。
もっとも簡単であたりまえの方法。例えばEXPR_BEGなら当然なにかの先頭
（beginning）なんだろうというのは予測が付く。
状態によってトークンの切りかたがどう変わるか見る。そして現実の動きと比 べて当たりをつける。
どの状態からどういうトークンで遷移してくるか見る。例えば'\n'の後に必
ずHEADという状態に遷移しているとしたら、それはきっと行頭を表しているに
違いない。
EXPR_BEGを例にして考えてみよう。
rubyの場合は状態遷移は全てlex_stateへの代入で表現されているので、ま
ずEXPR_BEGの代入をgrepして洗う。次にそれがどこにあるか書き出す。例えば
yylex()の'#'と'*'と'!'と……のように。そして遷移する前の状態を考慮して
それがどういう場合にあてはまるか考える（図1）。
図1: EXPR_BEGへの遷移
ああなるほど、これはいかにも文の先頭っぽいな。とわかる。
特に'\n'や';'のあたりがそれっぽい。そして開き括弧やカンマも
あることから、これは文だけではなくて式の先頭だろうと言える。
もっとお手軽に現実の挙動を確かめる方法もある。例えばデバッガで
yylex()にフックをかけてlex_stateを見ると簡単だ。
あるいはソースコードを書き換えて状態遷移を出力するようにしてしまっても
いい。lex_stateの場合は代入や比較が数パターンしかないので、それをテキ
ストのパターンでとらえて遷移を出力するように書き換えればよい。今回は添
付CD-ROMにrubylex-analyserというツールを付け
た\footnote{rubylex-analyser：添付CD-ROMのtools/rubylex-analyser.tar.gz}。
本書でも必要に応じてこのツールを使いつつ説明していく。
全体的な手順としては、まずデバッガやツールを使ってなんとなくの動きを 確認する。そしてその情報をソースコードを見て確認・敷衍していくという のがよいだろう。
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 MIDEND ENDARGARG CMDARGFNAME DOT
はそれぞれ似たような状況を表す。EXPR_CLASSだけはちょっと特殊だが、
出てくる場所が非常に限定されているのでそもそもあまり考えなくて済む。
Rubyの文には必ずしも終端が必要なかった。例えばCやJavaでは必ず文末に セミコロンを置かないといけないが、Rubyではそういうものは必要ない。 一行一文が基本なので、行末で勝手に文が終わるのである。
ところがその一方で「明らかに続きがある」場合は自動的に文が継続すること になっている。「明らかに続きがある」状態とは、
ifの直後などである。
このような文法を実現するためにはどうしたらいいのだろう。単にスキャナで
改行を読み飛ばすだけではだめである。Rubyのように文の両端が予約語で区切
られている文法ならC言語ほどは衝突しないが、軽く試してみたところ、return、
next、break、メソッド呼び出しの括弧省略は全て削らないと通らなかった。
そういうものを残しておくには文末にはなんらかの終端記号がないといけない。
それが\nであるか';'であるかは問わないが、とにかくなんらかの終端記号は
必要なのだ。
そこで解決策は二つある。即ちパーサで解決するかスキャナで解決するかだ。
パーサで解決するとしたら、\nが許されるところ全てにオプションで\nを置
けるような文法を書いてしまえばよい。スキャナで解決するなら、\nに意味の
あるところでだけ\nをパーサに渡せばよい（その他の場所で読み飛ばす）。
どちらを使うかは趣味の問題だが、普通はスキャナで対応する。そのほうがた いていコードがコンパクトになるし、どうでもいい記号で規則がぐちゃぐちゃ になってしまったらパーサジェネレータを使う意味がなくなってしまうからだ。
そういうわけで結論から言うとrubyでも改行にはスキャナで対応する。行を継
続したいときは\nを読み飛ばし、終端したいときは\nをトークンとして送る。
それがyylex()のここだ。
▼yylex()−'\n'
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)
EXPR_BEG・EXPR_FNAME・EXPR_DOT・EXPR_CLASSではgoto retry、
つまり意味がないので読み飛ばす。ラベルretryはyylex()の巨大switchの
前にある。
その他のところでは改行が意味を持つのでパーサに渡し、ついでに
lex_stateをEXPR_BEGに戻す。改行が意味のあるところは即ちexprの切れめ
だからだ。
またcommand_startは当面無視しておくべきである。最初に言ったように、
一度にいろいろなところを追うと必ず混乱する。
具体的な例を少し見てみよう。さっそく添付の解析ツール
rubylex-analyserを使う。
% 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
いろいろ出力が出ているが、ここで必要なのは左と真ん中の欄だけである。左
の欄はyylex()に入るの前のlex_stateを示し、真ん中の欄はトークンとそ
の記号を示す。
まず最初のトークンmの前と第二引数bの前では、改行しているが\nがトー
クンの前にくっついていて終端記号として出てきていない。lex_stateが
EXPR_BEG だからだ。
しかし下から二行目では\nが終端記号としても出てきている。EXPR_ARGだ
からだ。
というように、使っていけばいい。もうちょっとだけ例を見てみる。
% 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
予約語classのあとはEXPR_CLASSなので改行が無視される。
しかしスーパークラス式ObjectのあとはEXPR_ARGなので\nが出てきた。
% 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
'.'の後はEXPR_DOTなので\nが無視された。
ところで、classは予約語のはずなのに、なんでtIDENTIFIERになるのだろう。
次の節に続く。
Rubyでは予約語をメソッド名に使うことができる。ただしメソッド名に使える と一口に言ってもコンテキストがいくつかあって、
def xxxx）obj.xxxx）:xxxx）という三つが考えられる。Rubyではこの全てが可能である。以下それぞれに 考えてみよう。
まずメソッド定義は、専用の予約語defが先行するのでなんとかなりそうだ。
メソッド呼び出しについては、レシーバを省略されるとかなり面倒なことにな るのだが、実はさらに仕様が限定されていて、そういうのは許可されない。つ まりメソッド名が予約語の場合は決してレシーバを省略できないのだ。あるい は、ちゃんとパースできるようにそういう仕様になっていると言うべきかもし れない。
そしてシンボルの場合は、やはり終端記号':'が先行するのでなんとか通せそう
である。ただしこの場合は予約語とは関係なく':'がa?b:cのコロンと衝突する
という問題がある。これさえ解決できればなんとかなる。
いずれのケースにしてもやはり方法は二つ考えられる。即ちスキャナで解決す
るかパーサで解決するかだ。スキャナで解決する場合、defや.や:の次に来る
予約語をtIDENTIFIER（など）にすればよい。パーサで解決するなら、そうい
う規則を書けばよい。rubyでは三つそれぞれに両方を使い分けている。
メソッド定義の名前部分。ここではパーサ側で対処する。
▼メソッド定義の規則
| kDEF fname
f_arglist
bodystmt
kEND
| kDEF singleton dot_or_colon fname
f_arglist
bodystmt
kEND
メソッド定義を表す規則は二つだけで、それぞれ通常のメソッド定義と特異メ
ソッド定義に対応する。いずれもfnameが名前部分で、そのfnameは次のように
定義されている。
▼fname
fname : tIDENTIFIER
| tCONSTANT
| tFID
| op
| reswords
reswordsが予約語でopが二項演算子だ。どちらの規則も単に終端記号を全部並
べてあるだけなので省略する。それからtFIDはgsub!やinclude?のように語尾
に記号が付くものである。
予約語と同名のメソッド呼び出しに対してはスキャナで対処する。 予約語のスキャンのコードはこうなっていた。
識別子をスキャン
result = (tIDENTIFIERまたはtCONSTANT)
if (lex_state != EXPR_DOT) {
struct kwtable *kw;
/* See if it is a reserved word. */
kw = rb_reserved_word(tok(), toklen());
予約語を処理する
}
EXPR_DOTがメソッド呼び出しドットの後を表す。EXPR_DOTのときには無条件で
予約語の処理を抜かすから、ドットの後の予約語の記号はtIDENTIFIERか
tCONSTANTになる。
予約語のシンボルはパーサとスキャナの両方で対処される。 まず規則から。
▼symbol
symbol : tSYMBEG sym
sym : fname
| tIVAR
| tGVAR
| tCVAR
fname : tIDENTIFIER
| tCONSTANT
| tFID
| op
| reswords
このように、パーサで明示的に予約語（reswords）を通すようにしている。こ
うできるのはあくまでtSYMBEGという専用の終端記号が前にあるからで、記号
が':'だったりしたらこううまくはいかない。条件演算子（a?b:c）と衝突して
おしまいだ。つまりスキャナレベルでtSYMBEGを見分けるのがポイントである
ことに変わりはない。
ではその区別はどうやっているのだろうか。スキャナの実装を見てみよう。
▼yylex−':'
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)
前半のifは':'が二つ続いた場合。このときは最左最長一致原則で
優先的に'::'をスキャンする。
その次のifは先程言った条件演算子の':'だ。EXPR_ENDとEXPR_ENDARGは
どちらも式の終わりだから、引数が来ない……つまりシンボルはありえないので
条件演算子の':'にする。
また次の文字がスペースだった（ISSPACE(c)）ときもシンボルでは
なさそうなので条件演算子だ。
そして上記のどちらでもない場合は全てシンボルである。そのときは
EXPR_FNAMEに遷移してあらゆるメソッド名に備える。パースではなんでも困ら
ないのだが、これを忘れるとスキャナが予約語に対して値を渡してくれないの
で値の計算が変になる。
例えばifには通常の記法と後置修飾するものがある。
# 通常記法 if cond then expr end # 後置 expr if cond
これも衝突の原因になる。なぜかというと、これまたやっぱりメソッド括弧の 省略が原因である。例えばこんな場合だ。
call if cond then a else b end
この式はifまで読んだところで次の二通りに解釈できる。
call((if ....)) call() if ....
よくわからなければものは試しで、衝突するかどうかやってみよう。文法の中
のkIF_MODをkIFに変えてyaccで処理してみる。
% yacc parse.y parse.y contains 4 shift/reduce conflicts and 13 reduce/reduce conflicts.
目論見通り衝突しまくっている。興味があればyaccに-vオプションを
付けてログを取り、中を読んでみよう。どう衝突したのか詳細に書いてある。
さてどうしたらいいだろうか。rubyでは普通のifをkIF、後置のifを
kIF_MODというように記号レベルで（つまりスキャナレベルで）区別してし
まう。他の後置系演算子も全く同じで、
kUNLESS_MOD kUNTIL_MOD kWHILE_MOD kRESCUE_MODにkIF_MODの
合わせて五種類がある。この判断を行っているのは次のところだ。
▼yylex−予約語
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)
これがあるのはyylexの末尾、識別子をスキャンしたあとだ。最後の（一番内
側の）if〜elseが修飾子を扱う部分である。EXPR_BEGかどうかで返り値を
変えていることがわかる。ここが修飾子かどうかの判定だ。つまり変数kwが
カギである。そしてkwは……とずっと上を見ていくと、struct kwtableだと
わかる。
struct kwtableはkeywords内で定義されている構造体で、
ハッシュ関数rb_reserved_word()はgperfが作ってくれるということは
前章で話した。もう一度構造体を紹介しよう。
▼keywords ― struct kwtable
1 struct kwtable {char *name; int id[2]; enum lex_state state;};
(keywords)
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}。
% 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
doの衝突
イテレータの書式にはdo〜endと{〜}の二種類があるのだった。この二つの
違いは優先順で、{〜}のほうがずっと高い。優先順位が高いということは
文法として単位が「小さい」ということで、より小さい規則に入れることが
できる。例えばstmtでなくexprやprimaryに入れることができる。例えば
昔は{〜}イテレータがprimaryでdo〜endイテレータがstmtにあった。
ところが途中で次のような式に対する要求が出てきた。
m do .... end + m do .... end
これを許すにはdo〜endイテレータをargやprimaryに入れればいい。
ところがwhileの条件式はexpr、つまりargやprimaryを含むので、
ここでdoが衝突してしまう。具体的には次のようなときだ。
while m do .... end
ちょっと見ではdoはwhileのdoになるのが正しそうである。しか
しよくよく見るとm do〜endというくくりも考えられる。人間が混同でき
るということはyaccなら確実に衝突する。実際にやってみよう。
/* doの衝突の実験 */
%token kWHILE kDO tIDENTIFIER kEND
%%
expr: kWHILE expr kDO expr kEND
| tIDENTIFIER
| tIDENTIFIER kDO expr kEND
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もだ）を全て繰り返さないと
いけなくなる。従ってこの問題はスキャナで解決するのが適切だ。
以下に関連規則を簡約化したものを示す。
▼doの記号
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
見てのとおり、whileのdoとイテレータのdoで終端記号が違う。
whileがkDO_COND、イテレータがkDOだ。あとはスキャナでこの
区別をすればよい。
以下は、何度も見てきたyylexの予約語の処理部分の一部である。
doの処理をしているのはここだけなので、ここのコードを
調べれば判断基準がわかるはずだ。
▼yylex−識別子−予約語
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)
ぐちゃぐちゃとあるが、kDO_CONDに関係するところだけ見ればよい。なぜなら、
kDO_CONDとkDO/kDO_BLOCKという比較、kDOとkDO_BLOCKという
比較は意味があるが、それ以外の比較は意味がないからだ。いまは条件の
doさえ区別できればよいのであって、他の条件を一緒に追ってはいけない。
つまりCOND_P()が鍵となる。
COND_P()cond_stack
COND_P()はparse.yの先頭近くで定義されている。
▼cond_stack
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)
型stack_typeはlong（32ビット以上）かlong long（64ビット以上）だ。
cond_stackはパース開始時にyycompile()で初期化され、後は常にマクロ
経由で扱われるので、そのマクロを把握すればよい。
そのマクロCOND_PUSH/POPを見ると、どうやら整数をビット単位のスタック
として使うようである。
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()
そしてCOND_P()はというと、最下位ビット（LSB）が1かどうか
判定しているから、スタックの先頭が1かどうかの判定ということになる。
残るCOND_LEXPOP()はちょっと不思議な動きだ。現在のCOND_P()を
スタック先頭に残したまま右シフトしている。つまり下から2ビットめを
1ビットめで踏み潰すようになる。
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()
これがどういう意味を持つのかは後で説明しよう。
ではこのスタックの目的を調べるために、
COND_PUSH() COND_POP()を使っているところを全部リストアップしてみよう。
| 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();
ここから次のような法則を発見できる。
PUSH(1)PUSH(0)POP()LEXPOP()
とすると、なんとなく
使い道が見えてくる。cond_stackという名前も考えると、条件式と同じレベルに
いるかどうか判定するマクロに違いない（図2）。
図2: COND_P()の移り変わり
この仕掛けによって次のような場合にもうまく対処できるようになる。
while (m do .... end) # doはイテレータのdo（kDO） .... end
ということは、32ビットマシンでlong longがない場合には括弧か条件式が
32レベルネストしたあたりで変なことになる可能性がある。とはいえ普通は
そんなにネストしないから実害は出ない。
またCOND_LEXPOP()の定義がちょっと不思議なことになっていたのは、どうやら
先読み対策らしい。ただ現在はうまいこと先読みが起こらないような規則に
なっているためにPOPとLEXPOPを分ける意味がなくなっている。つまり
現時点では「COND_LEXPOP()は無意味」という解釈が正しい。
tLPAREN_ARG（1）
この問題は、非常にややこしい。これが通るようになったのはruby 1.7に
なってから、それもごく最近の話である。どういうことかというと……
call (expr) + 1
を
(call(expr)) + 1 call((expr) + 1)
のどちらに解釈するか、という話だ。以前は全て前者のように処理されてい
た。つまり括弧は常に「メソッド引数の括弧」だった。しかし
ruby 1.7では後者のように処理されるようになったのである。
つまり空白が入ると括弧は「exprの括弧」になる。
なぜ解釈が変わったのか、例を紹介しておこう。まず次のような文を書いた。
p m() + 1
ここまでなら問題はない。しかしmの返す値が実は小数で、桁数が多す
ぎたとしよう。そこで表示するときは整数にしてしまうことにする。
p m() + 1 .to_i # ??
しまった、括弧が必要だ。
p (m() + 1).to_i
これはどう解釈されるだろうか？ 1.6までなら、これは
(p(m() + 1)).to_i
となる。つまりせっかく付けたto_iが何の意味もなくなってしまう。これは困る。
そこで括弧との間に空白がある場合だけは特別扱いしてexprの括弧にすることに
したのである。
自分で調査してみたい人のために書いておくと、
この変更が実装されたのはparse.yのリビジョン1.100（2001-05-31）である。
だから1.99との差分を見ていくと比較的わかりやすい。
差分を取るコマンドはこうだ。
~/src/ruby % cvs diff -r1.99 -r1.100 parse.y
まず現実に仕組みがどう動いているか見てみることにしよう。添付の
ツールruby-lexer\footnote{ruby-lexer：添付CD-ROMのtools/ruby-lexer.tar.gz}を
使うとプログラムに対応する記号列を調べられる。
% ruby-lexer -e 'm(a)'
tIDENTIFIER '(' tIDENTIFIER ')' '\n'
-eはrubyと同じくプログラムをコマンドラインから直接渡すオプションだ。
これを使っていろいろ試してみよう。
まず問題の、第一引数が括弧でくくられている場合。
% ruby-lexer -e 'm (a)' tIDENTIFIER tLPAREN_ARG tIDENTIFIER ')' '\n'
スペースを入れたら開き括弧の記号がtLPAREN_ARGになった。
ついでに普通の式括弧も見ておこう。
% ruby-lexer -e '(a)' tLPAREN tIDENTIFIER ')' '\n'
普通の式括弧はtLPARENらしい。
まとめるとこうなる。
| 入力 | 開き括弧の記号 | ||
m(a) | '(' | ||
m (a) | tLPAREN_ARG | ||
(a) | tLPAREN |
つまりこの三つをどう区別するかが焦点となる。
今回は特にtLPAREN_ARGが重要だ。
まずは素直にyylex()の'('の項を見てみよう。
▼yylex−'('
3841 case '(':
3842 command_start = Qtrue;
3843 if (lex_state == EXPR_BEG || lex_state == EXPR_MID) {
3844 c = tLPAREN;
3845 }
3846 else if (space_seen) {
3847 if (lex_state == EXPR_CMDARG) {
3848 c = tLPAREN_ARG;
3849 }
3850 else if (lex_state == EXPR_ARG) {
3851 c = tLPAREN_ARG;
3852 yylval.id = last_id;
3853 }
3854 }
3855 COND_PUSH(0);
3856 CMDARG_PUSH(0);
3857 lex_state = EXPR_BEG;
3858 return c;
(parse.y)
最初のifはtLPARENだから、通常の式括弧だ。その判断基準はlex_stateが
BEGかMID、つまり確実に式の始まりにいるときである。
その次のspace_seenは括弧の前に「空白があるかどうか」を表している。
空白があり、かつlex_stateがARGかCMDARGのとき……つまり第一引数の
前なら、記号は'('でなくtLPAREN_ARGになる。これで例えば次のような
場合を排除できるわけだ。
m( # 括弧の前に空白がない……メソッド括弧（'('）
m arg, ( # 第一引数以外……式括弧（tLPAREN）
tLPARENでもtLPAREN_ARGでもなければ入力文字のcがそのまま
使われて'('になる。これはきっとメソッド呼び出しの括弧になるのだろう。
記号レベルでこのようにキッパリと区別されていれば、普通に規則を書いても 衝突しなくて済む。簡略化して書けば次のようになるだろう。
stmt : command_call
method_call : tIDENTIFIER '(' args ')' /* 通常メソッド */
command_call : tIDENTIFIER command_args /* 括弧省略メソッド */
command_args : args
args : arg
: args ',' arg
arg : primary
primary : tLPAREN compstmt ')' /* 通常の式括弧 */
| tLPAREN_ARG expr ')' /* 括弧でくくられた第一引数 */
| method_call
method_callとcommand_callに注目してほしい。もしtLPAREN_ARGを導入せず
'('のままにすると、command_argsからargsが出る、argsからargが出る、
argからprimaryが出る、そしてtLPAREN_ARGのところから'('が出て
method_callと衝突してしまう（図3）。
図3: method_callとcommand_call
さてうまいこと括弧がtLPAREN_ARGになってこれでバッチリか、と思いきや
実はそうではない。例えば次のような場合はどうなるのだろう。
m (a, a, a)
このような式はこれまではメソッド呼び出しとして扱われてきたので
エラーにならなかった。しかしtLPAREN_ARGが導入されると開き括弧が
expr括弧になってしまうので二個以上の引数があるとパースエラーになる。
互換性を考えるとなんとか配慮しなければならない。
しかし何も考えずに
command_args : tLPAREN_ARG args ')'
などという規則を追加してしまうとあっさり衝突する。全体を見てよく考えて みよう。
stmt : command_call
| expr
expr : arg
command_call : tIDENTIFIER command_args
command_args : args
| tLPAREN_ARG args ')'
args : arg
: args ',' arg
arg : primary
primary : tLPAREN compstmt ')'
| tLPAREN_ARG expr ')'
| method_call
method_call : tIDENTIFIER '(' args ')'
command_argsの一つめの規則を見てほしい。argsからはargが出る。
argからはprimaryが出る。そこからはtLPAREN_ARGの規則が出る。
そしてexprはargを含むから、展開の方法次第で
command_args : tLPAREN_ARG arg ')'
| tLPAREN_ARG arg ')'
という状況になる。即ちreduce/reduce conflictであり非常にまずい。
ではどうやったら衝突させずに二引数以上にだけ対処できるだろうか。 やはりそのむね限定して書くしかない。現実には次のように解決された。
▼command_args
command_args : open_args
open_args : call_args
| tLPAREN_ARG ')'
| tLPAREN_ARG call_args2 ')'
call_args : command
| args opt_block_arg
| args ',' tSTAR arg_value opt_block_arg
| assocs opt_block_arg
| assocs ',' tSTAR arg_value opt_block_arg
| args ',' assocs opt_block_arg
| args ',' assocs ',' tSTAR arg opt_block_arg
| tSTAR arg_value opt_block_arg
| block_arg
call_args2 : arg_value ',' args opt_block_arg
| arg_value ',' block_arg
| arg_value ',' tSTAR arg_value opt_block_arg
| arg_value ',' args ',' tSTAR arg_value opt_block_arg
| assocs opt_block_arg
| assocs ',' tSTAR arg_value opt_block_arg
| arg_value ',' assocs opt_block_arg
| arg_value ',' args ',' assocs opt_block_arg
| arg_value ',' assocs ',' tSTAR arg_value opt_block_arg
| arg_value ',' args ',' assocs ','
tSTAR arg_value opt_block_arg
| tSTAR arg_value opt_block_arg
| block_arg
primary : literal
| strings
| xstring
：
| tLPAREN_ARG expr ')'
こちらではcommand_argsの次にもう一段、open_argsがはさまっているが
規則上はなくても同じだ。このopen_argsの二つめ三つめの規則がカギであ
る。この形は先程書いた例と似てはいるが、微妙に違う。それは
call_args2というのを導入していることだ。このcall_args2の特徴はと言
うと、引数が必ず二つ以上あることである。その証拠にほとんどの規則が
','を含んでいる。例外はassocsの規則だが、exprからはassocsが出
てこないのでassocsはそもそも衝突しない。
やや説明がわかりにくかった。もうちょっと平易に言うと、
command_args : call_args
では通らない文法だけを、その次の規則でもって追加しているのである。
だから「この規則で通らない文法」とはどういうものか考えればいい。
また衝突するのはcall_argsの先頭にtLPAREN_ARGのprimaryが来るときだけ
なのだから、さらに限定して
「tIDENTIFIER tLPAREN_ARGという並びが来たとして、この規則だけでは
通らない文法」を考えればいい。その例をいくつか挙げる。
m (a, a)
これはtLPAREN_ARGリストの中に二つ以上の要素があるもの。
m ()
その逆に、tLPAREN_ARGリストの中が空であるもの。
m (*args) m (&block) m (k => v)
tLPAREN_ARGリストの中に、メソッド呼び出し特有の（exprにはない）
表現があるもの。
というあたりでだいたいカバーできるだろう。実装と照らし合わせて 見てみよう。
▼open_args（1）
open_args : call_args
| tLPAREN_ARG ')'
まずこの規則が空リストに対応する。
▼open_args（2）
| tLPAREN_ARG call_args2 ')'
call_args2 : arg_value ',' args opt_block_arg
| arg_value ',' block_arg
| arg_value ',' tSTAR arg_value opt_block_arg
| arg_value ',' args ',' tSTAR arg_value opt_block_arg
| assocs opt_block_arg
| assocs ',' tSTAR arg_value opt_block_arg
| arg_value ',' assocs opt_block_arg
| arg_value ',' args ',' assocs opt_block_arg
| arg_value ',' assocs ',' tSTAR arg_value opt_block_arg
| arg_value ',' args ',' assocs ','
tSTAR arg_value opt_block_arg
| tSTAR arg_value opt_block_arg
| block_arg
そしてcall_args2では、二つ以上の要素のリストと、assocsや
配列渡し、ブロック渡しなどの特殊型を含むものを扱う。
これでかなりの範囲に対応できるようになった。
tLPAREN_ARG（2）前の節でメソッド呼び出し特有の表現が「だいたい」カバーできると言ったの には訳がある。これだけではまだイテレータがカバーされていないからだ。 例えば以下のような文が通らない。
m (a) {....}
m (a) do .... end
この節ではさらにこの点を解決すべく導入された部分を突っこんで見ていこう。
まず規則から見ていく。
前のほうは既に登場した規則ばかりなのでdo_blockのあたりに注目してほしい。
▼command_call
command_call : command
| block_command
command : operation command_args
command_args : open_args
open_args : call_args
| tLPAREN_ARG ')'
| tLPAREN_ARG call_args2 ')'
block_command : block_call
block_call : command do_block
do_block : kDO_BLOCK opt_block_var compstmt '}'
| tLBRACE_ARG opt_block_var compstmt '}'
do、{の両方ともが全く新しい記号kDO_BLOCKとtLBRACE_ARGになっている。
なぜkDOや'{'ではいけないのだろう。そういうときはとりあえず試してみろ、
ということで、kDO_BLOCKをkDOに、tLBRACE_ARGを'{'にしてyaccで
処理してみた。すると……
% yacc parse.y conflicts: 2 shift/reduce, 6 reduce/reduce
思い切り衝突する。調べてみると、次のような文が原因であった。
m (a), b {....}
なぜなら、この形の文は既に通るようになっているからだ。b{....}が
primaryになる。そこにブロックがmと連結する規則を追加してしまったので、
m((a), b) {....}
m((a), (b {....}))
の二通りの解釈ができてしまい、衝突するのだ。 これが2 shift/reduce conflict。
もう一方はdo〜endがらみだ。こっちは
m((a)) do .... end # block_callでdo〜end追加 m((a)) do .... end # primaryでdo〜end追加
の二つが衝突する。これが6 reduce/reduce conflict。
{〜}イテレータ
ここからが本番である。先程見たように、doと'{'の記号を変えることで
衝突は回避できる。yylex()の'{'の項を見てみよう。
▼yylex―'{'
3884 case '{':
3885 if (IS_ARG() || lex_state == EXPR_END)
3886 c = '{'; /* block (primary) */
3887 else if (lex_state == EXPR_ENDARG)
3888 c = tLBRACE_ARG; /* block (expr) */
3889 else
3890 c = tLBRACE; /* hash */
3891 COND_PUSH(0);
3892 CMDARG_PUSH(0);
3893 lex_state = EXPR_BEG;
3894 return c;
(parse.y)
IS_ARG()は
▼IS_ARG
3104 #define IS_ARG() (lex_state == EXPR_ARG || lex_state == EXPR_CMDARG) (parse.y)
と定義されているから、EXPR_ENDARGのときには確実に偽になる。
つまりlex_stateがEXPR_ENDARGのときは常にtLBRACE_ARGになるのだから、
EXPR_ENDARGに遷移することこそが全ての鍵である。
EXPR_ENDARG
ではEXPR_ENDARGはどうやってセットされているのだろうか。
代入しているところをgrepしてみた。
▼EXPR_ENDARGへの遷移
open_args : call_args
| tLPAREN_ARG {lex_state = EXPR_ENDARG;} ')'
| tLPAREN_ARG call_args2 {lex_state = EXPR_ENDARG;} ')'
primary : tLPAREN_ARG expr {lex_state = EXPR_ENDARG;} ')'
おかしい。tLPAREN_ARGに対応する閉じ括弧のあとでEXPR_ENDARGに遷移すると
いうのならわかるが、実際には')'の前で代入
している。他にEXPR_ENDARGをセットしている個所があるのかと思ってgrepし
まくってみたが、やはりない。
もしかするとどこかで道を誤ったのだろうか。何か全く別の方法で
lex_stateが変更されているのかもしれない。確認のため、
rubylex-analyserでlex_stateの遷移を視覚化してみよう。
% rubylex-analyser -e 'm (a) { nil }'
+EXPR_BEG
EXPR_BEG C "m" tIDENTIFIER EXPR_CMDARG
EXPR_CMDARG S "(" tLPAREN_ARG EXPR_BEG
0:cond push
0:cmd push
1:cmd push-
EXPR_BEG C "a" tIDENTIFIER EXPR_CMDARG
EXPR_CMDARG ")" ')' EXPR_END
0:cond lexpop
1:cmd lexpop
+EXPR_ENDARG
EXPR_ENDARG S "{" tLBRACE_ARG EXPR_BEG
0:cond push
10:cmd push
0:cmd resume
EXPR_BEG S "nil" kNIL EXPR_END
EXPR_END S "}" '}' EXPR_END
0:cond lexpop
0:cmd lexpop
EXPR_END "\n" \n EXPR_BEG
大きく三つに分かれている行がyylex()による状態遷移を表している。
左がyylex()前の状態、真ん中の二つが単語のテキストとその記号、
右がyylex()後のlex_stateだ。
問題は単独の行に+EXPR_ENDARGのように出ている部分である。これはパーサ
のアクション中で遷移が起こっていることを示す。これによると、なぜか
')'を読んだあとにアクションが実行されてEXPR_ENDARGに遷移し
ており、うまいこと'{'がtLBRACE_ARGに変わっている。実はこれは
LALR(1)の(1)までを惜しみなく活用（逆用）したかなりの上級技なの
である。
ruby -yを使うとyaccのパーサエンジンの動きを逐一表示させることができる。
今度はこれを使ってさらに詳しくパーサをトレースしてみよう。
% ruby -yce 'm (a) {nil}' 2>&1 | egrep '^Reading|Reducing'
Reducing via rule 1 (line 303), -> @1
Reading a token: Next token is 304 (tIDENTIFIER)
Reading a token: Next token is 340 (tLPAREN_ARG)
Reducing via rule 446 (line 2234), tIDENTIFIER -> operation
Reducing via rule 233 (line 1222), -> @6
Reading a token: Next token is 304 (tIDENTIFIER)
Reading a token: Next token is 41 (')')
Reducing via rule 392 (line 1993), tIDENTIFIER -> variable
Reducing via rule 403 (line 2006), variable -> var_ref
Reducing via rule 256 (line 1305), var_ref -> primary
Reducing via rule 198 (line 1062), primary -> arg
Reducing via rule 42 (line 593), arg -> expr
Reducing via rule 260 (line 1317), -> @9
Reducing via rule 261 (line 1317), tLPAREN_ARG expr @9 ')' -> primary
Reading a token: Next token is 344 (tLBRACE_ARG)
：
：
コンパイルだけで中断する-cオプションと、コマンドラインからプログラムを
与える-eを併用している。そしてgrepでトークンの読み込みと還元の報告だけ
を抜き出す。
そこでまずリストの真ん中あたりを見てほしい。')'が読み込まれている。そ
して次に最後のほうを見ると……なんと、ここでようやく埋め込みアクション
（@9）の還元が起こっている（実行されている）。確かにこれなら')'の後・
'{'の前にEXPR_ENDARG をセットできそうだ。しかし、これは常に起こることな
のだろうか。もう一度セットしているところを見てみよう。
規則1 tLPAREN_ARG {lex_state = EXPR_ENDARG;} ')'
規則2 tLPAREN_ARG call_args2 {lex_state = EXPR_ENDARG;} ')'
規則3 tLPAREN_ARG expr {lex_state = EXPR_ENDARG;} ')'
埋め込みアクションは空の規則で代用することができるのだった。例えば 規則1を例に取ると、全く意味を変えずに次のように書き換えられる。
target : tLPAREN_ARG tmp ')'
tmp :
{
lex_state = EXPR_ENDARG;
}
いまtmpの前にいるとすると、終端記号一つ分は先読みされる可能性が
あるので（空の）tmpをすりぬけて次を読むことは確かにありうる。
そして、確実に先読みが起こるとわかっていれば、lex_stateへの代入が
')'の後でEXPR_ENDARGに変わることを保証できる。
ではこの規則では')'の先読みは確実に起こるだろうか。
これが、実は確かなのである。次のような三通りの入力で考えよう。
m () { nil } # A
m (a) { nil } # B
m (a,b,c) { nil } # C
ついでに規則も少し見やすく（しかし状況は変えずに）書き直した。
rule1: tLPAREN_ARG e1 ')' rule2: tLPAREN_ARG one_arg e2 ')' rule3: tLPAREN_ARG more_args e3 ')' e1: /* empty */ e2: /* empty */ e3: /* empty */
ではまず入力Aの場合。
m ( # ... tLPAREN_ARG
まで読んだところでe1の前に来る。もしここでe1を還元してしまったら
もう別の規則は選べないので、このままe1を還元してrule1と心中するか、
それとも他の規則を選ぶのか確認するためにここで先読みが起こる。
従って入力がrule1に合致する場合は必ず')'が先読みされる。
次に入力Bの場合。まず
m ( # ... tLPAREN_ARG
まで読んだところで先程と同じ理由で先読みがかかる。そしてさらに
m (a # ... tLPAREN_ARG '(' tIDENTIFIER
まで読んだところでまた先読みする。なぜなら次が','か')'かでrule2と
rule3に分かれるからだ。もし','だったらこれは引数区切りのカンマとしか
考えられないので即座に二引数以上、即ちrule3と確定する。もし入力が
単なるaではなくifだったりリテラルの「93」だったりしても同じことである。
その入力が完了したところでrule2とrule3を区別するために、即ち
一引数か二引数以上かを区別するために先読みが起こる。
この場合、全ての規則で')'の前に（別々の）埋め込みアクションがあると
いうことが重要なのだ。アクションというものは一回実行してしまうともう取
り返しが付かないので、パーサは「絶対確実」な状況になるまでアクションの
実行を先延ばししようとする。だからこそ先読み一つでそういう状況が作れな
いの場合はパーサ生成時に排除する必要があり、つまりそれが「衝突」である。
入力Cはどうだろうか。
m (a, b, c
ここまで来た時点でもうrule3しか可能性がないので、先読みはなさそうな気
がする。
ところがそうはいかない。次が'('ならメソッド呼び出しだし、','か')'なら
変数参照にしないといけない。つまり今度は埋め込みアクションの還元ではな
くて、引数の要素を確定するために先読みが起こる。
では他の入力ではどうなのだろうか。例えば第三引数がメソッド呼び出し だったらどうだろう。
m (a, b, c(....) # ... ',' method_call
これもやっぱり先読みが必要なのだ。なぜなら、次が','か')'かでシフトと還
元に分かれる。だから、この規則では結局あらゆる場合に埋め込みアクション
の実行よりも早く')'が読まれる。実にややこしい。よく思い付いたなあと感
動してしまう。
ところで埋め込みアクションではなく通常のアクションでlex_stateをセット
してはいけないのだろうか。例えばこのように。
| tLPAREN_ARG ')' { lex_state = EXPR_ENDARG; }
これは、いけない。なぜならアクションの還元の前に（また）先読みが起こる 可能性があるからだ。今度は先読みが裏目に出てしまうのである。このことか らもわかるように、LALRパーサの先読みを逆用するなんてのは相当な裏技である。 素人にはお勧めできない。
do〜endイテレータ
ここまでで{〜}イテレータには対処できたがまだdo〜endイテレータが残って
いる。同じイテレータなら同じ方法で対処できそうだが、それは違う。
{〜}とdo〜endでは優先順位が違うのだ。例えば次のように。
m a, b {....} # m(a, (b{....}))
m a, b do .... end # m(a, b) do....end
だから当然対処の方法も違って然るべきである。
とは言え、もちろん同じ対処で済む場合もある。例えば次のような場合は どちらでも同じになるだろう。
m (a) {....}
m (a) do .... end
とにかく現物を見てみることにする。
doだから、yylex()の予約語のところを見ればいい。
▼yylex−識別子−予約語−do
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)
今回注目するのはkDO_BLOCKとkDOを区別する部分だけだ。kDO_CONDのことは考
えてはいけない。状態付きスキャナでは常に関係するところだけ見るのだ。
まずEXPR_ENDARGを使った判定の部分がtLBRACE_ARGと同じ状況である。
このときは優先順位の違いは関係しないので'{'と同じでkDO_BLOCKに
するのが適切だろう。
問題はその前のCMDARG_P()とEXPR_CMDARGだ。順番に見ていこう。
CMDARG_P()▼cmdarg_stack
91 static stack_type cmdarg_stack = 0;
92 #define CMDARG_PUSH(n) (cmdarg_stack = (cmdarg_stack<<1)|((n)&1))
93 #define CMDARG_POP() (cmdarg_stack >>= 1)
94 #define CMDARG_LEXPOP() do {\
95 int last = CMDARG_P();\
96 cmdarg_stack >>= 1;\
97 if (last) cmdarg_stack |= 1;\
98 } while (0)
99 #define CMDARG_P() (cmdarg_stack&1)
(parse.y)
このようにcmdarg_stackの構造とインターフェイス（マクロ）は
cond_stackと全く同じだ。ビット単位のスタックである。モノが同じという
ことは調査方法も同じ手が通用する。使っている場所をリストアップしてみよ
う。まずアクション中に
command_args : {
$<num>$ = cmdarg_stack;
CMDARG_PUSH(1);
}
open_args
{
/* CMDARG_POP() */
cmdarg_stack = $<num>1;
$$ = $2;
}
というのがあった。
$<num>$は強制キャスト付きで左辺の
値を意味するのだった。この場合はそれが埋め込みアクション自体の値となっ
て出てくるから、その次のアクションでは$<num>1で取り出せる。つまり
cmdarg_stackをopen_argsの前で$$に退避して、アクションで復帰する、と
いう構造になっているわけだ。
なぜ単純なプッシュ・ポップではなくて退避・復帰にするのだろう。 それはこの節の最後で解説する。
またyylex()の中でCMDARG関係を探すと次のものが見付かった。
'(' '[' '{' | CMDARG_PUSH(0) | ||
')' ']' '}' | CMDARG_LEXPOP() |
つまり括弧にくくられていたらその括弧の中にいるあいだCMDARG_P()は偽、
ということだ。
両方を合わせて考えると、command_argsつまり括弧省略のメソッド呼び出し引
数中で、括弧にくくられていないときにCMDARG_P()が真になると言える。
EXPR_CMDARG
次にもう一つの条件、EXPR_CMDARGについて調べる。
まず定石通りEXPR_CMDARGに遷移している場所を探すことにする。
▼yylex−識別子−状態遷移
4201 if (lex_state == EXPR_BEG ||
4202 lex_state == EXPR_MID ||
4203 lex_state == EXPR_DOT ||
4204 lex_state == EXPR_ARG ||
4205 lex_state == EXPR_CMDARG) {
4206 if (cmd_state)
4207 lex_state = EXPR_CMDARG;
4208 else
4209 lex_state = EXPR_ARG;
4210 }
4211 else {
4212 lex_state = EXPR_END;
4213 }
(parse.y)
これはyylex()の中の識別子を扱うコードだ。
うじゃうじゃとlex_stateのテストがあるのはまあ置いておくとして、
cmd_stateは初めて見る。これはなんだろう。
▼cmd_state
3106 static int
3107 yylex()
3108 {
3109 static ID last_id = 0;
3110 register int c;
3111 int space_seen = 0;
3112 int cmd_state;
3113
3114 if (lex_strterm) {
/* ……略…… */
3132 }
3133 cmd_state = command_start;
3134 command_start = Qfalse;
(parse.y)
yylexのローカル変数だった。しかもgrepして調べたところ、値を変えている
のはここしかない。つまりこれはcommand_startをyylex一回の間だけ保存して
おく一時変数にすぎない。
ではcommand_startはどういうときに真になるのだろうか。
▼command_start
2327 static int command_start = Qtrue;
2334 static NODE*
2335 yycompile(f, line)
2336 char *f;
2337 int line;
2338 {
：
2380 command_start = 1;
static int
yylex()
{
：
case '\n':
/* ……略…… */
3165 command_start = Qtrue;
3166 lex_state = EXPR_BEG;
3167 return '\n';
3821 case ';':
3822 command_start = Qtrue;
3841 case '(':
3842 command_start = Qtrue;
(parse.y)
command_startはparse.yのスタティック変数で、
「\n ; (」のいずれかをスキャンすると真になる、とわかる。
ここまでをまとめる。まず「\n ; (」を読むとcommand_startが真になり、
次のyylex()のあいだcmd_stateが真になる。
そしてyylex()でcmd_stateを使うコードはこうだったから、
▼yylex−識別子−状態遷移
4201 if (lex_state == EXPR_BEG ||
4202 lex_state == EXPR_MID ||
4203 lex_state == EXPR_DOT ||
4204 lex_state == EXPR_ARG ||
4205 lex_state == EXPR_CMDARG) {
4206 if (cmd_state)
4207 lex_state = EXPR_CMDARG;
4208 else
4209 lex_state = EXPR_ARG;
4210 }
4211 else {
4212 lex_state = EXPR_END;
4213 }
(parse.y)
「\n ; (の後でEXPR_BEG MID DOT ARG CMDARGの状態にあるときに識別子を読
むとEXPR_CMDARGに遷移する」ということになる。しかし\n ; (の後にはそも
そもlex_stateはEXPR_BEGにしかならないので、EXPR_CMDARGへ遷移する場合に
はlex_stateはあまり意味がない。lex_stateの限定はEXPR_ARGに対する遷移に
とってだけ重要なのだ。
さて、以上を踏まえるとEXPR_CMDARGである状況が考えられる。
例えば以下のような場合だ。アンダーバーが現在位置である。
m _ m(m _ m m _
ここでdoの判定コードに戻ろう。
▼yylex−識別子−予約語−kDO−kDO_BLOCK
4185 if (CMDARG_P() && state != EXPR_CMDARG) 4186 return kDO_BLOCK; (parse.y)
括弧を省略したメソッド呼び出しの引数の中で、かつ第一引数の前でないとき。
ということはcommand_callの第二引数以降だ。つまりこういう場面だ。
m arg, arg do .... end m (arg), arg do .... end
なぜEXPR_CMDARGの場合を排除するかと言えば……例を書いてみればわかる。
m do .... end
このパターンは既にprimaryで定義されている、kDOを使うdo〜endイテ
レータでカバーできる。よってこの場合を含めるとまた衝突してしまうのである。
終わりだと思っただろうか。まだ終わりではない。 確かに論理は完結しているのだが、それは書いたことが正しければの話だ。 実はこの節の中には一つ嘘がある。
正しくは嘘というより厳密でないと言うべきだろうか。それは
CMDARG_P()について書いたこの部分だ。
どうやら、command_argsつまり括弧省略のメソッド呼び出し引数中に
いるときはCMDARG_P()が真になるようだ。
「括弧省略のメソッド呼び出し引数中にいるときは……」と言ったが、
引数「中」とはどこのことだろうか。再びrubylex-analyserを使って
厳密なところを確かめてみる。
% rubylex-analyser -e 'm a,a,a,a;'
+EXPR_BEG
EXPR_BEG C "m" tIDENTIFIER EXPR_CMDARG
EXPR_CMDARG S "a" tIDENTIFIER EXPR_ARG
1:cmd push-
EXPR_ARG "," ',' EXPR_BEG
EXPR_BEG "a" tIDENTIFIER EXPR_ARG
EXPR_ARG "," ',' EXPR_BEG
EXPR_BEG "a" tIDENTIFIER EXPR_ARG
EXPR_ARG "," ',' EXPR_BEG
EXPR_BEG "a" tIDENTIFIER EXPR_ARG
EXPR_ARG ";" ';' EXPR_BEG
0:cmd resume
EXPR_BEG C "\n" ' EXPR_BEG
右側の欄に「1:cmd push-」と出ているところがcmd_stackへのプッシュだ。そ
の行の数字の下一桁が1のときにCMDARG_P()は真になる。つまりCMDARG_P()で
ある期間は
括弧を省略したメソッド呼び出しの第一引数の直後から 最後の引数のその次の終端記号まで
と言うべきらしい。
だが本当に本当のことを言えばまだこれでも厳密ではない。 例えば次のような例がある。
% rubylex-analyser -e 'm a(),a,a;'
+EXPR_BEG
EXPR_BEG C "m" tIDENTIFIER EXPR_CMDARG
EXPR_CMDARG S "a" tIDENTIFIER EXPR_ARG
1:cmd push-
EXPR_ARG "(" '(' EXPR_BEG
0:cond push
10:cmd push
EXPR_BEG C ")" ')' EXPR_END
0:cond lexpop
1:cmd lexpop
EXPR_END "," ',' EXPR_BEG
EXPR_BEG "a" tIDENTIFIER EXPR_ARG
EXPR_ARG "," ',' EXPR_BEG
EXPR_BEG "a" tIDENTIFIER EXPR_ARG
EXPR_ARG ";" ';' EXPR_BEG
0:cmd resume
EXPR_BEG C "\n" ' EXPR_BEG
第一引数の中の、その最初の終端記号を読んだ時点でCMDARG_P()は真に
なっている。従って
括弧を省略したメソッド呼び出しの第一引数の 最初の終端記号の直後から、最後の引数のその次の終端記号まで
が完全な答えである。
この事実は何を意味だろうか。思い出してほしいのだが、CMDARG_P()を
使うのはこういうコードだった。
▼yylex−識別子−予約語−kDO−kDO_BLOCK
4185 if (CMDARG_P() && state != EXPR_CMDARG) 4186 return kDO_BLOCK; (parse.y)
EXPR_CMDARGは「command_callの最初の引数の前」という意味で、それを除外
している。ところが、CMDARG_P()は既にその意味をも含んでいるではないか。
つまりこの節最後の結論はこうである。
EXPR_CMDARGはあるだけ無駄。
本当に、これがわかったときは筆者のほうが泣きそうになってしまった。「絶
対意味がある、何かおかしい」と思ってひたすらソースを解析しまくってみ
ても全然わからないのだ。だが最終的にrubylex-analyserでいろいろなコー
ドを試しまくってやっぱり効果がないので、これは無意味なのだと結論した。
意味がないことをえんえんとやってきたのは別に単なるページ稼ぎというわけ ではなく、現実に起こりうる状況をシミュレートしたつもりである。この世に あるプログラムはどれも完全ではなく、間違いが含まれている。特に今回のよ うな微妙なところでは間違いが起こりやすい。そのとき原本を「絶対に正しい もの」として読んでいるとこのような間違いに出会ったときにハマる。結局ソー スコードを読むとき最後に信じられるのはそこで起こった事実だけなのだ。
こういう点からも動的な解析の大切さがわかってもらえると思う。調査すると きはまず事実を見るべきなのである。ソースコードは決して事実を語らない。 そこにあるのは読む人間の推測だけだ。
などといかにももっともらしい教訓を垂れたところで長く辛かった本章を終わ りとする。
一つ忘れていた。CMDARG_P()がなぜそういう値を取るのかを
説明しなければこの章は終われないのだ。問題はここだ。
▼command_args
1209 command_args : {
1210 $<num>$ = cmdarg_stack;
1211 CMDARG_PUSH(1);
1212 }
1213 open_args
1214 {
1215 /* CMDARG_POP() */
1216 cmdarg_stack = $<num>1;
1217 $$ = $2;
1218 }
1221 open_args : call_args
(parse.y)
結論から言うと、またもや先読みの影響である。command_argsは常に
次のようなコンテキストにある。
tIDENTIFIER _
ということは、これは変数参照にも見えるしメソッド呼び出しにも見える。も
し変数参照だとしたらvariableに、メソッド呼び出しならoperationに還元し
なければいけない。だから先読みをしなければ進む方向を決定できないのであ
る。それゆえcommand_argsの先頭では必ず先読みが起こり、第一引数の
最初の終端記号を読んだ後にCMDARG_PUSH()が実行されるのだ。
cmdarg_stackでPOPとLEXPOPが分かれている理由もここにある。
次の例を見てほしい。
% rubylex-analyser -e 'm m (a), a'
-e:1: warning: parenthesize argument(s) for future version
+EXPR_BEG
EXPR_BEG C "m" tIDENTIFIER EXPR_CMDARG
EXPR_CMDARG S "m" tIDENTIFIER EXPR_ARG
1:cmd push-
EXPR_ARG S "(" tLPAREN_ARG EXPR_BEG
0:cond push
10:cmd push
101:cmd push-
EXPR_BEG C "a" tIDENTIFIER EXPR_CMDARG
EXPR_CMDARG ")" ')' EXPR_END
0:cond lexpop
11:cmd lexpop
+EXPR_ENDARG
EXPR_ENDARG "," ',' EXPR_BEG
EXPR_BEG S "a" tIDENTIFIER EXPR_ARG
EXPR_ARG "\n" \n EXPR_BEG
10:cmd resume
0:cmd resume
cmd関係だけを見て対応関係を取っていくと……
1:cmd push- パーサpush(1) 10:cmd push スキャナpush 101:cmd push- パーサpush(2) 11:cmd lexpop スキャナpop 10:cmd resume パーサpop(2) 0:cmd resume ハーサpop(1)
「cmd push-」というように末尾にマイナスが付いているものがパーサでの
pushだ。つまりpushとpopの対応関係がずれている。本来は
push-が二回連続で起きてスタックは110になるはずなのに、先読みのせいで
101になってしまった。CMDARG_LEXPOP()が用意してあるのはこの現象に対応する
ための苦肉の策だ。そもそもスキャナではいつも0をpushするのだから、スキャ
ナがpopするのも常に0であるはずなのだ。そこが0にならないのならば、パー
サのpushが遅くなって1になっていると考えるしかない。だからその値を残す。
逆に言うと、パーサのpopに来たところではスタックはもう正常な状態に戻っ
ているはずである。だから本当は普通にpopしても問題ない。そうしていない
のは、とにかく正しく動けばいい、という理由からではないかと思われる。ポッ
プしようが$$に保存して復帰しようが動きは同じなのだ。特にこれからいろい
ろ変更していくことを考えると先読みの挙動がどう変わるかわからない。しか
もこの問題が起こるのは、将来禁止されることが決まっている文法だ（だから
警告が出ている）。そんなものを通すためにいろいろな場合を考え対処するの
は骨である。だから現実のrubyはこういう実装でいいのだと、筆者は思う。
これで本当に解決である。
御意見・御感想・誤殖の指摘などは 青木峰郎 <aamine@loveruby.net> までお願いします。
『Rubyソースコード完全解説』 はインプレスダイレクトで御予約・御購入いただけます (書籍紹介ページへ飛びます)。
Copyright (c) 2002-2004 Minero Aoki, All rights reserved.