[プログラミング言語の作り方] 抽象木構文(AST)

構文解析の結果として抽象木構文(AST)で出力する

### 抽象木構文(AST)とは
木構造はオブジェクトで表す

1
2
3
4
5
{
    left: "print",
    op: "()",
    right: "hello world"
}

以下のように表す

1
2
3
4
5
6
7
var left = "print";
var op = "()";
var right = "hello world";
 
var obj1 = {left:left, op:op, right:right};
 
var obj2 = {left, op, right};

run.jsを追加する
$ tree
.
├── interpretor.js
├── lexer.js
├── main.js
├── parser.js
├── run.js
├── source.3
└── utils.js

### interpretor.js

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
var {read, show} = require("./utils.js");
var lexer = require("./lexer.js");
var parser = require("./parser.js");
var run = require("./run.js");
 
var source = read("source.3");
 
var tokens = lexer(source);
 
var token = lexer(source);
show("token =", tokens);
 
var ast = parser(tokens);
show("ast=", ast);
 
run(ast);

### parser.js

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
module.exports = parser;
var {expect, accept, show, error} = require("./utils.js");
 
var tokens;
 
function parser(t){
    tokens = t;
    return callprint();
}
 
function callprint(){
    if(tokens.length==0) return;
 
    var left = expect(tokens, "print");
 
    var op = expect(tokens, "(");
 
    var msg = tokens.shift();
    num = calc(msg.length);
 
    var right = msg.substr(1, num);
 
    op += expect(tokens,")");
 
    return {left, op, right};
}
 
function calc(len) {
    var total = len - 2;
    return Number.isInteger(total) > 0 ? total : 0;
}

### run.js

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
const { error } = require("./utils");
 
module.exports = run;
 
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 == "()") {
        var func = run(a.left);
        if(func == "print"){
            var msg = run(a.right)
            console.log(msg);
        } else {
            error("未実装の関数呼び出し func=", func);
        }
    } else {
        error("未実装の演算子 op=", a.op)
    }
}

$ node interpretor.js
token =[ ‘print’, ‘(‘, ‘”hello world”‘, ‘)’ ]
ast={ left: ‘print’, op: ‘()’, right: ‘hello world’ }
hello world

最初にopを見て、それからprintかどうかを判定している。
astでは、ソースコードをleft, right, opに分けている。