技術

1.3. 字句解析器

LLVMによるプログラミング言語の実装チュートリアル日本語訳
第1章 万華鏡: まえがきと字句解析器
第3節 字句解析器

言語にまず必要になるのが、テキストファイルを処理しそれに何が書いてあるのか認識する能力の実装である。
伝統的な方法では、”字句解析器(lexer)”(別名スキャナー)を使ってテキスト(ソースコード)をトークンごとにバラバラにする。
各トークンは、トークンコードと潜在的ないくつかのメタデータを保持している字句解析器によって得られる。(例えば数値型の数値であるトークン、といった感じに。)
まず、”見込み(possibilities)”を定義する。
訳注: これからコードの説明に入っていくが、ここで説明してるコードの全文は第2章の最後にある。また、第1章と第2章ではまだLLVMは使わない点に注意。

// 未知の文字の場合、字句解析器は0以上255以下のトークン値を返す。
// 既知のトークンなら、そのトークンに合った値を返す。
enum Token {
  tok_eof = -1,

  // コマンド
  tok_def = -2, tok_extern = -3,

  // 主要なもの(primary)
  tok_identifier = -4, tok_number = -5,
};

static std::string IdentifierStr;  // tok_identifierの場合に代入される
static double NumVal;              // tok_numberの場合に代入される

我々の字句解析器によって返される各トークンは、Token列挙型の値のどれか、もしくは”+”のような不明な文字の場合にはそのASCIIコード値を返す。
もし現在のトークンが識別子(identifier)なら、グローバル変数IdentifierStrはその識別子の名前を保持する。
もし現在のトークンが数値リテラル(1.0のような)なら、NumValはその値を保持する。
説明を簡単にするためグローバル変数を使ってる事に注意。
これは本気の言語実装ではおすすめできない方法である。

字句解析器の実装は、gettok関数ただひとつだけである。
gettok関数は、標準入力から次のトークンを得るために呼ばれる。
その定義は次のように始まる。

/// gettok - 標準入力から次のトークンを返す。
static int gettok() {
  static int LastChar = ' ';

  // 空白をスキップする。
  while (isspace(LastChar))
    LastChar = getchar();

gettokはCのgetchar()関数を呼ぶことによって動作し、一度に一文字ずつ標準入力から読み込む。
gettokは文字を読み込み、そしてそれを認識し、そして最後に読んだ文字を(しかし処理はせずに)LastCharに保存する。
最初の仕事は、トークン間の空白を無視することである。
上記のループによってこれが行われる。

gettokの次の仕事は、識別子と”def”のような特定のキーワードの認識である。
万華鏡ではこれを以下の簡単なループで行う。

if (isalpha(LastChar)) { // 識別子: [a-zA-Z][a-zA-Z0-9]*
  IdentifierStr = LastChar;
  while (isalnum((LastChar = getchar())))
    IdentifierStr += LastChar;

  if (IdentifierStr == "def") return tok_def;
  if (IdentifierStr == "extern") return tok_extern;
  return tok_identifier;
}

このコードは、識別子を字句解析したらすぐにグローバル変数IdentifierStrにセットしてる事に注意。
そして、このループによって予約語(language keyword)に合致したら、それをここでインラインで処理する。
数値の場合も似ている。

if (isdigit(LastChar) || LastChar == '.') {   // 数値: [0-9.]+
  std::string NumStr;
  do {
    NumStr += LastChar;
    LastChar = getchar();
  } while (isdigit(LastChar) || LastChar == '.');

  NumVal = strtod(NumStr.c_str(), 0);
  return tok_number;
}

これら全て、入力を処理するための実に素直なコードである。
入力から数値を読み取るとき、NumValに保存した数値(の文字列)を変換するためにCのstrtod関数を使用している。
十分なエラーチェックを行っていない事に注意。
このままでは”1.23.45.67″を読み込んだ時に”1.23″として誤認識するだろう。
この部分を改良するのは簡単だからやってみるといい。

次はコメントの処理である。

if (LastChar == '#') {
  // 行の終わりまでがコメント
  do LastChar = getchar();
  while (LastChar != EOF && LastChar != '\n' && LastChar != '\r');

  if (LastChar != EOF)
    return gettok();
}

行の終わりまでスキップし、そして次のトークンを返す事によってコメントを処理(無視)する。
最後に、もし入力が以上のいずれかにも合致しない場合、それは”+”のような演算子を表す文字かファイルの終わり(EOF)である。
それらは以下のようにして処理される。

  // ファイルの終わりをチェックする。
  if (LastChar == EOF)
    return tok_eof;

  // それ以外の場合には、文字のASCIIコード値をそのまま返す。
  int ThisChar = LastChar;
  LastChar = getchar();
  return ThisChar;
}

これによって、我々は簡単な万華鏡言語のための完全な字句解析器を手にした。(この字句解析器のソース全体は次の章の最後で見れる。)
次は、AST(抽象構文木、Abstract Syntax Tree)構築のために、この字句解析器を使用した簡単な構文解析器を構築してみよう。
そのなかで、字句解析器と構文解析器を連携させるためのドライバも構築する。

コメントを残す

メールアドレスが公開されることはありません。



※画像をクリックして別の画像を表示

このサイトはスパムを低減するために Akismet を使っています。コメントデータの処理方法の詳細はこちらをご覧ください