仰々しいタイトルだけど、reddish-shellのパーサー部分のメモ。 いまは覚えているけど、数カ月後の自分が覚えている自信がないのでメモっておこうと思った次第…。
ここで解説する内容は、現状の実装に即したもので数カ月後には変わっているかもしれない。 また、私の勉強不足で間違っている/最適ではない部分があるかもしれないのでご容赦。。
この記事では、mrubyやGNU bisonについての詳しい説明はしないので私の過去記事を読むかググってください。
純粋パーサー(再入可能パーサー/リエントラントパーサー)
bisonの定義部に %define api.pure (古いbisonでは %pure-parser ) を定義すると純粋パーサーとして定義できる。
これを定義するとパーサーとのやり取りをするyylval変数がグローバル変数から、局所変数になる。
mrubyから呼び出す関係で、グローバル変数は使いづらいので純粋パーサーとして定義している*1。
また、mrubyでパーサーのアクションを処理したいのでmrb_stateをどうしてもyylex(yylval)に渡したい。 なので以下の定義をすることで、yyparserやyylex、yyerrorに引数を追加することができる。
%parse-param {parser_state *p}
%lex-param {parser_state *p}
最終的な各関数とparser_stateの定義は以下のとおりになる。
{%
typedef struct parser_state {
mrb_state* state;
mrb_value parser_class;
mrb_value result;
mrb_value action_class;
} parser_state;
static int yylex(void* , parser_state*);
static void yyerror(parser_state*, const char*);
static int yyparse(parser_state*);
%}
%define api.pure
%parse-param {parser_state* p}
%lex-param {parser_state* p}
-- snip --
処理の流れ
biosonでは、yyparseという関数がエンドポイントとして定義されており、パースを開始するときはこの関数を呼び出す。 yyparseはYYEOFまたエラーになるまでyylexを呼び出す。 前回のようにflexを使った場合は自動で生成されるが、今回は自作する必要がある。 yylexは入力データを適切に字句解析し、トークンの種類(int型)とトークンの内容をyylvalとして返す。 トークンを受け取ったbisonは、適切なアクションを実行する。
今回は、yyparseの呼び出し、yylexの処理、bisonのアクションをmrubyで定義する。
トークンと文法規則
シェルの構文はかなり多いので、今回はシンプルなコマンドを考える。
echo "hoge"hige'fuga' というコマンドのパースを考える。
以下は入力とトークン、Rubyオブジェクトの対比示した図になる(△は半角スペースを示す)。
まず、yylexでは入力された文字列をWORDというトークンに分割する。
また分割したトークンは、RubyのWordクラスのオブジェクトとしてyylvalに格納する。
Wordクラスには、文字列の種類を識別する情報(WordTypeクラス)を格納している。
echoやhigeはWordType::NORMAL、"hoge"はWordType::DQUOTE、'fuga'はWordType::QUOTEとしている。
文字種をわけることで、パーサー後にコマンドを実行するときにWordをどのように処理するかを識別する。
例えば、WordType::QUOTEはそのままの文字列としてあつかい、WodType::NORMALやWordType::DQUOTEは変数の置換などを行う。
最初、空白はSPというトークンにしていたのだけど、例えば echo foo > bar みたいな場合に正しくbisonのアクションが定義できなくなってしまう*2のでWORDにしている
WORDを受け取った場合のアクションはReddshParser::Actionモジュールのmake_word_listモジュールメソッドを呼び出す。 このメソッドは受け取ったWordを格納したWordlistのオブジェクトを返す。 WORDの次にWORDが来た場合、ReddishParser::Actionのadd_to_word_listモジュールメソッドを呼び出す。 このメソッドは、先行するWordlistにWORDを追加するメソッドになっている。 最終的にWordlistはCommandクラスのオブジェクトとして返す*3。
bisonの定義部は以下のようになる
#define ACTION(p, n, c, ...) mrb_funcall(p->state, p->action_class, n, c, __VA_ARGS__) -- snip -- simple_command : wordlist { $$ = ACTION(p, "make_command", 1, $1); wordlist : WORD { $$ = ACTION(p, "make_word_list", 1, $1); } | wordlist WORD { $$ = ACTION(p, "add_to_word_list", 2, $1, $2); }
最終的な定義
ReddishParser.parseモジュールメソッド 文字列を引数にとり、ReddishParser::Parserクラスのオブジェクトを生成し、アクションで扱いやすくするためにReddishParser::Actionのクラスオブジェクトを格納しておく。 yyparseの処理が完了するとpstate.resultにパースした結果が格納される。
mrb_value mrb_reddish_parser_parse(mrb_state *mrb, mrb_value self) {
mrb_value inputline;
cmdline_parse_state pstate;
struct RClass* rp = mrb_module_get(mrb, "ReddishParser");
mrb_get_args(mrb, "S", &inputline);
pstate.state = mrb;
pstate.parser_class = mrb_obj_new(mrb, mrb_class_get_under(mrb, rp, "Parser"), 1, &inputline);
pstate.result = mrb_nil_value();
pstate.action_class = mrb_obj_value(mrb_class_get_under(mrb, rp, "Action"));
yyparse(&pstate);
if (mrb_nil_p(pstate.result)) {
return mrb_nil_value();
}
return pstate.result;
}
yylex関数 Reddish::Parser#get_tokenメソッドを呼び出し、トークンを取得する。 戻り値のwordメソッドにWordオブジェクトが入っているので、これをlvalに格納してアクションに渡す。 typeメソッドにはトークンの種類が格納されているのでこれを取得して、yylex関数の戻り値とする。
int yylex(void* lval, cmdline_parse_state* p) {
mrb_value token;
int type;
token = mrb_funcall(p->state, p->parser_class, "get_token", 0);
if (mrb_nil_p(token)) {
return YYEOF;
}
*((YYSTYPE*)lval) = mrb_funcall(p->state, token, "word", 0);
type = mrb_fixnum(mrb_funcall(p->state, token, "type", 0));
return type;
}
ReddishParser::Actionの各メソッドに関しては省略。
最後に
船長の動画を見つつ片手間に書いていたら、なんだかまとまりのない文章になってしまった。。 とはいえ、肝心な部分はかけていると思う。
当初はパーサー部分はすべてC言語で書いて、yyparseの処理が完了したらRubyのオブジェクトを返すようにしていたが、C言語で文字列処理やリストを作るのが非常にめんどくさかったため*4、mrubyでラッパーするように書き換えたのであった。 ただ、mrubyに書き換えたことでparser.yが小さくなり、かつ、各アクションや処理をRubyのコードになりテスタブルになるというメリットがでた。 ・・・というもっともらしい理由を今考えた。
またいろいろ実装したらブログを書こうと思う。
