言語実装 Advent Calendar 2015の22日目として書かれました。
ErlangでBEAMで動くコンパイラする作成を説明します。
ulangというサンプルプログラムを作ったのでこれを元に説明します。
https://github.com/oskimura/ulang.git
主な流れとしては字句解析器、構文解析器を行って中間表現に変換しcompileモジュールを使ってBEAMで実行可能なバイナリを作成するという流れです。
今回はulang.xrlで字句解析を行い、ulang_yecc.yrlで構文解析及び中間表現の出力、compiler.erlでバイナリ出力するようにつくりました。
字句解析器
Erlangにはleexという字句解析器があります。
http://erlang.org/doc/man/leex.html
類似のツールを使ったことがある人なら分かるでしょうけど、Definitions、Rules、Erlang codeに分かれています。
Definitionsはruleで仕様される正規表現の定義を行います。
今回はこの箇所に該当します。
INT = [0-9]+
ATOM = :[a-z_]+
VAR = [a-z0-9_]+
CHAR = [a-z0-9_]
WHITESPACE = [\s\t\n\r]
Rulesは生成するトークンを記述します。
Erlang codeはRulesで仕様されるErlangのコードを記述します。
今回はこの部分に該当します。
module : {token,{module,TokenLine}}.
のように
マッチする字句 : {生成するトークン}
という風に書きます。
{token,{いろいろ,行数}}.
という風になっているようです。
Definitionsで定義された定義を仕様するには
という風にINTなら{INT}と{}で囲む必要があるようです。
今回の場合はここの
to_atom関数に該当します。
この様にRulesで使用することができます。
今回はこのように作成しました
https://github.com/oskimura/ulang/blob/master/ulang/src/ulang.xrl
構文解析器
同じようにErlangにはyeccという構文解析器があります。
http://erlang.org/doc/man/yecc.html
yeccはErlangのコンパイラコンパイラでBNFで文法を記述できます。
ちなみにErlangのパーサもyeccによって書かれています。
yeccはNonterminals、Terminals、規則部、Erlang codeに別れています。
Nonterminalsは非終端記号の集合の宣言を行います。
規則部はRootSymbolを開始記号とする簡約規則を記述します。RootSymbolがないとエラーになります。
https://github.com/oskimura/ulang/blob/master/ulang/src/ulang_yecc.yrl#L6
規則部は
https://github.com/oskimura/ulang/blob/master/ulang/src/ulang_yecc.yrl#L9-L13
program ->
module_exp: [ '$1' ].
program ->
module_exp exps: [ '$1' | '$2' ].
のように
非終端記号 -> ルール : アクション
という風にかきます。'$1'は引数です。基本的にはlex/flexと一緒です。非終端記号に複数のルールがある場合は上記のように複数書きます。
今回作成した規則部
今回作成するyeccはアクションに作成する中間表現を記述します。中間表現の詳細は後述します。
Erlang codeは
規則部で使用するErlangコードを記述します。leexと同じです。
https://github.com/oskimura/ulang/blob/master/ulang/src/ulang_yecc.yrl#L163-L174
今回作成したたyeccの全体はこちらです。
https://github.com/oskimura/ulang/blob/master/ulang/src/ulang_yecc.yrl
中間表現
erl_syntaxというドキュメントに中間表現のシンタックスツリーを組み立てるためのAPI書いてありますが、
http://erlang.org/doc/man/erl_syntax.html
今回コレは使用せずに自分で組み立てる事にします。
このモジュールでErlangプログラムファイルの中間表現を取得できます。
今回はコレを使って中間表現を解析して中間表現を組み立てます。
compileモジュール
生成された中間表現をコンパイルしてバイナリを出力するのはcompileモジュールでおこないます。
http://www.erlang.org/doc/man/compile.html
今回はnoenv_forms関数を使用して次のように書きました。
compile:noenv_forms(Spec,[return]) of
{ok,Module,Binary,Wornings} ->
end
compile:noenv_formsの第一引数はバイナリ変換したい中間表現、第二引数はオプションです。
コンパイルが成功した場合は{ok,Module,Binary,Wornings}というタプルが返されます。
Moduleはモジュール名、Binaryは変換バイナリ、Worningはコンパイル時の警告です。
中間表現について
中間表現は基本的にタプルで表現され、{タグ名,ソース行数,引数1,引数2,...}といった形になっています。
このタグのリストが中間表現です。compileモジュールの関数に渡すことでバイナリへとコンパイルされます。
サンプルプログラムを例に説明します。
Eralangの文法にかんしてはココを参考にしてください。
では中間表現の説明をしていきます。
module宣言
-module(sample).
というモジュール宣言は
{attribute,1,module,sample},
となります
module := {attribute,Line,module,ModuleName},
Lineは行数、ModuleNameはモジュール名となります。
attributeというタグは後述するexportなどmoduleの箇所を変えて使われます。
ModuleNameはモジュールの名前です今回はsampleです。
export宣言
-export([func1/0]).
というexport宣言は
{attribute,2,export,[{func1,0}]},
と変換されます。
export := {attribute,Line,export,[{f1,Arg},...]},
exportの後に関数のリストが必要です。{変数名,関数の数}のリストという形で表現されます。
関数宣言
func1 () ->
ok.
という関数宣言は
{function,3,func1,0,[{clause,3,[],[],[{atom,4,ok}]}]}
と変換されます。
function := {function, Line, FunctionName, ArgNumber [Clause1,...]}
Lineは行数、FunctionNameは関数名、ArgNumberは引数の数、Clauseのリストは関数の本体です。
なぜリストなのかというと、次のような場合
func2([]) ->
ok;
func2(X) ->
ok.
引数のマッチングによって複数の本体があるからです。
ちなみにこのClauseはcase hoge of～形式のパタンマッチの中間表現と共通の形式です。
clause := {clause,Line,[Args],[TestFuncs],[Bodys]}
Lineは行数、Argsのリストは仮引数、TestFuncのリストはガード節、Bodysのリストは関数本体です。
ガード節は
func3(X) when is_atom(X) ->
X.
のwhen以降で引数のチェックを行う箇所です。
上記のような関数の場合
{function,10,func3,1,[{clause,10,[{var,10,'X'}],[[{call,10,{atom,10,is_atom},[{var,10,'X'}]}]],[{var,11,'X'}]}]}
と変換されます。
文字列
string_fun() ->
"abc".
は
{function,15,string_fun,0,[{clause,15,[],[],[{string,16,"abc"}]}]}
と変換されます。
{string,Line,Str}
Strは文字列です
文字
char_fun() ->
$a.
は
{function,18,char_fun,0,[{clause,18,[],[],[{char,19,97}]}]}
と変換されます。
{char,Line,Char}
Charは文字のASCIIコードです
整数
integer_fun() ->
1.
は
{function,21,integer_fun,0,[{clause,21,[],[],[{integer,22,1}]}]
と変換されます。
{integer,Line,Num}
Numは数字です
演算子
op_fun() ->
1+1.
は
{function,24,op_fun,0,[{clause,24,[],[],[{op,25,'+',{integer,25,1},{integer,25,1}}]}]}
と変換されます。
{op,Line, Op,LVal,RVal}
Opは演算子です。LValとRValはそれぞれ演算子の左辺と右辺です。
関数呼び出し
callで呼ぶことができる関数は同じモジュール内の関数に限られる。他のモジュールで宣言してある関数は 後述するremote callで呼び出す必要があります。
call_fun() ->
func1().
という関数は
{function,13,call_fun,0,[{clause,13,[],[],[{call,14,{atom,14,func1},[]}]}]},
と変換されます。
call := {call,Line,{atom,Line,FunctionName},Args},
var := {var,Line,VarNme}
Lineは行数、FunctionNameは関数名、Argsは引数のリストです。
関数呼び出し
他のモジュールで宣言された関数はremote callで呼び出す必要があります。
remote_call_fun() ->
io:format("test").
という関数は
{function,16,remote_call_fun,0,[{clause,16,[],[],[{call,17,{remote,17,{atom,17,io},{atom,17,format}},[{string,17,"test"}]}]}]}
と変換されます。
remotecall :={call,Line,{remote,Line,{atom,Line,ModuleName},{atom,Line,FunctionName}},Args}
Args := {var,Line,VarNme}
remoteが入る以外はcallと同じです。
パタンマッチ
パタンマッチです
match_fun(X) ->
case X of
a ->
a;
b ->
b
という関数が
{function,19,match_fun,1,[{clause,19,[{var,19,'X'}],[],[{case,20,{var,20,'X'},[{clause,21,[{atom,21,a}],[],[{atom,22,a}]},{clause,23,[{atom,23,b}],[],[{atom,24,b}]}]}]}]}
と変換されます。
case := {'case', Line, MatchExp, [Clause1,...]}
matchexp := {clause, Line, Match, Test, Bodys}
MatchExpは上のソースでいうcaseとofの間の式にあたりますClauseの
代入
単一代入です。
bind_fun() ->
X = 1.
は
{function,29,bind_fun,0,[{clause,29,[],[],[{match,30,{var,30,'X'},{integer,30,1}}]}]}
と変換されます。
{match,Line,Var,Val}
VarにValを代入します。
{var,Line,Var}
は変数です。Varは変数名です。
{integer,Line,Val}
は整数です。Valは設定する整数です。
リスト
list_fun() ->
[1,2,3,4].
という関数は
{function,27,list_fun,0,[{clause,27,[],[],[{cons,28,{integer,28,1},{cons,28,{integer,28,2},{cons,28,{integer,28,3},{cons,28,{integer,28,4},{nil,28}}}}}]}]}
と変換されます。
{cons, Line, {Elent1,{Element2, Line,... {nil,Line}}
Element1,Element2はリストの要素です。consは入れ子構造になってます。
実演 fibをコンパイルしてErlngから呼び出してみましょう
最後に
上記の情報があればBEAMで動く処理系が作れるとおもいます。中間表現の他の文法等についてはいろいろ試してみよう