自作プログラミング言語にチャレンジし、挫折してしまったことがあるだろう。
最初に、javascriptでスクラッチ実装した、実際に動くコードを提示したい。これで、もう挫折することはなく、好きなように、独自プログラミング言語を、カスタマイズできるようになる。
カスタマイズできる手段を手に入れた後で、余裕をもって、インタプリタとコンパイラを自作するために必要な、字句解析、構文解析(パーサ)、抽象構文木(AST)、評価実行、コード生成を理解していこう。
最終的な応用として、プログラミング言語3izを開発していく。セルフホスティングされ、インタプリタでも動き、コンパイルもできるスクリプト言語だ。バイナリレベルの超低レイヤから再設計を行う。
自作インタプリタと自作コンパイラの作り方を解説するため、スクリプト言語を導入する。
この解説用スクリプト言語で書かれた、サンプルコードを提示しよう。
$ cat sample.code //--------独自プログラミング言語のサンプルコード---------- 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) ) //関数の引数内で、計算。
解説用のスクリプト言語の仕様を説明する。
コメントアウトは//を使う。
各文は、セミコロンで区切ることができる。
無くても動くようにしているが、セミコロンの有無で意味が異なるケースがあるので注意しよう。
数値については、整数、実数のどちらも扱う。
符号としてのマイナスが来てもいい。
足す、引く、掛ける、割るの四則演算が可能だ。整数、実数を混在してもいい。
さらに、丸カッコ()による、優先処理も可能だ。
文字列は、ダブルクオーテーション""で括る。
文字列に対して、プラス演算子を使うことで、文字列を連結することができる。
変数は、すべてグローバル変数だ。
組み込み関数として、printのみ設定している。これは、引数に指定された、変数、文字列、数値などを表示する。
関数呼び出しする際に、引数が複数あったり、引数内で、変数参照や計算があったりしても問題ない。
独自プログラミング言語の自作入門なので、
変数の型や、配列やオブジェクトなどのデータ構造、関数定義、if/whileなどの制御処理は、
組み込んでいない。
解説用のスクリプト言語仕様のまま、インタプリタを自作したので、コードを紹介する。
細かい解説は後ほど行うが、たったこれだけのコードで、スクリプト言語のインタプリタは動いているのだ。
プログラミング言語を自作することは、とても簡単なことが分かってもらえるはずだ。
このインタプリタは、javascript(node.js)で、ツールやライブラリは使わずに、フルスクラッチで実装した。
といっても、コード量は多くない。たったこれだけだ。
可読性が悪くなるので、エラーチェックは、敢えてやっていない。
プログラミング言語の作り方が理解できたら、やればいい。
あとで、嫌というほど、解説するので、今すぐに、理解する必要はない。
$ cat interpreter.js #!/usr/bin/env node //------ソースコード------// var sample = require('fs').readFileSync("sample.code","utf-8"); console.log("----------------ソースコード-----------------\n"+sample); //------自作字句解析------// var tokens = sample.split(/\/\/.*$|(".*?"|\d+(?:\.\d+){0,1}|\w+)|\s|(.)/m).filter(a=>a); console.log("------------字句解析結果(tokens)-------------\n"); console.log(tokens); //------自作構文解析------// //構文解析パーサで使う演算子の優先順位 var pris = [ {z:1,ops:[]},//セミコロン省略演算子 {z:2,ops:[";"]},//セミコロン演算子 {z:2,ops:[","],},//カンマ演算子 {ops:["="]},//代入演算子 {ops:["+","-"]},//二項演算子(加減算) {ops:["*","/"]},//乗算、除算演算子 {z:3,ops:["+","-"]},//単項演算子(符号から始まる) {z:4,ops:["("]},//二項演算子(関数呼び出し) {z:5,ops:["("]},//前置単項演算子(カッコから始まる) ]; //自作構文解析(パーサ)の処理 <再帰下降法> function parser(t,p=0){ var z = pris[p]&&pris[p].z?pris[p].z:0;//優先度pの処理方法 var ops = pris[p]&&pris[p].ops;//優先度pの演算子の配列 if(p==pris.length) return t.shift();//最上位ならそのまま返す 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) 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:{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; } } var ast = parser(tokens); console.log("----------構文解析(パーサ)の結果<抽象構文解析木(AST)>-----------\n"+require("util").inspect(ast,{depth:null})); //組み込み関数 var libs = {}; //print関数 libs["print"]= a=>console.log(Array.isArray(a)?a.join(""):a); //------グローバル変数置き場------// var env = {}; //------AST評価実行(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); //leftがあるなら２項演算子。無いなら単項演算子 if(ast.op == '+') return ast.left?run(ast.left) + run(ast.right):run(ast.right); if(ast.op == '-') return ast.left?run(ast.left) - run(ast.right):-run(ast.right); } //演算子ないなら、バリューにする if(ast[0]=='"') return ast.slice(1,-1);//""を捨てる if(ast[0].match(/^\d+$/)) return 1 * ast;//文字→数字 return env[ast];//定義済み変数なら値を返す。 } //評価実行 console.log("----------------評価実行の結果-----------------"); run(ast); //処理後のグローバル変数 console.log("-----------処理後のグローバル変数------------"); console.log("env=",env);
ブラウザが無くても動くjavascriptである、node.jsを使う。
パッケージマネージャーでインストールすると古いことが多い。
node.jsの最新版を、公式webサイトからインストールしておこう。
から、最新版Linux Binaries (x64)のURLをコピーしよう。
コマンドラインから、適当な場所(/tmp)移動。
$ cd /tmp
URLを指定してダウンロードする。
$ curl -O https://nodejs.org/dist/バージョン番号/node-バージョン番号-linux-x64.tar.xz
ファイルを解凍する。
$ tar Jxf node-バージョン番号-linux-x64.tar.xz
インストール先(~/bin)がなければ作り、nodeという１ファイルだけをコピーする。
$ mkdir -p ~/bin $ cp node-バージョン番号-linux-x64/bin/node ~/bin/
~/binにパスが通ってないなら通しておく。
$ echo 'PATH=$HOME/bin/:$PATH' >> ~/.bashrc $ source ~/.bashrc
$ node -v $ バージョン番号
バージョンが表示されればインストール完了だ。
さっそく、仮の独自プログラミング言語のインタプリタを実行してみよう。
$ chmod 755 interpreter.js $ ./interpreter.js ----------------ソースコード----------------- //--------独自プログラミング言語のサンプルコード---------- 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) ) //関数の引数内で、計算。 ------------字句解析結果(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: { op: '-', right: '5' } }, { op: '+', right: '2' } ], { left: 'b', op: '=', right: '7.62' }, { left: 'f', op: '=', right: { left: { left: { 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: { op: '-', right: '2' }, op: '*', right: { left: { op: '-', right: 'a' }, op: '+', right: '1' } } ] } ] ] ----------------評価実行の結果----------------- hello world f = 40.74 -2*(-a+1) = -12 -----------処理後のグローバル変数------------ env= { str1: 'hello', str2: 'world', a: -5, b: 7.62, f: 40.74 }
オレンジの評価実行の結果を見てほしい。
"hello"と" "と"world"を、文字列連結演算子で、連結してできた、hello worldが表示されている。
それだけなく、変数を使った実数の演算も行い、ちゃんと結果が表示されている。
つまり、仮の独自プログラミング言語の仕様に則った、インタプリタが、ちゃんと動いていることが、分かってもらえると思う。
解説用のスクリプト言語用のコンパイラを自作したので、コードを紹介する。
コンパイラは、別の言語（アセンブリ言語）へ翻訳する。アセンブリ言語の知識が、必要になってくる。
コンパイラの細かい解説は後ほど行う。
アセンブリ言語の出力を行うので、その分長くなっているが、javascriptのコード自体は、とても短い。
たったこれだけのコードで、スクリプト言語のコンパイラは動いているのだ。
プログラミング言語を自作することは、とても簡単なことが分かってもらえるはずだ。
$ cat compiler.js #!/usr/bin/env node //------ソースコード------// var sample = require('fs').readFileSync("sample.code","utf-8"); console.log("----------------ソースコード-----------------\n"+sample); //------自作字句解析------// var tokens = sample.split(/\/\/.*$|(".*?"|\d+(?:\.\d+){0,1}|\w+)|\s|(.)/m).filter(a=>a); console.log("------------字句解析結果(tokens)-------------\n"); console.log(tokens); //------自作構文解析------// //構文解析パーサーで使う演算子の優先順位 var pris = [ {z:1,ops:[]},//セミコロン省略演算子 {z:2,ops:[";"]},//セミコロン演算子 {z:2,ops:[","],},//カンマ演算子 {ops:["="]},//代入演算子 {ops:["+","-"]},//二項演算子(加減算) {ops:["*","/"]},//乗算、除算演算子 {z:3,ops:["+","-"]},//単項演算子(符号から始まる) {z:4,ops:["("]},//二項演算子(関数呼び出し) {z:5,ops:["("]},//前置単項演算子(カッコから始まる) ]; //自作構文解析(パーサー)の処理 <再帰下降法> function parser(t,p=0){ if(p==pris.length) return t.shift();//最上位ならそのまま返す var z = pris[p]&&pris[p].z?pris[p].z:0;//優先度pの処理方法 var ops = pris[p]&&pris[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) 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; } } var ast = parser(tokens); console.log("----------構文解析(パーサ)の結果<抽象構文解析木(AST)>-----------\n"+require("util").inspect(ast,{depth:null})); //アセンブラコード出力用元情報 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\n"); return 1;//数値を意味する } if(ast.op == '/'){ gen(ast.left); gen(ast.right); codes.push("pop10"); codes.push("divsd xmm0,xmm1"); codes.push("push0\n"); 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\n"); return 1;//数値を意味する }else{ //文字列連結 codes.push("pop rsi"); codes.push("pop rdi"); codes.push("call newcat"); codes.push("push rax\n"); return 0;//文字列 } } if(ast.op == '-'){ gen(ast.left); gen(ast.right); codes.push("pop10"); codes.push("subsd xmm0,xmm1"); codes.push("push0\n"); return 1;//数値を意味する } } //演算子ないなら、バリューにする if(globals.includes(ast)){//定義済み変数だったら if(types[ast]==1){//実数が代入されている codes.push("movsd xmm0,["+ast+"]"); codes.push("push0\n"); 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\n"); return 1;//数値を意味する } return 0; } //アセンブリコード生成 gen(ast); asmgen(); function asmgen(){ var asm=` .intel_syntax noprefix .global _start `; //マクロ定義 asm +=` .macro push0 enter 8,0 movsd [rsp],xmm0 #push left push result .endm .macro push1 enter 8,0 movsd [rsp],xmm1 #push right .endm .macro pop1 movsd xmm1,[rsp] # pop right leave .endm .macro pop0 movsd xmm0,[rsp] # pop left leave .endm .macro pop10 pop1 pop0 .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 call exit `; require("fs").writeFileSync("sample.s",asm); console.log("-------------アセンブリコード生成(テキスト)-----------"); console.log(asm); } exec=c=>require("child_process").execSync(c);//外部コマンド実行用 console.log("------アセンブラ(asコマンド)で、アセンブリをオブジェクトへ---------"); console.log("as sample.s -o sample.o"); exec("as sample.s -o sample.o"); console.log("------リンカ(ldコマンド)で、オブジェクトを実行ファイルへ------"); console.log("ld --dynamic-linker /lib64/ld-linux-x86-64.so.2 -lc -o sample sample.o"); exec("ld --dynamic-linker /lib64/ld-linux-x86-64.so.2 -lc -o sample sample.o");
$ chmod 755 compiler.js
$ ./compiler.js ----------------ソースコード----------------- //--------独自プログラミング言語のサンプルコード---------- 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) ) //関数の引数内で、計算。 ------------字句解析結果(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' } } ] } ] ] -------------アセンブリコード生成(テキスト)----------- .intel_syntax noprefix .global _start .macro push0 enter 8,0 movsd [rsp],xmm0 #push left push result .endm .macro push1 enter 8,0 movsd [rsp],xmm1 #push right .endm .macro pop1 movsd xmm1,[rsp] # pop right leave .endm .macro pop0 movsd xmm0,[rsp] # pop left leave .endm .macro pop10 pop1 pop0 .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 #別メモリを確保して連結する 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 .s1: .string "hello" .s2: .string "world" .s3: .string " " .s4: .string "f = " .s5: .string "-2*(-a+1) = " .d0: .double 0 .d5: .double 5 .d2: .double 2 .d7.62: .double 7.62 .d0.9: .double 0.9 .d12.21: .double 12.21 .d3: .double 3 .d1: .double 1 .comm str1,8 .comm str2,8 .comm a,8 .comm b,8 .comm f,8 _start: lea rax,[.s1] push rax pop rax mov str1,rax lea rax,[.s2] push rax pop rax mov str2,rax movsd xmm0, .d0 push0 movsd xmm0, .d5 push0 pop10 subsd xmm0,xmm1 push0 pop0 movsd a,xmm0 movsd xmm0, .d0 push0 movsd xmm0, .d2 push0 pop10 addsd xmm0,xmm1 push0 movsd xmm0, .d7.62 push0 pop0 movsd b,xmm0 movsd xmm0, .d0 push0 movsd xmm0, .d0.9 push0 pop10 subsd xmm0,xmm1 push0 movsd xmm0, .d12.21 push0 pop10 addsd xmm0,xmm1 push0 movsd xmm0, .d3 push0 movsd xmm0,[a] push0 movsd xmm0,[b] push0 movsd xmm0, .d2 push0 pop10 divsd xmm0,xmm1 push0 movsd xmm0, .d1 push0 pop10 addsd xmm0,xmm1 push0 pop10 subsd xmm0,xmm1 push0 pop10 mulsd xmm0,xmm1 push0 pop10 subsd xmm0,xmm1 push0 pop0 movsd f,xmm0 mov rax,str1 push rax lea rax,[.s3] push rax pop rsi pop rdi call newcat push rax mov rax,str2 push rax pop rsi pop rdi call newcat push rax pop rsi prints printn lea rax,[.s4] push rax pop rsi prints movsd xmm0,[f] push0 pop0 printd printn lea rax,[.s5] push rax pop rsi prints movsd xmm0, .d0 push0 movsd xmm0, .d2 push0 pop10 subsd xmm0,xmm1 push0 movsd xmm0, .d0 push0 movsd xmm0,[a] push0 pop10 subsd xmm0,xmm1 push0 movsd xmm0, .d1 push0 pop10 addsd xmm0,xmm1 push0 pop10 mulsd xmm0,xmm1 push0 pop0 printd printn mov rdi,0 call exit ------アセンブラ(asコマンド)で、アセンブリをオブジェクトへ--------- as sample.s -o sample.o ------リンカ(ldコマンド)で、オブジェクトを実行ファイルへ------ ld --dynamic-linker /lib64/ld-linux-x86-64.so.2 -lc -o sample sample.o
$ ./sample hello world f = 40.74 -2*(-a+1) = -12
字句解析の自作方法を入門レベルで解説する。
解説用のスクリプト言語で書かれた、サンプルコードには、改行コードはあるものの、１つの長い文字列だと、考えて欲しい。
インタプリタの実行結果の途中に、字句解析結果(tokens)を表示しておいた。抜き出すと、以下の部分になる。
------------字句解析結果(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', ')',
')'
]サンプルコードの長い文字列から、コメントや、空白改行などを捨ててしまい、必要なものだけ残して、いい感じに分割して、文字列の配列にしただけだ。
字句解析とは、長い文字列を分割して文字列の配列にすると捉えれば十分だ。
字句解析の難しい理論は忘れていい。
文字列が、文字列の配列になったという
データ変換イメージを持つことがとても大事だ。
実際の自作インタプリタのjavascriptのコードの中で、字句解析の処理は、正規表現を使ってはいるが、たった１行で済むくらい簡単な話だ。
var tokens = sample.split(/\/\/.*$|(".*?"|\d+(?:\.\d+){0,1}|\w+)|\s|(.)/m).filter(a=>a);あまりにもあっけない。
ついでなので、各正規表現について説明しておく。
\/\/.*$
\/\/は、\でエスケープしてあるが、//のコメントアウトのことだ。$は末尾のことなので、.*$で末尾までの文字列を意味する。
つまり、//で始まって行末までにマッチし、これを捨てている。
残すか捨てるかは、()で括っているかどうかだ。
".*?"
これは、"で始まって、"で終わる任意の文字、つまり文字列"hello"とかのことだ。
「.*」だと、
str1="hello" str2="world"
のように、長くマッチしてしまう。
「.*?」のように?をつけていれば
str1="hello" str2="world"
短くマッチしてくれる。
\d+(?:\.\d+){0,1}これは、数字だ。
\d+は数字の連続だ。\.は小数点で、その後に\d+で、数字の連続となっている。
(?: )の部分は、グループ化だ。要は小数点以下のカタマリを表している。
{0,1}は、0以上1回以下の繰り返し、つまり、小数点以下のカタマリが１回あっても、なくもていいということだ。
\w+
\w+は英数字の連続。つまり、printとかstr1とかだ。
\s
\sは、空白や改行のことだ。これは()で括っていないので、捨てられる。
.
最後に.は任意の１文字だ。結果的に丸カッコなどの記号とかがマッチする。
長くなったが、
字句解析は、文字列分割だ。
次は、構文解析の作り方を解説する。
構文解析(パーサ)の自作方法を入門レベルで解説する。
パーサーの処理の解説の前に、インプットとアウトプットを確認しておこう。
インプットは、字句解析の結果で、以下のような、文字列の配列だった。
------------字句解析結果(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: { op: '-', right: '5' } },
{ op: '+', right: '2' }
],
{ left: 'b', op: '=', right: '7.62' },
{
left: 'f',
op: '=',
right: {
left: { left: { 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: { op: '-', right: '2' },
op: '*',
right: { left: { op: '-', right: 'a' }, op: '+', right: '1' }
}
]
}
]
]とても重要なことだが、構文解析(パーサ)は、
配列を、階層構造に変換するだけだ。
忘れないでほしい。
この階層構造を抽象構文木(AST)と呼ぶ。
構文解析(パーサ)は、トークン配列を、抽象構文木(AST)に変換しているだけだ。
インプットとアウトプットの再確認ができたところで、構文解析(パーサ)のjavascript実装部分を見てみよう。
１つめは、解説用のスクリプト言語の、言語仕様ルール(演算子の優先度)だ。
パーサー本体(parser関数)に直接記述せずに、外部の配列(pris)にルールを定義することで、汎用性を持たせている。
あとから、異なる挙動をするようにカスタマイズしやすいからだ。
//------自作構文解析------// //構文解析パーサで使う演算子の優先順位 var pris = [ {z:1,ops:[]},//セミコロン省略演算子 {z:2,ops:[";"]},//セミコロン演算子 {z:2,ops:[","],},//カンマ演算子 {ops:["="]},//代入演算子 {ops:["+","-"]},//二項演算子(加減算) {ops:["*","/"]},//乗算、除算演算子 {z:3,ops:["+","-"]},//単項演算子(符号から始まる) {z:4,ops:["("]},//二項演算子(関数呼び出し) {z:5,ops:["("]},//前置単項演算子(カッコから始まる) ];
上の方が優先度が低く、下の方が優先度が高い。加減算(+、-)よりも乗除算(*と/)の方が強い。
同じ優先度を持った演算子は、演算子配列(ops)の中でまとめてある。
+と-、が２箇所あるが、これは、-aなどの符号のマイナスと、減算のマイナスだ。
(も２つあるが、関数呼び出しのカッコと計算で優先したい部分を括るカッコを分けている。
zは、細かい処理を切り替えるための値だ。今は気にしないで欲しい。
次に、２つ目の構文解析パーサ本体だ。
オレンジで色が、parser関数のメイン部分だ。
//自作構文解析(パーサ)の処理 <再帰下降法> function parser(t,p=0){ if(p==pris.length) return t.shift();//最上位ならそのまま返す var z = pris[p]&&pris[p].z?pris[p].z:0;//優先度pの処理方法 var ops = pris[p]&&pris[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) t.shift(); list.push(parser(t,p+1));//配列にしておく } 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:{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; } }
zの値で、細かい処理を分けているが、アウトプットのASTの形を変えたかったからだ。
メイン部分のみ抜き出して、わかりやすく書き換えると、以下のようになる。
function parser(t,p=0){
if(p==pris.length) return t.shift();
var ops = pris[p]&&pris[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は演算子の優先度を表している。pris配列の添字だ。つまり、pの値によって現在、どの演算子を処理の対象にしているのかを区別している。初期値はゼロだ。
次は、優先度pがprisの配列を超えたら、どの演算子にもマッチしなかったことになる。
要は、これ以上階層構造にする必要がないので、トークン配列の先頭の値をそのまま返している。
if(p==pris.length) return t.shift();
これは、pris配列からp番目のopsを取り出しているだけだ。
var ops = pris[p]&&pris[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};
}まず、階層データ構造である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になって欲しいかというサンプルをクドいくらいに、たくさん見ていこう。
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}} ]のように同じデータ構造にする。
さて次は、作成されたASTを、解釈実行していこう。
構文解析の実装が終わったので独自プログラミング言語向けに、実行処理の実装に移る。
構文解析のアウトプットとして、抽象構文木ASTができている。
この抽象構文木ASTはどんな作り方をしても良いが深いところを先に処理してもらうように作成したので、そのとおりに実行する必要がある。
つまり、深さ優先探索して、演算子などの指示にしたがって実行していけばいいだけだ。
//------実行(木構造を深さ優先探索しながらノードごとに実行)------// function run(t){ //配列は各要素を評価して、配列で返す。 if(Array.isArray(t)) return t.map(e=>run(e)); if(t.op){//演算子あり if(t.op == '=') return env[t.left] = run(t.right); if(t.op == '()') return libs[t.left](run(t.right));//関数呼び出し if(t.op == '*') return run(t.left) * run(t.right); if(t.op == '/') return run(t.left) / run(t.right); //leftがあるなら２項演算子。無いなら単項演算子 if(t.op == '+') return t.left?run(t.left) + run(t.right):run(t.right); if(t.op == '-') return t.left?run(t.left) - run(t.right):-run(t.right); } //演算子ないなら、バリューにする if(t[0]=='"') return t.slice(1,-1);//""を捨てる if(t[0].match(/^\d+$/)) return 1 * t;//文字→数字 return env[t];//定義済み変数なら値を返す。 }
その際、変数などを保管するエリアを用意しておく。
//------グローバル変数置き場------//
var env = {};抽象構文木ASTの探索が終わるまで流用し続けれればグローバル変数になる。
//アセンブラコード出力用元情報 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\n"); return 1;//数値を意味する } if(ast.op == '/'){ gen(ast.left); gen(ast.right); codes.push("pop10"); codes.push("divsd xmm0,xmm1"); codes.push("push0\n"); 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\n"); return 1;//数値を意味する }else{ //文字列連結 codes.push("pop rsi"); codes.push("pop rdi"); codes.push("call newcat"); codes.push("push rax\n"); return 0;//文字列 } } if(ast.op == '-'){ gen(ast.left); gen(ast.right); codes.push("pop10"); codes.push("subsd xmm0,xmm1"); codes.push("push0\n"); return 1;//数値を意味する } } //演算子ないなら、バリューにする if(globals.includes(ast)){//定義済み変数だったら if(types[ast]==1){//実数が代入されている codes.push("movsd xmm0,["+ast+"]"); codes.push("push0\n"); 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\n"); return 1;//数値を意味する } return 0; } //アセンブリコード生成 gen(ast); asmgen(); function asmgen(){ var asm=` .intel_syntax noprefix .global _start `; //マクロ定義 asm +=` .macro push0 enter 8,0 movsd [rsp],xmm0 #push left push result .endm .macro push1 enter 8,0 movsd [rsp],xmm1 #push right .endm .macro pop1 movsd xmm1,[rsp] # pop right leave .endm .macro pop0 movsd xmm0,[rsp] # pop left leave .endm .macro pop10 pop1 pop0 .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 call exit `; require("fs").writeFileSync("sample.s",asm); console.log("-------------アセンブリコード生成(テキスト)-----------"); console.log(asm); }
$ as sample.s -o sample.o
$ ld --dynamic-linker /lib64/ld-linux-x86-64.so.2 -lc -o sample sample.o
自作する独自プログラム言語は、3izと呼ぶことにする。
これまで、説明してきたのはプログラミング言語仕様、つまり、ルールだ。
これから解説するのは、どう実装するかであり、これを処理系と呼ぶ。
ルールである言語仕様とどう実装するかの処理系は独立しているので、
１つの言語仕様を、インタプリタとコンパイラのどちらでも実装可能だ。
つまり、
なんてことも可能だ。
今後の解説では、１つの同じプログラミング言語仕様に対して、インタプリタとコンパイラの両方の処理系を実装することにする。
インタプリタとコンパイラの実装するプログラミング言語として、簡単で実現力のあるjavascriptを用いる。
というイメージがあるかもしれないが、それは誤解だ。
プログラミング言語の作り方は本来は簡単であるにもかかわらず、
のどちらかに偏っている傾向がある。
実際に、独自プログラミング言語を自作してみて、一般的ないろんな説明と、実態が食い違っていることに気づいた。
つまり、入門レベルの比喩的な解説は最初は分かりやすいのだろうが、誤解を生じさせたままになる。
それらの誤解を解くために、難解な理論解説を読んで勉強するが、当然、理解できないまま挫折してしまうため、誤解を解くことには繋がらない。
つまり、いろんな誤解が存在したまま、変なイメージが刷り込まれている。
今後の解説では、難解な理論解説は行わない。
まず、やりことを整理し、それを簡単な実装で提示する。
要は、見れば分かるレベルで簡単に理解することができる。
こうして、事実が明らかになっていくにつれ、
など、と誤解が解けていけば幸いだ。
プログラミング言語自体は定義であり、どう実装するかの処理系とは異なる。
プログラミング言語定義としてはjavascriptなどのスクリプト言語や関数型プログラミングのように、やりたいことだけを、短く直感的に記述でき、あれ？もうできたの？としたい。つまり実現力を重要視したい。
その上で、C/C++/javaなどの厳格なプログラミング言語のように、静的なチェックを充実させ、ゆるゆるなプログラミング言語にはない強力なサポート力を実現する。
さらに、アセンブラの知識が必要になるがマシン語にコンパイルできるようすることで高速処理を実現する。
そのため、プログラミング言語の処理系としては、インタプリタやコンパイラの両方について実装した上で、いいとこ取りで融合させていく。最終的には、独自プログラミング言語自身で作り変えるセルフホスティングを行うことで独自プログラミング言語を開発する上でも、既存プログラミング言語の不満を抱えなくて済むようにしたい。
自作プログラミング言語を作る前に、設計コンセプトを整理しよう。
具体的な機能というより、方向性だ。
また、プログラミング言語、インタプリタ、コンパイラの違いや当面の利用する開発言語についても述べる。
独自のプログラム言語3izをどんな言語にするか考える。
具体的な機能というよりも、コンセプトだ。
普段、プログラムを作るフェーズとしては
がある。
開発初期フェーズでは、バグの有無ではなく
が重要だ。
何でもかんでもダメだダメだと小うるさく制限する言語だと、やりたいアイデアを思うように実装できずせっかくのアイデアがボツになってしまう原因になり開発初期フェーズには向かない。
開発の中盤フェーズでは
など使い勝手がわるい。
かといってまだまだ開発の中盤では
諸刃の剣になりかねない。
一方で開発の終盤フェーズでは
と言ったことが気になる。
そこで自作する3iz言語は
というように
各フェーズごとに異なる目的や要望に合わせて柔軟にかつ、１つの言語仕様のままで、シームレスに応えてくれる言語にしたい。
最初はスクリプトで記述し、途中で別言語に書き換えてコンパイルするなんてやりたくない。
まぁ、
である。
プログラミング言語自体は、ルール(言語仕様)だ。
言語仕様は、
というのを理解してほしい。
などは、言語仕様と、どう実装するかの処理系を、ごっちゃ混ぜにした、よくある誤解だ。
と言えば、違いが分かってもらえるはずだ。
狭義のコンパイラは、
機能しかない。
アセンブリ言語をマシン語に変換するのは別のプログラム（アセンブラ）が必要だ。
実は、アセンブラが出力した素のマシン語はそのままでは動かない。
別途、実行してくれるプログラム（ローダー）が必要になる。このローダーは、カーネル処理も含めて、ある意味インタプリタだ。
C言語で出力したバイナリはインタプリタで動いていると言えば伝わるはずだ。
javaのVMなんかがイメージしやすい。
マシン語を実行するCPUも、広義のインタプリタでと考えることもできるだろう。
要は
コンパイラは、翻訳をするだけでプログラムを実行できない
のだ。
インタプリタは
翻訳なんかせずにそのまま実行までやってしまう
のだ。
今は、何を言っているのかわからないかもしれないが、今後、プログラミング言語の開発を進めていけばこの違いを、無理なく理解してもらえると思う。
最終的な言語仕様として3izのコンセプトはあるものの最終目標であり、いきなり、難しいものを作るのは得策ではない。
そこでまずはアセンブリ言語を使う必要がなく簡単なインタプリタ形式で実装し、レベルを高めてから後から、面倒なコンパイラ形式でも実装する。
つまり最終的には、同じソースコード（言語仕様）を、インタプリタ形式でもコンパイラ形式でも動かせるようにするわけだ。
言語仕様的にゆるい記述も硬い記述もどちらも選択できるようにしておけばシームレス化を図ることができ当初の設計コンセプトを達成できると思う。
以上のような、アプローチを取ろうと思う。
さっそく、インタプリタ形式で、実装する。
ガチの低レイヤでの再設計アセンブラは、アセンブリ言語のコンパイラだが、それを使うだけでは、規定の低レイヤのままであり好みの言語仕様を実現できない。自作プログラミング言語を自作するにあたり、独自バイナリフォーマット、独自ローダーを、独自動的リンクなど、ガチの低レイヤから再設計する。
アセンブラとしてflat assembler(fasm)を使う。
linux用をダウンロードしてほしい。
fasm.x64という実行ファイルひとつをPATHの通った場所(例~/bin)にコピーする。
fasm.x64では打ちにくいのでfasmという名前に変えよう。
その他のファイルはなくても動く。こういうワンバイナリで動く、シンプルな構成がすばらしい。
$ tar zxvf fasm-(バージョン番号).tgz $ cp fasm/fasm.x64 ~/bin/fasm $ fasm flat assembler version 1.73.22 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
ちなみに、gccが裏で使っているGNU assembler(gas)やldだと、後述する巨大なELFバイナリとなるので使わない。
javascriptやCのようなヘルプしてくれる別プログラミング言語を使わずにアセンブラのみで実装する。ついでに、バイナリフォーマットから見直すガチの低レイヤに挑む。
アセンブラだと移植性が気になるかもしれない。
linuxしか使わないので、他OSへの移植性は不要だ。
コンパイル済みのバイナリのまま配布したいこともあるだろうしバイナリを別マシンにコピーしてすぐに動かしたい。p当然、root権限のないレンタルサーバー環境でも動くようにしたい。
linux 64bit OSなら、ほとんどの環境がx86_64(intel x64/amd64)だろう。
つまり、基本的にはコンパイル済みのバイナリを別のマシンに持っていっても動く。
ただし、sharedライブラリのバージョンが違うなど環境によっては動かない可能性が出てくる。
そこで、libcなども含めて、他ライブラリに依存しない構成にする。
単純に、staticコンパイルしてワンバイナリ化するとユーザバイナリが無駄にでかくなるので独自の3iz共有ライブラリを用意する。
この際なので、実行ファイル側のユーザrunファイルを独自の3izフォーマットにして、極限までサイズを切り詰める。
つまり、
の２ファイル構成にする。
２ファイル構成について、全体像を具体的に説明しよう。
ユーザソースをコンパイルして実際に実行されるまでの流れを下記画像にまとめたので見てほしい。
１つ目は、ブルーの部分だ。
3iz言語で記述されたユーザーが書くソースコードをコンパイルして出力されたアセンブリ言語をfasmでマシン語にしたバイナリファイルだ。
これをユーザーrunファイルと呼ぶことにする。
$ ./run
とすれば実行できるファイルだ。
２つ目は、オレンジの部分だ。
広義の意味で、3izコンパイラ呼ぶ。
これは、（狭義の）コンパイラ兼ライブラリ兼動的リンカ兼ローダーの役割があるが、１つの実行ファイルになっている。
つまり、この3izファイルをユーザーディレクトリのどこかに置くだけでインストールは完了する。
3izコンパイラ(広義)が担う各役割は以下になる。
低レイヤーを勉強したい者にとってとても大事なことだがユーザソース、ユーザアセンブリ、ユーザーrunファイルはほぼ同じサイズ感になることに、こだわっている。
見比べて対応付けながら、理解することが大事だからだ。
それでは、早速開発に入ろう。
まずは、ユーザーソースからコンパイルされて出力される実行runファイルについてだ。
このユーザrunファイルは、ソースコードと対応づけが簡単にでき全体像を把握しやすくするため、サイズを小さくしたい。
linuxが唯一サポートしているELFバイナリフォーマットと一般的に使われているgccではソースコードの227倍まで実行バイナリサイズが巨大になり途方にくれる。
信じられない？
gccでhello worldで確認してみよう。
$ cat gcc-hello.c #includeint 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
とできるようにする。
を紹介する。
どちらもユーザー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だろうがbinfmtだろうがローダー(3izコンパイラ)側のの処理を共通化しておきたい。
そこで、binfmtの際に使う、3izのマジックを改行コード(0x0a=10=\n)にしておく。
要は、先頭から改行コードがあるまでskipして、改行コードの次の場所から実行するロジックにしておく。
binfmtの詳細はmanに書いてある。
$ man binfmt.d
BINFMT.D(5) binfmt.d BINFMT.D(5)
NAME
binfmt.d - Configure additional binary formats for executables at boot
SYNOPSIS
/etc/binfmt.d/*.conf
/run/binfmt.d/*.conf
/usr/lib/binfmt.d/*.conf
DESCRIPTION
At boot, systemd-binfmt.service(8) reads configuration files from the
above directories to register in the kernel additional binary formats for
executables.
CONFIGURATION FORMAT
Each file contains a list of binfmt_misc kernel binary format rules.
Consult the kernel's binfmt-misc.rst[1] documentation file for more
information on registration of additional binary formats and how to write
rules.
Empty lines and lines beginning with ; and # are ignored. Note that this
means you may not use ; and # as delimiter in binary format rules.
CONFIGURATION DIRECTORIES AND PRECEDENCE
Configuration files are read from directories in /etc/, /run/, and
/usr/lib/, in order of precedence. Each configuration file in these
configuration directories shall be named in the style of filename.conf.
Files in /etc/ override files with the same name in /run/ and /usr/lib/.
Files in /run/ override files with the same name in /usr/lib/.
Packages should install their configuration files in /usr/lib/. Files in
/etc/ are reserved for the local administrator, who may use this logic to
override the configuration files installed by vendor packages. All
configuration files are sorted by their filename in lexicographic order,
regardless of which of the directories they reside in. If multiple files
specify the same option, the entry in the file with the lexicographically
latest name will take precedence. It is recommended to prefix all
filenames with a two-digit number and a dash, to simplify the ordering of
the files.
If the administrator wants to disable a configuration file supplied by the
vendor, the recommended way is to place a symlink to /dev/null in the
configuration directory in /etc/, with the same filename as the vendor
configuration file. If the vendor configuration file is included in the
initrd image, the image has to be regenerated.
EXAMPLE
Example 1. /etc/binfmt.d/wine.conf example:
# Start WINE on Windows executables
:DOSWin:M::MZ::/usr/bin/wine:
SEE ALSO
systemd(1), systemd-binfmt.service(8), systemd-delta(1), wine(8)
NOTES
1. binfmt-misc.rst
https://www.kernel.org/doc/html/latest/admin-guide/binfmt-misc.html
systemd 239 BINFMT.D(5)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ではアセンブラの破壊力によって簡単に実現できた。