# Kinx Library-Parser combinator (Part 2)

## Introduction

The script language Kinxdeliveredby”“ItlookslikeJavaScript,thebrain(contents)isRuby,(stabilityisAC/DC)”). This time is also a parser combinator.

Last time, I did it up to making AST with Kinx library-Parser combinator (1).

This time I will interpret this and execute it. At the end, I will compile and execute JIT.

## before that

### review

Let’s reconfirm the final program from last time.

``````using Parsek;

function makeAST(first, rest) {
var expr = first;
for (var i = 0, l = rest.length(); i <l; ++i) {
expr = {lhs: expr, op: rest[i][0], rhs: rest[i][1] };
}
return expr;
}

var \$ = new Parsek();
var number = \$.regex(/[1-9][0-9]*|[0-9]/).map(Integer.parseInt);
var muldiv = \$.oneOf("*/%");
var lbr = \$.string("(");
var rbr = \$.string(")");

var expression;
var factor = \$.lazy(&() => \$.alt(number, \$.seq(lbr, expression, rbr).map(&(value) => value[1])));
var term = \$.seqMap(factor, \$.seq(muldiv, factor).many(), makeAST);
expression = \$.seqMap(term, \$.seq(addsub, term).many(), makeAST);

// test
System.println(expression.parseAll("1+2*3+2*(14-2)").value.toJsonString(true));
``````

This. Let’s fix one problem with this. It’s not a problem, though.

Actually, this parser fails if there is a space character. Of course, there is no place to interpret white space, so it is not the character that you expect to encounter white space, and you will be confidently answering “There is no grammar!”

### Skipping whitespace characters

In normal programming languages, token breaks are any number of whitespace characters, and whitespace is commonly skipped. Therefore, let’s skip the white space character. There are two things to use there.

• `\$.optWhitespace` is a parser that interprets zero or more arbitrary whitespace characters. Specifically, it is the same as `\$.regex(/\s*/)`. Therefore, it matches blanks, line breaks (CR/LF), and tabs. There is also `\$.whitespace`, which uses `\$.regex(/\s+/)` to match one or more whitespace characters.
• `parser.skip(anotherParser)` tries to match `parser`, then `anotherParser`, and if so, returns the result of `parser`. That is, skip the match result of `anotherParser`.

These two can be used to skip whitespace characters after a particular parser match with `.skip(\$.optWhitespace)`.

Here, prepare a function called `lexeme()` as shown below and add a process to skip whitespace characters. Define `ignore` so that you can add it here when there are more things to ignore, and skip whitespace at the beginning.

``````var ignore = \$.optWhitespace;
var lexeme = &(p) => p.skip(ignore);
``````

This `lexeme()` function only needs to be at the break between tokens, so it is all right if it is in the minimum unit parser of `number`, `addsub`, `muldiv`, `lbr`, and `rbr`. If you rewrite the first program, it will be as follows.

``````using Parsek;

function makeAST(first, rest) {
var expr = first;
for (var i = 0, l = rest.length(); i <l; ++i) {
expr = {lhs: expr, op: rest[i][0], rhs: rest[i][1] };
}
return expr;
}

var \$ = new Parsek();
var ignore = \$.optWhitespace;
var lexeme = &(p) => p.skip(ignore);

var number = lexeme(\$.regex(/[1-9][0-9]*|[0-9]/)).map(Integer.parseInt);
var muldiv = lexeme(\$.oneOf("*/%"));
var lbr = lexeme(\$.string("("));
var rbr = lexeme(\$.string(")"));

var expression;
var factor = \$.lazy(&() => \$.alt(number, \$.seq(lbr, expression, rbr).map(&(value) => value[1])));
var term = \$.seqMap(factor, \$.seq(muldiv, factor).many(), makeAST);
expression = \$.seqMap(term, \$.seq(addsub, term).many(), makeAST);

// test
System.println(expression.parseAll("1+2*3+2*(14-2)").value.toJsonString(true));
System.println(ignore.then(expression).parseAll(" 1 + 2 * 3 + 2 * (14-2) ").value.toJsonString(true));
/* Both results are the same.
{
"lhs": {
"lhs": 1,
"op": "+",
"rhs": {
"lhs": 2,
"op": "*",
"rhs": 3
}
},
"op": "+",
"rhs": {
"lhs": 2,
"op": "*",
"rhs": {
"lhs": 14,
"op": "-",
"rhs": 2
}
}
}
*/
``````

Both return the same result.

The first `ignore.then()` is the part that ignores leading white space. `parser.then(anotherParser)` returns `anotherParser`, unlike `.skip()`. This causes `parser` to be ignored.

Now let’s get into the main subject.

## Interpreter

First, let’s implement the interpreter before JIT. This is easier. The interpreter traverses the AST and executes it serially. Evaluate the left side, evaluate the right side, and operate on the result. The `Interpreter` class looks like this:

``````class Interpreter(opts_) {
private sequence(r, op, lhs, rhs) {
return if (!opts_.enableSequence);
System.println("%d %s %d -> %d" %lhs %op %rhs %r);
}
public eval(ast) {
var lhs = ast.lhs.isObject ?eval(ast.lhs): ast.lhs;
var rhs = ast.rhs.isObject ?eval(ast.rhs): ast.rhs;
var r = 0;
switch (ast.op) {
case'+':
r = lhs + rhs;
break;
case'-':
r = lhs-rhs;
break;
case'*':
r = lhs * rhs;
break;
case'/':
r = lhs / rhs;
break;
case'%':
r = lhs %rhs;
break;
default:
throw RuntimeException('Invalid operator');
}
sequence(r, ast.op, lhs, rhs);
return r;
}
}
``````

I tried to make the calculation process visible (passing `{ enableSequence: true }` to the constructor will display the calculation process). Let’s run it like this.

``````System.println("Result = ",
new Interpreter({ enableSequence: true })
.eval(ignore.then(expression)
.parseAll(" 1 + 2 * 3 + 2 * (14-2) ").value)
);
/*
2 * 3 -> 6
1 + 6 -> 7
14-2 -> 12
2 * 12 -> 24
7 + 24 -> 31
Result = 31
*/
``````

It is calculated according to the priority order properly! Not surprisingly, because AST is built according to priority. Let’s try another formula.

``````System.println(
"Result = ",
new Interpreter({ enableSequence: true })
.eval(ignore.then(expression)
.parseAll("(( 123) * 2 * 4-3 * (12 + 10 )) %100").value)
);
/*
123 * 2 -> 246
246 * 4 -> 984
12 + 10 -> 22
3 * 22 -> 66
984-66 -> 918
918 %100 -> 18
Result = 18
*/
``````

There is.

## JIT compilation

I’m looking forward to JIT. However, JIT technology itself is wonderful, but please understand that the above interpreter is honestly faster at this level of computational complexity (no loops or conditional branches). JIT compilation time is like interpreter time (+α) because it is compiling with the same route as the interpreter and the interpreter itself does not do much. Mumu.

It’s just a technology base. I wish I could have made an example where the difference in speed was even greater. Will you rewrite Brainf*ck with the article of here next time?

Now, in `Interpreter`, we executed the calculation formula directly, but it is OK if we rewrite it so that the equivalent machine language code is output instead of executing the calculation. Looking at JIT library, the `Compiler` class that converts to machine language code will be as follows. It’s a little long, but I will post it as it is. Again, you can output the intermediate format compile code by setting `{ enableListing: true }` in the constructor.

``````class Compiler(opts_) {
var regs_, regsLen_;
enum {MOV, BOP, DIVMOD, RET}
private initialize() {
regs_ = [
// Jit.R0 and Jit.R1 is used as a work register when it is division.
{reg: Jit.R2, used: false, name: "R2" },
{reg: Jit.R3, used: false, name: "R3" },
{reg: Jit.R4, used: false, name: "R4" },
{reg: Jit.R5, used: false, name: "R5" },
{reg: Jit.S0, used: false, name: "S0" },
{reg: Jit.S1, used: false, name: "S1" },
{reg: Jit.S2, used: false, name: "S2" },
{reg: Jit.S3, used: false, name: "S3" },
{reg: Jit.S4, used: false, name: "S4" },
{reg: Jit.S5, used: false, name: "S5" },
];
regsLen_ = regs_.length();
}
private listing(type, op, dst, op1, op2) {
return if (!opts_.enableListing);
switch (type) {
case MOV:
System.println("%s <- %s" %dst %op1);
break;
case BOP:
System.println("%s <- %s %s %s" %dst %op1 %op %op2);
break;
case DIVMOD:
System.println("R0 <- %s" %op1);
System.println("R1 <- %s" %op2);
System.println("%s <- R0 %s R1" %dst %op);
break;
case RET:
System.println("ret %s" %dst);
break;
}
}
private getReg() {
for (var i = 0; i <regsLen_; ++i) {
if (!regs_[i].used) {
regs_[i].used = true;
return i;
}
}
throw RuntimeException("Not enough register");
}
private releaseReg(i) {
regs_[i].used = false;
}
private compileLeaf(c, leaf) {
var r = getReg();
c.mov(regs_[r].reg, Jit.IMM(leaf));
listing(MOV, null, regs_[r].name, leaf);
return r;
}
private compileNode(c, ast) {
var rl = ast.lhs.isObject ?compileNode(c, ast.lhs): compileLeaf(c, ast.lhs);
var rr = ast.rhs.isObject ?compileNode(c, ast.rhs): compileLeaf(c, ast.rhs);
var r = getReg();
switch (ast.op) {
case'+':
listing(BOP, ast.op, regs_[r].name, regs_[rl].name, regs_[rr].name);
break;
case'-':
c.sub(regs_[r].reg, regs_[rl].reg, regs_[rr].reg);
listing(BOP, ast.op, regs_[r].name, regs_[rl].name, regs_[rr].name);
break;
case'*':
c.mul(regs_[r].reg, regs_[rl].reg, regs_[rr].reg);
listing(BOP, ast.op, regs_[r].name, regs_[rl].name, regs_[rr].name);
break;
case'/':
c.mov(Jit.R0, regs_[rl].reg);
c.mov(Jit.R1, regs_[rr].reg);
c.sdiv();
c.mov(regs_[r].reg, Jit.R0);
listing(DIVMOD, ast.op, regs_[r].name, regs_[rl].name, regs_[rr].name);
break;
case'%':
c.mov(Jit.R0, regs_[rl].reg);
c.mov(Jit.R1, regs_[rr].reg);
c.sdivmod();
c.mov(regs_[r].reg, Jit.R1);
listing(DIVMOD, ast.op, regs_[r].name, regs_[rl].name, regs_[rr].name);
break;
default:
throw RuntimeException('Invalid operator');
}
releaseReg(rl);
releaseReg(rr);
return r;
}
public compile(ast) {
var c = new Jit.Compiler();
c.enter();
var r = compileNode(c, ast);
c.ret(regs_[r].reg);
listing(RET, null, regs_[r].name);
return c.generate();
}
public run(ast) {
var code = compile(ast);
return code.run();
}
}
```Registers are available from `R2` to `R5` and `S0` to `S5`. We need to save `R0` and `R1` because we need to use them for division. The register allocation method is "Reserve when using, and return when using".

Note that the `R` series registers may be destroyed after the function is called, but this time it is possible to handle it in the same way as the `S` series, since it only calculates and does not call the function. An error will occur if all available registers are used up, but many intermediate values are short-lived, so this should not be a problem. If the value to be saved increases, we will issue a code to save it in memory. Also, the Kinx JIT library can have a local variable area on the stack, so it's easiest to allocate to it when there is not enough space.

It is quite deep considering register allocation in earnest, but in JIT it is the theory that **it does not take much time for optimization**, so this level is enough. Because the optimization time is wasted. In the case of pre-compilation (AOT Compilation), you don't have to worry about the compile time, and the faster the run time is, the faster the optimization is.

Let's calculate now. Don't forget `using Jit;`.

```javascript
using Parsek;
using Jit;

/* omitted */
System.println(
"Result = ",
new Compiler({ enableListing: true })
.run(ignore.then(expression)
.parseAll(" 1 + 2 * 3 + 2 * (14-2) ").value)
);
/*
R2 <- 1
R3 <- 2
R4 <- 3
R5 <- R3 * R4
R3 <- R2 + R5
R2 <- 2
R4 <- 14
R5 <- 2
S0 <- R4-R5
R4 <- R2 * S0
R2 <- R3 + R4
ret R2
Result = 31
*/
``````

There is. Let’s try another example.

``````System.println(
"Result = ",
new Compiler({ enableListing: true })
.run(ignore.then(expression)
.parseAll("(( 123) * 2 * 4-3 * (12 + 10 )) %100").value)
);
/*
R2 <- 123
R3 <- 2
R4 <- R2 * R3
R2 <- 4
R3 <- R4 * R2
R2 <- 3
R4 <- 12
R5 <- 10
S0 <- R4 + R5
R4 <- R2 * S0
R2 <- R3-R4
R3 <- 100
R0 <- R2
R1 <- R3
R4 <- R0 %R1
ret R4
Result = 18
*/
``````

There is also here.

You can also dump the actual machine code, so let’s try it.

``````var code = new Compiler()
.compile(ignore.then(expression)
.parseAll(" 1 + 2 * 3 + 2 * (14-2) ").value);
code.dump();
System.println(code.run());
``````

Output on Linux.

``````       0: 53 push rbx
1: 41 57 push r15
3: 41 56 push r14
5: 48 8b df mov rbx, rdi
8: 4c 8b fe mov r15, rsi
b: 4c 8b f2 mov r14, rdx
e: 48 83 ec 10 sub rsp, 0x10
12: 48 c7 c7 01 00 00 00 mov rdi, 0x1
19: 48 c7 c1 02 00 00 00 mov rcx, 0x2
20: 49 c7 c0 03 00 00 00 mov r8, 0x3
27: 49 89 cb mov r11, rcx
2a: 4d 0f af d8 imul r11, r8
2e: 4a 8d 0c 1f lea rcx, [rdi+r11]
32: 48 c7 c7 02 00 00 00 mov rdi, 0x2
39: 49 c7 c0 0e 00 00 00 mov r8, 0xe
40: 49 c7 c3 02 00 00 00 mov r11, 0x2
47: 4c 89 c3 mov rbx, r8
4a: 49 2b db sub rbx, r11
4d: 49 89 f8 mov r8, rdi
50: 4c 0f af c3 imul r8, rbx
54: 4a 8d 3c 01 lea rdi, [rcx+r8]
58: 48 89 f8 mov rax, rdi
5b: 48 83 c4 10 add rsp, 0x10
5f: 41 5e pop r14
61: 41 5f pop r15
63: 5b pop rbx
64: c3 ret
31
``````

• The prologue is up to the 0xe line.
• At line 0x12, assign 0x01 to the `rdi` register
• At line 0x19, assign 0x02 to the `rcx` register
• At line 0x20, assign 0x03 to the `r8` register
• At line 0x27-0x2a, assign the result of `rcx * r8` to the `r11` register
• At line 0x2e, assign the result of `rdi + r11` to the `rcx` register
• At line 0x32, assign 0x02 to the `rdi` register
• At line 0x39, assign 0x0e to the `r8` register
• At line 0x40-0x4a, assign the result of `r8-r11` to `rbx` register
• At line 0x4d-0x50, assign the result of `rdi * rbx` to `r8` register
• At line 0x54, assign the result of `rcx + r8` to the `rdi` register
• At line 0x58, assign `rdi` to `rax` register
• From line 0x5b, it is the epilogue.

The return value of the function is determined to be the `rax` register on x64, so this returns the result.

So in another example.

``````var code = new Compiler()
.compile(ignore.then(expression)
.parseAll("(( 123) * 2 * 4-3 * (12 + 10 )) %100").value);
code.dump();
System.println(code.run());
``````

This is also the output on Linux.

``````       0: 53 push rbx
1: 41 57 push r15
3: 41 56 push r14
5: 48 8b df mov rbx, rdi
8: 4c 8b fe mov r15, rsi
b: 4c 8b f2 mov r14, rdx
e: 48 83 ec 10 sub rsp, 0x10
12: 48 c7 c7 7b 00 00 00 mov rdi, 0x7b
19: 48 c7 c1 02 00 00 00 mov rcx, 0x2
20: 49 89 f8 mov r8, rdi23:   4c 0f af c1                                 imul r8, rcx
27:   48 c7 c7 04 00 00 00                        mov rdi, 0x4
2e:   4c 89 c1                                    mov rcx, r8
31:   48 0f af cf                                 imul rcx, rdi
35:   48 c7 c7 03 00 00 00                        mov rdi, 0x3
3c:   49 c7 c0 0c 00 00 00                        mov r8, 0xc
43:   49 c7 c3 0a 00 00 00                        mov r11, 0xa
4a:   4b 8d 1c 18                                 lea rbx, [r8+r11]
4e:   49 89 f8                                    mov r8, rdi
51:   4c 0f af c3                                 imul r8, rbx
55:   48 89 cf                                    mov rdi, rcx
58:   49 2b f8                                    sub rdi, r8
5b:   48 c7 c1 64 00 00 00                        mov rcx, 0x64
62:   48 89 f8                                    mov rax, rdi
65:   48 89 ce                                    mov rsi, rcx
68:   48 99                                       cqo
6a:   48 f7 fe                                    idiv rsi
6d:   48 89 d6                                    mov rsi, rdx
70:   49 89 f0                                    mov r8, rsi
73:   4c 89 c0                                    mov rax, r8
76:   48 83 c4 10                                 add rsp, 0x10
7a:   41 5e                                       pop r14
7c:   41 5f                                       pop r15
7e:   5b                                          pop rbx
7f:   c3                                          ret
18
``````

## おわりに

そうは言っても本気のプロダクトは JIT 頑張ってますよね。Kinx も native 関数などで一部 JIT 化可能です。しかも抽象化アセンブラ（SLJIT）で表現可能な範囲で実現しているので、基本的には色々なプラットフォームへの移植性は高いはず。

いずれにしても、JIT は言語処理系では昔からホットな話題なので、Kinx の JIT ライブラリはちょっとしたオモチャとしては楽しいかなー、と自画自賛してます。しかも今回頑張ってパーサ・コンビネータなんて実装してしまったので、手軽に独自の DSL とか作ったりできるのではないでしょうか。結構楽しいと思いますがいかがでしょう。

Kinx JIT ライブラリのキャッチフレーズは 「気軽に JIT」、ですね。

ということで、では、また次回。

Tags:

Updated: