javascript/C言語/アセンブラを用い、 字句解析、構文解析、インタプリタ、コンパイラのプログラムをスクラッチから作りながら、 「プログラミング言語の作り方」を解説する。
別のプログラムが、プログラミング言語を理解するためには、「プログラミング言語の文法規則（ルール）」が必要だ。
文法規則といっても、プログラミング言語のルールは、とても機械的なので、プログラムで解析するのは難しくない。
自作プログラミング言語を作るための流れは以下だ。
字句解析の作り方では、文法規則に従い、ソースコードからトークン配列の作成を勉強する。
自作構文解析の作り方では、再帰下降構文解析法で、文法規則に従い、トークン配列から、中間表現である自作抽象構文木ASTの作成を解説する。
自作インタプリタの作り方では、組み込みライブラリ、ASTの評価実行などを解説する。
自作コンパイラの作り方では、ASTの最適化による高速化、意味解析、コード生成を勉強する。
最後に、Linux64bitのアセンブリ言語、マシン語などの低レイヤレベルでプログラミング言語をどう動かすかを再設計し、自作バイナリ、ローダ、動的リンカなどの作成を勉強する。
最初に、独自プログラミング言語を作るプログラムのソースコードを提示する。
長く見えるが、コンパイラで使うアセンブラが半分以上だ。また、それ以外の半分も、 インタプリタとコンパイラで共通処理だ。
$ cat 3izjs
#!/usr/bin/env node
//引数処理。拡張子「.3」ならコンパイラ。それ以外ならインタプリタとして動く
if(process.argv.length<=2){
console.log("Usage: 3iz filename or filename.3");
console.log("\tcompiler mode with filename.3");
console.log("\tinterpreter mode with filename");
process.exit();
}
var filename = process.argv[2];
var args = process.argv.slice(3);
//---------------------ここからメイン処理---------------------//
//字句解析器lexerを呼び出して、トークンの配列を取得
var tokens = lexer(filename);
//文法規則：演算子の優先順位
var rules = [
{z:1,ops:[]},//セミコロン省略演算子
{z:2,ops:[";"]},//セミコロン演算子
{z:2,ops:[","],},//カンマ演算子
{ops:["="]},//代入演算子
{ops:["+","-"]},//二項演算子(加減算)
{ops:["*","/"]},//乗算、除算演算子
{z:3,ops:["+","-"]},//単項演算子(符号から始まる)
{z:4,ops:["("]},//二項演算子(関数呼び出し)
{z:5,ops:["("]},//前置単項演算子(カッコから始まる)
];
var parser = parser_generator(rules);
//構文解析器(パーサ)を実行し、トークンをASTに変換
var ast = parser(tokens);
//コンパイラかインタプリタの分岐
if(filename.endsWith(".3")){
compile(ast,filename);//コンパイラ
}else{
runAST(ast);//インタプリタ
}
//---------------------ここから本体の実装---------------------//
//------自作字句解析------//
function lexer(filename){
var source = require('fs').readFileSync(filename,"utf-8");
source = source.replace(/^#!.*?\n/,"");
return source.split(/\/\/.*$|(".*?"|\d+(?:\.\d+){0,1}|\w+)|\s|(.)/m).filter(a=>a);
}
//自作構文解析(パーサー) <再帰下降構文解析法>
//パーサジェネレータ(文法を引数にパーサを返す関数)
function parser_generator(rules){
//ここでパーサを返している(このreturn function がパーサジェネレータ)
return function parser(t,p=0){
if(p==rules.length) return t.shift();//最上位ならそのまま返す
var z = rules[p]&&rules[p].z?rules[p].z:0;//優先度pの処理方法
var ops = rules[p]&&rules[p].ops;//優先度pの演算子の配列
if([1,2].includes(z)){//配列で格納する
var left = parser(t,p+1);//丸投げ
var list = [left];
while((z == 1 && t.length > 0 )||(z == 2 && ops.includes(t[0])) ){
if(z == 2) var op = t.shift();
var right = parser(t,p+1);
if(right) list.push(right);//配列にしておく
}
return list.length>1? list: left;
}else if([3,4,5].includes(z)){//オブジェクトで格納(イレギュラー版)
if ( z ==4 ) var left = parser(t,p+1);//丸投げ=関数名
while(ops.includes(t[0])){
var op = t.shift();//符号のプラスマイナス
var right = parser(t,z==3?p+1:2);//丸投げ
if(z!=3) op += t.shift();//カッコ)
if(z!=4) return z==5?right:{left:"0",op,right};//単項演算子を二項演算子化
left = {left,op,right};
}
return z==4?left:parser(t,p+1);//ここがleftでなくparser
}else{//オブジェクトで格納する（通常版）
var left = parser(t,p+1);
while(ops.includes(t[0])) left = {left,op:t.shift(),right:parser(t,p+1)};
return left;
}
}
}
//------AST評価実行(ASTを深さ優先探索しながらノードごとに評価実行)------//
function runAST(ast){
//組み込みライブラリprint関数
var libs = {print:a=>console.log(Array.isArray(a)?a.join(""):a)};
var env = {};//インタプリタ用グローバル変数置き場
//ASTを実行する
return run(ast);
function run(ast){
//配列は各要素を評価して、配列で返す。
if(Array.isArray(ast)) return ast.map(e=>run(e));
if(ast.op){//演算子あり
if(ast.op == '=') return env[ast.left] = run(ast.right);
if(ast.op == '()') return libs[ast.left](run(ast.right));
if(ast.op == '*') return run(ast.left) * run(ast.right);
if(ast.op == '/') return run(ast.left) / run(ast.right);
if(ast.op == '+') return run(ast.left) + run(ast.right);
if(ast.op == '-') return run(ast.left) - run(ast.right);
}
//演算子ないなら、バリューにする
if(ast[0]=='"') return ast.slice(1,-1);//「""」を捨てる
if(ast[0].match(/^\d+/)) return 1 * ast;//文字→数字
return env[ast];//定義済み変数なら値を返す。
}
}
function compile(ast,filename){
var basefile = filename.slice(0,-2);
var asmfile = basefile + ".s";
var objfile = basefile + ".o";
var exefile = basefile;
//アセンブラコード出力用元情報
var strs = []//文字列定数
var nums = [];//数値定数
var globals = []//グローバル変数
var types = {};//実数か文字列かの判定
var codes = [];//コード生成
//------ASTからコード生成元情報作成(ASTを深さ優先探索しながらアセンブリ出力)------//
function gen(ast){
//配列は各要素を評価して、配列で返す。
if(Array.isArray(ast)) return ast.map(e=>gen(e));
if(ast.op){//演算子あり
if(ast.op == '='){
//グローバル変数に登録されていなかったら登録する。
if(!globals.includes(ast.left)) globals.push(ast.left);
var type = types[ast.left] = gen(ast.right);//数値/文字列どっち代入？
if(type == 1){//実数
codes.push("pop0");
codes.push("movsd "+ast.left+",xmm0\n");
}else{
codes.push("pop rax");
codes.push("mov "+ast.left+",rax\n");
}
return 0;
}
if(ast.op == '()'){
if(ast.left == "print"){
(Array.isArray(ast.right)?ast.right:[ast.right]).forEach(a=>{
if(gen(a)==1){
codes.push("pop0");
codes.push("printd");
}else{
codes.push("pop rsi");
codes.push("prints");
}
});
}
codes.push("printn\n");
return 0;
}
//数値計算
if(ast.op == '*'){
gen(ast.left);
gen(ast.right);
codes.push("pop10");
codes.push("mulsd xmm0,xmm1");
codes.push("push0");
return 1;//数値を意味する
}
if(ast.op == '/'){
gen(ast.left);
gen(ast.right);
codes.push("pop10");
codes.push("divsd xmm0,xmm1");
codes.push("push0");
return 1;//数値を意味する
}
if(ast.op == '-'){
gen(ast.left);
gen(ast.right);
codes.push("pop10");
codes.push("subsd xmm0,xmm1");
codes.push("push0");
return 1;//数値を意味する
}
if(ast.op == '+'){
var type = gen(ast.left);
gen(ast.right);
if(type == 1){
codes.push("pop10");
codes.push("addsd xmm0,xmm1");
codes.push("push0");
return 1;//数値を意味する
}else{
//文字列連結
codes.push("pop rsi");
codes.push("pop rdi");
codes.push("call newcat");
codes.push("push rax\n");
return 0;//文字列
}
}
}
//演算子ないなら、バリューにする
if(globals.includes(ast)){//定義済み変数だったら
if(types[ast]==1){//実数が代入されている
codes.push("movsd xmm0,["+ast+"]");
codes.push("push0");
return 1;
}else{
codes.push("mov rax,"+ast);
codes.push("push rax\n");
return 0;
}
return 0;
}
if(ast[0]=='"'){
if(!strs.includes(ast)) strs.push(ast);//文字列定数として登録
codes.push("lea rax,[.s"+strs.length+"]");//文字列シンボル名ならlea
codes.push("push rax\n");
return 0;//数値以外を意味する
}
if(typeof ast == "number") return ast;
if(ast[0].match(/^\d+$/)){
if(!nums.includes(ast)) nums.push(ast);//数値定数として登録
codes.push("movsd xmm0, .d"+ast);//シンボル名
codes.push("push0");
return 1;//数値を意味する
}
return 0;
}
//アセンブリコード生成
gen(ast);
asmgen();
function asmgen(){
var asm=`
.intel_syntax noprefix
.global _start
`;
//マクロ定義：x64のxmmレジスタにはpush/popがない。
asm +=`
.macro push0
enter 8,0
movsd [rsp],xmm0 #push left push result
.endm
.macro pop0
movsd xmm0,[rsp] # pop left
leave
.endm
.macro pop10
movsd xmm1,[rsp] # pop right
leave
movsd xmm0,[rsp] # pop left
leave
.endm
.printf.s: .string "%s"
.printf.g: .string "%g"
.newline: .string "\\n"
.macro prints
lea rdi,[.printf.s]
call printf
.endm
.macro printn
lea rdi,[.newline]
call printf
.endm
.macro printd
lea rdi,[.printf.g]
call printf
.endm
`;
//文字列連結ライブラリ
asm +=`
#別メモリを確保して連結する
newcat:
# rax(連結後の新メモリ <---- rdi(str1),rsi(str2))
enter 32,0 # str1,str2,合計サイズ,新しいメモリ
mov [rsp],rdi # str2
mov [rsp+8],rsi #str1
movq [rsp+16],1 # 合計サイズ(最後のnull分の1)
call strlen # str1の長さ
add [rsp+16],rax # str1の長さを足す
mov rdi,[rsp+8]
call strlen # str2の長さ
add [rsp+16],rax # str2の長さを足す
mov rdi,1024
call malloc
mov [rsp+24],rax # 新メモリ
#lea rax,[rsp+24]
#movb [rax],0 #先頭nullを代入
mov rdi,[rsp+24]
mov rsi,[rsp]
call strcat
mov rdi,[rsp+24]
mov rsi,[rsp+8]
call strcat
mov rax,[rsp+24] # 新メモリを返す
leave
ret
`;
//文字列定数
strs.forEach((s,i)=>asm+=".s"+(i+1)+": .string "+s+"\n");
//数値定数
nums.forEach(n=>asm+=".d"+n+": .double "+n+"\n");
//グローバル変数
globals.forEach(g=>asm+=".comm "+g+",8\n");
asm += "\n_start:\n";
//メインコードを出力
codes.forEach(c=>asm+=" "+c+"\n");
//終了処理
asm += " mov rdi,0\n call exit\n";
//-------------アセンブリ言語のコード生成(テキスト)-----------//
require("fs").writeFileSync(asmfile,asm);
}
exec=c=>require("child_process").execSync(c);//外部コマンド実行用
//------アセンブラ(asコマンド)で、アセンブリをオブジェクトへ---------//
exec("as "+asmfile+" -o "+objfile);
//------リンカ(ldコマンド)で、オブジェクトを実行ファイルへ------//
exec("ld --dynamic-linker /lib64/ld-linux-x86-64.so.2 -lc -o "+exefile +" "+ objfile);
//exec("rm -f " + asmfile +" "+ objfile);
}プログラミング言語を作る上で、最初のステップとなる、字句解析について解説する。
字句解析は、文字列であるソースコードを分割し、トークン配列にすることだと述べた。
字句解析のインプットのソースコードは、すでに提示したので、字句解析のアウトプットになる、トークン配列も提示しよう。
tokens= [
'str1', '=', '"hello"', 'str2',
'=', '"world"', 'a', '=',
'-', '5', ';', '+',
'2', 'b', '=', '7.62',
'f', '=', '-', '0.9',
'+', '12.21', '-', '3',
'*', '(', 'a', '-',
'(', 'b', '/', '2',
'+', '1', ')', ')',
'print', '(', 'str1', '+',
'" "', '+', 'str2', ')',
'print', '(', '"f = "', ',',
'f', ')', ';', 'print',
'(', '"-2*(-a+1) = "', ',', '-',
'2', '*', '(', '-',
'a', '+', '1', ')',
')'
]普通の文字列の配列だ。
文字列を分割して配列にするだけだ。
しかし、むやみに分割すればいいわけではないので、どんな単位に分割しているのか、整理分類してみよう。
文字列の分割なので、正規表現を使う。それぞれの分類ごとに、正規表現がどうなるのかも説明しておく。
まずは、コメントの削除だ。コメントアウトされている内部にはいろんなコードが入っている可能性がある。
つまり、先に取り除いてやらないといけない。
「//」より後ろの行末までをコメントアウトにする。
コメントにマッチする正規表現は以下になる。
\/\/.*?$
とても見辛い。可読性が悪い。正規表現のデメリットだ。
今後作る自作言語では、このあたりは、解消したいところだ。
正規表現において、スラッシュは正規表現自体を表す文字なのでそのままでは使えない。
バックスラッシュ「\」でエスケープしてやる必要がある。
「/」一文字を表すのに「\/」としてやらなければならない。「//」のように２文字なら「\/\/」とする。
気持ち悪いが仕方ない。
次に、文末を表す記号として「$」を使う。
ちなみに、行末にマッチする「$」と行頭にマッチする「^」は、「mオプション」を有効にしないと機能してくれないので注意したい。付け忘れると、なぜ動かないのか頭を悩ませることになる。
話をもとに戻す。
「\/\/」で始まって、文末「$」で終わる任意の文字列にしたい。
「.」が任意の１文字を表し、「*」が0回以上の連続を表す。「.*」とすれば、0文字以上の任意文字という意味になる。
しかし、デフォルトの動作が、貪欲マッチ、最長マッチになっている。つまり、できるだけ長くマッチするようになっている。
今回の場合、直近の改行である行末にマッチさせたいのに、文末まで行ってしまうイメージだ。
直近の改行である行末でいいよという、非貪欲マッチ、最短マッチさせるには「.*?」のようにハテナを足す。
次に文字列の抽出だ。
文字列は、ダブルクオーテーションで括られている。
しかし、
"hello"+"world"
のような場合、デフォルト動作の最長マッチであったら「"hello"+"world"」という長い文字列にマッチしてしまう。
「"hello"」と「"world"」それぞれに分割したい。
つまり、最短マッチだ。正規表現は以下になる。
".*?"
まず、a、b、str1などの変数名、printなどの関数名などだ。
これらをシンボル名と呼ぶ。
シンボル名は、英数字の連続だと考えることができる。
一般的に、変数名の先頭は数字がダメというルールがある。
これは、英数字の連続というルールだと、数字も作ることができるからだ。
しかし、1st,2ndという変数があってもいい。
つまり、123というような数字を先に処理しておけば、英字数字というルールのままで十分なのだ。
プログラミング言語を作る上で、２つ目のステップになる構文解析について解説する。
構文解析の作り方を説明する。
構文解析(パーサ)の自作方法を入門レベルで解説する。
パーサーの処理の解説の前に、インプットとアウトプットを確認しておこう。
インプットは、字句解析の結果で、以下のような、文字列の配列だった。
tokens= [
'str1', '=', '"hello"', 'str2',
'=', '"world"', 'a', '=',
'-', '5', ';', '+',
'2', 'b', '=', '7.62',
'f', '=', '-', '0.9',
'+', '12.21', '-', '3',
'*', '(', 'a', '-',
'(', 'b', '/', '2',
'+', '1', ')', ')',
'print', '(', 'str1', '+',
'" "', '+', 'str2', ')',
'print', '(', '"f = "', ',',
'f', ')', ';', 'print',
'(', '"-2*(-a+1) = "', ',', '-',
'2', '*', '(', '-',
'a', '+', '1', ')',
')'
]次に、アウトプットは、構文解析(パーサ)の結果だ。
ast= [
{ left: 'str1', op: '=', right: '"hello"' },
{ left: 'str2', op: '=', right: '"world"' },
[
{ left: 'a', op: '=', right: { left: '0', op: '-', right: '5' } },
{ left: '0', op: '+', right: '2' }
],
{ left: 'b', op: '=', right: '7.62' },
{
left: 'f',
op: '=',
right: {
left: {
left: { left: '0', op: '-', right: '0.9' },
op: '+',
right: '12.21'
},
op: '-',
right: {
left: '3',
op: '*',
right: {
left: 'a',
op: '-',
right: {
left: { left: 'b', op: '/', right: '2' },
op: '+',
right: '1'
}
}
}
}
},
{
left: 'print',
op: '()',
right: {
left: { left: 'str1', op: '+', right: '" "' },
op: '+',
right: 'str2'
}
},
[
{ left: 'print', op: '()', right: [ '"f = "', 'f' ] },
{
left: 'print',
op: '()',
right: [
'"-2*(-a+1) = "',
{
left: { left: '0', op: '-', right: '2' },
op: '*',
right: {
left: { left: '0', op: '-', right: 'a' },
op: '+',
right: '1'
}
}
]
}
]
]とても重要なことだが、構文解析(パーサ)は、
&配列を、階層構造に変換する
だけだ。
忘れないでほしい。
この階層構造を抽象構文木(AST)と呼ぶ。
構文解析(パーサ)は、トークン配列を、抽象構文木(AST)に変換しているだけだ。
具体的な実装を見ていこう。
パーサジェネレータの実装を見ただけでは、抽象構文木ASTの理解が不十分だろう。
抽象構文木ASTの作り方についてサンプルデータを使って見ていこう。
プログラミング言語を作る上で必要な、構文解析パーサの作り方について解説した。
次に、パーサを作り出すパーサジェネレータを解説する。
インプットとアウトプットの再確認ができたところで、構文解析(パーサ)のjavascript実装部分を見てみよう。
文法規則の定義だ。
といっても、演算子の優先順位を定義しているだけだ。
//文法規則：演算子の優先順位 var rules = [ {z:1,ops:[]},//セミコロン省略演算子 {z:2,ops:[";"]},//セミコロン演算子 {z:2,ops:[","],},//カンマ演算子 {ops:["="]},//代入演算子 {ops:["+","-"]},//二項演算子(加減算) {ops:["*","/"]},//乗算、除算演算子 {z:3,ops:["+","-"]},//単項演算子(符号から始まる) {z:4,ops:["("]},//二項演算子(関数呼び出し) {z:5,ops:["("]},//前置単項演算子(カッコから始まる) ];
先程定義した文法規則を引数に渡して、parser_generator関数を呼んでいる。返ってくるのは、パーサだ。つまり関数だ。
var parser = parser_generator(rules);
この、パーサジェネレータとは、文法規則を引数にして、パーサを返す関数だ。
//自作構文解析(パーサー) <再帰下降構文解析法> //パーサジェネレータ(文法を引数にパーサを返す関数) function parser_generator(rules){//ここでパーサを返している(このreturn returnfunction がパーサジェネレータ)function parser(t,p=0){
何のことはない。以下のようにするだけだ。
function パーサジェネレータ(文法規則){
return function parser(){
与えられた文法規則を使うパーサー処理;
}
}
１つめは、解説用のスクリプト言語の、言語仕様ルール(演算子の優先度)だ。
パーサー本体(parser関数)に直接記述せずに、外部の配列(rules)にルールを定義することで、汎用性を持たせている。
あとから、異なる挙動をするようにカスタマイズしやすいからだ。上の方が優先度が低く、下の方が優先度が高い。加減算(+、-)よりも乗除算(*と/)の方が強い。
同じ優先度を持った演算子は、演算子配列(ops)の中でまとめてある。
「+」と「-」が２箇所あるが、これは、-aなどの符号のマイナスと、減算のマイナスだ。
「(」も２つあるが、関数呼び出しのカッコと計算で優先したい部分を括るカッコを分けている。
zは、細かい処理を切り替えるための値だ。今は気にしないで欲しい。
次に、構文解析パーサ本体だ。
parser関数のメイン部分だ。
zの値で、細かい処理を分けているが、アウトプットのASTの形を変えたかったからだ。
メイン部分のみ抜き出して、わかりやすく書き換えると、以下のようになる。
function parser(t,p=0){
if(p==rules.length) return t.shift();
var ops = rules[p]&&rules[p].ops;//優先度pの演算子の配列
var left = parser(t,p+1);
while(ops.includes(t[0])){
var op = t.shift();
var right = parser(t,p+1);
left = {left:left,op:op,right:right};
}
return left;
}
最初の行だが、tにトークン配列が渡ってくる。
function parser(t,p=0){
pは演算子の優先度を表している。rules配列の添字だ。つまり、pの値によって現在、どの演算子を処理の対象にしているのかを区別している。初期値はゼロだ。
次は、優先度pがrulesの配列を超えたら、どの演算子にもマッチしなかったことになる。
要は、これ以上階層構造にする必要がないので、トークン配列の先頭の値をそのまま返している。
if(p==rules.length) return t.shift();
これは、rules配列からp番目のopsを取り出しているだけだ。
var ops = rules[p]&&rules[p].ops;//優先度pの演算子の配列
以下の部分が、構文解析(パーサ)のコアになる。とても重要だ。
var left = parser(t,p+1);
while(ops.includes(t[0])){
var op = t.shift();
var right = parser(t,p+1);
left = {left:left,op:op,right:right};
}
この部分で階層構造を作り出しているのだ。
left = {left:left,op:op,right:right};
パーサの大枠が分かってきたところで上のコードがどう抽象構文木ASTを作っていくのか見ていこう。
プログラミング言語を作る上で、字句解析、構文解析と解説してきた。
これら２つは、抽象構文木ASTを作ることが目的だ。
ここでは、抽象構文木ASTの作り方を解説する。
まず、階層データ構造であるASTは、自由に作ればいい。
ここでは、左辺(項)、演算子、右辺(項)の意味だ変数left,op,rightの部分を使っている。
a = 1
なら
{left:"a",op:"=",right:1} 1 + 2
なら
{left:"1",op:"+",right:2} とするイメージだ。
順を追って見ていく。
最初のleftの部分では、parser関数が再度呼び出されている。
var left = parser(t,p+1);
ポイントは、引数のpがp+1となっている部分だ。つまり、今までは優先度pに注目していたが、先に、次の優先度p+1の演算子を処理しろという意味だ。
こういう処理があることで、
1 - 2 * 3
のように、前に記述されているマイナスではなく、後ろに記述されている掛け算を先に処理することができるようになる。
次は、whileの部分だ。
while(ops.includes(t[0])){ これは
1 - 2 + 3 - 4
のように同じ優先度の演算子が連続していた場合にループする。
例えば、トークンtの先頭の"1"はすでにleftに入っているので、残りは
t = ["-","2","+","3","-","4"]
となっている。opsは
ops = ["+","-"]
となっているので
ops.includes(t[0])
は、
["+","-"].includes("-") となる。includes関数は、配列に、引数が含まれるかどうかチェックする関数だ。
while文の中の本体を見ていこう。
最初は、opだ。これは演算子を表している。
var op = t.shift();
while文のinclude関数で、優先度pの演算子であることをチェック済みなので、先頭の要素を抜き出しているだけだ。
先程の例だと、トークンの先頭はマイナスだったので
t = ["-","2","+","3","-","4"]
op = "-"
t = ["2","+","3","-","4"]
のようにopにマイナスを代入し、トークン配列は短くなる。
次は、rightの部分だが、これはleftの処理と同じだ。
右辺だろうが、左辺だろうが、優先度の高い演算子を先に処理できる。
var right = parser(t,p+1);
といっても、例の場合は優先度が同じなので
right = "2"
となり、トークンは短くなる。
t = ["+","3","-","4"]
さぁ、次は、構文解析(パーサー)で一番重要なポイントだ。
というのも、階層構造ASTを作っているのはここだけだからだ。
left = {left:left,op:op,right:right}; 左辺の(新しい)leftに、右辺の(古い)left含めた{left,op,right}を代入することで、階層構造を作り出している。
わかったようで、分かっていないだろう。
しかし、javascriptのコードは、これ１行だけだ。
これをどんなに眺めても、これ以上の理解は得られない。
そこで、
&あるコードは、どんなASTになって欲しいか
というサンプルをクドいくらいに、たくさん見ていこう。
パーサジェネレータの作り方でも解説したが、抽象構文木ASTを作るパーサ処理のコアは以下になる
var left = parser(t,p+1);
while(ops.includes(t[0])){
var op = t.shift();
var right = parser(t,p+1);
left = {left:left,op:op,right:right};
}
このコードだけ見ても抽象構文木ASTは理解できない。
もっと具体的なサンプルを使って理解を深めていこう。
javascriptのコードは1行なので、理解を深めるために、構文解析(パーサ)のアウトプットである抽象構文木(AST)がどうなって欲しいかのケーススタディをする。
クドいと思われるかもしれないが、実は、このように段階を追って考える方が、何倍も早く理解が深まるのだ。
ASTは、言語のルールに従っていれば、どんな形でも自由に作って良い。
しかし、後に解説する評価実行のところで、どんな順番で実行すればいいかが、明確になっている必要がある。
今回のASTは、一番深いところから先に処理されるように作る。つまり、後で深さ優先探索できるようにしておくだ。
それでは、ケーススタディを始めよう。
1 + 2
というコードの場合、ASTは、
{left:1, op:"+", right:2} となってほしい。簡単だ。
同じ優先度の演算子が連続する場合を考えよう。例えば、+、-だ。
同じ優先度が連続する場合、左側から順に処理すればいい。
1 - 2 + 3 - 4
というコードの場合を考えるが、一度に全部を考えると混乱する。
まず、先に処理される、左側の1-2だけを考えよう。
1 - 2 + 3 - 4
{left:1, op:"-", right:2} となる。簡単だ。
ASTを作る前提のところで話をしたが、後から、深さ優先探索ができるようにする。
つまり、
&先に処理して欲しいものは、内側の階層にいれる
ということだ。
-4のことは考えずに、+3の部分を考慮に入れて、階層を表現してみよう。
1 - 2 + 3 - 4
内側の階層 + 3 - 4
{left:内側の階層, op:"+", right:3} {left:{left:1, op:"-", right:2}, op:"+", right:3} という具合だ。
さらに、これまでの値を、内側の階層に入れるように、-4を作る。
{left:内側の階層,op:"-",right:4} {left:{left:{left:1, op:"-", right:2}, op:"+", right:3},op:"-",right:4} となる。簡単だ。
これまで、同じ優先度の演算子が連続していたので単純に、左側を優先していた。
丸カッコで括られていたら、その順番が変わるので見ていこう。
1 - (2 + 3) - 4
まず、最初に(2+3)を作ろう。
{left:2, op:"+", right:3} となる。簡単だ。
この(2+3)を先に処理して欲しいので、これが内側の階層になるようにして、左側から処理する。1-の部分だ。
{left:1, op:"-", right:{left:2, op:"+", right:3}} となる。今までは、左側の階層が深くなっていたが、右側の階層が深くなっていることが分かる。
これは、左右のどちらを先に処理して欲しいかで変わる。
続きも、内側に来るように、-4の部分だ。
{left:{left:1, op:"-", right:{left:2, op:"+", right:3}, op:"-",right:4} となる。簡単だ。
次は、異なる優先度の演算子があるケースだ。プラスマイナスに加えて、掛け算を入れてみる。
1 - 2 * 3 - 4
先に、2*3を処理してほしいので
{left:2, op:"*", right:3} を作り、これが内側に来るように、1-の階層を作る。
{left:1, op:"-", {left:2, op:"*", right:3} } これは、先程の
1 - (2 + 3)
と同じ形のASTであることが分かる。
つまり、優先する丸カッコと、演算子の違いはあるが、優先度が強い方を、内側の階層の深いところにハメることは、同じだ。
最後に-4を足す。
{left:{left:1, op:"-",{left:2, op:"*", right:3}},op:"-",right:4} となる。簡単だ。
次は、優先度の強い演算子とカッコの混在のケースだ。
通常は、マイナスよりも、掛け算の方が強い。しかしカッコがあるのでそっちを優先するケースだ。
1 * (2 - 3)
カッコの方が強いので
{left:2,op:"-",right:3} を先に作り、これを内側にはめればいい。
{left:1, op:"*", right:{left:2,op:"-",right:3}} という具合だ。
四則演算は大分つかめてきたので、次は代入演算子だ。
a = 1
なら
{left:"a", op:"=", right:1} とする。
a = (1 - 2) * 3
の場合なら、先に、右辺の
{left: {left:1,op:"-",right:2}, op:"*", right:3} を作っておく。これが内側になるようにrightにはめるだけだ。
{left:"a", op:"=", right: {left: {left:1,op:"-",right:2}, op:"*", right:3} } 通常であれば、left,op,rightがそろっている。これを二項演算子と呼ぶ。
次は、left,rightがそろっていないケースだ。例えば、-3などの、符号だ。
単純な-3であれば、数値-3と考えることもできるが、-aなどの場合は、演算子として扱う必要がある。
-a
これは
{op:"-", right:a} とする。aにマイナスを掛けているイメージだ。
これを単項演算子と呼ぶ。
b = -a * 2 + 1
なら、
{left:{op:"-",right:a}, op:"*",right:2} {left:{left:{op:"-",right:a}, op:"*",right:2},op:"+",right:1} {left:"b", op:"=", right:{left:{left:{op:"-",right:a}, op:"*",right:2},op:"+",right:1}} とすればいい。
次は、関数呼び出しだ。関数呼び出しを２項演算子のように扱っている。
print("hello") だったら
{left:"print", op:"()", right:'"hello"'} とすればいい。
演算子opは、==、<=など２文字になることがある。関数呼び出しの際のopを()にしているが、別に何でもいい。
leftが関数名、rightが引数になっている。
print("hello"+"world") だったらどうだろうか？
まず、引数の内側を先に計算してから、print関数を呼んでほしいので
{left:"hello", op:"+", right:"world"} を先に作り、内側にはめる。関数名がleftで、rightが引数だ。
{left:"print", op:"()",right: {left:"hello", op:"+", right:"world"} } 関数の引数が2つあったらどうだろうか。
print("a=", 1) 引数の内側を先に計算してから、print関数を呼んでほしいことに変わりはない。
引数の内側をどう表現するか自由だが、配列で表現しようと思う。
"a=", 1
["a=", 1]
のように配列にする。これを内側にはめるようにしてprint関数で呼ぶと
{left:"print", op:"()", right: ["a=",1] } となる。ついでなので、引数が増えて、計算式が入ったケースだ。
print("a=", 1, "b=", 2+3*-1) 一番最初に計算してほしいのは2+3*-1の部分ので先にこの部分を作る。
{op:"-",right:1} {left:3,op:"*",right: {op:"-",right:1} } {left:2, op:"+", right:{left:3,op:"*",right:{op:"-",right:1}}} これを、引数配列の最後に、はめる。
["a=", 1, "b=", {left:2, op:"+", right:{left:3,op:"*",right:{op:"-",right:1}}}] その上で、print関数を呼ぶ。
{left:"print", op:"()", right:["a=", 1, "b=", {left:2, op:"+", right:{left:3,op:"*",right:{op:"-",right:1}}}] } 最後に、複数文だ。セミコロンの有無にかかわらず、文の連続を配列で表現する。
a = 1; b = a + 2
の場合、セミコロン演算子と捉えてもいいがa=1と、b=a+2のデータを作りそれを配列に並べる。
{left:"a", op:"=", right:1} {left:"a", op:"+", right:2} {left:"b", op:"=", right:{left:"a", op:"+", right:2} } [ {left:"a", op:"=", right:1}, {left:"b", op:"=", right:{left:"a", op:"+", right:2}} ] という感じだ。
たとえ、セミコロンがなくても、
a = 1 b = a + 2
[ {left:"a", op:"=", right:1}, {left:"b", op:"=", right:{left:"a", op:"+", right:2}} ] のように同じデータ構造にする。
プログラミング言語を作るための処理系として、インタプリタ形式とコンパイラ形式がある。
ここでは、自作インタプリタの作り方を入門レベルで説明する。まず、インタプリタ作成の流れは大きく、以下のようになる。
これらの自作インタプリタ作成に必要な処理を順に解説していく。
解説で利用するソースコードは以下だ。
$ cat interpretMe #!/usr/bin/env 3izjs//--------独自プログラミング言語「3iz」---------- str1 ="hello"//文字列の変数代入 str2= "world" a = -5; +2//マイナス符号つき整数、セミコロン、プラス符号 b = 7.62//実数 f = -0.9 +12.21 -3*(a -( b /2+1))// 変数参照と、演算子たくさん print(str1 + " "+str2)//hello worldの文字列連結。表示。 print("f = ",f);//複数引数の関数呼び出し print("-2*(-a+1) = ", -2 * (-a+1) )//関数の引数内で、計算。
悩まずに簡単に、自作インタプリタを作る上で大事なことだが、これをプログラミング言語だと思わないことだ。
これらは、単なる１つの文字列だと考えよう。
複数行だが、改行コードが挟まっているだけの１つの文字列だ。
さて次は、作成されたASTを、実行していこう。自作インタプリタ固有の処理だ。
構文解析の実装が終わったのでインタプリタ専用の機能であるAST実行(runAST)処理の実装に移る。
構文解析のアウトプットとして、抽象構文木ASTができている。
この抽象構文木ASTはどんな作り方をしても良いが深いところを先に処理してもらうように作成したので、そのとおりに実行する必要がある。
つまり、深さ優先探索して、演算子などの指示にしたがって実行していけばいいだけだ。
javascriptのコードを一つずつ見ていこう。
抽象構文木ASTを実行するのは、runAST関数の部分だ。
//------AST評価実行(ASTを深さ優先探索しながらノードごとに評価実行)------// function runAST(ast){
組み込みライブラリを定義している。print関数だけがある状態だ。引数が1つのときはそのまま表示し、配列のときは、joinして表示している。
//組み込みライブラリprint関数 var libs = {print:a=>console.log(Array.isArray(a)?a.join(""):a)};
グローバル変数置き場だ。変数名をキーに値を保存する。
var env = {};//インタプリタ用グローバル変数置き場 ASTを引数にrun関数を実行している。これ以降、run関数の定義になる。
//ASTを実行する return run(ast);function run(ast){
まずは、AST上の配列の部分だ。これは、複数の文の時もあるし、関数に渡す複数引数のときもある。それぞれの要素に対して、run関数を再帰呼び出ししている。
//配列は各要素を評価して、配列で返す。 if(Array.isArray(ast)) return ast.map(e=>run(e));
これによって、配列の各要素に、まだ深い階層のASTがあれば評価する。
[ast,ast,ast]
[値,値,値]
結果的に、値の配列にして戻す。
どうやって値にしているかは一番最後の「AST上のバリュー、変数参照」を見てほしい。
複数の文のときは、実行されたことになる。
複数の引数のときは、値に変わった配列を返すので、関数呼び出しができる状態になる。
ASTに演算子があった場合だ。
if(ast.op){//演算子あり それぞれの演算子によって処理を分けているのでそれらを見ていこう。
まず、代入演算子「=」の場合だ。
if(ast.op == '=') return env[ast.left] = run(ast.right);
代入演算子の場合は、右辺を先に評価(run関数を呼んでいる)してその結果を、左辺に代入する。
ポイントは、左辺は、評価していないことだ。ast.leftの部分は、run関数を呼んでいない。
何をしているのかというと、グローバル変数置き場のenvオブジェクトにast.leftをそのままキーとして、右辺値を代入しているだけだ。
env[ast.leftに入っている変数名の文字列そのまま] = ast.rightはrunで値
env["a"] = 3
print関数しかないが、関数呼び出しの部分だ。
if(ast.op == '()') return libs[ast.left](run(ast.right));
ast.leftには関数名、つまり、"print"が入っている。
先程と同じく、ast.leftについては、run関数を呼び出していない。つまり、
libs[ast.left](引数)
は、そのまま
libs["print"](引数)
となり、
print(引数)
となっているわけだ。
次に、関数に渡している引数を見ていこう。
引数はast.rightに入っている。
これはAST上の配列の部分で説明したが、複数の引数であれば、各要素を値にしてくれる
print([ast,ast,ast])
なら
print([値,値,値])
として、呼び出しているわけだ。
次に四則演算だ。
特に難しいことはない。左辺も右辺もrun関数で値にしてそれぞれ計算し戻している。
ちなみに、「+」演算子は、文字列に対して使えば、文字列の連結してくれる。
if(ast.op == '*') return run(ast.left) * run(ast.right); if(ast.op == '/') return run(ast.left) / run(ast.right); if(ast.op == '+') return run(ast.left) + run(ast.right); if(ast.op == '-') return run(ast.left) - run(ast.right);
ASTにopが設定されていなかったら、値として扱う。ダブルクオーテーションで始まっていたら文字列と判断しダブルクオーテーションを捨ていている。
数字で始まる文字列だったら、数字と判断し、数値にしている。
//演算子ないなら、バリューにする if(ast[0]=='"') return ast.slice(1,-1);//「""」を捨てる if(ast[0].match(/^\d+/)) return 1 * ast;//文字→数字
それ以外の文字であれば、変数なのだと判定し、envからastをキーに値を参照している。
return env[ast];//定義済み変数なら値を返す。
astが変数aなら
return env["a"]
となっているわけだ。
これでインタプリタは完成だ。
ちゃんと動いていることを確認しよう。
プログラミング言語を作るための処理系として、インタプリタ形式とコンパイラ形式がある。
ここでは、自作コンパイラの作り方を入門レベルで説明する。まず、自作コンパイラ作成の流れは大きく、以下のようになる。
これらの自作コンパイラ作成に必要な処理を順に解説していく。
解説で利用するソースコードは以下だ。
$ cat compileMe.3//--------独自プログラミング言語「3iz」---------- str1 ="hello"//文字列の変数代入 str2= "world" a = -5; +2//マイナス符号つき整数、セミコロン、プラス符号 b = 7.62//実数 f = -0.9 +12.21 -3*(a -( b /2+1))// 変数参照と、演算子たくさん print(str1 + " "+str2)//hello worldの文字列連結。表示。 print("f = ",f);//複数引数の関数呼び出し print("-2*(-a+1) = ", -2 * (-a+1) )//関数の引数内で、計算。
悩まずに簡単に、自作コンパイラを作る上で大事なことだが、これをプログラミング言語だと思わないことだ。
これらは、単なる１つの文字列だと考えよう。
複数行だが、改行コードが挟まっているだけの１つの文字列だ。
さて次は、作成されたASTから「コード生成」していこう。自作コンパイラ固有の処理だ。
アセンブリ言語のコード生成についての解説は、別ページで行っている。
以下のリンクから進んで欲しい。
コンパイラ作成の大きな機能のうちの３つ目「コード生成」では3iz言語からアセンブリ言語への翻訳(変換)を行った。
つまり、コンパイラの自作はすでに終わっているのだ。
しかし、アセンブリ言語は、まだテキストファイルでありマシン語のようなバイナリではない。
このアセンブリ言語をどうやってバイナリにするのかを解説する。
アセンブリ言語には、アセンブリ語のコンパイラが別途存在する。この別コンパイラのことを、アセンブラと呼ぶ。
実は、gccは、C言語のコンパイラであるが、C言語のソースコードをアセンブラにコンパイルするだけだ。
裏で、別コンパイラであるアセンブラを起動させている。
3izコンパイラが作成したアセンブリ言語のファイルがcompileM3.sだった。
これをGNU assembler(GASと呼ぶがコマンドはas)でマシン語にする。このGASは、gccでも利用されている。
asコマンドの実行方法は以下だ。
$ as compileMe.s -o compileMe.o
出力ファイルは、アセンブラが本来出力するべきマシン語に加えて、巨大なデータを加えてELFフォーマットと呼ばれるLinux標準のバイナリフォーマットになる。
これをオブジェクトファイル(compileMe.o)と呼ぶ。
実はこのオブジェクトファイルは、バイナリファイルではあるがまだ、実行ファイルではない。
これを実行ファイルにするにはまたひと手間かかる。
リンカと呼ばれる別プログラムが、複数のオブジェクトファイルや共有ライブラリなどの情報を含めて１つのファイルにする。
１つのファイルにリンクするので、リンカと呼ばれる。リンカのコマンドはldだ。
$ ld --dynamic-linker /lib64/ld-linux-x86-64.so.2 -lc -o compileMe compileMe.o
このアウトプットとして、ようやく実行ファイルと呼ばれるファイルが出力された。
このファイルを実行してみよう。
$ ./compileMe hello world f = 40.74 -2*(-a+1) = -12
ちゃんと結果が表示された。
狭義のコンパイラとは、アセンブラに出力するまでのことだ。
gccなど、コンパイラと呼ぶとき、実行ファイルに出力するまでのことを指すことが多い。
つまり、普通は広義のコンパイラを指している。要は、asコマンドやldコマンドは別のプログラムだがこの部分もコンパイラに含まれていると扱う。
実際、gccコマンドを実行すると、いきなり実行ファイルが出力されているように見える。
これは、gccの中で、asコマンドやldコマンドを呼び出して実行しているからだ。
3izのjavascript実装の中でも、同じように、asコマンドとldコマンドを実行することでいきなり実行ファイルができるようになっている。
Linuxの標準バイナリフォーマットに採用されているELFは、汎用性は高いが、冗長だ。
バイナリを勉強するのには向かない。
そこで、シンプルな自作バイナリフォーマット3izbinを導入し、自作バイナリフォーマットの作り方を解説する。
その際、バイナリレベルの低レイヤで、プログラムが動く仕組みも解説する。
自由にバイナリファイルを作成できるアセンブラとしてflat assembler(fasm)を使う。
コンパイラの作成で使うアセンブラとしてflat assembler(fasm)を使う。
flat assembler バージョン番号 for LinuxとなっているリンクのURLをコピーしよう。curlでダウンロードする。
解凍する。
fasm.x64という実行ファイルひとつをPATHの通った場所(~/bin)にコピーする。fasm.x64では打ちにくいのでfasmという名前に変えている
$ cd /tmp $ curl -O https://flatassembler.net/fasm-バージョン番号.tgz $ tar zxvf fasm-バージョン番号.tgz $ cp fasm/fasm.x64 ~/bin/fasm
fasmを実行すると以下のようになれば実行できている。
$ fasm flat assembler usage: fasm[output] optional settings: -m set the limit in kilobytes for the available memory -p set the maximum allowed number of passes -d = define symbolic variable -s dump symbolic information for debugging
javascriptやCのようなヘルプしてくれる別プログラミング言語を使わずにアセンブラのみで実装する。ついでに、バイナリフォーマットから見直すガチの低レイヤに挑む。
アセンブラだと移植性が気になるかもしれない。
linuxしか使わないので、他OSへの移植性は不要だ。
コンパイル済みのバイナリのまま配布したいこともあるだろうしバイナリを別マシンにコピーしてすぐに動かしたい。p当然、root権限のないレンタルサーバー環境でも動くようにしたい。
linux 64bit OSなら、ほとんどの環境がx86_64(intel x64/amd64)だろう。
つまり、基本的にはコンパイル済みのバイナリを別のマシンに持っていっても動く。
ただし、sharedライブラリのバージョンが違うなど環境によっては動かない可能性が出てくる。
そこで、libcなども含めて、他ライブラリに依存しない構成にする。
単純に、staticコンパイルしてワンバイナリ化するとユーザバイナリが無駄にでかくなるので独自の3iz共有ライブラリを用意する。
この際なので、実行ファイル側のユーザrunファイルを独自の3izフォーマットにして、極限までサイズを切り詰める。
つまり、
3iz独自の共有ライブラリ3iz独自のフォーマットのユーザー実行runファイル
の２ファイル構成にする。
２ファイル構成について、全体像を具体的に説明しよう。
ユーザソースをコンパイルして実際に実行されるまでの流れを確認しよう。
１つ目は、ブルーの部分だ。
3iz言語で記述されたユーザーが書くソースコードをコンパイルして出力されたアセンブリ言語をfasmでマシン語にしたバイナリファイルだ。
これをユーザーrunファイルと呼ぶことにする。
$ ./run
とすれば実行できるファイルだ。
２つ目は、オレンジの部分だ。
広義の意味で、3izコンパイラ呼ぶ。
これは、（狭義の）コンパイラ兼ライブラリ兼動的リンカ兼ローダーの役割があるが、１つの実行ファイルになっている。
つまり、この3izファイルをユーザーディレクトリのどこかに置くだけでインストールは完了する。
3izコンパイラ(広義)が担う各役割は以下になる。
(狭義の)コンパイラ: ソースコードをアセンブラにする（fasmでマシン語のユーザーrunファイルにする）
ローダー：ユーザrunファイルをメモリ上にロードする
動的リンカ：ユーザーrunファイルで動的callしているライブラリ関数を実行時にアドレス解決する。
ライブラリ：libc不使用の、オリジナルの共有ライブラリ。
低レイヤーを勉強したい者にとってとても大事なことだがユーザソース、ユーザアセンブリ、ユーザーrunファイルはほぼ同じサイズ感になることに、こだわっている。
見比べて対応付けながら、理解することが大事だからだ。
それでは、早速開発に入ろう。
まずは、ユーザーソースからコンパイルされて出力される実行runファイルについてだ。
このユーザrunファイルは、ソースコードと対応づけが簡単にでき全体像を把握しやすくするため、サイズを小さくしたい。
linuxが唯一サポートしているELFバイナリフォーマットと一般的に使われているgccではソースコードの227倍まで実行バイナリサイズが巨大になり途方にくれる。
信じられない？
gccでhello worldで確認してみよう。
$ cat gcc-hello.c
#include
int main(){
printf("hello world\n");
return 0;
}
$ gcc gcc-hello.c -o gcc-hello $ ./gcc-hello hello world
ここでソースコードとバイナリのサイズを確認してみよう。
$ wc -c gcc-hello.c 73 gcc-hello.c $ wc -c gcc-hello 16616 gcc-hello
gccでコンパイルするとバイナリサイズはなんと227倍に膨れ上がった。
次にアセンブラで記述してみよう
$ cat run.s
use64
;;write(int fd=stdout=1, char *buf=msg, int len=12byte)
mov rdi,1;第1引数 fd=stdout=1
lea rsi,[msg];第2引数 buf=msg
mov rdx,12; 第3引数 len=12
mov rax,1; write=1
syscall; systemcall呼び出し
ret
msg db "hello world",10,0; 10=\n。全部で12バイト。
$ fasm run.s run flat assembler version 1.73.22 (16384 kilobytes memory, x64) 2 passes, 43 bytes.
コメントを外したソースコードのサイズとバイナリのサイズを確認する
$ wc -c run.s 104 run.s $ wc -c hello 43 hello
これは素のマシン語ファイルでありELFヘッダがついていないので単純には比較できないが増えるどころかサイズが半分になっている。
さぁ、さっそく3izローダーの開発に入る。
素のマシン語のバイナリは単に先頭から実行すればいいだけなのだがlinuxカーネルは実行してくれない。
役割分担のところで紹介したローダーが必要だ。
かなり嫌だが、ELFバイナリフォーマットを使う必要がある。
苦労に苦労を重ねてexitとopen(readonly)を含めてELFヘッダ部分を76バイトまで圧縮した。世界最小だと思う。
ローダーの役割としては、mmapを使って、ファイルの内容をメモリにマッピングしている。
あとはcall raxのところで、メモリの先頭から実行しているだけだ。
$ cat 3iz.s use64 db 127,'ELF' readonly: ; edi=filename, ret rax fd xor esi,esi;readonly=0 mov rax,2;open=2 syscall ret dq 0x007a6933003e0003,0x10000004c,28,0,0x38000000000001 dw 1 exit: push 0; exit value dq 0x50f583c6a5f,0x50f583c6a5f;(exit実装の一部filesz=memsz) start:;;------ここまでELFヘッダ(76バイト)。 ;;ここから実行開始----- ;;引数からユーザーrunファイルを取得する pop rax;;引数の個数 cmp al,2;;引数１つならpop=2になる。 jne exit;;不一致なら終了する。 pop rax;;自分自身のファイル名いらない pop rdi;;引数指定された、ユーザーrunファイルをようやく入手 ;;【ローダー】 ユーザrunファイルの内容をメモリにロードする。 call mmap;;rdi=filename,ret rax=mem, rbx=filesize call rax;;先頭から実行する jmp exit;制御が返ってきたら強制終了;;---------------------------------- mmap: ;★ rdi=filename, ret rax=mem,rbx=filesize call fsize;;ret filesize=ebx call readonly mov r8,rax;; set fd xor edi,edi;;addr=0=any 2byte mov rsi,rbx;;restore file size=3byte push 7 pop rdx;rwx push 2 pop r10; PRIVATE=2 xor r9,r9;file offset=0 push 9 pop rax syscall ret;retを忘れないこと fsize:;;★ edi=filename, ret rbx enter 152,0;stat構造体=152byte lea rsi,[rbp-152]; push 4; stat systemcall pop rax syscall mov ebx,[rbp-152 +48];//48バイト目にファイルサイズ leave ret;retを忘れないこと
後述するが、fasmの出力先をPATHの通ったフォルダにする（例：~/bin)
$ fasm 3iz.s ~/bin/3iz $ chmod 755 ~/bin/3iz $ wc -c ~/bin/3iz 143 3iz
143バイトになった。このうち76バイトはELFなので仕方ない。
$ ~/bin/3iz ./run hello wolrd
ようやくこれでアセンブラで書かれた素のマシン語バイナリのhello worldが実行できた。
お気づきだと思うが、実行の仕方がjavaみたいだ。
$ ~/bin/3iz ./run
かっこ悪いので
$ ./run
とできるようにする。
当面正式採用するのは、root権限がなくても動くshebang（シバン）将来使うかもしれないroot権限が必要なbinfmt
を紹介する。
どちらもユーザーrun実行ファイルの先頭に決まった文字列を加えることで
$ ./run
と叩けば
$ ~/bin/3iz ./run
と裏で勝手にやってくれるという代物だ。
なんか、ELFに負けたように見えるが実はELFも実行ファイルなのに自分自身では実行できない。
もう一度いう。
ELFは実行ファイルなのに自分一人で実行できない
gccで作ったhello worldを見てみよう。ELFフォーマットだ。
$ strings gcc-hello | grep ld-linux /lib64/ld-linux-x86-64.so.2
としてみれば、隠されれているローダーが表示される。
$ /lib64/ld-linux-x86-64.so.2 ./gcc-hello hello world
話が逸れたがroot権限がない場合、#!(shebang)を使うしかない。
shellスクリプトの先頭に「#!/bin/sh」があるのはご存知だろう。
「#!」で始まるとそれ以降の絶対パスを実行してくれる。
この機能は設定が不要な代わりに実行ファイルの先頭にローダーのフルパスを記述しないといけない。
そのぶん、ちょっと長くなる上にスクリプトっぽくってかっこ悪いがroot権限なくても動くようにしたいのでしかたないことにする。
「#!/home/3iz/bin/3iz」というようにフルパスで指定しても動くが3izの置き場が変わると対応できなくなる。
そこで、他のスクリプトも採用しているが「#!/usr/bin/env 3iz+改行コード」とする。
こうすればenvコマンドがPATHから3izを見つけてくれて置き変わる。
$ ./run
と実行したときに、一瞬
$ /usr/bin/env 3iz ./run
となり
$ /home/3iz/bin/3iz ./run
最終的にこうなる。
binfmtを使う場合、拡張子やファイルの先頭の数バイト（マジックと呼ぶ）で判定してshebangと似たことをやってくれる。
3izのマジックを何にするかだが、当面shebangを使うが将来はbinfmtを使うと思う。
さきほど紹介したローダーのアセンブラのソースだとrunファイルの先頭から実行していたがshebangもしくはbinfmtを使うと先頭に余分な文字列が入る。
この文字列の直後から、マシン語が続く。
つまり、
shebangだと、#!/usr/bin/env 3iz\nbinfmtだとマジック
をスキップした、メモリアドレスから実行する必要がある。
shebangだろうがbinfmtだろうがローダー(3izコンパイラ)側のの処理を共通化しておきたい。
そこで、binfmtの際に使う、3izのマジックを改行コード(0x0a=10=\n)にしておく。
要は、先頭から改行コードがあるまでskipして、改行コードの次の場所から実行するロジックにしておく。
root権限が必要だがetc/binfmt.d/フォルダに、適当な名前の設定ファイルを作る。
$ cat /etc/binfmt.d/3iz.conf :3iz:M::\x0a::/usr/bin/3iz:
:適当な名前:M::マッチさせたい数バイト::起動させたいローダー:
というフォーマットだ。
16進の書き方がユニークだが、\x0aとする。(0x0a=10=\n)起動させたいローダーは/usr/bin/3izとする。
manに書いてあるが、systemd-binfmtを再起動させるとetc/binfmt.d/の設定ファイルを読み込んでくれる。
$ sudo systemctl restart systemd-binfmt
まずは、ユーザーrunファイルだ。先頭にshebangを追加した。将来binfmtにするなら10=\nだけになるがコメントアウトしている。
$ cat run.s use64 db "#!/usr/bin/env 3iz",10;当面shebangを使う(root権限不要) ;;db 10; 将来binfmtの場合はこちらを使う(root権限必要) ;;write(int fd=stdout=1, char *buf=msg, int len=12byte) mov rdi,1;第1引数 fd=stdout=1 lea rsi,[msg];第2引数 buf=msg mov rdx,12; 第3引数 len=12 mov rax,1; write=1 syscall; systemcall呼び出し ret msg db "hello world",10,0; 10=\n。全部で12バイト。
$ cat 3iz.s use64 db 127,'ELF' openreadonly: ; edi=filename, ret rax fd xor esi,esi;readonly=0 mov rax,2;open=2 syscall ret dq 0x007a6933003e0003,0x10000004c,28,0,0x38000000000001 dw 1 exit: push 0; exit value dq 0x50f583c6a5f,0x50f583c6a5f;(exit実装の一部filesz=memsz) start:;;------ここまでELFヘッダ(76バイト)。 ;;ここから実行開始----- ;;引数からユーザーrunファイルを取得する pop rax;;引数の個数 cmp al,2;;引数１つならpop=2になる。 jne exit;;不一致なら終了する。 pop rax;;自分自身のファイル名いらない pop rdi;;引数指定された、ユーザーrunファイルをようやく入手 ;;【ローダー】 ユーザrunファイルの内容をメモリにロードする。 call mmap;;rdi=filename,ret rax=mem, rbx=filesize ;;(binfmt/shebang共通対応)runファイルの先頭の改行まではskipして実行する mov rdi,rax;バイナリの先頭(rax=mmapの返り値)をrdi検索対象にセット push -1;無限ループ pop rcx push 10;改行コードを探す pop rax repne scasb;;alとedi比較してedi++。bは1byte。repne不一致なら繰り返す call rdi;;改行の次まできたので、ようやく実行する jmp exit;制御が返ってきたら強制終了;;---------------------------------- mmap: ;★ rdi=filename, ret rax=mem,rbx=filesize call fsize;;ret filesize=ebx call openreadonly mov r8,rax;; set fd xor edi,edi;;addr=0=any 2byte mov rsi,rbx;;restore file size=3byte add si,80;とりあえず関数置き場10個分固定で追加。 push 7 pop rdx;rwx push 2 pop r10; PRIVATE=2 xor r9,r9;file offset=0 push 9 pop rax syscall ret;retを忘れないこと fsize:;;★ edi=filename, ret rbx enter 152,0;stat構造体=152byte lea rsi,[rbp-152]; push 4; stat systemcall pop rax syscall mov ebx,[rbp-152 +48];//48バイト目にファイルサイズ leave ret;retを忘れないこと
それぞれコンパイルする。
$ fasm run.s run flat assembler version 1.73.22 (16384 kilobytes memory, x64) 2 passes, 62 bytes.
3izのは出力先を~/binにしていることに注意。
$$ fasm 3iz.s ~/bin/3iz flat assembler version 1.73.22 (16384 kilobytes memory, x64) 2 passes, 162 bytes.
runを直接実行するので実行権限をつける。
$ chmod 755 run ~/bin/3iz $ ./run hello world
ようやく、直接runファイルを実行することができた。
これまではユーザソース(run.s)にwriteシステムコールを記述して直接callしていたが個々のユーザソースにこれを書くのではなく共有ライブラリ(shared library)化する。
共有ライブラリは、3izローダーに含める。
実行runファイルから見ると別のファイルにあるまったく知らないところにある関数だ。これを呼び出す。
共有ライブラリにある外部関数を実行時に呼び出すことを動的呼び出し(dynamic call)と言う。
3izではアホみたいに簡単だ。
prints関数がどこにあるのか知らないのにcall qword[prints]でprints関数を呼び出している。
最終行にあるprints=$だが$はその時点のファイルの先頭からのバイト数だ。
つまり、このprintsはファイル末尾のバイト数を持っているだけだ。
物理ファイルの末尾より先に何もあるわけはない。このままでは当然エラーになる。
$ cat run.s use64 db "#!/usr/bin/env 3iz",10 lea rdi,[msg] call qword[prints] ret msg db "hello world",10,0; 10=\n。全部で12バイト。 prints=$
次に、3izローダーを見てみよう。
$ cat 3iz.s use64 db 127,'ELF' openreadonly: ; edi=filename, ret rax fd xor esi,esi;readonly=0 mov rax,2;open=2 syscall ret dq 0x007a6933003e0003,0x10000004c,28,0,0x38000000000001 dw 1 exit: push 0; exit value dq 0x50f583c6a5f,0x50f583c6a5f;(exit実装の一部filesz=memsz) start:;;------ここまでELFヘッダ(76バイト)。ここから実行開始----- ;;引数からユーザーrunファイルを取得する pop rax;;引数の個数 cmp al,2;;引数１つならpop=2になる。 jne exit;;不一致なら終了する。 pop rax;;自分自身のファイル名いらない pop rdi;;引数指定された、ユーザーrunファイルをようやく入手 ;;【ローダー】 ユーザrunファイルの内容をメモリにロードする。 call mmap;;rdi=filename,ret rax=mem, rbx=filesize ;;【動的リンカ】 共有ライブラリのアドレス解決をする。 lea rsi,[prints]; printsだけだとposition。leaでアドレス表現にする。 mov qword[rax+rbx],rsi;実行ファイル末尾(rax+rbx)の仮想アドレス置き場へ格納;;(binfmt/shebang共通対応)runファイルの先頭の改行まではskipして実行する mov rdi,rax;バイナリの先頭(rax=mmapの返り値)をrdi検索対象にセット push -1;無限ループ pop rcx push 10;改行コードを探す pop rax repne scasb;;alとedi比較してedi++。bは1byte。repne不一致なら繰り返す call rdi;;改行の次まできたので、ようやく実行する jmp exit;制御が返ってきたら強制終了;;------------------------------------- ;;【共有ライブラリ】 prints:;rdi=str 文字列表示 call strlen;ret edx=len mov rsi,rdi;buf push 1 pop rdi;stdout push 1 pop rax;write syscall ret;;------------------------------------ ;;以降は共有していない mmap: ;★ rdi=filename, ret rax=mem,rbx=filesize call fsize;;ret filesize=ebx call openreadonly mov r8,rax;; set fd xor edi,edi;;addr=0=any 2byte mov rsi,rbx;;restore file size=3byte add si,80;とりあえず関数置き場10個分固定で追加。 push 7 pop rdx;rwx push 2 pop r10; PRIVATE=2 xor r9,r9;file offset=0 push 9 pop rax syscall ret;retを忘れないこと strlen: ;★文字列長rdi=str, ret=edx push rdi;; ediはincされるので、バックアップ push -1 pop rcx xor eax,eax; 2byte repne scasb;; alとedi比較してedi++。bは1byte。repne不一致なら繰り返す not ecx; ecxが内部でマイナスされているので、プラスにする。 sub ecx,1;+1するとちょうどよい pop rdi; edi復活 mov edx, ecx; 文字列長をediで返す ret ;retを忘れないこと fsize:;;★ edi=filename, ret rbx enter 152,0;stat構造体=152byte lea rsi,[rbp-152]; push 4; stat systemcall pop rax syscall mov ebx,[rbp-152 +48];//48バイト目にファイルサイズ leave ret;retを忘れないこと
共有ライブラリとして、printsが実装されている。文字列長を数えるstrlenも非公開だが実装されている。
ポイントは動的リンカの部分だ。
mov qword[rax+rbx],rsiでraxには、3izローダーがメモリにロードしたrunファイルの先頭アドレスが入っている。同じくrbxにはファイルサイズが入っている。
つまり、rax+rbxは、物理ファイルではなくメモリ上でrunの末尾のアドレスを指している。
実は、こっそり、mmapの実装で8バイト×10個分として80バイト余分にメモリ確保するようにしておいた。
そこの先頭８バイトに、rsiの値を書き込んでいるわけだ。rsiには何が入っているのかというと１行前のlea rsi,[prints]の部分だ。
prints自体は、3izファイルの先頭からprints関数の実装までのバイト数が入っているだけだ。
当然、3izローダ自身もメモリ上にロードされている。
そのメモリアドレスの先頭からprintsバイト分だけ後ろのアドレスが、メモリ上にロードされたprintsの実装（マシン語）になるわけだ。
この計算をやってくれるのがlea命令だ。
結果として、rsiにはprints実装のメモリ上のアドレスが入っている。Cでいうところの関数ポインタになっている。
結局この値を、メモリ上のrunファイルの最後に書き込んでいる。
これらの作業により、runファイル上から、3iz上にあるprints関数を実行できることになる。
実行時に行われるのでこれを動的アドレス解決という。
$ cat run.s use64 db "#!/usr/bin/env 3iz",10 lea rdi,[msg] call qword[prints] ret msg db "hello world",10,0; 10=\n。全部で12バイト。 prints=$
runバイナリを見ると、#!/usr/bin/env 3iz\nで始まっている。最後に「hello world\n」があるが、物理的にはそれ以降は何もないことがわかる。
$ hexdump -vC run 00000000 23 21 2f 75 73 72 2f 62 69 6e 2f 65 6e 76 20 33 |#!/usr/bin/env 3| 00000010 69 7a 0a 48 8d 3d 07 00 00 00 ff 15 0e 00 00 00 |iz.H.=..........| 00000020 c3 68 65 6c 6c 6f 20 77 6f 72 6c 64 0a 00 |.hello world..| 0000002e
$ ./run hello world
3izではアセンブラの破壊力によって簡単に実現できた。
とりあえずやってみた