javascript/C言語/アセンブラを用い、 字句解析、構文解析、インタプリタ、コンパイラのプログラムをスクラッチから作りながら、 「プログラミング言語の作り方」を解説する。

抽象構文木対応

javascript版プログラミング言語の作り方(インタプリタ開発)

構文解析と実行を分離する。

構文解析のアウトプットとして、抽象構文木(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に修正を行う。

• interpretor.js: インタプリタのメイン
• lexer.js: 字句解析
• parser.js: 構文解析
• run.js: 実行
• utils.js: ユーティリティ系

interpretor.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.jsの実装

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の実装

最後に、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関数で実行することができた。