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

Summary. コンピュータにとってテキストデータとは文字の羅列にすぎません。これを人間の読み方に近づけるために「トークン」というものを導入します。

トークン

ダメージ計算スクリプトで扱う対象は

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

のような文字列です。これを文法的に意味のある最小単位（トークンという）に分解すると

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

のようになります。セミコロンやカンマのように "１文字で意味のあるもの" もあれば、コマンド名や数字のように "何文字か集まって意味をなすもの" もあります。プログラムを書くときに「もし記号だったら１文字で処理して、逆に数字だったら何文字かまとめて読んで・・・」などといちいち意識するのは人間にとって辛い作業です。

そこで、入力テキストを渡せば勝手にトークンに分解して教えてくれるような機能が欲しくなります。全部関数として作ってもいいですが、そこはせっかくJavaScriptを使っているのでオブジェクトで実現したいです（そのほうが持ち運びやすい）。

一般に、文字列をトークンに分解する処理のことを「字句解析」と呼びます。今回のお題は、字句解析を自動で行うオブジェクトを作ることです。なお、簡単のため コマンド名に使える文字種をアルファベット＆数字だけに限定 しています。あらかじめご了承ください（増やすのは造作も無いです）。

トークンを表すオブジェクト

さて、上でいうトークンとはあくまで ";" や "5C" などの文字列のことでした。「トークンに分解する」というのは、つまり与えられた文字列を小さくちぎって順番に返すことです。しかしそれだけでは使うときに不便です。単に文字列を返すのではなく「それがどの種類のトークンか？」という付加情報を抱き合わせてみましょう。

SingleToken = function(c){
  this.type = this.value = c;
}
 
WordToken = function(text){
  this.type = /\D/.test(text) ? "WORD" : "NUMBER";
  this.value = text;
}
 
SINGLE_TOKENS = new Array();
SINGLE_TOKENS["("] = new SingleToken("(");
SINGLE_TOKENS[")"] = new SingleToken(")");
SINGLE_TOKENS[";"] = new SingleToken(";");
SINGLE_TOKENS[","] = new SingleToken(",");
SINGLE_TOKENS[">"] = new SingleToken(">");

JavaScriptのオブジェクトの定義法は独特で、普通にSingleTokenなどの関数を定義すると、なぜかその関数に対して new を呼び出すことができて、それでオブジェクトを生成することができてしまいます。

ともあれ、new SingleToken(">") とか new WordToken("5C") と書けばトークンを表すオブジェクトが作れるようになりました。これらのオブジェクトは type と value の２つのフィールドをもっていて、前者を見ればトークンの種類がわかります。

Lexer

トークンが定義できたので、実際に分解を行うオブジェクトを書いてみましょう。世の中では普通こういう種類のオブジェクトに Lexer という名前を付けるようなので、今回もそれに倣います。

Lexer = function(input){
  this.text = input;
  this.current = null;
  this.nextToken();
}
 
Lexer.prototype.nextToken = function(){
  if(this.text.match(/\S/)){
    if(RegExp.lastMatch in SINGLE_TOKENS){
      this.text = RegExp.rightContext;
      this.current = SINGLE_TOKENS[RegExp.lastMatch];
      return this.current;
    }
 
    if(this.text.match(/^\s*(\w+)/)){
      this.text = RegExp.rightContext;
      this.current = new WordToken(RegExp.$1);
      return this.current;
    }
  }
 
  this.current = null;
  return null;
}
 
Lexer.prototype.skip = function(type){
  if(this.current && this.current.type == type){
    var prev = this.current;
    this.nextToken();
    return prev;
  }
  else{
    return null;
  }
}

Lexerは２つのメソッドを持っています。

nextToken()

入力テキストからトークンを１つ切り出します。１行目の正規表現が少々わかりづらいですが、実行すると RegExp.lastMatch に空白類でない最初の１文字が格納されます。もしこの文字が記号だったら、この１文字だけ切り取ってトークンに仕立てます。

ここで生成されたトークンは Lexer の current フィールドにも代入されます。大事なことは「トークンを作るのに失敗したらどうするの？」ということで、今回はトークンの代わりに null が登場するようにしました。

skip(type)

指定された種類のトークンを１つ読み飛ばします。もし現在のトークンが別の種類だったら失敗です。この手のメソッドは true / false を返すケースも多いですが、代用が利くので読み飛ばされたトークン（失敗時は null ）を返すようにしておきます。

定義だけではピンとこないですので、使用例も書いておきます：

run = function(text){
  var lex = new Lexer(text);
 
  while( lex.current ){
    window.alert(lex.current.type);
    lex.nextToken();
  }
}
 
run("JC; 5C(1,2,3,4); 3C; 236C;")

run() という関数を呼び出すと、トークンが無くなるまでループ部分を繰り返します。おそらく "WORD" とか ";" とかが何回も表示されるはずです（入力が長すぎると途中でダルくなるので注意）。

小細工

基本的にJavaScriptには例外処理がありません^[1]。そのため、この後に待ち構える「構文解析」のプログラムを書くときに解析処理とエラー処理が入り交じって色々大変なことになりそうです。

なので、Lexer にちょっと小細工をしておきましょう：

Lexer = function(input){
  this.enabled = true; // 使用可能か否か
  this.text = input;
  this.current = null;
  this.nextToken();
}
 
Lexer.prototype.nextToken = function(){
  if(this.enabled && this.text.match(/(\S)(.*)/)){
    if(RegExp.$1 in SINGLE_TOKENS){
      this.text = RegExp.$2;
      this.current = SINGLE_TOKENS[RegExp.$1];
      return this.current;
    }
 
    if(this.text.match(/^\s*(\w+)/)){
      this.text = RegExp.rightContext;
      this.current = new WordToken(RegExp.$1);
      return this.current;
    }
  }
 
  this.enabled = false; // 使用不可能にする
  this.current = null;
  return null;
}
 
Lexer.prototype.skip = function(type){
  var prev = this.softskip(type);
 
  if(prev == null){
    this.enabled = false; // 使用不可能にする
  }
 
  return prev;
}
 
Lexer.prototype.softskip = function(type){
  if(this.enabled && this.current.type == type){
    var prev = this.current;
    this.nextToken();
    return prev;
  }
  else{
    return null;
  }
}
 
Lexer.prototype.abort = function(){
  this.enabled = false;
}

簡単に言うと「問題が起きたらそれ以降はトークンを読み出さないようにする」という寸法です。使用可能か否かは enabled フィールドを見ればわかります。abort() というメソッドを呼び出すと強制的に使用不可能な状態になります^[2]。

softskip() は失敗しても使用不可能にはならない skip() です。このあと実際に使ってみて「こういうのがあると楽になる」と判断したので追加してみました。

機能一覧

最後に、今回作った Lexer クラスの仕様を表にまとめておきます。

Field summary
enabled	このLexerがまだ使用可能なら true。このフィールドが true である限り、current は決して null ではない
current	一番最後に読み込んだトークン（残ってなければ null ）。 nextToken() や skip() などを実行したとき変更される。
text	解析対象であるテキスト

Method summary
abort()	このオブジェクトを使用不可能にする
nextToken()	新しいトークンを読み出して返す。失敗時は null を返すと共に、このオブジェクトを使用不可能にする
skip(type)	current が指定された種類のトークンならそれを読み飛ばす。失敗時は null を返すと共に、このオブジェクトを使用不可能にする
softskip(type)	skip(type) と同じだが、失敗しても使用不可能にならない

[1]
実はブラウザの独自仕様としては try ... catch が存在するらしい。興味があれば使ってみてください。

[2]
たった１行のコードをわざわざメソッドにしたのは、将来もっと仕事が増えるかもしれないから。

「字句解析」をウィキ内検索

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

mblen @ ウィキ