第10章 パーサ

指針

パーサの構築

パーサのメインソースはparse.yである。*.yだからyaccの入力で、 ここからparse.cが生成される。

また他にはlex.cという思わせぶりな名前のファイルがあるのだが、スキャナ が入っているわけではない。これはgperfというツールが生成したファイルで、 予約語のハッシュテーブルが定義されている。その入力ファイルはkeywordsだ。 lex.cparse.c#includeして使われる。 中身について説明するのはその場にならないと難しいので後にまわそう。

まとめるとパーサの構築手順は図1のようになる。 Windowsで生きている人のために説明するとmvはファイルを移動する コマンドである。ccはもちろんCコンパイラでcppは Cのプリプロセッサだ。

(build)
図1: パーサの構築手順

parse.yの腑分け

続いてparse.yを眺めてみよう。 おおざっぱに言うとparse.yは次のような形をしている。

▼parse.y

%{
ヘッダ
%}
%union ....
%token ....
%type ....

%%

規則

%%
ユーザ定義コード部
    パーサインターフェイス
    スキャナ(文字列処理)
    構文木の構築
    意味解析
    ローカル変数の管理
    IDの実装

定義部・規則部に関しては既に述べたとおり。ここはまさにパーサの核心で あるので、真っ先に次の節から解説を始める。

ユーザ定義コード部にはかなりたくさんの補助関数があるのだが、おおまかに 言って上記の六つに分類できる。それぞれ以下のような割り振りで解説してい く。

セクション
パーサインターフェイス本章第三節「スキャナ」
スキャナ関連本章第三節「スキャナ」
構文木の構築第12章『構文木の構築』第二節「構文木の構築」
意味解析第12章『構文木の構築』第三節「意味解析」
ローカル変数の管理第12章『構文木の構築』第四節「ローカル変数」
IDの実装第3章『名前と名前表』第二節「IDとシンボル」

文法規則総論

コーディングルール

rubyの文法は一定のコーディングルールに則って書かれているので、 それを知っておくと読みやすくなる。

まず記号名について。非終端記号は全部小文字。終端記号はプリフィクス+大 文字。プリフィクスは、予約語(keyword)がk。それ以外の終端記号 (terminal)がtである。

▼記号名の例

単語記号
(非終端)bodystmt
ifkIF
defkDEF
rescuekRESCUE
varnametIDENTIFIER
ConstNametCONST
1tINTEGER

このルールの例外はklBEGINklENDのみだ。それぞれ予約語の 「BEGIN」「END」に対応する記号で、llargelだと思われる。 予約語には小文字のbegin endもあるのでこのような区別が付いている。

重要な記号

規則ファイルには文法とアクションが書いてあるのだった。しかしいまは規則 にだけ注目したいので、アクションは必要ない。規則だけ取り出すには、 rubysample/に入っているexyacc.rbなどのツールが使える。他には yacc -vで出力されるy.outputというログファイルにも規則が出ているが、 こちらは見ためがあまりよくない。本章ではexyacc.rbを少し改造した もの\footnote{exyacc.rb改:添付CD-ROMtools/exyacc2.rb}を 使って文法を見ていくことにしよう。

parse.y(規則)

program         : compstmt

bodystmt        : compstmt
                  opt_rescue
                  opt_else
                  opt_ensure

compstmt        : stmts opt_terms
                       :
                       :

かなり長いリストが出力された。現在、規則は450以上ある。 ここまで大きいとさすがにいきなり全体を並べて把握するなんてことは 不可能だ。こういうものは重要なところだけ見ていくに限る。

ではどの記号が重要だとわかるのだろうか。それには記号の名前に注目すれば よい。例えばprogramexprstmtprimaryargなどの名前は非 常に重要である。なぜならそれはプログラム言語の文法要素の一般的な区分を 表すからだ。一般にプログラムの構文で注目すべき要素を以下に一覧する。

構文要素予測される記号名
プログラム全体program prog file input stmts whole
statement stmt
expression expr exp
最小要素primary prim
代入の左辺lhs(left hand side)
代入の右辺rhs(right hand side)
関数呼び出しfuncall function_call call function
メソッド呼び出しmethod method_call call
引数argument arg
関数定義defun definition function fndef
宣言一般declaration decl

そして普通の言語なら次のような階層構造が存在する。

プログラム全体だいたいは文のリスト。
文(statement)組み合わせられないもの。構文木の幹。
式(expression)それ自体が組み合わせで、また他の式の一部になれるもの。構文木の枝。
項(primary)分割できないもの。構文木の葉。

文はCの関数定義やJavaのクラス定義のようなもの。式は手続き呼び出しや数 式など。文字列リテラルや数値はたいてい項である。いずれかの要素がないこ とはよくあるが、この上下関係、つまりprogramstmtexprprimary、が通用しない言語はまずない。

ただし小さいレベルの構造は上の構造に入ることもできる。例えばCでは関数 呼び出しは式だが単独で置ける。つまり式でありながら文にもなれる。

またその逆に、式を括弧で囲むと項になったりもする。レベルの低い要素ほど 優先順位が高くなるからだ。

文の範囲は言語によってだいぶ違う。例えば代入を考えてみよう。Cだと式に 入っているので代入式全体の値というものを使うことができる。しかし Pascalだと代入は文なのでそういうことはできない。また関数やクラスの定 義は文に入るのが一般的だが、LispやSchemeだとあらゆるものが式なので文が なかったりする。Rubyもイメージはそちらに近い。

全体構造

それではrubyの規則に移ろう。まずyaccでは最初の規則の左辺が文法全体を表 しているのだった。つまり現在はprogramである。ここからずっと辿りながら 見ていくと定石通りprogram stmt expr primaryの四つが見付かる。これに argを加えた規則を見てみよう。

rubyの文法(概要)

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

それぞれの最後の規則に注目すると、非常にわかりやすく programstmtexprargprimary という上下関係が出ている。

またprimaryのこの規則も注目したい。

primary         : literal
                    :
                    :
                | tLPAREN_ARG expr  ')'      /* これ */

tLPAREN_ARGは、終端記号を示すt、leftのL、parentheses(丸括弧)の PARENから成る。つまり開き括弧のことだ。なぜ'('としないかは 次章『状態付きスキャナ』で説明しよう。なんにしても、この規則がexprprimaryに縮退させるための規則である。つまりここのところで 図2のように規則が循環している。矢印は実際にパースするとき に還元される順だ。

(exprloop)
図2: exprの縮退

そしてその次の規則はさらにすごい。

primary         : literal
                    :
                    :
                | tLPAREN compstmt ')'   /* これ */

なんとcompstmt、つまりプログラム全体(program)と等しいものを primaryに縮退させてしまおうというのだ。また図にすると図3の ようになる。

(progloop)
図3: programの縮退

これが何を意味するかというと、Rubyに存在するあらゆる構文は括弧で囲むと primaryになってしまう、即ちメソッドの引数にも代入の右辺にもできる ということである。これはとんでもない事実だ。実際に確かめてみよう。

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

このファイルを-cオプション付きでrubyにかける。 -cは構文チェックをするオプションだ。

% ruby -c primprog.rb
Syntax OK

実に信じ難いことだが、本当に通ってしまった。どうやら勘違いではないよう である。

細かいことを言うと意味解析(第12章『構文木の構築』参照)で弾かれるものが あるので完璧に通用するわけではない。例えばreturn文を引数にするとエラー になる。だが少なくとも見ためレベルでは「括弧で囲むとなんでも引数にでき る」という法則は実際に成立する。

次は重要要素の中身を順番に見ていこう。

program

program

program         : compstmt

compstmt        : stmts opt_terms

stmts           : none
                | stmt
                | stmts terms stmt

前述の通りprogramは文法全体、即ちプログラム全体を表している。その programcompstmtsと同じであり、compstmtsstmtsとほぼ同じである。 そのstmtsterms区切りのstmtのリストである。つまりプログラム全体は terms区切りのstmtのリストである。

termsはもちろんterminatorsの略で、文を終端する記号、セミコロンだとか 改行のことだ。opt_termsはOPTional terms(省略可能なterms)だろう。 定義は次のようになっている。

opt_terms

opt_terms       :
                | terms

terms           : term
                | terms ';'

term            : ';'
                | '\n'

terms';''\n'の後に任意の数だけ';'が続く並びなので、 この規則だけから考えると二個以上の改行があるとまずいように 思える。実際に試してみよう。

1 + 1   # 改行一つめ
        # 改行二つめ
        # 改行三つめ
1 + 1

再びruby -cを使う。

% ruby -c optterms.rb
Syntax OK

おかしい。通ってしまった。実を言うと、連続した改行はスキャナのレベルで 捨てられてしまってパーサには最初の一つしか渡らないようになっているのだ。

ところで、programcompstmtは同じものだと言ったが、それならこの規則は 何のために存在するのだろう。実はこれはアクションを実行するためだけにあ るのだ。例えばprogramならプログラム全体について一度だけ必要な処理を実 行するために用意されている。純粋に文法のことだけ考えるならprogramは省 略しても全く問題ない。

これを一般化すると、規則には見ための解析のために必要なものと、アクショ ンを実行するために必要なものの二種類があるということになる。stmtsのと ころにあるnoneもアクションのために必要な規則の一つで、空リストに対して (NODE*型の)NULLポインタを返すために用意されている。

stmt

次に文、stmtだ。stmtの規則はわりと量があるので、少しずつ見ていく ことにする。

stmt(1)

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 '}'

なんとなくわかる。最初にいくつかあるのはaliasだし、 次がundef、その後にいくつか並ぶ「なんたら_MOD」は modifier(修飾子)のことだろうから、後置系構文だと想像が付く。

expr_valueprimary_valueはアクションのために用意されている規則である。 例えばexpr_valueなら値(value)を持つexprであることを示す。値 を持たないexprとはreturnbreak、あるいはそういうものを含むif文 などのことだ。「値を持つ」の詳しい定義は 第12章『構文木の構築』で見る。 primary_valueも同じく「値を持つ」primaryである。

klBEGINklENDは説明した通りBEGINENDのこと。

stmt(2)

                | 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

この規則は全部くくって見るのが正しい。 共通点は右辺に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)

                | lhs '=' mrhs_basic
                | mlhs '=' mrhs

この二つは多重代入である。mrhsmlhsと同じ作りで、multipleな rhs(右辺)。 こう見てくると、名前の意味を知るだけでもかなりわかりやすいということが わかる。

stmt(4)

                | expr

最後に、exprへ連結する。

expr

expr

expr            : kRETURN call_args
                | kBREAK call_args
                | kNEXT call_args
                | command_call
                | expr kAND expr
                | expr kOR expr
                | kNOT expr
                | '!' command_call
                | arg

式。rubyの式は文法上はかなり小さい。なぜなら普通はexprに入るものがほと んどargに行ってしまっているからだ。逆に言うと、ここにはargに行けなかっ たものが残っているということになる。では行けなかったものはなにかと言う と、これまたメソッド呼び出し括弧の省略組である。call_argsは剥き出しの 引数リストで、command_callは先程言ったとおり括弧省略メソッドのこと。こ ういうものを「小さい」単位に入れると衝突しまくることになる。

ただし以下の二つだけは種類が違う。

expr kAND expr
expr kOR expr

kANDは「and」でkORは「or」。この二つは制御構造としての役割があ るので、command_call以上に「大きい」構文単位に入れなければならない。 そしてcommand_callexprにある。だから最低でもexprにしてやらない とうまくいかない。例えば次のような使いかたが存在するのだが……

  valid_items.include? arg  or raise ArgumentError, 'invalid arg'
# valid_items.include?(arg) or raise(ArgumentError, 'invalid arg')

もしkANDの規則がexprでなくてargにあったとすると、次のように 連結されてしまうことになる。

valid_items.include?((arg or raise)) ArgumentError, 'invalid arg'

当然パースエラーだ。

arg

arg

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

規則の数は多いが、文法の複雑さは規則の数には比例しない。単に場合分けが 多いだけの文法はyaccにとっては非常に扱いやすく、むしろ規則の深さである とか再帰のほうが複雑さに影響する。

そうすると演算子のところでarg OP argという形で再帰しているのが気になる のだが、これらの演算子には全て演算子優先順位が設定されているため 実質上ただの列挙にすぎない。 そこでargの規則からそういう「ただの列挙」を併合して削ってしまおう。

arg: lhs '=' arg              /* 1 */
   | primary T_opeq arg       /* 2 */
   | arg T_infix arg          /* 3 */
   | T_pre arg                /* 4 */
   | arg '?' arg ':' arg      /* 5 */
   | primary                  /* 6 */

終端記号および終端記号のリストは区別する意味がないので全部まとめてT_の 付く記号で表現した。opeqoperator + equalT_pre'!''~'の ような前置型演算子、T_infix'*''%'と言った二項演算子を表す。

この構造で衝突しないためには以下のようなことが重要になる (ただしこれが全てではない)。

arglhsと部分的に重なるので'='があると規則1と3が区別できない。

argprimaryを含むから共通項を持つと規則2と3が区別できない。

もし含むと規則3と5がshift/reduce conflictを起こす。

もし含むと規則4と5がかなり複雑に衝突する。

結論としては全ての条件が成立しているので、この文法は衝突しない。 当然と言えば当然だ。

primary

primaryは規則が多いので最初から分割して示す。

primary(1)

primary         : literal
                | strings
                | xstring
                | regexp
                | words
                | qwords

リテラル類。literalSymbolリテラル(:sym)と数値。

primary(2)

                | var_ref
                | backref
                | tFID

変数類。var_refはローカル変数やインスタンス変数など。 backref$1 $2 $3……。 tFID!?が付いた識別子、例えばinclude? reject!など。 tFIDはローカル変数ではありえないので、 それ単独で出てきたとしてもパーサレベルでメソッド呼び出しになる。

primary(3)

                | kBEGIN
                  bodystmt
                  kEND

bodystmtrescueensureも含んでいる。 つまりこれは例外制御のbeginである。

primary(4)

                | tLPAREN_ARG expr  ')'
                | tLPAREN compstmt ')'

既に説明した。構文縮退。

primary(5)

                | primary_value tCOLON2 tCONSTANT
                | tCOLON3 cname

定数の参照。tCONSTANTは定数名(大文字で始まる識別子)。

tCOLON2::tCOLON3は両方とも::なのだが、tCOLON3はトップレベルを 意味する::だけを表している。つまり::Constという場合の::である。 Net::SMTPのような::tCOLON2だ。

同じトークンに違う記号が使われているのは括弧省略メソッドに対応する ためである。例えば次の二つを見分けるためだ。

p Net::HTTP    # p(Net::HTTP)
p Net  ::HTTP  # p(Net(::HTTP))

直前にスペースがあるか、あるいは開き括弧などの境界文字がある場合は tCOLON3でそれ以外ではtCOLON2になる。

primary(6)

                | primary_value '[' aref_args ']'

インデックス形式の呼び出し、例えばarr[i]

primary(7)

                | tLBRACK aref_args ']'
                | tLBRACE assoc_list '}'

配列リテラルとハッシュリテラル。こちらのtLBRACK'['を表して いるのだが、'[''['でも前に空白のない'['のこと。この区別が必要 なのもメソッド呼び出し括弧の省略の余波だ。

それにしてもこの規則の終端記号は一文字しか違わないので非常にわかりずらい。 以下の表に括弧の読みかたを書いておいたので対照しながら読んでほしい。

▼各種括弧の英語名

記号英語名日本語名(の一例)
( )parentheses丸括弧、括弧
{ }bracesヒゲ括弧、中括弧
[ ]brackets角括弧、大括弧

primary(8)

                | kRETURN
                | kYIELD '(' call_args ')'
                | kYIELD '(' ')'
                | kYIELD
                | kDEFINED opt_nl '('  expr ')'

メソッド呼び出しと形式が似ている構文。 順番に、returnyielddefined?

yieldには引数が付いているのにreturnに引数がないのはどうしてだろう。 根本的な原因は、yieldはそれ自体に返り値があるのに対しreturnには返り値が ないことである。ただし、ここで引数がないからといって値を渡せないわけでは、 もちろんない。exprに次のような規則があった。

kRETURN call_args

call_argsは剥き出しの引数リストなのでreturn 1return nilには対 処できる。return(1)のようなものはreturn (1)として扱われる。という ことは、次のように引数が二個以上あるreturnには括弧が付けられないはず だ。

return(1, 2, 3)   # return  (1,2,3)と解釈されてパースエラー

このあたりは次章『状態付きスキャナ』を読んでから もう一度見てもらうとよくわかるだろう。

primary(9)

                | operation brace_block
                | method_call
                | method_call brace_block

メソッド呼び出し。method_callは引数あり(括弧もある)、operationは 括弧も引数もなし。brace_block{}doendで、それがついて いるメソッドとはつまりイテレータだ。braceなのになぜdoendが入る のか……ということにはマリアナ海溝よりも深淵な理由があるのだが、これも やはり次章『状態付きスキャナ』を読んでもらうしかない。

primary(10)

  | 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

基本制御構造。ちょっと意外なのは、こんなデカそうなものがprimaryという 「小さい」ものの中にあることだ。primaryargでもあるのでこんなこと もできるということになる。

p(if true then 'ok' end)   # "ok"と表示される

Rubyの特徴の一つに「ほとんどの構文要素が式」というのがあった。 ifwhileprimaryにあることでそれが具体的に表現されている。

それにしてもどうしてこんな「大きい」要素がprimaryにあって大丈夫なのだ ろう。それはRubyの構文が「終端記号Aで始まり終端記号Bで終わる」 という特徴があるからに他ならない。この点については次の項で改めて 考えてみる。

primary(11)

  | 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
                                                 # 特異メソッド定義

定義文。クラス文クラス文と呼んできたが、本当はクラス項と呼ぶべきで あったか。これらも全て「終端記号Aで始まりBで終わる」パターンなので、 いくら増えたところで一向に問題はない。

primary(12)

                | kBREAK
                | kNEXT
                | kREDO
                | kRETRY

各種ジャンプ。このへんはまあ、文法的にはどうでもいい。

衝突するリスト

先の項ではifprimaryなんかにあって大丈夫なのだろうか、という疑問を 提示した。厳密に証明するにはなかなか難しいのだが、感覚的にならわりと 簡単に説明できる。ここでは次のような小さい規則でシミュレーション してみよう。

%token A B o
%%
element   : A item_list B

item_list :
          | item_list item

item      : element
          | o

elementがこれから問題にしようとしている要素だ。例えばifについて考える ならifだ。elementは終端記号Aで始まりBで終わるリストである。 ifで言うならifで始まりendで終わる。内容物のoはメソッドや 変数参照やリテラルである。リストの要素には、そのoか、またはelementが ネストする。

この文法に基くパーサで次のような入力をパースしてみよう。

A  A  o  o  o  B  o  A  o  A  o  o  o  B  o  B  B

ここまでネストしまくっていると人間にはインデントなどの助けがないとちょっ とわかりにくい。だが次のように考えればわりと簡単である。いつか必ず ABoだけを狭んで現れるので、それを消してoに変える。それを繰り 返すだけでいい。結論は図4のようになる。

(ablist)
図4: Aで始まりBで終わるリストのリストをパース

しかしもし終端のBがなかったりすると……

%token A o
%%
element   : A item_list    /* Bを消してみた */

item_list :
          | item_list item

item      : element
          | o

これをyaccで処理すると2 shift/reduce conflictsと出た。つまりこの文法は 曖昧である。入力は、先程のものから単純にBを抜くと次のようになってしまう。

A  A  o  o  o  o  A  o  A  o  o  o  o

どうにもよくわからない。しかしshift/reduce conflictはシフトしろ、とい うルールがあったので、試しにそれに従ってシフト優先(即ち内側優先)でパー スしてみよう(図5)。

(alist)
図5: Aで始まるリストのリストをパース

とりあえずパースできた。しかしこれでは入力と意図が全く違うし、どうやっ ても途中でリストを切ることができなくなってしまった。

実はRubyの括弧省略メソッドはこれと似たような状態にある。わかりにくいが、 メソッド名と第一引数が合わせてAだ。なぜならその二つの間にだけカンマが ないので、新しいリストの始まりだと認識できるからである。

他に「現実的な」HTMLもこのパターンを含む。例えば</p></li>が省略され たときはこうなる。そういうわけでyaccは普通のHTMLにはまるで通用しない。

スキャナ

パーサ概形

スキャナに移る前にパーサの概形について説明しておこう。 図6を見てほしい。

(interf)
図6: パーサインターフェイス(コールグラフ)

パーサの公式インターフェイスは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のように図示できる。

(scanner)
図7: スキャナの全体像

入力バッファ

まず入力バッファから見ていこう。インターフェイスは nextc()pushback()peek()の三つだけだ。

しつこいようだがまずデータ構造を調べるのだった。 入力バッファの使う変数はこうだ。

▼入力バッファ

2279  static char *lex_pbeg;
2280  static char *lex_p;
2281  static char *lex_pend;

(parse.y)

バッファの先頭と現在位置、終端。どうやらこのバッファは単純な一列の 文字列バッファらしい(図8)。

(ibuffer)
図8: 入力バッファ

nextc()

ではこれを使っているところを見てみる。まずは一番オーソドックスと 思われるnextc()から。

nextc()

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)

最初のifで入力バッファの最後まで行ったかどうかテストしているようだ。そ してその内側のifは、else-1EOF)を返していることから入力全体の 終わりをテストしているのだと想像できる。逆に言えば、入力が終わったときには lex_inputが0になる。

ということは入力バッファには少しずつ文字列が入ってきているのだというこ とがわかる。その単位はと言うと、バッファを更新する関数の名前が lex_getline()なので行に間違いない。

まとめるとこういうことだ。

if (バッファ終端に到達した)
    if (まだ入力がある)
        次の行を読み込む
    else
        return EOF
ポインタを進める
CRを読み飛ばす
return c

行を補給する関数lex_getline()も見てみよう。 この関数で使う変数も一緒に並べておく。

lex_getline()

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)

最初の行以外はどうでもよい。 lex_getsが一行読み込み関数へのポインタ、lex_inputが本当の入力だろう。 lex_getsをセットしているところを検索してみると、こう出た。

lex_getsをセット

2430  NODE*
2431  rb_compile_string(f, s, line)
2432      const char *f;
2433      VALUE s;
2434      int line;
2435  {
2436      lex_gets = lex_get_str;
2437      lex_gets_ptr = 0;
2438      lex_input = s;

2454  NODE*
2455  rb_compile_file(f, file, start)
2456      const char *f;
2457      VALUE file;
2458      int start;
2459  {
2460      lex_gets = rb_io_gets;
2461      lex_input = file;

(parse.y)

rb_io_gets()はパーサ専用というわけではなく、rubyの汎用ライブラリだ。 IOオブジェクトから一行読み込む関数である。

一方のlex_get_str()は次のように定義されている。

lex_get_str()

2398  static int lex_gets_ptr;

2400  static VALUE
2401  lex_get_str(s)
2402      VALUE s;
2403  {
2404      char *beg, *end, *pend;
2405
2406      beg = RSTRING(s)->ptr;
2407      if (lex_gets_ptr) {
2408          if (RSTRING(s)->len == lex_gets_ptr) return Qnil;
2409          beg += lex_gets_ptr;
2410      }
2411      pend = RSTRING(s)->ptr + RSTRING(s)->len;
2412      end = beg;
2413      while (end < pend) {
2414          if (*end++ == '\n') break;
2415      }
2416      lex_gets_ptr = end - RSTRING(s)->ptr;
2417      return rb_str_new(beg, end - beg);
2418  }

(parse.y)

この関数はいいだろう。lex_gets_ptrが既に読み込んだところを記憶している。 それを次の\nまで移動し、同時にそこを切り取って返す。

ここでnextcに戻ろう。このように同じインターフェイスの関数を二つ用意 して、パーサの初期化のときに関数ポインタを切り替えてしまうことで他の部 分を共通化しているわけだ。コードの差分をデータに変換して吸収していると も言える。st_tableにも似たような手法があった。

pushback()

バッファの物理構造とnextc()がわかればあとは簡単だ。 一文字書き戻すpushback()。Cで言えばungetc()である。

pushback()

2501  static void
2502  pushback(c)
2503      int c;
2504  {
2505      if (c == -1) return;
2506      lex_p--;
2507  }

(parse.y)

peek()

そしてポインタを進めずに次の文字をチェックするpeek()(語意は 「覗き見る」)。

peek()

2509  #define peek(c) (lex_p != lex_pend && (c) == *lex_p)

(parse.y)

トークンバッファ

トークンバッファは次のレベルのバッファである。 トークンが一つ切り出せるまで文字列を保管しておく。 インターフェイスは以下の五つである。

newtok新しいトークンを開始する
tokaddバッファに文字を足す
tokfixバッファを終端する
tokバッファリングしている文字列の先頭へのポインタ
toklenバッファリングしている文字列長さ
toklastバッファリングしている文字列の最後のバイト

ではまずデータ構造から見ていく。

▼トークンバッファ

2271  static char *tokenbuf = NULL;
2272  static int   tokidx, toksiz = 0;

(parse.y)

tokenbufがバッファで、tokidxがトークンの末尾(intなのでインデッ クスらしい)、toksizがバッファ長だろう。こちらも入力バッファと同じく 単純な構造だ。絵にすると図9のようになる。

(tbuffer)
図9: トークンバッファ

引き続きインターフェイスに行って、新しいトークンを開始するnewtok()を 読もう。

newtok()

2516  static char*
2517  newtok()
2518  {
2519      tokidx = 0;
2520      if (!tokenbuf) {
2521          toksiz = 60;
2522          tokenbuf = ALLOC_N(char, 60);
2523      }
2524      if (toksiz > 4096) {
2525          toksiz = 60;
2526          REALLOC_N(tokenbuf, char, 60);
2527      }
2528      return tokenbuf;
2529  }

(parse.y)

バッファ全体の初期化インターフェイスというのはないので、バッファが初期 化されていない可能性がある。だから最初のifでそれをチェックし初期化す る。ALLOC_N()rubyが定義しているマクロで、calloc()とだいたい 同じだ。

割り当てる長さは初期値で60だが、大きくなりすぎていたら(> 4096)小さく 戻している。一つのトークンがそんなに長くなることはまずないので、このサ イズで現実的だ。

次はトークンバッファに文字を追加するtokadd()を見る。

tokadd()

2531  static void
2532  tokadd(c)
2533      char c;
2534  {
2535      tokenbuf[tokidx++] = c;
2536      if (tokidx >= toksiz) {
2537          toksiz *= 2;
2538          REALLOC_N(tokenbuf, char, toksiz);
2539      }
2540  }

(parse.y)

一行目で文字を追加。そのあとトークン長をチェックし、バッファ末尾を 越えそうだったらREALLOC_N()する。REALLOC_N()は引数指定方式が calloc()と同じrealloc()だ。

残りのインターフェイスはまとめてしまう。

tokfix() tok() toklen() toklast()

2511  #define tokfix() (tokenbuf[tokidx]='\0')
2512  #define tok() tokenbuf
2513  #define toklen() tokidx
2514  #define toklast() (tokidx>0?tokenbuf[tokidx-1]:0)

(parse.y)

問題ないだろう。

yylex()

yylex()はとても長い。現在1000行以上ある。そのほとんどが巨大な switch文一つで占められており、文字ごとに分岐するようになっている。 まず一部省略して全体構造を示す。

yylex概形

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) {
              /* ……文字列のスキャン…… */
3131          return token;
3132      }
3133      cmd_state = command_start;
3134      command_start = Qfalse;
3135    retry:
3136      switch (c = nextc()) {
3137        case '\0':                /* NUL */
3138        case '\004':              /* ^D */
3139        case '\032':              /* ^Z */
3140        case -1:                  /* end of script. */
3141          return 0;
3142
3143          /* white spaces */
3144        case ' ': case '\t': case '\f': case '\r':
3145        case '\13': /* '\v' */
3146          space_seen++;
3147          goto retry;
3148
3149        case '#':         /* it's a comment */
3150          while ((c = nextc()) != '\n') {
3151              if (c == -1)
3152                  return 0;
3153          }
3154          /* fall through */
3155        case '\n':
              /* ……省略…… */

            case xxxx:
                :
              break;
                :
            /* 文字ごとにたくさん分岐 */
                :
                :
4103        default:
4104          if (!is_identchar(c) || ISDIGIT(c)) {
4105              rb_compile_error("Invalid char `\\%03o' in expression", c);
4106              goto retry;
4107          }
4108
4109          newtok();
4110          break;
4111      }

          /* ……通常の識別子を扱う…… */
      }

(parse.y)

yylex()の返り値はゼロが「入力終わり」、非ゼロなら記号である。

c」などという非常に簡潔な変数が全体に渡って使われているので注意。 スペースを読んだときのspace_seen++は後で役に立つ。

あとは文字ごとに分岐してひたすら処理すればよいのだが、単調な処理が続く ので読むほうはとても退屈だ。そこでいくつかポイントを絞って見てみること にする。本書では全ての文字は解説しないが、同じパターンを敷衍していけば 簡単である。

'!'

まずは簡単なものから見てみよう。

yylex'!'

3205        case '!':
3206          lex_state = EXPR_BEG;
3207          if ((c = nextc()) == '=') {
3208              return tNEQ;
3209          }
3210          if (c == '~') {
3211              return tNMATCH;
3212          }
3213          pushback(c);
3214          return '!';

(parse.y)

日本語でコードの意味を書き出したので対照して読んでみてほしい。

case '!':
  EXPR_BEGに移行
  if (次の文字が'='なら) {
      トークンは「!=(tNEQ)」である
  }
  if (次の文字が'~'なら) {
      トークンは「!~(tNMATCH)」である
  }
  どちらでもないなら読んだ文字は戻しておく
  トークンは「'!'」である。

このcase節は短かいが、スキャナの重要な法則が示されている。それは 「最長一致の原則」である。"!="という二文字は「!=」「!=」の 二通りに解釈できるが、この場合は「!=」を選ばなければならない。 プログラム言語のスキャナでは最長一致が基本である。

またlex_stateはスキャナの状態を表す変数である。 次章『状態付きスキャナ』で嫌になるほど やるので、とりあえず無視しておいていい。いちおう意味だけ言っておくと、 EXPR_BEGは「明らかに式の先頭にいる」ことを示している。not!だろ うと!=だろうと!~だろうと、次は式の先頭だからだ。

'>'

次はyylval(記号の値)を使う例として'>'を見てみる。

yylex'>'

3296        case '>':
3297          switch (lex_state) {
3298            case EXPR_FNAME: case EXPR_DOT:
3299              lex_state = EXPR_ARG; break;
3300            default:
3301              lex_state = EXPR_BEG; break;
3302          }
3303          if ((c = nextc()) == '=') {
3304              return tGEQ;
3305          }
3306          if (c == '>') {
3307              if ((c = nextc()) == '=') {
3308                  yylval.id = tRSHFT;
3309                  lex_state = EXPR_BEG;
3310                  return tOP_ASGN;
3311              }
3312              pushback(c);
3313              return tRSHFT;
3314          }
3315          pushback(c);
3316          return '>';

(parse.y)

yylvalのところ以外は無視してよい。プログラムを読むときは一つのことに だけ集中するのが肝心だ。

ここでは>=に対応する記号tOP_ASGNに対してその値tRSHFTをセットして いる。使っている共用体メンバがidだから型はIDである。tOP_ASGNは自 己代入の記号で、+=とか-=とか*=といったものを全部まとめて表してい るから、それを後で区別するために何の自己代入かを値として渡すわけだ。

なぜ自己代入をまとめるかというと、そのほうが規則が短くなるからだ。 スキャナでまとめられるものはできるだけたくさんまとめてしまったほうが規 則がすっきりする。ではなぜ二項演算子は全部まとめないのかと言うと、優先 順位が違うからである。

':'

スキャンがパースから完全に独立していれば話は簡単なのだが、現実はそう 簡単ではない。Rubyの文法は特に複雑で空白が前にあるとなんか違うとか、 まわりの状況でトークンの切り方が変わったりする。以下に示す':'の コードは空白で挙動が変わる一例だ。

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)

今度もlex_state関係は無視してspace_seenまわりだけに注目してほしい。

space_seenはトークンの前に空白があると真になる変数だ。それが成立 すると、つまり'::'の前に空白があるとそれはtCOLON3になり、空白がな ければtCOLON2になるらしい。これは前節でprimaryのところで説明した通 りだ。

識別子

ここまでは記号ばかりなのでせいぜい一文字二文字だったが、今度は もう少し長いものも見てみることにする。識別子のスキャンパターンだ。

まずyylexの全体像はこうなっていた。

yylex(...)
{
    switch (c = nextc()) {
      case xxxx:
        ....
      case xxxx:
        ....
      default:
    }

    識別子のスキャンコード
}

次のコードは巨大switchの末尾のところからの引用である。 やや長いのでコメントを入れつつ示そう。

yylex−識別子

4081        case '@':                 /* インスタンス変数かクラス変数 */
4082          c = nextc();
4083          newtok();
4084          tokadd('@');
4085          if (c == '@') {         /* @@、つまりクラス変数 */
4086              tokadd('@');
4087              c = nextc();
4088          }
4089          if (ISDIGIT(c)) {       /* @1など */
4090              if (tokidx == 1) {
4091    rb_compile_error("`@%c' is not a valid instance variable name", c);
4092              }
4093              else {
4094    rb_compile_error("`@@%c' is not a valid class variable name", c);
4095              }
4096          }
4097          if (!is_identchar(c)) { /* @の次に変な文字がある */
4098              pushback(c);
4099              return '@';
4100          }
4101          break;
4102
4103        default:
4104          if (!is_identchar(c) || ISDIGIT(c)) {
4105              rb_compile_error("Invalid char `\\%03o' in expression", c);
4106              goto retry;
4107          }
4108
4109          newtok();
4110          break;
4111      }
4112
4113      while (is_identchar(c)) {   /* 識別子に使える文字のあいだ…… */
4114          tokadd(c);
4115          if (ismbchar(c)) {      /* マルチバイト文字の先頭バイトならば */
4116              int i, len = mbclen(c)-1;
4117
4118              for (i = 0; i < len; i++) {
4119                  c = nextc();
4120                  tokadd(c);
4121              }
4122          }
4123          c = nextc();
4124      }
4125      if ((c == '!' || c == '?') &&
              is_identchar(tok()[0]) &&
              !peek('=')) {      /* name!またはname?の末尾一文字 */
4126          tokadd(c);
4127      }
4128      else {
4129          pushback(c);
4130      }
4131      tokfix();

(parse.y)

最後に!/?を追加しているところの条件に注目してほしい。 この部分は次のような解釈をするためである。

obj.m=1       # obj.m  =   1       (obj.m= ... ではない)
obj.m!=1      # obj.m  !=  1       (obj.m! ... ではない)

つまり最長一致「ではない」。 最長一致はあくまで原則であって規則ではないので、 ときには破っても構わないのだ。

予約語

識別子をスキャンした後には実はもう100行くらいコードがあって、そこでは 実際の記号を割り出している。先程のコードではインスタンス変数やクラス変 数、ローカル変数などをまとめてスキャンしてしまっていたから、それを改め て分類するわけだ。

それはまあいいのだが、その中にちょっと変わった項目がある。それは予約語 を漉し取ることだ。予約語は文字種的にはローカル変数と変わらないので、ま とめてスキャンしておいて後から分類するほうが効率的なのである。

ではchar*文字列strがあったとして、予約語かどうか見分けるにはどうしたら いいだろうか。まずもちろんif文とstrcmp()で比較しまくる方法がある。しか しそれでは全くもって賢くない。柔軟性がない。スピードも線型増加する。 普通はリストとかハッシュにデータだけ分離して、コードを短く済ますだろう。

/* コードをデータに変換する */
struct entry {char *name; int symbol;};
struct entry *table[] = {
    {"if",     kIF},
    {"unless", kUNLESS},
    {"while",  kWHILE},
    /* ……略…… */
};

{
    ....
    return lookup_symbol(table, tok());
}

それでrubyはどうしているかと言うと、ハッシュテーブルを使っている。そ れも完全ハッシュだ。st_tableの話をしたときにも言った が、キーになりうる集合が前もってわかっていれば絶対に衝突しないハッシュ 関数を作れることがある。予約語というのは「キーになりうる集合が前もって わかってい」るわけだから、完全ハッシュ関数が作れそうだ。

しかし「作れる」のと実際に作るのとは別の話だ。 手動で作るなんてことはやっていられない。予約語は増えたり減ったり するのだから、そういう作業は自動化しなければいけない。

そこでgperfである。gperfはGNUプロダクトの一つで、値の集合から完全 ハッシュ関数を作ってくれる。gperf自体の詳しい使いかたはman gperfし てもらうとして、ここでは生成した結果の使いかただけ述べよう。

rubyでのgperfの入力ファイルはkeywordsで出力はlex.cである。 parse.yはこれを直接#includeしている。基本的にはCの ファイルを#includeす るのはよろしくないが、関数一つのために本質的でないファイル分割をやるの はさらによろしくない。特にrubyではextern関数はいつのまにか拡張ライブラリ に使われてしまう恐れがあるので、互換性を保ちたくない関数はできるだけ staticにすべきなのだ。

そしてそのlex.cにはrb_reserved_word()という関数が定義されている。 予約語のchar*をキーにしてこれを呼ぶと索ける。返り値は、見付から なければNULL、見付かれば(つまり引数が予約語なら)struct kwtable*が返る。 struct kwtableの定義は以下のとおり。

kwtable

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

(keywords)

nameが予約語の字面、id[0]がその記号、id[1]が修飾版の記号 (kIF_MODなど)。 lex_stateは「その予約語を読んだ後に移行すべきlex_state」である。 lex_stateについては次章で説明する。

実際に索いているのはこのあたりだ。

yylex()−識別子−rb_reserved_word()を呼ぶ

4173                  struct kwtable *kw;
4174
4175                  /* See if it is a reserved word.  */
4176                  kw = rb_reserved_word(tok(), toklen());
4177                  if (kw) {

(parse.y)

文字列類

yylex()のダブルクォート(")のところを見ると、こうなっている。

yylex'"'

3318        case '"':
3319          lex_strterm = NEW_STRTERM(str_dquote, '"', 0);
3320          return tSTRING_BEG;

(parse.y)

なんと一文字目だけをスキャンして終了してしまう。そこで今度は 規則を見てみると、次の部分にtSTRING_BEGが見付かった。

▼文字列関連の規則

string1         : tSTRING_BEG string_contents tSTRING_END

string_contents :
                | string_contents string_content

string_content  : tSTRING_CONTENT
                | tSTRING_DVAR string_dvar
                | tSTRING_DBEG term_push compstmt '}'

string_dvar     : tGVAR
                | tIVAR
                | tCVAR
                | backref

term_push       :

この規則は文字列中の式埋め込みに対応するために導入された部分である。 tSTRING_CONTENTがリテラル部分、tSTRING_DBEG"#{"である。 tSTRING_DVARは「後に変数が続く#」を表す。例えば

".....#$gvar...."

のような構文である。説明していなかったが埋め込む式が変数一個の 場合には{}は省略できるのだ。ただしあまり推奨はされない。 ちなみにDVARDBEGDdynamicの略だと思われる。

またbackref$1 $2……とか$& $'といった正規表現関連の 特殊変数を表す。

term_pushは「アクションのための規則」である。

さてここでyylex()に戻る。 単純にパーサに戻っても、コンテキストが文字列の「中」になる わけだから、次のyylex()でいきなり変数だのifだのスキャンされたら困る。 そこで重要な役割を果たすのが……

      case '"':
        lex_strterm = NEW_STRTERM(str_dquote, '"', 0);
        return tSTRING_BEG;

……lex_strtermだ、ということになる。yylex()の先頭に戻ってみよう。

yylex()先頭

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) {
              /* ……文字列のスキャン…… */
3131          return token;
3132      }
3133      cmd_state = command_start;
3134      command_start = Qfalse;
3135    retry:
3136      switch (c = nextc()) {

(parse.y)

lex_strtermが存在するときは問答無用で文字列モードに突入するようになっ ている。ということは逆に言うとlex_strtermがあると文字列をスキャン中と いうことであり、文字列中の埋め込み式をパースするときにはlex_strtermを 0にしておかなければならない。そして埋め込み式が終わったらまた戻さな ければならない。それをやっているのが次の部分だ。

string_content

1916  string_content  : ....
1917                  | tSTRING_DBEG term_push
1918                      {
1919                          $<num>1 = lex_strnest;
1920                          $<node>$ = lex_strterm;
1921                          lex_strterm = 0;
1922                          lex_state = EXPR_BEG;
1923                      }
1924                    compstmt '}'
1925                      {
1926                          lex_strnest = $<num>1;
1927                          quoted_term = $2;
1928                          lex_strterm = $<node>3;
1929                          if (($$ = $4) && nd_type($$) == NODE_NEWLINE) {
1930                              $$ = $$->nd_next;
1931                              rb_gc_force_recycle((VALUE)$4);
1932                          }
1933                          $$ = NEW_EVSTR($$);
1934                      }

(parse.y)

埋め込みアクションでlex_strtermtSTRING_DBEGの値として保存し (事実上のスタックプッシュ)、通常のアクションで復帰している(ポップ)。 なかなかうまい方法だ。

しかしなんでこのような七面倒くさいことをするのだろう。普通にスキャンし ておいて、「#{」を見付けた時点でyyparse()を再帰呼び出しすればいい のではないだろうか。そこに実は問題がある。yyparse()は再帰呼び出しで きないのだ。これはよく知られたyaccの制限である。値の受け渡しに利用す るyylvalがグローバル変数なので、うかつに再帰すると値が壊れてしまう。 bison(GNUのyacc)だと%pure_parserというディレクティブを使うこと で再帰可能にできるのだが、現在のrubybisonを仮定しないことになっ ている。現実にBSD由来のOSやWindowsなどではbyacc(Berkeley yacc) を使うことが多いのでbisonが前提になるとちょっと面倒だ。

lex_strterm

見てきたようにlex_strtermは真偽値として見た場合はスキャナが文字列モードか そうでないかを表すわけだが、実は内容にも意味がある。まず型を見てみよう。

lex_strterm

  72  static NODE *lex_strterm;

(parse.y)

まずこの定義から型はNODE*だとわかる。これは構文木に使うノードの型で、 第12章『構文木の構築』で詳しく説明する。とりあえずは、三要素を持つ構造体 である、VALUEなのでfree()する必要がない、の二点を押さえておけばよ い。

NEW_STRTERM()

2865  #define NEW_STRTERM(func, term, paren) \
2866          rb_node_newnode(NODE_STRTERM, (func), (term), (paren))

(parse.y)

これはlex_strtermに格納するノードを作るマクロだ。まずtermは文字列の終 端文字を示す。例えば"文字列ならば"である。'文字列ならば'である。

paren%文字列のときに対応する括弧を格納するのに使う。例えば

%Q(..........)

ならparen'('が入る。そしてtermには閉じ括弧')'が入る。 %文字列以外のときはparenは0だ。

最後にfuncだが、文字列の種類を示す。 使える種類は以下のように決められている。

func

2775  #define STR_FUNC_ESCAPE 0x01  /* \nなどバックスラッシュ記法が有効 */
2776  #define STR_FUNC_EXPAND 0x02  /* 埋め込み式が有効 */
2777  #define STR_FUNC_REGEXP 0x04  /* 正規表現である */
2778  #define STR_FUNC_QWORDS 0x08  /* %w(....)または%W(....) */
2779  #define STR_FUNC_INDENT 0x20  /* <<-EOS(終了記号がインデント可) */
2780
2781  enum string_type {
2782      str_squote = (0),
2783      str_dquote = (STR_FUNC_EXPAND),
2784      str_xquote = (STR_FUNC_ESCAPE|STR_FUNC_EXPAND),
2785      str_regexp = (STR_FUNC_REGEXP|STR_FUNC_ESCAPE|STR_FUNC_EXPAND),
2786      str_sword  = (STR_FUNC_QWORDS),
2787      str_dword  = (STR_FUNC_QWORDS|STR_FUNC_EXPAND),
2788  };

(parse.y)

つまりenum string_typeのそれぞれの意味は次のようだとわかる。

str_squote'文字列/%q
str_dquote"文字列/%Q
str_xquoteコマンド文字列(本書では説明していない)
str_regexp正規表現
str_sword%w
str_dword%W

文字列スキャン関数

あとは文字列モードのときのyylex()、つまり冒頭のifを読めばいい。

yylex−文字列

3114      if (lex_strterm) {
3115          int token;
3116          if (nd_type(lex_strterm) == NODE_HEREDOC) {
3117              token = here_document(lex_strterm);
3118              if (token == tSTRING_END) {
3119                  lex_strterm = 0;
3120                  lex_state = EXPR_END;
3121              }
3122          }
3123          else {
3124              token = parse_string(lex_strterm);
3125              if (token == tSTRING_END || token == tREGEXP_END) {
3126                  rb_gc_force_recycle((VALUE)lex_strterm);
3127                  lex_strterm = 0;
3128                  lex_state = EXPR_END;
3129              }
3130          }
3131          return token;
3132      }

(parse.y)

大きくヒアドキュメントとそれ以外に分かれている。のだが、今回は parse_string()は読まない。前述のように大量の条件付けがあるため、凄まじ いスパゲッティコードになっている。例え説明してみたとしても「コードその ままじゃん!」という文句が出ること必至だ。しかも苦労するわりに全然面白 くない。

しかし全く説明しないわけにもいかないので、スキャンする対象ごとに関数を 分離したものを添付CD-ROMに入れて おく\footnote{parse_string()の解析:添付CD-ROMdoc/parse_string.html}。 興味のある読者はそちらを眺めてみてほしい。

ヒアドキュメント

普通の文字列に比べるとヒアドキュメントはなかなか面白い。やはり他の 要素と違って単位が「行」であるせいだろう。しかも開始記号がプログラムの 途中に置けるところが恐ろしい。まずヒアドキュメントの開始記号をスキャン するyylex()のコードから示そう。

yylex'<'

3260        case '<':
3261          c = nextc();
3262          if (c == '<' &&
3263              lex_state != EXPR_END &&
3264              lex_state != EXPR_DOT &&
3265              lex_state != EXPR_ENDARG &&
3266              lex_state != EXPR_CLASS &&
3267              (!IS_ARG() || space_seen)) {
3268              int token = heredoc_identifier();
3269              if (token) return token;

(parse.y)

例によってlex_stateの群れは無視する。すると、ここでは「<<」だけを 読んでおり、残りはheredoc_identifier()でスキャンするらしいとわかる。 そこでheredoc_identifier()だ。

heredoc_identifier()

2926  static int
2927  heredoc_identifier()
2928  {
          /* ……省略……開始記号を読む */
2979      tokfix();
2980      len = lex_p - lex_pbeg;   /*(A)*/
2981      lex_p = lex_pend;         /*(B)*/
2982      lex_strterm = rb_node_newnode(NODE_HEREDOC,
2983                          rb_str_new(tok(), toklen()),  /* nd_lit */
2984                          len,                          /* nd_nth */
2985          /*(C)*/       lex_lastline);                /* nd_orig */
2986
2987      return term == '`' ? tXSTRING_BEG : tSTRING_BEG;
2988  }

(parse.y)

開始記号(<<EOS)を読むところはどうでもいいのでバッサリ省略した。 ここまでで入力バッファは図10のようになっているはずだ。 入力バッファは行単位だったことを思い出そう。

(lexparams)
図10: "printf(<<EOS, n)"のスキャン

heredoc_identifier()でやっていることは以下の通り。 (A)lenは現在行のうち読み込んだバイト数だ。 (B)そしていきなりlex_pを行の末尾まで飛ばす。 ということは、読み込み中の行のうち開始記号の後が読み捨てられて しまっている。この残りの部分はいつパースするのだろう。 その謎の答えは(C)でlex_lastline(読み込み中の行)と len(既に読んだ長さ)を保存しているところにヒントがある。

ではheredoc_identifier()前後の動的コールグラフを以下に簡単に示す。

yyparse
    yylex(case '<')
        heredoc_identifier(lex_strterm = ....)
    yylex(冒頭のif)
        here_document

そしてこのhere_document()がヒアドキュメント本体のスキャンを行っている。 以下に、異常系を省略しコメントを加えたhere_document()を示す。 lex_strtermheredoc_identifier()でセットしたままであることに 注意してほしい。

here_document()(簡約版)

here_document(NODE *here)
{
    VALUE line;                      /* スキャン中の行 */
    VALUE str = rb_str_new("", 0);   /* 結果をためる文字列 */

    /* ……異常系の処理、省略…… */

    if (式の埋め込み式が無効) {
        do {
            line = lex_lastline;     /*(A)*/
            rb_str_cat(str, RSTRING(line)->ptr, RSTRING(line)->len);
            lex_p = lex_pend;        /*(B)*/
            if (nextc() == -1) {     /*(C)*/
                goto error;
            }
        } while (読み込み中の行が終了記号と等しくない);
    }
    else {
        /* 式の埋め込み式ができる場合……略 */
    }
    heredoc_restore(lex_strterm);
    lex_strterm = NEW_STRTERM(-1, 0, 0);
    yylval.node = NEW_STR(str);
    return tSTRING_CONTENT;
}

rb_str_cat()はRubyの文字列の末尾にchar*を連結する関数だ。 つまり(A)では現在読み込み中の行lex_lastlinestrに連結している。 連結したらもう今の行は用済みだ。(B)でlex_pをいきなり行末に 飛ばす。そして(C)が問題で、ここでは終了チェックをしているように 見せかけつつ実は次の「行」を読み込んでいるのだ。思い出してほしいの だが、nextc()は行が読み終わっていると勝手に次の行を読み込むという 仕様だった。だから(B)で強制的に行を終わらせているので (C)でlex_pは次の行に移ることになる。

そして最後にdowhileループを抜けてheredoc_restore()だ。

heredoc_restore()

2990  static void
2991  heredoc_restore(here)
2992      NODE *here;
2993  {
2994      VALUE line = here->nd_orig;
2995      lex_lastline = line;
2996      lex_pbeg = RSTRING(line)->ptr;
2997      lex_pend = lex_pbeg + RSTRING(line)->len;
2998      lex_p = lex_pbeg + here->nd_nth;
2999      heredoc_end = ruby_sourceline;
3000      ruby_sourceline = nd_line(here);
3001      rb_gc_force_recycle(here->nd_lit);
3002      rb_gc_force_recycle((VALUE)here);
3003  }

(parse.y)

here->nd_origには開始記号のあった行が入っている。 here->nd_nthには開始記号のあった行のうち既に読んだ長さが入っている。 つまり開始記号の直後から何事もなかったかのようにスキャンしつづけられる というわけだ(図11)。

(heredoc)
図11: ヒアドキュメントのスキャン分担図


御意見・御感想・誤殖の指摘などは 青木峰郎 <aamine@loveruby.net> までお願いします。

『Rubyソースコード完全解説』 はインプレスダイレクトで御予約・御購入いただけます (書籍紹介ページへ飛びます)。

Copyright (c) 2002-2004 Minero Aoki, All rights reserved.