第11章 状態付きスキャナ

概要

理論のように、スキャナはただひたすらトークンに区切り、パーサはその並び だけを扱い、両者は完璧に独立している……という段階で済むならば、それは とてもありがたいことだ。しかし現実はそううまくはいかない。プログラムの 文脈によってトークンの切りかたや記号を変えなければならないということは よくある。この章ではスキャナとパーサの連携について見ていくことにする。

具体例

普通のプログラム言語なら、空白は単語の区切りになる以外はたいし て意味を持たない。しかし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)。

(transittobeg)
図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の状態について簡単に説明しておく。

式の先端。\n ( { [ ! ? : , 演算子 op=などの直後。 最も一般的な状態である。

予約語のreturn break next rescueの直後。 二項演算子の*&が無効になる。 挙動はEXPR_BEGと似ている。

メソッド呼び出しのメソッド名部分である可能性がある要素の直後、 または'['の直後。 ただしEXPR_CMDARGである場所を除く。

通常形式のメソッド呼び出しの最初の引数の前。 詳しくは「doの衝突」の節を参照。

文が終端可能なところ。例えばリテラルや括弧のあと。ただしEXPR_ENDARGで ある場所は除く。

EXPR_ENDの特殊版。tLPAREN_ARGに対応する閉じ括弧の直後。 「括弧でくくられた第一引数」の項を参照。

メソッド名の前。具体的にはdefaliasundef・シンボルの':'の 直後である。「`」が単独で名前になる。

メソッド呼び出しのドットのあと。EXPR_FNAMEと扱いは似ている。 あらゆる予約語がただの識別子として扱われる。 '`'が単独で名前になる。

予約語classの後ろ。この状態だけはかなり限定的である。

まとめると、

はそれぞれ似たような状況を表す。EXPR_CLASSだけはちょっと特殊だが、 出てくる場所が非常に限定されているのでそもそもあまり考えなくて済む。

改行の制御

問題

Rubyの文には必ずしも終端が必要なかった。例えばCやJavaでは必ず文末に セミコロンを置かないといけないが、Rubyではそういうものは必要ない。 一行一文が基本なので、行末で勝手に文が終わるのである。

ところがその一方で「明らかに続きがある」場合は自動的に文が継続すること になっている。「明らかに続きがある」状態とは、

などである。

実装

このような文法を実現するためにはどうしたらいいのだろう。単にスキャナで 改行を読み飛ばすだけではだめである。Rubyのように文の両端が予約語で区切 られている文法ならC言語ほどは衝突しないが、軽く試してみたところ、returnnextbreak、メソッド呼び出しの括弧省略は全て削らないと通らなかった。 そういうものを残しておくには文末にはなんらかの終端記号がないといけない。 それが\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_BEGEXPR_FNAMEEXPR_DOTEXPR_CLASSではgoto retry、 つまり意味がないので読み飛ばす。ラベルretryyylex()の巨大switchの 前にある。

その他のところでは改行が意味を持つのでパーサに渡し、ついでに lex_stateEXPR_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_stateEXPR_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では予約語をメソッド名に使うことができる。ただしメソッド名に使える と一口に言ってもコンテキストがいくつかあって、

という三つが考えられる。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が二項演算子だ。どちらの規則も単に終端記号を全部並 べてあるだけなので省略する。それからtFIDgsub!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のときには無条件で 予約語の処理を抜かすから、ドットの後の予約語の記号はtIDENTIFIERtCONSTANTになる。

シンボル

予約語のシンボルはパーサとスキャナの両方で対処される。 まず規則から。

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_ENDEXPR_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_MODkIFに変えてyaccで処理してみる。

% yacc parse.y
parse.y contains 4 shift/reduce conflicts and 13 reduce/reduce conflicts.

目論見通り衝突しまくっている。興味があればyacc-vオプションを 付けてログを取り、中を読んでみよう。どう衝突したのか詳細に書いてある。

実装

さてどうしたらいいだろうか。rubyでは普通のifkIF、後置のifkIF_MODというように記号レベルで(つまりスキャナレベルで)区別してし まう。他の後置系演算子も全く同じで、 kUNLESS_MOD kUNTIL_MOD kWHILE_MOD kRESCUE_MODkIF_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の末尾、識別子をスキャンしたあとだ。最後の(一番内 側の)ifelseが修飾子を扱う部分である。EXPR_BEGかどうかで返り値を 変えていることがわかる。ここが修飾子かどうかの判定だ。つまり変数kwが カギである。そしてkwは……とずっと上を見ていくと、struct kwtableだと わかる。

struct kwtablekeywords内で定義されている構造体で、 ハッシュ関数rb_reserved_word()gperfが作ってくれるということは 前章で話した。もう一度構造体を紹介しよう。

keywords struct kwtable

   1  struct kwtable {char *name; int id[2]; enum lex_state state;};

(keywords)

nameid[0]については説明済みである。予約語名とその記号だ。 今回は残りのメンバについて話す。

まずid[1]がいま問題の修飾子に対応する記号である。例えばifなら kIF_MODだ。 修飾子版がない予約語だとid[0]id[1]には同じものが入っている。

そしてstateenum 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の衝突

問題

イテレータの書式にはdoend{}の二種類があるのだった。この二つの 違いは優先順で、{}のほうがずっと高い。優先順位が高いということは 文法として単位が「小さい」ということで、より小さい規則に入れることが できる。例えばstmtでなくexprprimaryに入れることができる。例えば 昔は{}イテレータがprimarydoendイテレータがstmtにあった。

ところが途中で次のような式に対する要求が出てきた。

m do .... end + m do .... end

これを許すにはdoendイテレータをargprimaryに入れればいい。 ところがwhileの条件式はexpr、つまりargprimaryを含むので、 ここでdoが衝突してしまう。具体的には次のようなときだ。

while m do
  ....
end

ちょっと見ではdowhiledoになるのが正しそうである。しか しよくよく見るとm doendというくくりも考えられる。人間が混同でき るということはyaccなら確実に衝突する。実際にやってみよう。

/* doの衝突の実験 */
%token kWHILE kDO tIDENTIFIER kEND
%%
expr: kWHILE expr kDO expr kEND
    | tIDENTIFIER
    | tIDENTIFIER kDO expr kEND

while、変数参照、イテレータだけに問題を単純化した。この規則は条件式の 冒頭にtIDENTIFIERが来るとshift/reduce conflictを起こす。tIDENTIFIERを 変数参照にしてdowhileに付けるのが還元、イテレータのdoにするのが シフトだ。

悪いことにshift/reduce conflictはシフト優先なので放置しておくとdoはイ テレータのdoになる。かと言って演算子優先順位その他で還元に倒すとdoが全 くシフトされなくなり、doそれ自体が使えなくなる。つまり全ての問題を矛 盾なく解決するには、doendイテレータをexprにすることなく演算子が使え る規則を書くか、スキャナレベルで解決するしかない。

しかしdoendイテレータをexprに入れないというのはとても非現実的である。 exprのための規則(ということはargprimaryもだ)を全て繰り返さないと いけなくなる。従ってこの問題はスキャナで解決するのが適切だ。

規則レベルの解決

以下に関連規則を簡約化したものを示す。

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

見てのとおり、whiledoとイテレータのdoで終端記号が違う。 whilekDO_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_CONDkDO/kDO_BLOCKという比較、kDOkDO_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_typelong(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();

ここから次のような法則を発見できる。

とすると、なんとなく 使い道が見えてくる。cond_stackという名前も考えると、条件式と同じレベルに いるかどうか判定するマクロに違いない(図2)。

(condp)
図2: COND_P()の移り変わり

この仕掛けによって次のような場合にもうまく対処できるようになる。

while (m do .... end)   # doはイテレータのdo(kDO)
  ....
end

ということは、32ビットマシンでlong longがない場合には括弧か条件式が 32レベルネストしたあたりで変なことになる可能性がある。とはいえ普通は そんなにネストしないから実害は出ない。

またCOND_LEXPOP()の定義がちょっと不思議なことになっていたのは、どうやら 先読み対策らしい。ただ現在はうまいこと先読みが起こらないような規則に なっているためにPOPLEXPOPを分ける意味がなくなっている。つまり 現時点では「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'

-erubyと同じくプログラムをコマンドラインから直接渡すオプションだ。 これを使っていろいろ試してみよう。 まず問題の、第一引数が括弧でくくられている場合。

% 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)

最初のiftLPARENだから、通常の式括弧だ。その判断基準はlex_stateBEGMID、つまり確実に式の始まりにいるときである。

その次のspace_seenは括弧の前に「空白があるかどうか」を表している。 空白があり、かつlex_stateARGCMDARGのとき……つまり第一引数の 前なら、記号は'('でなく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_callcommand_callに注目してほしい。もしtLPAREN_ARGを導入せず '('のままにすると、command_argsからargsが出る、argsからargが出る、 argからprimaryが出る、そしてtLPAREN_ARGのところから'('が出て method_callと衝突してしまう(図3)。

(trees)
図3: method_callcommand_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の規則が出る。 そしてexprargを含むから、展開の方法次第で

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_ARGprimaryが来るときだけ なのだから、さらに限定して 「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_BLOCKtLBRACE_ARGになっている。 なぜkDO'{'ではいけないのだろう。そういうときはとりあえず試してみろ、 ということで、kDO_BLOCKkDOに、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。

もう一方はdoendがらみだ。こっちは

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_stateEXPR_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-analyserlex_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

まで読んだところでまた先読みする。なぜなら次が','')'かでrule2rule3に分かれるからだ。もし','だったらこれは引数区切りのカンマとしか 考えられないので即座に二引数以上、即ちrule3と確定する。もし入力が 単なるaではなくifだったりリテラルの「93」だったりしても同じことである。 その入力が完了したところでrule2rule3を区別するために、即ち 一引数か二引数以上かを区別するために先読みが起こる。

この場合、全ての規則で')'の前に(別々の)埋め込みアクションがあると いうことが重要なのだ。アクションというものは一回実行してしまうともう取 り返しが付かないので、パーサは「絶対確実」な状況になるまでアクションの 実行を先延ばししようとする。だからこそ先読み一つでそういう状況が作れな いの場合はパーサ生成時に排除する必要があり、つまりそれが「衝突」である。

入力Cはどうだろうか。

m (a, b, c

ここまで来た時点でもうrule3しか可能性がないので、先読みはなさそうな気 がする。

ところがそうはいかない。次が'('ならメソッド呼び出しだし、','')'なら 変数参照にしないといけない。つまり今度は埋め込みアクションの還元ではな くて、引数の要素を確定するために先読みが起こる。

では他の入力ではどうなのだろうか。例えば第三引数がメソッド呼び出し だったらどうだろう。

m (a, b, c(....)    # ... ',' method_call

これもやっぱり先読みが必要なのだ。なぜなら、次が','')'かでシフトと還 元に分かれる。だから、この規則では結局あらゆる場合に埋め込みアクション の実行よりも早く')'が読まれる。実にややこしい。よく思い付いたなあと感 動してしまう。

ところで埋め込みアクションではなく通常のアクションでlex_stateをセット してはいけないのだろうか。例えばこのように。

                | tLPAREN_ARG ')' { lex_state = EXPR_ENDARG; }

これは、いけない。なぜならアクションの還元の前に(また)先読みが起こる 可能性があるからだ。今度は先読みが裏目に出てしまうのである。このことか らもわかるように、LALRパーサの先読みを逆用するなんてのは相当な裏技である。 素人にはお勧めできない。

doendイテレータ

ここまでで{}イテレータには対処できたがまだdoendイテレータが残って いる。同じイテレータなら同じ方法で対処できそうだが、それは違う。 {}doendでは優先順位が違うのだ。例えば次のように。

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_BLOCKkDOを区別する部分だけだ。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_stackopen_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_startyylex一回の間だけ保存して おく一時変数にすぎない。

では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_startparse.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_stateEXPR_BEGにしかならないので、EXPR_CMDARGへ遷移する場合に はlex_stateはあまり意味がない。lex_stateの限定はEXPR_ARGに対する遷移に とってだけ重要なのだ。

さて、以上を踏まえるとEXPR_CMDARGである状況が考えられる。 例えば以下のような場合だ。アンダーバーが現在位置である。

m _
m(m _
m m _

まとめ

ここでdoの判定コードに戻ろう。

yylex−識別子−予約語−kDOkDO_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を使うdoendイテ レータでカバーできる。よってこの場合を含めるとまた衝突してしまうのである。

事実と真実

終わりだと思っただろうか。まだ終わりではない。 確かに論理は完結しているのだが、それは書いたことが正しければの話だ。 実はこの節の中には一つ嘘がある。

正しくは嘘というより厳密でないと言うべきだろうか。それは 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−識別子−予約語−kDOkDO_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_stackPOPLEXPOPが分かれている理由もここにある。 次の例を見てほしい。

% 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だ。つまりpushpopの対応関係がずれている。本来は 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.