きつねさんでもわかる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
;
ここで始めてその項の評価が終わります。（ツリーの葉に到達する。）
詳しく知りたい方は是非本を読んでみることをおすすめしますが、今回の電卓の全体像を載せておきます。

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

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

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

さいごに

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