JavaScriptで言語処理系の勉強をしましょう：字句解析編

昨日のエントリーで、小学生レベルの算術計算をする仮想機械RAC0（Rudimentary Arithmetic Calculator Level-0）を示しました。たいへん貧弱な仮想機械ですから、機能を拡張したいとは思うのですが、その前に、RAC0用の高級言語を作っておきましょう。

高級言語といっても、1 + 2, (5 - 2)*4 のような算術式（arithmetic expression）です。詳しく仕様を書いても次の程度。

1. 定数リテラルは、符号なしの整数。03 のように先行する0があってもよい*1。
2. 負の数を表すリテラルがないので、(0-3) のように引き算で代用。
3. 演算記号は、+, -, *, /, % の5種類。いずれも二項中置演算子。
4. *, /, % は、+, - より優先される。
5. 丸括弧を使って、式のグループ（まとまり）を作ってよい。
6. 同じ優先順位の演算は左結合的。例えば、 5*3/2 は、(5*3)/2 のこと。

今日は、この“高級言語”の処理系の一部を作ってみます。

Web上で試せるURL

• http://www.chimaira.org/tools/rac0sca.html

使い方と結果の見方の説明は、このエントリーの後のほうにあります。[追記]ありっ、IEだと結果が表示されないな。toSource() のせいでした。テケトーに直しておきました。（IEとFirefoxで表示が完全に同じじゃないです）。[/追記]

言語処理の第一歩：作業の分類

コンピュータ業界の「言語処理」と言えば、典型的には、高級言語をコンパイルして機械（もちろん、仮想機械でもよい）の実行可能コードに変換するような作業です。その作業は、次の3つの部分に分けるのが普通です。

1. トークンの読み取り（字句解析）
2. 構文解析木の作成
3. 機械語コードの生成

それぞれの作業を担当するプログラムモジュールは次のように呼ばれます。

1. 字句解析器 or トークンスキャナー（単にスキャナー） or トークナイザー or レクサー
2. 構文解析器 or パーザー
3. コード生成器 or コードジェネレータ

この3つの部分に分けて考えるのが定石ですね。いろいろなバリエーションはありますが、まずは定石に従ったほうがいいと思います。

トークンスキャナーの実装

算術式のトークンを読み取るトークンスキャナーをJavaScriptで実装すると、次のような感じでしょう。[追記]うへーー、なんでこんなに長いんだ？ と思った方は最後の追記を見てください。[/追記]

/* rac0sca.js */
/* RAC0仮想機械向け高級言語のトークンスキャナー */

var EOF = -1;

var ZERO  = 48; // '0'
var NINE  = 57; // '9'
var TAB   =  9; // '\t'
var LF    = 10; // '\n'
var CR    = 13; // '\r'
var BLANK = 32; // ' '

// 記号文字（文字番号）
var PLUS  = 43; // '+'
var MINUS = 45; // '-'
var STAR  = 42; // '*'
var SLASH = 47; // '/'
var PERC  = 37; // '%'
// 括弧
var LPAR  = 40; // '('
var RPAR  = 41; // ')'

// この関数、ここにあったほうが目視確認しやすい。
// よって、ここに置く。
function _textOf(c) {
  switch (c) {
  // 記号文字（文字番号）
  case PLUS  : return "+";
  case MINUS : return "-";
  case STAR  : return "*";
  case SLASH : return "/";
  case PERC  : return "%";
  // 括弧
  case LPAR  : return "(";
  case RPAR  : return ")";
  default: return "";
  }
}

// データ付きトークン
var NUMBER = 400;
var ERROR  = 500;


function Scanner(src) {
  this.init(src? src : "");
}
var _p = Scanner.prototype; // _p は使い捨て、globalを汚してスマンね

_p.init = function(src) {
  this.src = src;
  this.index = 0;
  this.ungotten = null; // 1個分だけのバッファ
};
_p.getchar = function () {
  if (this.index >= this.src.length) {
    return EOF;
  }
  return this.src.charCodeAt(this.index++);
};
// 直前のgetcharをなかったことにする
_p.revertchar = function () {
  if (0 < this.index) {
    this.index--;
  }
  return this.index; // デバッグに役立つ
};
_p.reset = function() {
  this.index = 0;
};

_p.isWhitespace = function(c) {
  return (c === TAB || c === BLANK || c === LF || c === CR);
};
_p.isDigit = function(c) {
  return (ZERO <= c && c <= NINE);
};
_p.textOf = function(c) {
  return _textOf(c);
};

_p.skipWhitespaces = function() {
  for (var c = this.getchar(); c != EOF; c = this.getchar()) {
    if (!this.isWhitespace(c)) {
      this.revertchar();
      break;
    }
  }
  return this.index; // デバッグに役立つ
};

/*
 * getToken() の仕様：
 *
 * 戻り値は、[kind, data, pos] という配列（タプル）
 * kind はトークンの種別（定数定義を参照）
 * data はトークンに付随するデータ、
 *      特にデータが不要な場合もデバッグ用データを入れている。
 * pos  はトークン出現の"目安"の位置。実際は次の読み出し位置なので
 *      トークンはこの位置より前に出現していることに注意。
 */

_p.getToken = function() {
  var t = this.ungotten;
  if (t) {
    this.ungotten = null;
    return t;
  }
  this.skipWhitespaces();
  var c = this.getchar();
  switch (c) {
  case EOF:
    return [EOF, "EOF", this.index];
  case PLUS: case MINUS: case STAR: case SLASH: case PERC:
  case LPAR: case RPAR:
    return [c, this.textOf(c), this.index];
  default:
    if (this.isDigit(c)) {
      this.revertchar();
      return this.getNumber();
    }
    return [ERROR, "unexpected char: '" + String.fromCharCode(c) + "'",
	    this.index];
  }
};

_p.ungetToken = function(t) {
  if (this.ungotten) {
    throw "cannot unget token";
  }
  this.ungotten = t;
};

_p.getNumber = function() {
  var n = 0;
  for (var c = this.getchar(); c != EOF; c = this.getchar()) {
    if (! this.isDigit(c)) {
      this.revertchar();
      break;
    }
    n = n*10 + (c - ZERO);
  }
  return [NUMBER, n, this.index];
};

APIのメインとなるメソッドはgetToken()です。getToken()が返すトークンデータの仕様はコメントに書いてあります。パーザー（構文解析器）において、取得したトークンを戻したいことがあるので、ungetToken()も付けています。

テストしてみる

http://www.chimaira.org/tools/rac0sca.html は、rac0sca.js をテストするためのフロントエンドです。HTMLページ上側のテキストエリアに、なんでもいいからテキストを入力します。トークンスキャナーは、式の構文を認識するわけではなくて、単にトークンを切り出して返すだけです。

[トークンスキャン実行]ボンタンを押すと、トークンの列を、下側のテキストエリアに表示します。認識できるトークンは、整数リテラル、演算子、括弧だけです。その他の文字はエラーとなりますが、エラーがあっても入力の最後まで読み取ります。

トークンスキャン結果は、getToken()が戻したデータを配列にしたものをそのまま表示しています。あんまり見やすくはないですが、デバッグ・テストにはこのほうが好都合です。

あとは

パーザーとコードジェネレータが必要ですね。まー、そのうち。

---

[追記]

rac0sca.js を次の rac0shortsca.js に置き換えても、rac0sca.html はほぼ同じように動きます。上で示したJavaScriptコードは、他の言語（例えばC言語*2とか）でも同じように書けること、それと後で拡張しやすいことを考慮したものです。

/* rac0shortsca.js */

var EOF = -1;
var DELIM = 300;
var NUMBER = 400;
var ERROR = 500;

function Scanner(src) {
  this.init(src? src : "");
}

Scanner.prototype.init = function(s) {
  // デリミタの前後に空白を置き、空白で分割
  this.src = s.replace(/([-+*/%()])/g, " $& ").split(/[ \t\n\r]+/);
};

Scanner.prototype.getToken = function() {
  // 念のため空文字列をスキップ
  for (var t = this.src.shift(); t == ""; t = this.src.shift()) {};
  if (t === undefined) {
    return [EOF, "EOF"];
  }
  // とりあえず数値化してみる
  var n = Number(t);
  if (isNaN(n)) {
    // 数値じゃなかった
    if (t.search(/[-+*/%()]/) === -1) {
      // 区切り記号でもない
      return [ERROR, "illegal char"];
    } else {
      // 区切り記号
      return [DELIM, t];
    }
  } else {
    // 数値
    return [NUMBER, n];
  }
};

[/追記]

*1:この仕様は、「トークン切り出しで手抜きしたい」という理由からです。

*2:実はこれ、簡単な言語処理系をC言語で書いてもらうコースの説明用素材です。