しかくいさんかく

解答略のメモ

19日目: [コンパイラ] 字句解析

この記事はひとりでCPUとエミュレータとコンパイラを作る Advent Calendar 2017の19日目の記事です。

今日は字句解析をやる。まず昨日のサンプルコードを人力で字句解析し、コツを掴んだところで実装を説明する。

字句解析とは

昨日のサンプルコード

// C言語風コード
int main () {
  int a ;
  a = 3 ;
  return 0 ;
}

コードに出現する各単語に対し、トークン属性を付与することを字句解析というのだった。

f:id:kaitou_ryaku:20171219000027p:plain:w500

ここで(TYPE_KEYWORD, "int")のようなペアをトークンと呼び、緑字のTYPE_KEYWORDトークン属性と呼ぶ。

属性の定義は、BNFで与えるのだった。

BNF (バッカス-ナウア記法)

BNFとは「文字列に属性を与える」ために「属性のマッチ条件を正規表現で定義」したものだった。 そこでは「定義済みの属性」を他の属性の定義式中に埋め込むことができた。いわば正規表現の代入だ。

昨日のBNFは簡易版だったので、ここに正式版のBNFを貼っておく。

f:id:kaitou_ryaku:20171219062443p:plain

パイプ記号|正規表現の or を表している。(hoge|piyo)*正規表現と同じ。

また画像中にも書いたが * int や if という文字列の属性は、IDENTIFYではなくTYPE_KEYWORDIF_KEYWORDとする * CHAR_ALPHABETCHAR_NUMBERIDENTIFYNUMBERを定義するために導入した一時的属性なので、最終結果には残らない

という二点に気をつけよう。

minc言語誕生

ところで、ここで定義した言語はC言語のサブセットになっている。 いや、サブセットというのもおこがましい。 なんせ型はintしかないし、配列、ポインタ、構造体等は一切使えない。 #include#defineもないし、breakswitchもない。

しかし、しかしだ!!

変数が使えて、整数が計算できて、関数を定義して呼び出すことも可能な言語になっている。 しかもifとwhileが使えるので、構造化定理が発動してgoto文が不要になる。構造化プログラミングができるのだ。 C言語はウルトラリッチな超高級言語だが、今回の言語だって必要不可欠な機能は全ておさえていると思う。 特に「アセンブラのコーディングが辛いのを改善する」という目的は十分に果たせる。 立派だ。

立派なので名前をつけてやろう。 名前はmincにしよう。 C言語を最小限にした言語という雰囲気で命名した。

字句解析 (人力)

字句解析のコツを掴むため、BNFで昨日のサンプルコードを人力解析してみる。

// C言語風コード
int main () {
  int a ;
  a = 3 ;
  return 0 ;
}

まず前処理として改行文字を空白文字に置換する。 もしコメント行 // comment/* comment */があれば、それも空白文字に置換する。

int main () { int a ; a = 3 ; return 0 ; }

ここからBNFによる解析が始まる。 まず一番最初にintがある。BNFを上から順に眺めると

TYPE_KEYWORD := "int"

が目に入るだろう。左辺と右辺を := で繋いだ。

次はintmainの間だが、空白文字を見つけたら、そこまでの単語で字句解析を行い、空白文字はスキップする。 つまりintmainは別のトークンということだ。

次はmainが目に入る。 一見すると、BNFの中にmainは見当たらない。 しかしmaといった単体の文字にはCHAR_ALPHABETという属性が定義されている。 従ってmainCHAR_ALPHABETの4連打ということになる。 しかし注意したようにCHAR_ALPHABETは字句解析の最終結果に出現しないはずだった。 あらためてBNFを見返すと、

IDENTIFY := CHAR_ALPHABET ( CHAR_NUMBER | CHAR_ALPHABET )*

が目に入る。従って mainの属性はIDENTIFYだと分かる。

さて次は(という文字に到達するが、これはBNF表でLPARENになっている。 次は)で、RPARENだ。 ここで、()の間には空白文字が入っていないかった。 字句解析のコードを書く時は、 異なるトークンの間に空白文字が無いこともある ことに注意しなければならない。

この調子で進めていけば、記事冒頭の字句解析結果が得られる。 コツは掴めたと思うので、人力から自動化に移ろう。

字句解析の実装

今からC言語でmincの字句解析プログラムを作成する。 リポジトリはこれ

全部追うのは大変なので、大まかな流れだけ書くことにする。

列挙型で属性にエイリアスを貼る

まず以下のような 列挙型のTOKEN_KINDをinclude/common.hで宣言 した。

typedef enum {
  TERM_OPERATOR   ,
  FACTOR_OPERATOR ,
  COMPARE_OPERATOR,
  ...
} TOKEN_KIND      ;

列挙型(enum)は馴染みがないかもしれないが、要するにTERM_OPERATORのような属性に対し、エイリアスとして整数を割り当てているイメージだ。 雰囲気としては

#define TERM_OPERATOR    0
#define FACTOR_OPERATOR  1
#define COMPARE_OPERATOR 2
...

とするのに近い。

トークンの構造体

トークンは単語と属性のペアだった。 これを表すために /include/common.hでTOKEN 構造体を宣言 した。

typedef struct {
  int kind;
  char str[TOKEN_STRING_MAX_LENGTH];
} TOKEN;

kindの部分に、さっき列挙体で定義した整数(つまりトークンの属性)を入れ、 strの部分に、読んだ文字列を入れる。

コメントの読み飛ばし

mincコードの文字列を受け取り、「次の文字」を取得する関数を用意する。 もうすこしちゃんと言うと、

  • コメント部分に遭遇すると、空白文字を返す
  • 改行文字に遭遇すると、空白文字を返す
  • その他の文字に遭遇すると、そのまま1文字返す

という関数を作る。

これを src/lexer.cのget_next_char関数 で定義した。

次のトークンを取得

mincコードの文字列を受け取り、「次のトークン」を返す関数を作る。 その際に、さっき作ったget_next_char関数を呼び出すことでコメントをスキップできる。

これを src/lexer.cのget_next_token関数 で定義した。

ここで、C言語のFILE構造体は「ファイルの中身の文字列」と「ファイルの読込現在地」という2つの情報を持つことに注意してほしい。 get_next_token関数は、ファイルの現在地から先方へと伸びるトークンを返す関数になっている。

extern TOKEN get_next_token(FILE *file) {
  TOKEN ret = initialize_token(); // TOKEN構造体を準備。

  int count = 0;
  char ch, ch_more;
  while (true) {          // 無限ループでファイルを1文字ずつ読み込む
    ch = get_next_char(file);

    // 空白文字を読み飛ばす
    if (isspace(ch)) {
      while (true) {
        ch = get_next_char(file);
        if (!isspace(ch)) break;
      }
    }

    if (ch == EOF) break; // ファイルの終端ならループを抜ける

    if      (ch == '+' || ch == '-') {
      add_char_to_token_str(&ret, &count, ch); // ret -> str[*count] = ch する関数
      ret.kind = TERM_OPERATOR;
      break;
    }

    else if (ch == '*' || ch == '/' || ch == '%') {
      add_char_to_token_str(&ret, &count, ch);
      ret.kind = FACTOR_OPERATOR;
      break;
    }
// 略
  }
  ret.str[count] = '\0';
  return ret;
}

全属性のパーサを貼るとえらいことになるので、 TERM_OPERATORFACTOR_OPERATOR の部分だけ抜粋した。

複雑な属性をパースするには文字列処理を工夫する必要がある。 BNFとにらめっこしながら頑張って作ろう。

トークンの配列を取得

前節では、mincソースコードの文字列を入力し、トークンを1つ出力するget_next_token関数を作った。 これをループで回せば、ソースコードトークンの配列が得られる。

このあたりの処理は main関数の最初の方 で行っている。

FILE *file;
file = fopen(argv[1], "r");

// 全トークンの数を数える。内部でget_next_tokenを回している
const int max_token_num = count_token_num(file);

// 全トークンの配列を作る
TOKEN *token;
token = (TOKEN *)malloc( sizeof(TOKEN)*max_token_num );
for (int i=0; i<max_token_num; i++) token[i] = get_next_token(file);

fclose(file);
  • まずトークンの数を数える。これはget_next_token関数を使えば簡単だ。
  • 次にmallocトークンの配列領域を確保した後、全トークンの配列を読み込む。これもget_next_tokenを使えば簡単に実現できる。

どうでもいい話

今回はBNFの定義に始まり、人力で字句解析し、さらに字句解析プログラムを概要をざっくりと説明した。

今日のところは肩慣らし。明日からの構文解析が本番。 そこでは、今日作ったget_next_tokenの超絶複雑版を作る必要がある。 心してかかろう。