javascript/C言語/アセンブラを用い、 字句解析、構文解析、インタプリタ、コンパイラのプログラムをスクラッチから作りながら、 「プログラミング言語の作り方」を解説する。
構文解析と実行を分離する。
構文解析のアウトプットとして、抽象構文木(AST)として出力するように変更する。 実行部分ASTを渡すと、実行するrun.jsを実装することにする。
実装の前に、構文解析のアウトプットとなる、抽象構文木(AST)について、先にイメージをしておきたい。
javascriptでは、木構造は、オブジェクトで表す。
printという関数名をleftに、 関数呼び出しを表す演算子"()"をopに、 引数として渡す文字列"hello world"をrightにセットすると、以下のようになる。
//print("hello world")の場合の、ASTの例 { left: "print", op: "()", right: "hello world" }
このオブジェクト(tree構造のノード)を生成するコードは以下のように書けばよい。
//すでに変数に値が入っているとする var left = "print"; var op = "()"; var right = "hello world"; //オブジェクトが生成される。 var obj1 = {left:left,op:op,right:right}; //変数名とkey名が同じであれば省略できる var obj2 = {left,op,right};
出力されたASTを実行できるインタプリタを作るにあたり、以下のファイル構成で実装した。 run.jsが新規追加となり、interpretor.jsとparser.jsに修正を行う。
変更点としては、parserからastを受け取るように変更し、結果のastを表示しておく。
さらに、run.jsを取り込むようにし、run(ast)で実行する。
$ cat interpretor.js #!/usr/bin/node //別ファイルに記述している処理を読み込む var {read,show} = require("./utils.js"); var lexer = require("./lexer.js"); var parser = require("./parser.js"); (@var run = require("./run.js");@) //source.3から読み込む var source = read("source.3"); //字句解析 var tokens = lexer(source); show("tokens =",tokens); //------構文解析------// (@var ast =@) parser(tokens); (@show("ast=",ast); //------実行------// run(ast);@)
parserの変更点は、callfunc関数内で、これまで捨てていたexpectの戻り値を、left,op,rightに保持している。
さらに、最後に新しいオブジェクト(ASTのノード)を作成している。
$ cat parser.js module.exports = parser; var {expect,accept,show,error} = require("./utils.js"); var tokens; //構文解析開始 function parser(t){ tokens = t; return callprint(); } //print関数呼び出しの構文解析 function callprint(){ if(tokens.length==0)return; //関数名がprintであること (@var left = @)expect(tokens,"print"); //関数呼び出しの丸カッコであること (@var op = @)expect(tokens,"("); //文字列を取得 var msg = tokens.shift(); //ダブルクォーテーションを取り除く (@var right = @)msg.substr(1,msg.length-2); //閉じカッコであること (@op += @)expect(tokens,")"); (@//新しいオブジェクト(tree構造でのノード)を作成 return {left, op, right};@) }
最後に、run.jsを追加する。
astはtree構造なので、run関数は、再帰的に呼び出されるように実装してあるが、 やっていることは単純だ。
$ cat run.js module.exports = run; var {error} = require("./utils.js"); //astの階層をたどりながら実行 function run(a){ if(!a) return; if(!a.op){ //文字列ならダブルクォーテーションを取り除く if(a[0] == '"') return a.substr(1,a.length-2); //それ以外ならそのまま返す return a; }else if(a.op == "()"){ //leftに関数名 var func = run(a.left); if( func == "print"){ //rightに表示する文字列 var msg = run(a.right) //表示=実行 console.log(msg); }else{ error("未実装の関数呼び出し func=",func); } }else{ error("未実装の演算子 op=",a.op); } }
interpretor.jsを実行する。
まず、tokensとASTが意図どおりに分割されているか、念のため表示しているので、確認しよう。
「hello world」と表示されており、問題ない。
$ ./interpreter.js tokens =[ 'print', '(', '"hello world"', ')' ] ast={ left: 'print', op: '()', right: 'hello world' } hello world
即実行するのではなく、 一度ASTに出力した後、ASTをrun関数で実行することができた。