ダメージ計算/calc_damage.js/教科書版/構文解析 - mblen @ ウィキ

Summary. 字句解析で作成した Lexer を使って、入力されたテキストデータを実際に解析してみます。

目標

今回の目標は

JC; 5C(1,2,3,4); 3C; 236C;

のような入力テキストを解析して適切な計算処理を導くことです。まあ、実際に計算するところはまた別の話になるので、とにかく入力されたデータを解析してコマンドや引数を抽出してみようって感じです。

話を簡単にするために、5C(1-4) のような範囲指定や特殊コマンドはひとまず扱わないことにします。

最終的な成果物は parse_all() という関数です。しかし、こういう処理は一般に「構文解析」と呼ばれるもので（そんな大袈裟なものじゃないですが）、大抵は１関数で記述できるほど簡単にはなりません。それを念頭に、今回も細かく下請け関数を用意する形で作っていきます。

Step 1. まず入り口だけ作る

さて、上の入力データがどのような「構造」を持っているか考えてみましょう。すると、少し大雑把ですが

コマンド１ ; コマンド２ ; コマンド３ ; ……

という形式をしていることがわかります（見やすいように空白を挟みました）。従って、大まかに言うと

コマンドを１つ読み込んで、それを実行する
セミコロンを１つ読み飛ばす
もしまだデータが余っていたら最初に戻る

というプログラムを書けばうまくいくことになります。

素案

上の１～３を前回作った Lexer も交えてJavaScriptのコードっぽく書けば

parse_all = function(text){
  var lex = new Lexer(text);
 
  while( lex.enabled ){
    parse_command(lex);
    lex.skip(";");
  }
}

という風になります。もちろん、途中に出てくる parse_command(lex) という部分はまだ用意されていません。これを実際に作るのが次のステップになります。

こんな感じに、まだ決まってない部分を未完成の関数として先送りしてしまって、全体の流れだけを先に記述してしまうわけです。長いコードを書くときの基本です。

実際のコード

次のステップにいく前に、少し小細工を施しておきましょう：

parse_all = function(input){
  var lex = new Lexer(input);
 
  do{
    parse_command(lex);
  } while( lex.softskip(";") );
 
  if(lex.text.match(/\S/)){
    window.alert("Error: コマンド解析に失敗しました");
  }
}

while ループを do ～ while 構文に取り替えてみました。こうしておかないと、一番最後のコマンドのあとにセミコロンがないときエラー扱いになります（それもありだと思いますが一応）。skip() ではなく softskip() を使っているのは、lex にとどめを刺さないためです。

また、ループを抜けた後にまだ入力が余っている場合は「どこかで失敗して処理が不完全になった」ということなので、申し訳程度にエラーメッセージを出しておきます。

Step 2. parse_command() を作る

ここでもう一度おさらいです。「コマンド」はその定義から

コマンド名 ( 引数の羅列 )　または　コマンド名だけ

という形をしています。いずれにせよ、まず最初にコマンド名があって、段数指定ver.ではその後に括弧が続く（指定無しならセミコロンが続く）はずです。もっと詳しく言うと、段数指定がある場合は

コマンド名を読み込む
"(" を１つ読み飛ばす
引数を順に読み込んで、然るべき処理をする
")" を１つ読み飛ばす

という処理の流れになります。３の処理は少し面倒なのでまた関数として括り出すことになるでしょう。

素案

……となれば、早速その通りのコードを書いてみるまでです。

parse_command = function(lex){
  var token = lex.skip("WORD");
 
  if( lex.softskip("(") ){
    parse_arguments(lex, token.value);
    lex.skip(")");
  }
  else{
    window.alert(token.value + "を全段実行");
  }
}
 
parse_arguments = function(lex, name){
  do{
    var n = lex.skip("NUMBER");
    window.alert(name + "の" + n.value + "段目を実行");
  } while( lex.softskip(",") );
}

最初にコマンド名を読み込んでしまい、次の文字に応じて処理を分けています。本来ならダメージ計算のためのコードを記述しないといけませんが、今回はお遊びなので適当にメッセージだけ表示します。

引数有りver.のコードがやや読みづらいかもしれません。

parse_all() のコードと parse_arguments() のコードを見比べてみてください。前処理やエラー処理の部分こそ無いものの、ほとんど同じものだと気付くと思います。先程やったのが「セミコロンで区切られたコマンドの列の処理」で、今回やるのが「カンマで区切られた引数の列の処理」なのだから転用できて当然というわけです。

実際のコード

ところで、上で出したコードにはある弱点が存在するんですがわかるでしょうか？

それは「エラーが発生すると無言でスクリプト自体が停止する」という点です。どんなときにそうなるかというと、lex.skip("WORD") や lex.skip("NUMBER") でトークンを読み出そうとして失敗したとき起こります（コマンド名を書くべきところに全然関係ない記号が書かれていた・・・など）。

失敗時には null を返すので、このままだと null.value という命令が実行されます。これは不正な処理なので問答無用でJavaScriptが止まります。きちんとエラーチェックするように書き換えましょう：

parse_command = function(lex){
  var token = lex.skip("WORD");
  if(!token){ return; }
 
  if( lex.softskip("(") ){
    parse_arguments(lex, token.value);
    lex.skip(")");
  }
  else{
    window.alert(token.value + "を全段実行");
  }
}
 
parse_arguments = function(lex, name){
  do{
    var n = lex.skip("NUMBER");
    if(n){ window.alert(name + "の" + n.value + "段目を実行"); }
  } while( lex.softskip(",") );
}

JavaScriptでは true / false 以外の値も条件分岐に使うことができます（良い慣習とは言い難いが便利）。null は自動的に false に読み替えられるので !null は true になります。

Step 3. 派生技に対応する（おまけ）

さてさて、大人げなく Lexer なんぞ定義してきたせいでもうプログラムが完成してしまいました。しかしこれでは拍子抜けです。せっかくなので「派生技」にも対応させましょう。

ルール

派生技は次のルールで２つのコマンドに置換されます：

X1(a1)>X2(a2)　　→　　X1(a1); X1X2(a2)

ここで X1X2 は２つのコマンド名を連結した文字列です。実際のコードでは、まず X1(a1) の部分だけ先に処理してしまって、その後 ">" を取り除いてから再度 parse_command() をやり直すようにしています。

書き換え

というわけで、ちょっといじってみましょう：

parse_command = function(lex, prefix){
  var token = lex.skip("WORD");
  if(!token){ return; }
 
  if( lex.softskip("(") ){
    parse_arguments(lex, prefix + token.value);
    lex.skip(")");
  }
  else{
    window.alert(prefix + token.value + "を全段実行");
  }
 
  if( lex.softskip(">") ){
    parse_command(lex, token.value);
  }
}

最初に注意されたいのは prefixという引数が増えた ことです。これは派生技の処理で「コマンド名の連結」が必要になるからです。この変更に合わせて、parse_all() の中に登場する parse_command() の呼び出しも parse_command(lex, ""); に差し替えないといけません。

この辺は小細工でごまかすこともできるんですが、大人しく書き換えたほうがいいです。というか、むしろ面倒なのはこれだけで、あとは parse_command() の最後に追加した３行だけで派生技が実現されます。

完成品

まとめとして、ここまでのコードをすべてつなげてみましょう（今回書いた部分のみ）。

parse_all = function(input){
  var lex = new Lexer(input);
 
  do{
    parse_command(lex, "");
  } while( lex.softskip(";") );
 
  if(lex.text.match(/\S/)){
    window.alert("Error: コマンド解析に失敗しました");
  }
}
 
parse_command = function(lex, prefix){
  var token = lex.skip("WORD");
  if(!token){ return; }
 
  if( lex.softskip("(") ){
    parse_arguments(lex, prefix + token.value);
    lex.skip(")");
  }
  else{
    window.alert(prefix + token.value + "を全段実行");
  }
 
  if( lex.softskip(">") ){
    parse_command(lex, token.value);
  }
}
 
parse_arguments = function(lex, name){
  do{
    var n = lex.skip("NUMBER");
    if(n){ window.alert(name + "の" + n.value + "段目を実行"); }
  } while( lex.softskip(",") );
}

あとはHTMLのフォームに「ボタンが押されたらフォームの書き込み内容を読み込んで parse_all() を実行する」という処理を登録しておけばよいです。実際に書いたものを用意しました → parse_sample.html

未対応の機能

前回も断りましたが、今のままだと 236[A] などがコマンド名として認識されません。
引数として 1-4 のような範囲指定を渡せるようにしたいところですね。
エラーメッセージが不親切極まりないので、もうちょっと具体的にしたいです・・・^^;

１～２は別に難しくもなんともない処理です。ましてや今回は calc_damage.js にある種の解答が用意されているわけですし。興味があればどうやって組み込むか考えてみてください。

３はちゃんと方針を決めて取り組まないといけないかもしれません。横着する分にはどうにでもなりますが。

「構文解析」をウィキ内検索

最終更新：2012年12月10日 11:01

mblen @ ウィキ