- BNFが読める
- Yacc/Lex系ツールを使ったことがある。
- Erlangがすこし書ける
- Erlangのビルドフロー
- ツールを使った処理系作成方法 https://github.com/oskimura/ulang を例にお話します
説明不要
Ruby like
Lisp like
ErlangのVMはBEAMと呼ばれている バイナリコンパイルしたものをBEAM上で実行する バイナリコンパイルされたファイルはbeamと呼ばれている
- AST
- Core Erlang
- BEAM Binary(ASM)
という順番で生成されます
Erlangにおける中間表現とはASTをタプルで表現したもの
-module(fib).
factorial(0) -> 1;
factorial(N) -> N * factorial(N-1).
を変換します
[{attribute,1,module,fib},
{function,2,factorial,1,[{clause,2,[{integer,2,0}],[],[{integer,2,1}]},
{clause,3,[{var,3,'N'}],[],[{op,3,'*',{var,3,'N'},{call,3,{atom,3,factorial},[{op,3,'-',{var,3,'N'},{integer,3,1}}]}}]}]}]
- Erlangから複雑な構文を取り去って単純化
- High Performance Erlangというネイティブ作成モジュールの副産物
詳しくは https://www.it.uu.se/research/group/hipe/cerl/doc/core_erlang-1.0.3.pdf
'factorial'/1 =
%% Line 2
fun (_cor0) ->
case _cor0 of
<0> when 'true' ->
1
%% Line 3
<N> when 'true' ->
let <_cor1> =
call 'erlang':'-'
(N, 1)
in let <_cor2> =
apply 'factorial'/1
(_cor1)
in call 'erlang':'*'
(N, _cor2)
end
- BEAMに対応するアセンブリ形式にする
- アセンブリ形式からバイナリファイルを生成する
{function, module_info, 0, 2}.
{label,1}.
{line,[]}.
{func_info,{atom,fib},{atom,module_info},0}.
{label,2}.
{move,{atom,fib},{x,0}}.
{line,[]}.
{call_ext_only,1,{extfunc,erlang,get_module_info,1}}.
{function, module_info, 1, 4}.
{label,3}.
{line,[]}.
{func_info,{atom,fib},{atom,module_info},1}.
{label,4}.
{move,{x,0},{x,1}}.
{move,{atom,fib},{x,0}}.
{line,[]}.
{call_ext_only,2,{extfunc,erlang,get_module_info,2}}.
自作言語からbeamファイルを生成するには3つの方法が考えられる
- 自分でバイナリコードを生成する
- 中間表現まで作成してErlnagのコンパイラに任せる
- Core Erlangを作成してErlangのコンパイラに任せる
中間表現に置き換えてコンパイルする方法を採用
Erlangを使う前提で中間表現の解析さえできればこれが一番早いと思います leex、yeccで中間表現まで変換 中間表現をErlangでコンパイルする。
├── README.md
├── bin
├── ebin beamファイル
├── rebar.config rebarの設定
├── src
│ ├── compiler.erl コンパイラ本体
│ ├── ulang.app.src Erlangアプリケーションの設定
│ ├── ulang_lex.xrl 字句解析
│ └── ulang_yecc.yrl 構文解析
基本的にはOTP標準構成
Erlangの統合ビルドツール 今回はなにもしてない
{ tag, "v1.0.0" }.
Erlang VM用ににアプリケーションの設定する
{application, ulang,
[
{description, ""},
{vsn, "1"},
{registered, []},
{applications, [
kernel,
stdlib
]},
{mod, { compiler, []}},
{env, []}
]}.
compiler.erl より
compile(File) ->
call_with_read_file(File,
fun(Bin) ->
Lexed = lexer(binary_to_list(Bin)),
AST = parser(Lexed),
{Module,Binary,_} = compiler(AST),
save_beam(Module,Binary)
end).
字句解析 -> 構文解析 -> バイナリ出力 という順番で出力する
字句解析は次のようにモジュール:string()と言うふうにして使います
lexer(String) ->
case ulang_lex:string(String) of
{ok,Ret,_} ->
Ret;
{error,Reason,_} ->
erlang:error({"lex error",Reason});
_ ->
erlang:error("lex error")
end.
構文解析は次のように字句解析された結果をモジュール:parseとして使います
parser(LexedText) ->
case ulang_yecc:parse(LexedText) of
{ok,Spec} ->
Spec;
{error,Reason} ->
erlang:error({"parse error",Reason});
_ ->
erlang:error("parse error")
end.
構文解析後の中間表現はcompile:noenv_forms()を使ってバイナリを主力します
http://www.erlang.org/doc/man/compile.html
compiler(ParsedAst) ->
case compile:noenv_forms(ParsedAst,[return]) of
{ok,Module,Binary,Warnings} ->
{Module,Binary,Warnings};
error ->
erlang:error({"compile errord"});
{error,Error,Warning} ->
erlang:error({"compile error",Error,Warning})
end.
Erlangのタプルで表現されてる このタプルをコンパイルすることでバイナリファイルを取得できる。 Erlangのファイルを次のスクリプトに通すことでそのタプルを取得できる。
#!/usr/bin/env escript
%% -*- erlang -*-
%%! -smp enable -sname factorial -mnesia debug verbose
eval(File) ->
{ok, B} = file:read_file(File),
Forms = scan(erl_scan:tokens([],binary_to_list(B),1),[]),
F = fun(X) -> {ok,Y} = erl_parse:parse_form(X), Y end,
[F(X) || X <- Forms].
scan({done,{ok,T,N},S},Res) ->
scan(erl_scan:tokens([],S,N),[T|Res]);
scan(_,Res) ->
lists:reverse(Res).
main([File]) ->
erlang:display(eval(File)).
compile:noenv_forms(Spec,[return]) of
{ok,Module,Binary,Wornings} ->
end
Erlangはleexという字句解析器をつかいます。(http://erlang.org/doc/man/leex.html) 使い方はlexとほぼ同じです。
- Definitions
- Rules
- Erlang code
という3つの部分に分かれてます
https://github.com/oskimura/ulang/blob/master/src/ulang_lex.xrl
Definitionsはruleで使用される正規表現の定義を行います
Definitions.
INT = [0-9]+
ATOM = :[a-z_]+
VAR = [a-z0-9_]+
CHAR = [a-z0-9_]
WHITESPACE = [\s\t\n\r]
という風に書きます。
Rulesは生成するトークンを記述します。
Rules.
module : {token,{module,TokenLine}}.
export : {token, {export,TokenLine}}.
fn : {token,{'fn',TokenLine}}.
\+ : {token,{'op',TokenLine, to_atom(TokenChars)}}.
\- : {token,{'op',TokenLine, to_atom(TokenChars)}}.
\* : {token,{'op',TokenLine, to_atom(TokenChars)}}.
\/ : {token,{'op',TokenLine, to_atom(TokenChars)}}.
\=\= : {token,{'op',TokenLine, to_atom(TokenChars)}}.
\< : {token,{'op',TokenLine, to_atom(TokenChars)}}.
\> : {token,{'op',TokenLine, to_atom(TokenChars)}}.
\<\= : {token,{'op',TokenLine, to_atom(TokenChars)}}.
\>\= : {token,{'op',TokenLine, to_atom(TokenChars)}}.
if : {token,{'if',TokenLine}}.
while : {token,{'while',TokenLine}}.
let : {token,{'let', TokenLine}}.
\<\- : {token,{'<-', TokenLine}}.
\" : {token,{'\"', TokenLine}}.
\-\> : {token,{'->', TokenLine}}.
\{ : {token,{'{', TokenLine}}.
\} : {token,{'}', TokenLine}}.
; : {token,{';', TokenLine}}.
if : {token,{'if', TokenLine}}.
then : {token,{'then', TokenLine}}.
else : {token,{'else', TokenLine}}.
end : {token,{'end', TokenLine}}.
{INT} : {token, {int, TokenLine, TokenChars}}.
{ATOM} : {token, {atom, TokenLine, to_atom(TokenChars)}}.
{VAR} : {token, {var, TokenLine, to_atom(TokenChars)}}.
\[ : {token, {'[', TokenLine}}.
\] : {token, {']', TokenLine}}.
\( : {token, {'(', TokenLine}}.
\) : {token, {')', TokenLine}}.
\. : {token, {'.', TokenLine}}.
, : {token, {',', TokenLine}}.
{WHITESPACE}+ : skip_token.
のように
マッチする字句 : {生成するトークン}
記号などは
\<\- : {token,{'<-', TokenLine}}.
\" : {token,{'\"', TokenLine}}.
バックスラッシュを挟む必要があります
Erlang codeはRulesで仕様されるErlangのコードを記述します。
Erlang code.
to_atom(Chars) ->
list_to_atom(Chars).
この例はErlangのatomに変換する例です
Erlangにはyeccという構文解析器があります BNFで文法を記述できます。
- Nonterminals
- Terminals
- 規則部
- Erlang code
に別れています
https://github.com/oskimura/ulang/blob/master/src/ulang_yecc.yrl を例に話します
Nonterminals と書いて非終端記のリストを書いていきます
具体的な定義については規則部に書きます
Nonterminals program module_exp functions function args arg while_exp let_exp exp exps if_exp test_exp true_exp false_exp op_exp call_exp remote_call_exp stmt list_exp tail_exp export_exp fundecs fundec tuple_exp tuple_build.
Terminals 終端記号のリストを書いて行きます
Terminals '.' '(' ')' '->' '<-' '{' '}' '[' ']' '<' '>' '<=' '>=' ',' 'fn' 'let' 'if' 'then' 'else' 'module' ';' 'end' 'export' int atom char string var op.
規則部 RootSymbolを開始記号とする簡約規則を記述します。RootSymbolがないとエラーになります。
Rootsymbol program.
次のようにBNFを書いて行きますが、Yacc系ツールと同じです。
program ->
module_exp: [ '$1' ].
program ->
module_exp exps: [ '$1' | '$2' ].
program ->
module_exp export_exp exps: [ '$1', '$2' | '$3' ].
program ->
exps: '$1'.
module_exp ->
'module' var:
{attribute, ?line('$2'),module, element(3,'$2')}.
export_exp ->
'export' '[' fundecs ']' :
{attribute,?line('$1'),export, '$3' }.
モジュールやexport関数の宣言
fundecs ->
fundec : [ '$1' ].
fundecs ->
fundec ',' fundecs :
[ '$1' | '$3' ].
fundec ->
'(' var ',' int ')' :
{element(3,'$2'), string_to_integer(element(3,'$4'))}.
export関数宣言
functions ->
function functions:
[ '$1' | '$2' ].
functions ->
function : ['$1'].
function ->
'fn' var '(' args ')' '->' '{' exps '}' :
{function,?line('$1'),element(3,'$2'), length('$4'),
[{clause,?line('$1'),'$4',[],
'$8'
}]
}.
function ->
'fn' var '(' ')' '->' '{' exps '}' :
{function,?line('$1'),element(3,'$2'), 0,
[{clause,?line('$1'),[],[],
'$7'
}]
}.
関数定義
args ->
arg ',' args :
[ '$1' | '$3' ].
args ->
arg : [ '$1' ].
arg ->
var : '$1'.
関数の引数
exps ->
exp :
[ '$1' ].
exps ->
exp ';' exps :
[ '$1' | '$3' ].
stmt ->
'{' exps '}'.
式の定義
exp ->
function : '$1'.
exp ->
let_exp : '$1'.
exp ->
if_exp : '$1'.
exp ->
op_exp : '$1'.
exp ->
list_exp : '$1'.
exp ->
call_exp : '$1'.
exp ->
remote_call_exp : '$1'.
exp ->
tuple_exp : '$1'.
exp ->
int : {integer, ?line('$1'), string_to_integer(element(3,'$1'))}.
exp ->
string : '$1'.
exp ->
var : '$1'.
式の定義
let_exp ->
'let' var '<-' exp :
{'match', ?line('$1'), '$2', '$4'}.
if_exp ->
'if' test_exp 'then' true_exp 'else' false_exp 'end':
{'case', ?line('$1'),
'$2',
[{'clause', ?line('$3'), [{atom, ?line('$3'),'true'}],
[],
'$4'},
{'clause', ?line('$5'), [{atom, ?line('$5'),'false'}],
[],
'$6'}]}.
test_exp ->
exp : '$1' .
true_exp ->
exps : '$1' .
false_exp ->
exps : '$1' .
letおよびifの定義
op_exp ->
exp op exp :
{op, ?line('$1'), element(3,'$2'), '$1', '$3' }.
call_exp ->
var '(' ')':
{call, ?line('$1'),var_to_atom('$1'),nil}.
call_exp ->
var '(' exps ')' :
{call, ?line('$1'),var_to_atom('$1'),'$3'}.
remote_call_exp ->
var '.' var '(' ')' :
{call, ?line('$1'), {remote, ?line('$1'), var_to_atom('$1'), var_to_atom('$3')}, nil}.
remote_call_exp ->
var '.' var '(' exps ')' :
{call, ?line('$1'), {remote, ?line('$1'), var_to_atom('$1'), var_to_atom('$3')}, '$5'}.
演算子、関数呼び出し
list_exp ->
'[' ']': {nil, ?line('$1')}.
list_exp ->
'[' exp tail_exp:
{cons, ?line('$2'), '$2', '$3'}.
tail_exp ->
',' exp tail_exp:
{cons, ?line('$1'), '$2', '$3'}.
tail_exp ->
']':
{nil, ?line('$1')}.
tuple_exp ->
'(' ')' :
{tuple, ?line('$1'),[]}.
tuple_exp ->
'(' tuple_build ')' :
{tuple, ?line('$1'), '$2'}.
tuple_build ->
exp ',' tuple_build :
[ '$1' | '$3' ].
tuple_build ->
exp :
[ '$1' ].
リストとタプル
Erlangのコード
Erlang code.
-define(line(Tup), element(2, Tup)).
line(Tup)-> element(2, Tup).
string_to_integer(Str) ->
case string:to_integer(Str) of
{Code,_} ->
Code
end.
var_to_atom({var,Line,V}) ->
{atom,Line,V}.
これは整数やatomを作るコードです
fib.uをコンパイルしてerlから呼び出してみましょう
以外と簡単だっとことがわかったことです。 あなたも挑戦してみましょう。