** "Sieht aus wie JavaScript, Gehirn (Inhalt) ist Ruby, (Stabilität ist AC / DC)" ** Skriptsprache Kinx ). Diese Zeit ist auch ein Parser-Kombinator.
Letztes Mal habe ich mit [Kinx Library-Parser Combinator (Teil 1)] einen AST erstellt (https://qiita.com/Kray-G/items/0224128078af7554fd08).
Dieses Mal werde ich dies interpretieren und ausführen. Schließlich wird JIT kompiliert und ausgeführt.
Lassen Sie uns das letzte endgültige Programm erneut bestätigen.
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 addsub = $.oneOf("+-");
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));
Dies. Beheben wir damit nur ein Problem. Das ist jedoch kein Problem.
Tatsächlich schlägt dieser Parser fehl, wenn ein Leerzeichen vorhanden ist. Natürlich gibt es keinen Platz, um die Leerzeichen zu interpretieren, daher sollten die Zeichen nicht auf die Leerzeichen treffen, also antworten sie zuversichtlich mit "Es gibt keine Grammatik!".
In normalen Programmiersprachen sind Token-Unterbrechungen eine beliebige Anzahl von Leerzeichen, und Leerzeichen werden häufig übersprungen. Lassen Sie uns daher die Leerzeichen überspringen. Es gibt zwei Dinge zu verwenden:
$ .optWhitespace ist ein Parser, der null oder mehr beliebige Whitespace-Zeichen interpretiert. Insbesondere ist es dasselbe wie "$ .regex (/ \ s * /)". Daher werden Leerzeichen, Zeilenumbrüche (CR / LF) und Tabulatoren abgeglichen. Es gibt auch "$ .whitespace", dh "$ .regex (/ \ s + /)", um einem oder mehreren Leerzeichen zu entsprechen.Mit diesen beiden können Sie ".skip ($ .optWhitespace)" verwenden, um leere Zeichen nach einem bestimmten Parser-Abgleich zu überspringen.
Bereiten Sie hier eine Funktion namens "lexeme ()" vor, wie unten gezeigt, und fügen Sie einen Prozess hinzu, um leere Zeichen zu überspringen. Definieren Sie "Ignorieren", damit Sie es hier hinzufügen können, wenn weitere Dinge zu ignorieren sind, und Sie müssen bereits beim ersten Start leere Zeichen überspringen.
var ignore = $.optWhitespace;
var lexeme = &(p) => p.skip(ignore);
Diese lexeme () Funktion muss sich nur in der Unterbrechung des Tokens befinden, daher sollte sie sich im Parser der kleinsten Einheit von number, addsub, muldiv, lbr, rbr befinden. Wenn Sie das erste Programm neu schreiben, sieht es wie folgt aus.
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 addsub = lexeme($.oneOf("+-"));
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
}
}
}
*/
Beide geben das gleiche Ergebnis zurück.
Das erste ignore.then () ist, wo das führende Leerzeichen ignoriert wird. parser.then (anotherParser) gibt im Gegensatz zu.skip ()einen anderenParser zurück. Dies führt dazu, dass der Parser ignoriert wird.
Kommen wir nun zum Hauptthema.
Lassen Sie uns zunächst den Interpreter vor JIT implementieren. Das ist einfacher. Der Interpreter wird nacheinander ausgeführt, während der AST durchlaufen wird. Bewerten Sie die linke Seite, bewerten Sie die rechte Seite und berechnen Sie mit dem Ergebnis. Die Klasse "Dolmetscher" sieht folgendermaßen aus:
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;
}
}
Ich habe auch versucht, den Berechnungsprozess sichtbar zu machen (wenn Sie {{enableSequence: true} `an den Konstruktor übergeben, wird der Berechnungsprozess angezeigt). Lassen Sie es uns so laufen.
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
*/
Es wird nach der Priorität berechnet! Es überrascht nicht, dass der AST nach Priorität gebaut wird. Versuchen wir eine andere Formel.
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
*/
Es gibt.
Dies ist die lang erwartete JIT. Obwohl die JIT-Technologie selbst ehrlich gesagt wunderbar ist, verstehen Sie bitte, dass der oben genannte Interpreter auf dieser Berechnungsebene schneller ist (keine Schleifen oder bedingten Verzweigungen). Da ich mit derselben Wurzel wie der Interpreter kompiliere und der Interpreter selbst nicht viel tut, entspricht die JIT-Kompilierungszeit der Interpreterzeit (+ α). Hmmm.
Es ist nur eine technologische Basis. Ich hätte ein Beispiel machen sollen, das einen Unterschied in der Geschwindigkeit macht. Möchten Sie Brainf * ck als Thema unter Bezugnahme auf den Artikel hier neu schreiben?
Übrigens wurde in "Interpreter" die Berechnungsformel direkt ausgeführt, aber es ist in Ordnung, wenn Sie sie so umschreiben, dass der entsprechende Maschinensprachencode ausgegeben wird, anstatt die Berechnung auszuführen. In der JIT-Bibliothek lautet die Compiler-Klasse zum Konvertieren in Maschinensprachencode wie folgt. Es ist ein bisschen lang, aber ich werde es so ausdrücken, wie es ist. Auch hier können Sie Kompilierungscode im Zwischenformat ausgeben, indem Sie im Konstruktor "{enableListing: true}" festlegen.
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 '+':
c.add(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.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();
}
}
Register können von "R2" bis "R5" und "S0" bis "S5" verwendet werden. Speichern Sie R0 und R1, da sie für die Division verwendet werden müssen. Die Zuordnung des Registers erfolgt über "Reservieren, wenn Sie es verwenden, und Zurückgeben, wenn Sie es nicht mehr verwenden".
Beachten Sie, dass die Register der "R" -Serie nach dem Aufruf der Funktion möglicherweise zerstört werden. Diesmal wird die Funktion jedoch nicht aufgerufen, sodass sie auf die gleiche Weise wie die "S" -Serie behandelt werden kann. Sie erhalten eine Fehlermeldung, wenn Ihnen die verfügbaren Register ausgehen, aber viele der Zwischenwerte sind kurzlebig und sollten in Ordnung sein. Wenn sich der zu speichernde Wert erhöht, geben Sie den Code aus, um ihn im Speicher zu speichern. Außerdem verfügt die JIT-Bibliothek von Kinx über einen lokalen Variablenbereich auf dem Stapel, sodass es am einfachsten ist, ihn zuzuweisen, wenn er leer ist.
Wenn man die Registerzuweisung ernsthaft betrachtet, ist sie ziemlich tiefgreifend, aber im Fall von JIT nimmt die ** Optimierung nicht viel Zeit in Anspruch **, so die Theorie. Weil es eine Verschwendung von Optimierungszeit ist. Bei der Vorkompilierung (AOT-Kompilierung) müssen Sie sich keine Gedanken über die Kompilierungszeit machen. Je schneller die Ausführungszeit, desto besser die Optimierung. In JIT liegt die Kompilierungszeit jedoch auch innerhalb der Ausführungszeit, sodass dies nicht der Fall ist.
Berechnen wir es jetzt. Vergessen Sie nicht, Jit zu verwenden.
using Parsek;
using Jit;
/*Kürzung*/
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
*/
Es gibt. Versuchen wir ein anderes Beispiel.
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
*/
Da ist auch das.
Sie können auch den eigentlichen Maschinensprachencode ausgeben, also versuchen wir es.
var code = new Compiler()
.compile(ignore.then(expression)
.parseAll(" 1 + 2 * 3 + 2 * ( 14 - 2 ) ").value);
code.dump();
System.println(code.run());
Ausgabe unter 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
Lass es uns grob lesen.
rdi-Register in Zeile 0x12 0x01 zurdi + r11 dem Register rcx in Zeile 0x2e zur8 --r11 in das Register rbx in Zeile 0x40-0x4a einrcx + r8 dem Register rdi in Zeile 0x54 zuDer Rückgabewert der Funktion wird in x64 als "rax" -Register bestimmt, sodass das Ergebnis zurückgegeben wird.
Dann in einem anderen Beispiel.
var code = new Compiler()
.compile(ignore.then(expression)
.parseAll("(( 123 ) * 2 * 4 - 3 * ( 12 + 10 )) % 100").value);
code.dump();
System.println(code.run());
Dies ist auch die Ausgabe unter 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, rdi
23: 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
Es gibt auch Berechnungsergebnisse!
Normalerweise konvertiert das Skriptsprachensystem AST in seinen eigenen Zwischenformatcode (Bytecode) und führt ihn aus. So ist Kinx. Was Sie jedoch tun, unterscheidet sich nicht wesentlich von den oben genannten. Es ist eher so, als würde man etwas Ähnliches wie "Compiler" machen und es in seinem eigenen "Interpreter" ausführen. Sie benötigen keinen "Intrpreter", wenn Sie ihn in maschinensprachlichen Code konvertieren können. Normalerweise werden Operationen mit mehreren Längen und Klassenobjekte behandelt, und dynamisch typisierte Sprachen kennen den Typ erst zur Laufzeit, sodass das Kompilieren in die Maschinensprache nur mühsam ist. Insbesondere wenn Sie x64 (Windows / Linux) / ARM usw. unterstützen möchten, müssen Sie für jeden einen Compiler erstellen. Die Byte-Codierung scheint daher die beste Vorgehensweise zu sein.
Trotzdem gibt JIT sein Bestes für seriöse Produkte. Kinx kann auch teilweise mit nativen Funktionen in JIT konvertiert werden. Da es innerhalb des Bereichs realisiert wird, der vom abstrakten Assembler (SLJIT) ausgedrückt werden kann, sollte es außerdem für verschiedene Plattformen in hohem Maße portierbar sein.
Auf jeden Fall war JIT schon immer ein heißes Thema in der Sprachverarbeitung, daher dachte ich, dass die JIT-Bibliothek von Kinx als kleines Spielzeug Spaß machen würde. Ich preise dich. Da ich dieses Mal hart daran gearbeitet habe, einen Parser-Kombinator zu implementieren, denke ich außerdem, dass ich leicht mein eigenes DSL erstellen kann. Ich denke, es macht ziemlich viel Spaß, aber wie wäre es damit?
Das Schlagwort für die Kinx JIT-Bibliothek lautet ** "Fühlen Sie sich frei für JIT" **, nicht wahr?
Also nächstes Mal.