構文解析

Ruby のノード

既に書いたようにスクリプトはいったん構文木に変換される。そして 構文木とはノード構造体のリンクなのであった。Ruby ではノードは NODE (struct RNode) で表わされる。

typedef struct RNode {
    unsigned long flags;
    char *nd_file;
    union {
        struct RNode *node;
        ID id;
        VALUE value;
        VALUE (*cfunc)();
        ID *tbl;
    } u1;
    union {
        struct RNode *node;
        ID id;
        long argc;
        VALUE value;
    } u2;
    union {
        struct RNode *node;
        ID id;
        long state;
        struct global_entry *entry;
        long cnt;
        VALUE value;
    } u3;
} NODE;

(node.h 編集)

flags は主にこの共用体の使われかたを示すフラグである。ただしこの三つの 共用体メンバの使い方の組み合わせは一つのノードにおいて一通りしかない。 つまり、フラグによってどのメンバを使うかは一意に決まる。 またこの後にはこれら共用体メンバにアクセスするためのマクロが用意されていて、 ソース中ではほぼ間違いなくこのマクロのほうが使われる。 そのごくわずかな例外として u1 u2 u3 を直接使っているところが二カ所だけあり、 それは gc.cNODE をマークするところと、parse.yNODE を生成している ところである。これらマクロは数が多いので後の章で順次紹介していくことにする。

それから構造体名が RNode であることから推測できるようにノードは VALUE である。 つまりノードの生成と解放は Ruby の GC によって管理される。これは GC の章で書いたとおりである。

ファイル名と行番号

NODEnd_file にはこのノードに対応するテキストが存在していたファイル名 (へのポインタ) が保持されている。ファイル名があれば行番号もありそうだが 対応するメンバは見あたらない。実は行番号は以下のマクロによって flags に 埋めこまれているのである。

#define NODE_LSHIFT (FL_USHIFT+8)
#define NODE_LMASK  (((long)1<<(sizeof(NODE*)*CHAR_BIT-NODE_LSHIFT))-1)
#define nd_line(n) (((RNODE(n))->flags>>NODE_LSHIFT)&NODE_LMASK)
#define nd_set_line(n,l) \
    RNODE(n)->flags=((RNODE(n)->flags&~(-1<<NODE_LSHIFT))|(((l)&NODE_LMASK)<<NODE_LSHIFT))

(node.h)

ほとんど暗号だ。プリプロセッサの制約を外して改行などを加え、 優先順位もちょっと無視して括弧を外すと以下のようになる。

#define NODE_LSHIFT (FL_USHIFT + 8)
#define NODE_LMASK
    ((long)1 << (sizeof(NODE*) * CHAR_BIT - NODE_LSHIFT)) - 1

#define nd_line(n)
    (RNODE(n)->flags >> NODE_LSHIFT) & NODE_LMASK

#define nd_set_line(n,line)
    RNODE(n)->flags =
        RNODE(n)->flags & ~(-1 << NODE_LSHIFT)    |
        (line & NODE_LMASK) << NODE_LSHIFT

まず NODE_LMASK から見ていこう。sizeof(NODE*) * CHAR_BITNODE のビットサイズである。これから NODE_LSHIFT だけ引いたビット分だけ 1 を左にシフトする。

<----------- sizeof(NODE), bit ----------->
<--- NODE_LSHIFT-1 -->100000000000000000000

ここから 1 を引くとくりさがりがおこるので

<----------- sizeof(NODE), bit ----------->
<---- NODE_LSHIFT ---->11111111111111111111

となる。つまり NODE_LMASKsizeof(NODE) - NODE_LSHIFT ビット分の 1 の並びである。続いて set_nd_line を見よう。-1 は全ビット 1 であることに 注意すると、

-1                    111111111111111111111111111
-1 << NODE_LSHIFT     111111<--- NODE_LSHIFT --->
~(-1 << NODE_LSHIFT)  000000111111111111111111111

であるので、まず最初の bit-and で行番号のうち NODE_LMASK より左のビットが クリアされる。そして行番号を NODE_LSHIFT 分左に動かし、flagsbit-or する。 つまり結局 flags の上位 NODE_LMASK ビット分が行番号のために使われているのだと いうことがわかる。現在は FL_USHIFT が 11 なので (ruby.h)、32 ビットマシンでは 32-(11+8) = 13 ビット分が行番号に使えることになる。ということは行番号が 2**13=8192 を超えると Ruby の行番号表示はおかしくなるはずである。試そう。

File.open( 'overflow.rb', 'w' ) do |f|
  10000.times { f.puts }
  f.puts 'raise'
end

筆者のマシンでは ruby overflow.rb で 1809 行と表示された。成功である。 ただし 64 ビットマシンではもうちょっとファイルを大きくしないとうまく 失敗できないだろう。

ところで 8000 行でオーバーフローということは 「このサイズを超えるスクリプトは書いちゃいかん」という思想を 暗示しているのだろうか? 真相やいかに。

パーサ

rubyパーサyacc を使って書かれており、 parse.y がその入力ソースである。しかし yacc についての解説は本論から外れる ので、拙著 『Ruby を 256 倍使う本・無道編』でも読んでくれ。こっちは yacc の Ruby 版 Racc についての本なんだけど、まあ同じようなもんだ。

パーサの目的は、すでに書いたようにソースコードから構文木を作りだすことである。 さてそれでパーサがあればスキャナもある。

スキャナ

トークンバッファ

スキャナの最も低レベルな部分には入力バッファとトークンバッファがある。 ruby(Ruby の) IO と 文字列の両方から入力できるようになっていて、 入力バッファはそれを隠蔽する。一方トークンバッファはひとつのトークンが 完成するまでまとめてとっておく。まずは読み出しバッファのインターフェイス から示す。

int nextc()

ポインタ上の文字を返してポインタをひとつ進める

void pushback(int c)

一文字バッファに戻す (ポインタもひとつ戻る)。c を明示するように なっているのは、

int peek(int c) [マクロ]

ポインタ上にある文字が c と同じかどうか調べる (ポインタは進まない)

以下がトークンバッファのインターフェイス。

void tokadd(char c)

バッファに一文字追加する

void tokfix() [マクロ]

トークンを終端する。

char *tok() [マクロ]

トークンへのポインタ

int toklen() [マクロ]

現在読み込み中のトークンの長さ (不含 NUL)

int toklast()

現在読み込み中のトークンの最後の文字 (長さゼロのときは 0)

yylex()

それで

文脈依存の解析

スキャンがパースから完全に独立していれば話は簡単なのだが、現実はそう 簡単ではない。Ruby の文法は特に複雑で空白が前にあるとなんか違うとか、 まわりの状況でトークンの切り方が変わったりする。例えば左シフト演算子なんかは 左シフトの時もあれば特異クラス定義にもなり、ヒアドキュメントにもなる。 そういうものを区別するために Ruby では細々とフラグを立てて状況を判断する。