字句解析器の作り方

（2）では，一般に字句解析器や構文解析器に利用されるパーサジェネレータツール（Yacc/Bison）を利用せずに，自分の手で字句解析器を作成する際に気をつけなければいけない点や設計方針について，Compiler::Lexerを開発した際に得られた知見をもとに解説します。

正規表現で処理するのは正解？

字句解析器や構文解析器を開発するときによく利用するものとして正規表現があります。正規表現は文字列処理を行ううえでとても有益ですが，言語処理系の場合はそうとも限りません。正規表現で表現できないシンタックスが存在する場合や同じ文字を何度も探索しなければならない場合は，正規表現ではなく，後述する1文字ずつ処理する方法をお勧めします。

正規表現で表現できないシンタックスが存在する場合

当然ながら，Perl 5のような複雑なシンタックスの場合，すべてを正規表現で処理することは難しいです。たとえば#があったら，それ以降は行末までコメントと判断してよいでしょうか。答えはノーで，正規表現のデリミタ（区切り文字）の場合や，文字列やヒアドキュメントの中に記述されている場合は無視しなければいけません。Perl 5にはほかにも，正規表現で記述することを考えるとぞっとするシンタックスが多く存在します。

もちろん，1つの正規表現で表現しきれない場合は，いったんスペースなどでソースを分解したあとに個別に適用するなど，段階的に正規表現を適用していく方法が考えられますが，次第にソースコードが複雑化し，保守しにくくなる原因となります。このため，正規表現を用いたパターンマッチによってトークンに切り出す方法は，あまりお勧めできません（PPIでも初めは正規表現で実装されていたそうですが，途中でパターンマッチによる解析に限界を感じ，書き直すことになったそうです）。

同じ文字を何度も探索しなければならない場合

1つの正規表現で表現できない場合，段階的に正規表現を適用する方法も考えられると説明しましたが，この方法だと同じ文字を何度も正規表現の適用対象にしてしまうことになり，実行パフォーマンスの観点から望ましくありません。パフォーマンスの面からも正規表現は避けるべきでしょう。

字句解析器の基本構成

本項では，字句解析器を構成する主なコンポーネントや用語について説明します。字句解析器の説明でよく登場する用語は次のようなものです。

トークン（Token）

字句解析器によって切り出された文字列

カーソル（Cursor）

現在処理している文字の位置を表す

スキャナ（Scanner）

デリミタの開始位置から終了位置までカーソルを進める（また，その間の文字列をトークンとして切り出す）

アノテータ（Annotator）

切り出したトークンに解析情報を付加する

これらの用語を用いて字句解析器のテンプレートを表現すると，次のような擬似コードになります（擬似コードはC++言語をベースとして書かれています）。

std::vector<char *> token_array;
Scanner scanner;
// 字句解析器のメインループ
for ( ソースコードの終端まで，カーソルを1 文字ずつ進める) {
  // カーソルがある位置の文字を得る
  char current_char = get_current_char(cursor,
                                       source_code);
  switch (current_char) {
  case '\'': '"': // 文字列の開始デリミタの場合
      // スキャナによってcursor を進めつつ，
      // 文字列の終端を見つけたら，トークンに切り出す
      char *token = scanner.scanQuote(current_char,
                                      source_code,
                                      cursor);
      // 切り出したトークンをトークン列に加える
      token_array.push_back(token);
      break;
  ...
  default:
      break;
  }
}
Annotator annotator;
for (トークン列を端から端までなめる) {
  // トークンに解析情報を付加する
  annotator.annotateInformation(token);
}

前項で説明したように，正規表現ではなくカーソルを1文字ずつ進めながら解析することで，何度も同じ文字が解析対象にならず，ソースコードの見通しも良くなります。Compiler::Lexerは，まさに上記に近い構成で実装されています。

本項からは，字句解析器をスムーズに開発するための勘どころを解説します。

「デリミタ」の判断がすべて

字句解析器の目的は文字列から文字列を切り出すことです。文字列を切り出すためには，どの位置からどの位置までを切り出し対象とするか，つまりある文字がデリミタかどうかの判断が重要となります（（1）で示した擬似コードの中では，スキャナがこの役目を担っています）。

上記を踏まえ字句解析器が内部で行う処理を整理すると，

• ソースコードを1文字ずつ読み進めながら，その文字があるトークンの開始デリミタかどうかを判断し，開始デリミタだと判断できた場合には，スキャナに開始デリミタとカーソル位置を渡して，終了デリミタまで読み進めてもらう
• 読み進める際には，文字をすべてバッファに貯めておき，終了デリミタに到着した際にトークンに切り出す

となります。これをそのままコードにすることで，シンプルなシンタックスであれば簡単に字句解析器を作成できます。

状態をできる限り持たない

「必要以上に状態を持たないようにする」というプログラミングの鉄則は，字句解析器を作成するうえでも重要です。具体的には，「デリミタかどうかを判断するために，状態変数をなるべく使わないようにする」ことが重要となります。たとえば文字列や空白の終了デリミタを探す際に状態変数を使う必要はないでしょう。

しかし，Perl 5では次に示すヒアドキュメントの処理などが状態を持たざるをえないので，複雑になりがちです。

my $a =<<HERE_DOCUMENT . $ext_string;
… document …
HERE_DOCUMENT

上記のヒアドキュメントを処理する場合，<<HERE_DOCUMENTを解析した際に，ヒアドキュメントの開始フラグを保持しつつ，以降の解析を続けなければなりません。そのうえで，改行文字が現れた際に保持しておいたフラグと照らし合わせ，それ以降をヒアドキュメントと判断するという処理になります。

このようなやむを得ない場合を除き，なるべく状態変数を使うことは避けましょう。