きつねさんでもわかるLLVM - kosen14s読書会

はじめに

この投稿はkosen14s読書会用の記事です。
Kosen14s読書会
kosen14s読書会では、何人かのメンバーが自由なジャンルの本を紹介します。前回はPractical Malware Analysisについて投稿しました。

きつねさんでもわかるLLVM

本記事で紹介する本は、柏木 餅子さんと風薬さんの著書「きつねさんでもわかるLLVM ~コンパイラを自作するためのガイドブック~」です。
きつねさんでもわかるLLVM ~コンパイラを自作するためのガイドブック~
表紙とタイトルを見て、「これならコンパイラが作れそう！」と思った時期もありました......
というのも、やはり内容は難しかったです。そして私はまだ完全に理解してません。そのため今回は、電卓を例にとってプログラミング言語がどのように表現されるかについて、かいつまんで説明します。ただ、あまり細かいところを理解していないのでところどころ説明に間違いがあるかもしれません。

電卓を作ってみる

こんな記事に辿り着く人はコンパイラを使ったことがある人がほとんどだと思います。コンパイラは入力されたソースコードを解析し、中間言語を生成したり実行ファイルを生成したり、とにかく人間が読めるコードを機械が解釈できるコードに変換するツールです。本書で使用するLLVMでは、ソースコードをレキシカルアナライザと呼ばれるプロセッサでトークンと呼ばれる意味を持った単語に分割されます。例えば次のような入力ソースコードがあったとします。
「4 / 3 * 3.14 * 10 ** 2」
レキシカルアナライザはこれを次のように分割します。
「4」「/」「*」「3.14」「*」「10」「**」「2」
そして、lex/yaccという言語(?)を使うと自分がどんな言語を作りたいかを規定するだけでこのトークン分割を自動でやってくれるのです。電卓程度ならこれを規定するのが非常に簡単です。例えば足し算「+」を定義したければ次のように書きます。
"+" {
    return OPERATOR_ADD;
}



OPERATOR_ADDなども別ファイルで自分で定義するので、四則演算だけでなく、複雑な演算やオリジナルの演算子を簡単に定義できてしまうのです。また、演算子以外にも「整数とは何か」や「小数とは何か」も定義する必要があります。例えば小数は次のように定義されます。
[0-9] *\.[0-9]* {
    double temp_box;
    sscanf(yytext, "%lf", &temp_box);
    yylval.double_value = temp_box;
    return DOUBLE_LITERAL;
}



先程の足し算より長くなりましたが、これは計算時に具体的な数字を参照するためにyytextなどを設定する必要があるからです。詳しくはぜひ本を読んでみてください。


このように「足し算とは」「整数とは」「文字列とは」「変数とは」「関数とは」などなど、トークンについて全て定義します。次にこれらトークンを解釈するのがパーサと呼ばれるプロセッサです。例えば「1+2*3」を計算するとき、人間は掛け算を優先します。また、「*は乗算である」だけでなく、「乗算とは何か」という具体的な処理を解釈するのがこのパーサyaccです。さらに、パーサはコンパイルエラーを出す必要があります。例えば「1+2*3*」という計算式はエラーとなります。ではエラーでない乗算とは何かというと、「A*B」のように「*」の両側に数字が付いていることです。数字というより、最終的に数字になる式がAやBにあたります。例えば「(1+2)*(3*4+1)」の場合、(1+2)と(3*4+1)をそれぞれA,Bとして認識させる必要があります。そういった表現の定義はBNFという記法で書かれます。先の例でAやBをtermとして定義します。（もちろんこれも自分で定義するのでtermじゃなくてhogeとかでもいいです。）
term
: primary_expression
| term OPERATOR_MUL primary_expression
{
    $$ = $1 * $3;
}
| term OPERATOR_DIV primary_expression
{
    $$ = $1 / $3;
}
;
一行目は「termとは何か」の定義開始です。二行目は「termとはprimary_expressionである」という意味です。ちなみにprimary_expressionは後で定義する「値」を表すものです。ここまでで「式termとは値primary_expressionである」と定義されました。三行目は「もしくはterm * primary_expressionである」という意味です。OPERATOR_MULは前にレキシカルアナライザのところで定義しました。ここで注目したいのが、termの定義にtermが入っているということです。これだとずっと自分自身を参照しそうですが、一行目の「termとはprimary_expressionである」があることにより、いつかはprimary_expressionに移るのです。「term * primary_expression」を宣言しましたが、これが返す具体的な値を各必要があります。これが四行目から六行目の括弧内にある「$$ = $1 * $3;」で、「返す値 = term * primary_expression」という意味です。$1とか$3は今解析しているトークンから何番目のトークンであるかを示します。同様にして除算も定義しました。加算や減算は優先順位が低いのでexpressionとして定義します。（最後に全体のコードを示します。）
さて、 「termとはprimary_expressionである」と定義したので、今度はprimary_expressionも定義します。これはただの値（今回は小数のみ）なので、次のようにかけます。
primary_expression
: DOUBLE_LITERAL
;
ここで始めてその項の評価が終わります。（ツリーの葉に到達する。）
詳しく知りたい方は是非本を読んでみることをおすすめしますが、今回の電卓の全体像を載せておきます。

	/*
	%{ ...%}で囲まれた行はC言語そのままとして解釈されます。
	したがって、%{ ... %}内は解析時にスキップされ、
	コンパイル時にコンパイラが読むだけです。
	*/
	%{
	/* stdio.hはキーボードからの入力に必要です。 */
	#include <stdio.h>
	/* "y.tab.h"はyaccコマンド実行時に出力されます。 */
	#include "y.tab.h"
	/* 必要な関数だけど使わないので空 */
	int yywrap(void) { return 1; }
	%}
	/*
	%% ... %%で囲まれた行はlexに解析されます。
	ここには自分の作りたいプログラム言語の規則を書きます。
	*/
	%%
	/**** 次のようにyaccでは「演算子」を定義します。
	「足し算」とは...
	"+" : "+"である
	詳細な計算方法はcalc.yで定義します。
	*/
	"+" {
	/* ここには上の定義のもと「足し算」と判断された場合の処理を書きます */
	return OPERATOR_ADD;
	}
	"-" {
	return OPERATOR_SUB;
	}
	/* returnだけの場合、次のように{}を省略できます。 */
	"*" return OPERATOR_MUL;
	"/" return OPERATOR_DIV;
	"\n" return EOL;
	/**** 次のようにyaccでは「整数とは」を定義する必要があります。
	整数とは...
	[1~9] --> 文字の1~9が最初にある
	[0-9]* --> 文字の0~9が続く('*'が繰り返しを意味する)
	*/
	[1-9][0-9]* {
	/*** ここには上の定義のもと「整数」と判断された場合の処理を書きます。 */
	double temp_box;
	/* 今回は実数しか使わないので実数として読み込みます */
	/* 現在の文字(yytext)を整数(%d)としてtemp_boxに入力します。 */
	sscanf(yytext, "%lf", &temp_box);
	/* 現在のint_valueは上で取得した整数です。 */
	yylval.double_value = temp_box;
	return DOUBLE_LITERAL;
	}
	/* 上の定義だと0が整数にならないので定義します。 */
	"0" {
	yylval.double_value = 0.0; // "0"は0.0
	return DOUBLE_LITERAL;
	}
	/**** 実数とは...
	[0-9]* --> 文字の0~9が続く
	\. --> 文字の"."がある('.'は正規表現で意味を持つので'\.'と書きます)
	[0-9]* --> 文字の0~9が続く
	*/
	[0-9]*\.[0-9]* {
	/*** ここには上の定義のもと「実数」と判断された場合の処理を書きます。 */
	double temp_box;
	/* 現在の文字(yytext)を実数(%lf)としてtemp_boxに入力します。 */
	sscanf(yytext, "%lf", &temp_box);
	/* 現在のdouble_valueは上で取得した実数です。 */
	yylval.double_value = temp_box;
	return DOUBLE_LITERAL;
	}
	/*
	DOUBLE_LITERALやOPERATOR_ADDなどの定数は
	calc.yの方で定義するので、それと同じ名前であれば
	何でも構いません。
	yytextやyylvalもcalc.yの方で定義します。
	yylval内のdouble_valueなどもcalc.yで定義します。
	*/
	%%

view raw calc.l hosted with ❤ by GitHub

	/*
	%{ ...%}で囲まれた行はC言語そのままとして解釈されます。
	したがって、%{ ... %}内は解析時にスキップされ、
	コンパイル時にコンパイラが読むだけです。
	*/
	%{
	#include <stdio.h>
	#include <stdlib.h>
	%}
	// 現在解析中の具体的な値が入ります
	%union {
	// プログラミング言語などでは型がたくさんあるので
	// 構造体などをここに入れますが、
	// 今回は実数しか使わないようにしました。
	double double_value;
	}
	%token <int_value> INT_LITERAL // 例えばcalc.lで整数と判定されたら、
	%token <double_value> DOUBLE_LITERAL // INT_LITERALを受け取ることになります。
	%token OPERATOR_ADD // 演算子にも名前を付けておきます。
	OPERATOR_SUB // これらもcalc.lで使う用なので、
	OPERATOR_MUL // ここでは宣言だけをしておきます。
	OPERATOR_DIV
	EOL // 行の終端すら定義します
	//
	// %type <int_value>
	%type <double_value> expression term primary_expression
	/*
	%% ... %%で囲まれた行はlexに解析されます。
	ここには自分の作りたいプログラム言語の規則を書きます。
	*/
	%%
	//// 次のようにyaccでは「ソースコードとは」すら定義する必要があります
	// 「ソースコード」とは...
	// line --> 1行
	// | --> または
	// source_code line --> 「ソースコード」「1行」で構成される
	source_code
	: line
	| source_code line
	;
	//// 次のようにyaccでは「行とは」すら定義する必要があります
	// 「行」とは...
	// expression --> 何かしらの式がある
	// EOL --> 改行文字がある
	line
	: expression EOL
	{
	//// ここには「行である」であると判定された際の処理を書きます。
	// 行判定されたら解析結果($1)を出力します。
	printf(">> %lf\n", $1);
	}
	;
	//// 上で使った「何かしらの式」(expression)を定義します
	// 「何かしらの式」(expression)とは...
	// term --> 項である
	// | --> または
	// expression OPERATOR_ADD term --> 「何かしらの式」 + 項 である
	// | --> または
	// expression OPERATOR_SUB term --> 「何かしらの式」 - 項 である
	expression
	: term
	| expression OPERATOR_ADD term
	{
	//// ここには入力文字が「expression + term」であると判定された際の処理を書きます。
	// $1 : expression
	// $2 : OPERATOR_ADD
	// $3 : term
	// 結果 = expression + term
	$$ = $1 + $3;
	}
	| expression OPERATOR_SUB term
	{
	$$ = $1 - $3;
	}
	;
	//// もちろん「項」も定義します。
	// 「項」(term)とは...
	// primary_expression --> 「1つの項」である
	// | --> または
	// term OPERATOR_MUL primary_expression --> 「項」 * 「1つの項」である
	// | --> または
	// term OPERATOR_DIV primary_expression --> 「項」 / 「1つの項」である
	term
	: primary_expression
	| term OPERATOR_MUL primary_expression
	{
	$$ = $1 * $3;
	}
	| term OPERATOR_DIV primary_expression
	{
	$$ = $1 / $3;
	}
	;
	// 「1つの項」(primary_expression)とは...
	// DOUBLE_LITERAL --> 実数である
	primary_expression
	: DOUBLE_LITERAL
	;
	%%
	/*
	ここにコンパイルエラー発生時の処理を書きます。
	*/
	int yyerror(char const* str)
	{
	extern char *yytext;
	fprintf(stderr, "Error near %s\n", yytext);
	return 0;
	}
	/*
	ここにコンパイラを書きます。
	今回は電卓なので、標準入力から文字を受け取って計算結果を出力します。
	*/
	int main(void)
	{
	// yaccが勝手に解析してくれる関数
	extern int yyparse(void);
	// コンパイルすべきファイル
	extern FILE *yyin;
	// 今回はファイルではなくstdinからの入力
	yyin = stdin;
	if (yyparse()) {
	// エラー発生
	fprintf(stderr, "ERROR!\n");
	exit(1);
	}
	return 0;
	}

view raw calc.y hosted with ❤ by GitHub

	# calc.binを出力するコマンド
	calc.bin: y.tab.c lex.yy.c # 下のコマンドに必要なファイル
	cc -o calc.bin y.tab.c lex.yy.c
	# y.tab.cを出力するコマンド
	y.tab.c: calc.y # 下のコマンドに必要なファイル
	yacc -dv calc.y
	# lex.yy.cを出力するコマンド
	lex.yy.c: calc.l # 下のコマンドに必要なファイル
	lex calc.l
	# ゴミを削除
	clean:
	rm y.output y.tab.c y.tab.h
	rm lex.yy.c

view raw Makefile hosted with ❤ by GitHub

実行するとこんな感じで計算できます。

ついでに括弧付き計算や累乗にも対応したバージョンです。

	%{
	#include <stdio.h>
	#include "y.tab.h"
	int yywrap(void) { return 1; }
	%}
	%%
	"+" return OPERATOR_ADD;
	"-" return OPERATOR_SUB;
	"*" return OPERATOR_MUL;
	"/" return OPERATOR_DIV;
	"^" return OPERATOR_POW;
	[1-9][0-9]* {
	double temp_box;
	sscanf(yytext, "%lf", &temp_box);
	yylval.double_value = temp_box;
	return DOUBLE_LITERAL;
	}
	"0" {
	yylval.double_value = 0.0;
	return DOUBLE_LITERAL;
	}
	[0-9]*\.[0-9]* {
	double temp_box;
	sscanf(yytext, "%lf", &temp_box);
	yylval.double_value = temp_box;
	return DOUBLE_LITERAL;
	}
	[ \t] ; // [追加]タブや空白は無視
	"\n" return EOL;
	%%

view raw calc.l hosted with ❤ by GitHub

	%{
	#include <stdio.h>
	#include <stdlib.h>
	%}
	%union {
	double double_value;
	}
	%token <int_value> INT_LITERAL
	%token <double_value> DOUBLE_LITERAL
	%token OPERATOR_ADD
	OPERATOR_SUB
	OPERATOR_MUL
	OPERATOR_DIV
	OPERATOR_POW // [追加]累乗
	EOL
	%type <double_value> expression
	expression_addsub
	expression_muldiv
	expression_power
	expression_term
	%%
	source_code
	: line
	| source_code line
	;
	line
	: expression EOL
	{
	printf(">> %lf\n", $1);
	}
	;
	/* [変更]
	expressionやらtermやらややこしいので、
	expression_演算子
	に変更。
	優先順位が高いほどexpression_termに近く、
	優先順位が同じものは同じexpressionに記述する。
	*/
	expression
	: expression_addsub
	;
	expression_addsub
	: expression_muldiv
	| expression_addsub OPERATOR_ADD expression_muldiv
	{
	$$ = $1 + $3;
	}
	| expression_addsub OPERATOR_SUB expression_muldiv
	{
	$$ = $1 - $3;
	}
	;
	expression_muldiv
	: expression_power
	| expression_muldiv OPERATOR_MUL expression_power
	{
	$$ = $1 * $3;
	}
	| expression_muldiv OPERATOR_DIV expression_power
	{
	$$ = $1 / $3;
	}
	;
	expression_power
	: expression_term
	| expression_power OPERATOR_POW expression_term
	{
	int i;
	double ret;
	// 累乗とは
	for(i = 0, ret = 1.0; i < (int)$3; i++) {
	ret *= $1;
	}
	$$ = ret;
	}
	;
	expression_term
	: DOUBLE_LITERAL
	;
	%%
	int yyerror(char const* str)
	{
	extern char *yytext;
	fprintf(stderr, "Error near %s\n", yytext);
	return 0;
	}
	int main(void)
	{
	// yaccが勝手に解析してくれる関数
	extern int yyparse(void);
	// コンパイルすべきファイル
	extern FILE *yyin;
	// 今回はファイルではなくstdinからの入力
	yyin = stdin;
	if (yyparse()) {
	// エラー発生
	fprintf(stderr, "ERROR!\n");
	exit(1);
	}
	return 0;
	}

view raw calc.y hosted with ❤ by GitHub

実行するとこんな感じで計算できます。

さいごに

数年前にもこの本を手に取ったのですが、当時は何一つ分からずに放置していました。しばらくして読んでみると内容が全然違うとうに思えて面白いですね。まだまともな変数も実装できないですが、ちょっとずつ勉強して、いつかまともな言語を作れたらと思います。