19日目: [コンパイラ] 字句解析
この記事はひとりでCPUとエミュレータとコンパイラを作る Advent Calendar 2017の19日目の記事です。
今日は字句解析をやる。まず昨日のサンプルコードを人力で字句解析し、コツを掴んだところで実装を説明する。
字句解析とは
昨日のサンプルコード
// C言語風コード int main () { int a ; a = 3 ; return 0 ; }
コードに出現する各単語に対し、トークン属性を付与することを字句解析というのだった。
ここで(TYPE_KEYWORD, "int")のようなペアをトークンと呼び、緑字のTYPE_KEYWORDをトークン属性と呼ぶ。
属性の定義は、BNFで与えるのだった。
BNF (バッカス-ナウア記法)
BNFとは「文字列に属性を与える」ために「属性のマッチ条件を正規表現で定義」したものだった。 そこでは「定義済みの属性」を他の属性の定義式中に埋め込むことができた。いわば正規表現の代入だ。
昨日のBNFは簡易版だったので、ここに正式版のBNFを貼っておく。
パイプ記号|
は 正規表現の or を表している。(hoge|piyo)*
も正規表現と同じ。
また画像中にも書いたが * int や if という文字列の属性は、IDENTIFYではなくTYPE_KEYWORDやIF_KEYWORDとする * CHAR_ALPHABETとCHAR_NUMBERはIDENTIFYとNUMBERを定義するために導入した一時的属性なので、最終結果には残らない
という二点に気をつけよう。
minc言語誕生
ところで、ここで定義した言語はC言語のサブセットになっている。
いや、サブセットというのもおこがましい。
なんせ型はint
しかないし、配列、ポインタ、構造体等は一切使えない。
#include
も#define
もないし、break
もswitch
もない。
しかし、しかしだ!!
変数が使えて、整数が計算できて、関数を定義して呼び出すことも可能な言語になっている。 しかも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"
が目に入るだろう。左辺と右辺を := で繋いだ。
次はint
とmain
の間だが、空白文字を見つけたら、そこまでの単語で字句解析を行い、空白文字はスキップする。
つまりint
とmain
は別のトークンということだ。
次はmain
が目に入る。
一見すると、BNFの中にmain
は見当たらない。
しかしm
やa
といった単体の文字にはCHAR_ALPHABETという属性が定義されている。
従ってmain
はCHAR_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_OPERATOR と FACTOR_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
の超絶複雑版を作る必要がある。
心してかかろう。