図1: パーサの構築手順
パーサのメインソースはparse.yである。*.yだからyaccの入力で、
ここからparse.cが生成される。
また他にはlex.cという思わせぶりな名前のファイルがあるのだが、スキャナ
が入っているわけではない。これはgperfというツールが生成したファイルで、
予約語のハッシュテーブルが定義されている。その入力ファイルはkeywordsだ。
lex.cはparse.cに#includeして使われる。
中身について説明するのはその場にならないと難しいので後にまわそう。
まとめるとパーサの構築手順は図1のようになる。
Windowsで生きている人のために説明するとmvはファイルを移動する
コマンドである。ccはもちろんCコンパイラでcppは
Cのプリプロセッサだ。
図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 | ||
if | kIF | ||
def | kDEF | ||
rescue | kRESCUE | ||
varname | tIDENTIFIER | ||
ConstName | tCONST | ||
| 1 | tINTEGER |
このルールの例外はklBEGINとklENDのみだ。それぞれ予約語の
「BEGIN」「END」に対応する記号で、lはlargeのlだと思われる。
予約語には小文字のbegin endもあるのでこのような区別が付いている。
規則ファイルには文法とアクションが書いてあるのだった。しかしいまは規則
にだけ注目したいので、アクションは必要ない。規則だけ取り出すには、
rubyのsample/に入っている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以上ある。 ここまで大きいとさすがにいきなり全体を並べて把握するなんてことは 不可能だ。こういうものは重要なところだけ見ていくに限る。
ではどの記号が重要だとわかるのだろうか。それには記号の名前に注目すれば
よい。例えばprogram、expr、stmt、primary、argなどの名前は非
常に重要である。なぜならそれはプログラム言語の文法要素の一般的な区分を
表すからだ。一般にプログラムの構文で注目すべき要素を以下に一覧する。
| 構文要素 | 予測される記号名 | ||
| プログラム全体 | 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のクラス定義のようなもの。式は手続き呼び出しや数
式など。文字列リテラルや数値はたいてい項である。いずれかの要素がないこ
とはよくあるが、この上下関係、つまりprogram→stmt→expr→
primary、が通用しない言語はまずない。
ただし小さいレベルの構造は上の構造に入ることもできる。例えば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
それぞれの最後の規則に注目すると、非常にわかりやすく
program→stmt→expr→arg→primary
という上下関係が出ている。
またprimaryのこの規則も注目したい。
primary : literal
：
：
| tLPAREN_ARG expr ')' /* これ */
tLPAREN_ARGは、終端記号を示すt、leftのL、parentheses（丸括弧）の
PARENから成る。つまり開き括弧のことだ。なぜ'('としないかは
次章『状態付きスキャナ』で説明しよう。なんにしても、この規則がexprを
primaryに縮退させるための規則である。つまりここのところで
図2のように規則が循環している。矢印は実際にパースするとき
に還元される順だ。
図2: exprの縮退
そしてその次の規則はさらにすごい。
primary : literal
：
：
| tLPAREN compstmt ')' /* これ */
なんとcompstmt、つまりプログラム全体（program）と等しいものを
primaryに縮退させてしまおうというのだ。また図にすると図3の
ようになる。
図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は文法全体、即ちプログラム全体を表している。その
programはcompstmtsと同じであり、compstmtsはstmtsとほぼ同じである。
そのstmtsはterms区切りの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
おかしい。通ってしまった。実を言うと、連続した改行はスキャナのレベルで 捨てられてしまってパーサには最初の一つしか渡らないようになっているのだ。
ところで、programとcompstmtは同じものだと言ったが、それならこの規則は
何のために存在するのだろう。実はこれはアクションを実行するためだけにあ
るのだ。例えば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_valueやprimary_valueはアクションのために用意されている規則である。
例えばexpr_valueなら値（value）を持つexprであることを示す。値
を持たないexprとはreturnやbreak、あるいはそういうものを含むif文
などのことだ。「値を持つ」の詳しい定義は
第12章『構文木の構築』で見る。
primary_valueも同じく「値を持つ」primaryである。
klBEGINとklENDは説明した通りBEGINとENDのこと。
▼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
この二つは多重代入である。mrhsはmlhsと同じ作りで、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_callはexprにある。だから最低でも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_の
付く記号で表現した。opeqはoperator + equal、T_preは'!'や'~'の
ような前置型演算子、T_infixは'*'や'%'と言った二項演算子を表す。
この構造で衝突しないためには以下のようなことが重要になる （ただしこれが全てではない）。
T_infixが'='を含まないこと
argはlhsと部分的に重なるので'='があると規則1と3が区別できない。
T_opeqとT_infixが共通項を持たないこと
argはprimaryを含むから共通項を持つと規則2と3が区別できない。
T_infixの中に'?'がないこともし含むと規則3と5がshift/reduce conflictを起こす。
T_preが'?'や':'を含まないもし含むと規則4と5がかなり複雑に衝突する。
結論としては全ての条件が成立しているので、この文法は衝突しない。 当然と言えば当然だ。
primary
primaryは規則が多いので最初から分割して示す。
▼primary（1）
primary : literal
| strings
| xstring
| regexp
| words
| qwords
リテラル類。literalはSymbolリテラル（:sym）と数値。
▼primary（2）
| var_ref
| backref
| tFID
変数類。var_refはローカル変数やインスタンス変数など。
backrefは$1 $2 $3……。
tFIDは!や?が付いた識別子、例えばinclude? reject!など。
tFIDはローカル変数ではありえないので、
それ単独で出てきたとしてもパーサレベルでメソッド呼び出しになる。
▼primary（3）
| kBEGIN
bodystmt
kEND
bodystmtがrescueやensureも含んでいる。
つまりこれは例外制御の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 ')'
メソッド呼び出しと形式が似ている構文。
順番に、return、yield、defined?。
yieldには引数が付いているのにreturnに引数がないのはどうしてだろう。
根本的な原因は、yieldはそれ自体に返り値があるのに対しreturnには返り値が
ないことである。ただし、ここで引数がないからといって値を渡せないわけでは、
もちろんない。exprに次のような規則があった。
kRETURN call_args
call_argsは剥き出しの引数リストなのでreturn 1やreturn 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は{〜}かdo〜endで、それがついて
いるメソッドとはつまりイテレータだ。braceなのになぜdo〜endが入る
のか……ということにはマリアナ海溝よりも深淵な理由があるのだが、これも
やはり次章『状態付きスキャナ』を読んでもらうしかない。
▼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という
「小さい」ものの中にあることだ。primaryはargでもあるのでこんなこと
もできるということになる。
p(if true then 'ok' end) # "ok"と表示される
Rubyの特徴の一つに「ほとんどの構文要素が式」というのがあった。
ifやwhileがprimaryにあることでそれが具体的に表現されている。
それにしてもどうしてこんな「大きい」要素が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
各種ジャンプ。このへんはまあ、文法的にはどうでもいい。
先の項ではifがprimaryなんかにあって大丈夫なのだろうか、という疑問を
提示した。厳密に証明するにはなかなか難しいのだが、感覚的にならわりと
簡単に説明できる。ここでは次のような小さい規則でシミュレーション
してみよう。
%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
ここまでネストしまくっていると人間にはインデントなどの助けがないとちょっ
とわかりにくい。だが次のように考えればわりと簡単である。いつか必ず
AとBがoだけを狭んで現れるので、それを消してoに変える。それを繰り
返すだけでいい。結論は図4のようになる。
図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）。
図5: Aで始まるリストのリストをパース
とりあえずパースできた。しかしこれでは入力と意図が全く違うし、どうやっ ても途中でリストを切ることができなくなってしまった。
実はRubyの括弧省略メソッドはこれと似たような状態にある。わかりにくいが、
メソッド名と第一引数が合わせてAだ。なぜならその二つの間にだけカンマが
ないので、新しいリストの始まりだと認識できるからである。
他に「現実的な」HTMLもこのパターンを含む。例えば</p>や</li>が省略され
たときはこうなる。そういうわけでyaccは普通のHTMLにはまるで通用しない。
スキャナに移る前にパーサの概形について説明しておこう。 図6を見てほしい。
図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のように図示できる。
図7: スキャナの全体像
まず入力バッファから見ていこう。インターフェイスは
nextc()、pushback()、peek()の三つだけだ。
しつこいようだがまずデータ構造を調べるのだった。 入力バッファの使う変数はこうだ。
▼入力バッファ
2279 static char *lex_pbeg; 2280 static char *lex_p; 2281 static char *lex_pend; (parse.y)
バッファの先頭と現在位置、終端。どうやらこのバッファは単純な一列の 文字列バッファらしい（図8）。
図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で-1（EOF）を返していることから入力全体の
終わりをテストしているのだと想像できる。逆に言えば、入力が終わったときには
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のようになる。
図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...."
のような構文である。説明していなかったが埋め込む式が変数一個の
場合には{と}は省略できるのだ。ただしあまり推奨はされない。
ちなみにDVAR、DBEGのDはdynamicの略だと思われる。
また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_strtermをtSTRING_DBEGの値として保存し
（事実上のスタックプッシュ）、通常のアクションで復帰している（ポップ）。
なかなかうまい方法だ。
しかしなんでこのような七面倒くさいことをするのだろう。普通にスキャンし
ておいて、「#{」を見付けた時点でyyparse()を再帰呼び出しすればいい
のではないだろうか。そこに実は問題がある。yyparse()は再帰呼び出しで
きないのだ。これはよく知られたyaccの制限である。値の受け渡しに利用す
るyylvalがグローバル変数なので、うかつに再帰すると値が壊れてしまう。
bison（GNUのyacc）だと%pure_parserというディレクティブを使うこと
で再帰可能にできるのだが、現在のrubyはbisonを仮定しないことになっ
ている。現実に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のようになっているはずだ。
入力バッファは行単位だったことを思い出そう。
図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_strtermがheredoc_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_lastlineをstrに連結している。
連結したらもう今の行は用済みだ。（B）でlex_pをいきなり行末に
飛ばす。そして（C）が問題で、ここでは終了チェックをしているように
見せかけつつ実は次の「行」を読み込んでいるのだ。思い出してほしいの
だが、nextc()は行が読み終わっていると勝手に次の行を読み込むという
仕様だった。だから（B）で強制的に行を終わらせているので
（C）でlex_pは次の行に移ることになる。
そして最後にdo〜whileループを抜けて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）。
図11: ヒアドキュメントのスキャン分担図
御意見・御感想・誤殖の指摘などは 青木峰郎 <aamine@loveruby.net> までお願いします。
『Rubyソースコード完全解説』 はインプレスダイレクトで御予約・御購入いただけます (書籍紹介ページへ飛びます)。
Copyright (c) 2002-2004 Minero Aoki, All rights reserved.