前々からOSとかコンパイラを作ってみたいとは思っていたのですが，なかなか作る機会などなく，そうこうしているうちに時が経ち...
今回はたまたまLTをする機会があり，何話そうかな〜と思っていたところ，コンパイラ作れば，LTのネタにもなるし，コンパイラも作れるし，一石二鳥やん，ということでyacc/lexを使って作ってみることにしました．

なんとなくコンパイラ作ってみたいと思っている人は意外といると思いますし，もしそういう人の一助になればありがたいですねぇ．
また，強い人には是非アドバイス等いただけると嬉しいです...

コンパイラとは

ソースコードを中間コードや機械語に変換するプログラムのこと．

一般的には，
1. 字句解析
2. 構文解析
3. 最適化
4. コード生成
という感じの流れらしいですね．

字句解析器

さて，字句解析は，lexで行なっていきます．
lexというのは，字句解析をして，c言語のコードを吐き出すためのシステムです．
とりあえず，lexについてこことここで軽くお勉強しました．
ざっくりまとめておくと，lexでは（入力した）文字が何なのかを逐一判別し，その結果を適宜yaccに送る，というような使い方をするようです．
もちろん字句解析のみをしたいのであれば，yaccなしでlexのみで使うこともできます．

構文解析器

構文解析はyaccで行います．
yaccについてはここでお勉強しました．
yaccでは，lexで書いたプログラムが吐き出してきたトークンを拾ってそれがどういう意味を持つのか解釈します．

実装

電卓を作ってみよう等を参考にしつつ，まずは電卓JCalc(ただの電卓なので，Just a Calculatorの略ということで)を実装することにしました．
電卓に必要な機能としては，数字を認識すること，四則演算を行うこと，結果を出力すること，くらいですかね？あとは何行目かわかるようにもしておきましょう．

lexで実装すること

演算子，数字，文字，改行，空白の識別
終了コマンドの識別（今回は'quit'と打ったら終わるようにします．）

%% からが規則部です．
<INTIAL> ではどの文字が来たらどのトークンを返すか指定しています．
<COMMENT> では，BEGIN COMMENT　が呼ばれた後の挙動を表しています．

<COMMENT>\n|\r|\r\n BEGIN INITIAL;
<COMMENT>.      ;

のように書くことで，改行=>INTIALの規則に戻る，その他どの文字が来てもスルーする，という感じになります．

JCalc.l

%{
    #include <stdio.h>
    #include <string.h>
    #include "y.tab.h"
    int line=1;
%}

%start COMMENT
%%
<INITIAL>"quit" exit(0);
<INITIAL>"how_many_line" {fprintf(stderr, "%d lines are read.\n", line);return HOW_MANY_LINE;};
<INITIAL>"("        return LP;
<INITIAL>")"        return RP;
<INITIAL>"+"        return ADD;
<INITIAL>"-"        return SUB;
<INITIAL>"*"        return MUL;
<INITIAL>"/"        return DIV;
<INITIAL>"%"        return MOD;
<INITIAL>[1-9][0-9]* {sscanf(yytext,"%d",&yylval);return INT_LITERAL;};
<INITIAL>[A-Za-z_][A-Za-z_0-9]* {sscanf(yytext,"%s",&yylval);return STR;};
<INITIAL>[0-9]*\.[0-9]* ;
<INITIAL>[ \t] ;
<INITIAL>[\n\r]|\r\n {line++;return NL;};
<INITIAL>^# BEGIN COMMENT;
<INITIAL>. fprintf(stderr, "Please input 'quit' to finish the program.\n");
<COMMENT>\n|\r|\r\n BEGIN INITIAL;
<COMMENT>.      ;
%%

yaccで実装すること

識別された記号たちを解釈して，四則演算（括弧付きの優先順位も含む）を行う

として，やっていきました．
%で始まる部分は宣言部で，どういうトークンを意味のあるものとして認識するか，などということを指定します．また，%{ %}で囲めばc言語を記述できます．
%%以降は規則部です．ここに直接構文規則を書いていきます．
構文規則は下から参照されて行くことに注意して，( )の位置や乗除の位置を記述しています．
ちなみに( )はそれぞれLP (Left Parenthesis), RP (Right Parenthesis)と名付けています．また，ここでは電卓の途中で今何行目か知りたくなったときのためにHOW_MANY_LINEトークンを定義しています．
ちなみに$nでn番目の項が渡す値を定義でき，$$はそのトークンが次に渡す値です．

JCalc.y

%{
    #include<stdio.h>
%}
%token NL
%token HOW_MANY_LINE
%token INT_LITERAL
%token STR
%token LP RP ADD SUB MUL DIV MOD

%%

list
    : /* Empty */
    | list expr NL {printf("%d\n", $2);}
    | list string NL 
    {
        fprintf(stderr, "Please input 'quit' to finish the program.\n");
    }
    | list NL
    | list HOW_MANY_LINE NL

    ;
string
    : STR
    | string STR
    | ADD
    | SUB
    | MUL
    | DIV
    | MOD
    ;
expr
    : term
    | expr ADD expr {$$ = $1 + $3;}
    | expr SUB term {$$ = $1 - $3;}
    | expr MOD term {$$ = $1 % $3;}
    | expr expr {$$ = $2;}
    ;
term
    : factor
    | term MUL term {$$ = $1 * $3;}
    | term DIV term {$$ = $1 / $3;}
    ;
factor
    : INT_LITERAL
    | LP expr RP {$$ = $2;}
    ;

%%

#include "lex.yy.c"

これで JCalcは完成です．

あとはコンパイルの仕方ですが，

yacc -d JCalc.y
lex JCalc.l
cc y.tab.c -ly -ll -o JCalc

とすればできるはずです．y.tab.cはyaccをコンパイルしたときに自動で生成されます．
ソースコードはGitHubに置いてあるので，ご参考まで．

終わりに

今回はyacc/lexを使って，電卓を実装してみました．
なんとなくコンパイラづくりのイメージがつかめて来た気がするので，次回は変数を使用できるようにしたり，簡単な関数を宣言できるようにしようかな〜と思っています．
先人たちがネット上に色々と参考になるものを落としてくれていて非常にありがたいなあとしみじみ感じた次第です．

追記

そういえば，今回のものはとりあえず整数型のみで計算できるようにしていますので，ご注意を．

Reference

お世話になったページたち．

yacc/lexについて

Yacc/Lexの使い方（簡略版）
Flexとのインターフェイス
 電卓を作ってみよう
 プログラミング言語を作る/yaccとlex
構文解析器のC言語インタフェース

その他

Rubyソースコード完全解説

電卓作ってみた