re2cで字句解析（fillについて）

2014-01-28
#compiler

今までだいたい手書きでスキャナを書いてたんだけど、re2cというスキャナ生成ツールがあって、flexや手書きよりも高速なスキャナが生成できるという話なので試してみた。

Macでのre2cのインストール：

$ brew install re2c

使い方：

$ re2c -o 出力ファイル名 入力ファイル名

re2cではflexなどと同様に正規表現でルールを書いて、それにマッチした時に行うアクションやトークンの種類などを定義すると、スキャナとなるCのソースを生成してくれる。

flexとの違いは、re2cではスキャンするバッファの管理を自分でする必要があるということだ。スキャナが判定するための入力文字が必要となった時、YYFILLという関数（？）が呼び出されるので、バッファに必要な文字を読み込んで返す必要がある。しかしこれがどうにもややこしい。なにがわかりづらいかというと、いくつものポインタを操作しなくちゃならないのと、そもそもYYFILLに渡される値が「追加で何文字必要」という数ではないことだと思う。

というわけで、試したソースはこちら：

#include <string.h>  // memmove
#include <stdio.h>

// Tokens
enum Token {
  ERROR = -2,
  EOS = -1,
  LPAR = 1,
  RPAR,
  DOT,
  INT,
  SYMBOL,
  STRING,
};

class Scanner {
  FILE* fp_;            // Input file handler.
  char* buffer_;        // Read buffer.
  size_t bufferSize_;   // Buffer size.
  const char* token_;   // Beginning of token.
  const char* cursor_;  // Looking point.
  const char* marker_;  // Backtrack information.
  char* limit_;         // Character loaded point.
  bool eof_;            // is end of file?

 public:
  Scanner(FILE* fp)
    : fp_(fp), buffer_(NULL), bufferSize_(0),
      token_(NULL), cursor_(NULL), marker_(NULL), limit_(NULL),
      eof_(false) {
  }

  ~Scanner() {
    delete[] buffer_;
  }

  Token scan();

  inline const char* getToken() const  { return token_; }
  inline const char* getLimit() const  { return limit_; }
  inline int getLength() const  { return cursor_ - token_; }

 private:
  bool fill(int n);
  void shiftBuffer();
  void expandBuffer(int n);
};

Token Scanner::scan() {
 initial:
  token_ = cursor_;
  /*!re2c
    re2c:define:YYCTYPE = "char";
    re2c:define:YYCURSOR = cursor_;
    re2c:define:YYLIMIT = limit_;
    re2c:define:YYMARKER = marker_;
    re2c:define:YYFILL:naked = 1;
    re2c:define:YYFILL@len = #;
    re2c:define:YYFILL = "if (!fill(#)) { return EOS; }";
    re2c:yyfill:enable = 1;
    re2c:indent:top = 1;
    re2c:indent:string = "  ";
    SYMBOL_CHAR = [^ \t\n\000"];
    STRING_CHAR = [^"\000\n];
    OTHER = .;
    "\000"          { return EOS; }
    "\n"            { goto initial; }
    [ \t]+          { goto initial; }
    [0-9]+          { return INT; }
    "("             { return LPAR; }
    ")"             { return RPAR; }
    "\."            { return DOT; }
    ["] STRING_CHAR* ["] { return STRING; }
    SYMBOL_CHAR+    { return SYMBOL; }
    OTHER           { return ERROR; }
  */
}

bool Scanner::fill(int n) {
  if (eof_ && (limit_ - cursor_) <= 0)
    return false;

  size_t need = n - (limit_ - cursor_);
  size_t offset = limit_ - buffer_;
  if (offset + need > bufferSize_) {  // Need more buffer for read.
    size_t dust = token_ - buffer_;  // Size of consumed characters.
    if (offset + need - dust <= bufferSize_)
      shiftBuffer();
    else
      expandBuffer(need);
  }

  size_t readSize = fread((void*)limit_, 1, need, fp_);
  limit_ += readSize;
  for (int i = readSize; i < need; ++i)
    limit_[i] = '\0';
  if (readSize < need)
    eof_ = true;
  return true;
}

void Scanner::shiftBuffer() {
  size_t dust = token_ - buffer_;
  memmove(buffer_, token_, limit_ - token_);
  token_ = buffer_;
  limit_ -= dust;
  cursor_ -= dust;
  marker_ -= dust;
}

void Scanner::expandBuffer(int n) {
  const int MIN_EXPAND_SIZE = 16;
  size_t dust = token_ - buffer_;
  size_t newSize = bufferSize_ + (n > MIN_EXPAND_SIZE ? n : MIN_EXPAND_SIZE);
  char* newBuffer = new char[newSize];
  if (bufferSize_ > 0)
    memmove(newBuffer, token_, bufferSize_ - dust);
  // Change pointers to point new buffer.
  cursor_ = &newBuffer[(cursor_ - buffer_) - dust];
  limit_ = &newBuffer[(limit_ - buffer_) - dust];
  token_ = &newBuffer[(token_ - buffer_) - dust];
  marker_ = &newBuffer[(marker_ - buffer_) - dust];
  // Switch to new buffer.
  delete[] buffer_;
  buffer_ = newBuffer;
  bufferSize_ = newSize;
}

int main() {
  Scanner scanner(stdin);

  for (bool loop = true; loop; ) {
    Token tok = scanner.scan();
    int len = scanner.getLength();
    switch (tok) {
    case EOS:
      loop = false;
      break;
    case ERROR:
      printf("illegal [%.*s]\n",
             (int)(scanner.getLimit() - scanner.getToken()), scanner.getToken());
      loop = false;
      break;
    case LPAR:
      puts("(");
      break;
    case RPAR:
      puts(")");
      break;
    case DOT:
      puts(".");
      break;
    case INT:
      printf("INT    [%.*s]\n", len, scanner.getToken());
      break;
    case SYMBOL:
      printf("SYMBOL [%.*s]\n", len, scanner.getToken());
      break;
    case STRING:
      printf("STRING [%.*s]\n", len, scanner.getToken());
      break;
    }
  }

  return 0;
}

マニュアルとかサンプルとか難しくてちゃんと読んでないけど、とりあえず動きます。

まず、re2cで生成されたスキャナはYYCURSOR, YYLIMIT, YYMARKERという3つのポインタを必要とする。YYCURSORはスキャナが今見ているトークンのポイント（トークンの先頭ではない）、YYLIMITは読み込まれたバッファの上限、YYMARKERはなんかわからないけどバックトラックの情報らしい（ルールによっては使われない場合もある）。

re2cではスキャンを進めるごとにポインタを進めていってしまい、トークンが受理された時にはそのトークンがどういう文字列だったかという情報は管理していない。必要な場合には利用する側で管理する必要がある(上記のプログラムではtoken_というメンバ変数で保持している)。

YYFILLに渡ってくる値は「次に何文字必要か」じゃなくて、「現在見ているYYCURSORから何文字必要か」なので、新たに読み込む必要のある文字数は n - (YYLIMIT - YYCURSOR) となる。

でその数が確保しているバッファ(buffer_)に収まりきらない場合にはバッファを操作する必要がある。バッファの前半部分にはすでに消費済みの領域がある場合があるので、メモリの動的確保を最小限にするため、それを詰めて入るようだったら詰める(shiftBuffer)。詰めても入らないようであればバッファ自体を拡張してやる(expandBuffer)。で必要な文字数がバッファに収まるようになったので、YYLIMITから必要な文字数分だけ読み込んでやり、YYLIMITを末尾にあわせる。

バッファをシフトする場合は、トークンの開始位置(token_)から上限(YYLIMIT)までをバッファの先頭に移動する。バッファを拡張する場合は、新しいバッファを確保して古いバッファから必要な内容をコピーする。どちらも管理しているポインタを新しいバッファの位置を指すように調整する必要がある。

使用する側は定義したスキャン関数(scan)を呼び出すと対応するトークンが返ってくる。トークンの値が必要な場合には、スキャナのアクションでtoken_からYYCURSORまでを使って、atoiなりなんなりして、yylvalなどという共用体を作って値を格納しておけばよろしいかと。

生成されたスキャナが高速化どうかの比較などは試してない。またre2cの導入は、Lispではリードマクロで読み込みの動作を変えることができてしまい、その際にスキャナ側に先読みされた文字をポート側にungetcしたりする必要が発生するのではないかということで、ためらっている。自作の言語を作る場合には使ってみようかな。

関連記事

新着記事