** "Ressemble à JavaScript, le cerveau (contenu) est Ruby, (la stabilité est AC / DC)" ** Langage de script Kinx ). Cette fois, c'est aussi un combinateur d'analyseur.
La dernière fois, je suis allé au point de créer un AST dans Kinx Library-Parser Combinator (Part 1).
Cette fois, je vais l'interpréter et l'exécuter. Enfin, JIT compile et s'exécute.
Reconfirmons le dernier programme final.
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));
Cette. Résolvons un seul problème avec cela. Ce n'est pas un problème, cependant.
En fait, cet analyseur échouera s'il y a un caractère vide. Bien sûr, il n'y a pas de place pour interpréter les blancs, donc les caractères ne sont pas censés rencontrer les blancs, donc ils répondent avec confiance "Il n'y a pas de grammaire!".
Dans les langages de programmation ordinaires, les sauts de jeton sont n'importe quel nombre de caractères vides, et il est courant que les blancs soient ignorés. Par conséquent, sautons les caractères vides. Il y a deux choses à utiliser:
$ .optWhitespace est un analyseur qui interprète zéro ou plusieurs espaces blancs arbitraires. Plus précisément, c'est la même chose que $ .regex (/ \ s * /). Par conséquent, il correspond aux espaces, aux sauts de ligne (CR / LF) et aux tabulations. Il y a aussi $ .whitespace, qui est $ .regex (/ \ s + /) pour correspondre à un ou plusieurs caractères vides.parser.skip (anotherParser) pour correspondre à parser, puis essayez de faire correspondre ʻanotherParser, et si c'est le cas, renvoyez le résultat de parser. Autrement dit, il ignore le résultat du match ʻanotherParser.En utilisant ces deux, vous pouvez utiliser .skip ($ .optWhitespace) pour ignorer les caractères vides après un parseur particulier correspondant.
Ici, préparez une fonction appelée lexeme () comme indiqué ci-dessous, et ajoutez un processus pour sauter les caractères vides. ʻIgnore` doit être ajouté ici quand il y a plus de choses à ignorer, et il est nécessaire de sauter les caractères vides même au premier démarrage, alors définissez-le.
var ignore = $.optWhitespace;
var lexeme = &(p) => p.skip(ignore);
Cette fonction lexeme () doit seulement être à la rupture du jeton, donc elle devrait être dans l'analyseur de la plus petite unité de number, ʻaddsub, muldiv, lbr, rbr`. Si vous réécrivez le premier programme, ce sera comme suit.
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
}
}
}
*/
Les deux renvoient le même résultat.
Le premier ʻignore.then () est la partie qui ignore le premier blanc. parser.then (anotherParser) renvoie ʻanotherParser, contrairement à .skip (). Cela entraînera l'ignorance de l'analyseur.
Entrons dans le sujet principal.
Tout d'abord, implémentons l'interpréteur avant JIT. C'est plus simple. L'interpréteur s'exécute séquentiellement tout en parcourant l'AST. Évaluez le côté gauche, évaluez le côté droit et calculez avec le résultat. La classe ʻInterpreter` ressemble à ceci:
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;
}
}
J'ai aussi essayé de rendre le processus de calcul visible (passer {enableSequence: true} au constructeur montrera le processus de calcul). Lançons-le comme ça.
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
*/
Il est calculé en fonction de la priorité! Sans surprise, l'AST est construit selon la priorité. Essayons une autre formule.
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
*/
Il y a.
C'est le JIT tant attendu. Cependant, bien que la technologie JIT elle-même soit merveilleuse, honnêtement, comprenez que l'interpréteur ci-dessus est plus rapide à ce niveau de calcul (pas de boucles ou de branches conditionnelles). Puisque je compile avec la même racine que l'interpréteur et que l'interpréteur lui-même ne fait pas grand-chose, le temps de compilation JIT est comme le temps de l'interpréteur (+ α). Hmmm.
C'est juste une base technologique. J'aurais dû faire un exemple qui fait une différence de vitesse. Souhaitez-vous réécrire Brainf * ck en tant que sujet, en vous référant à l'article ici?
Au fait, dans ʻInterpreter, la formule de calcul a été exécutée directement, mais ce n'est pas grave si vous la réécrivez afin que le code équivalent en langage machine soit sorti au lieu d'exécuter le calcul. En regardant la [Bibliothèque JIT](https://qiita.com/Kray-G/items/a237f195630f3f0a91df), la classe Compilerqui se traduit en code de langage machine ressemblera à ceci: C'est un peu long, mais je vais le dire tel quel. Encore une fois, vous pouvez générer un code de compilation au format intermédiaire en définissant{enableListing: true}` dans le constructeur.
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();
}
}
Les registres peuvent être utilisés de «R2» à «R5» et «S0» à «S5». Enregistrez «R0» et «R1» car ils doivent être utilisés pour la division. La méthode d'allocation des registres est "Réserver lors de l'utilisation et renvoyer une fois terminé".
Notez que les registres de la série «R» peuvent être détruits après l'appel de la fonction, mais cette fois la fonction n'est pas appelée, elle peut donc être traitée de la même manière que la série «S». Vous obtiendrez une erreur si vous manquez de registres disponibles, mais la plupart des valeurs intermédiaires sont de courte durée et devraient convenir. Si la valeur à enregistrer augmente, émettez le code pour l'enregistrer dans la mémoire. De plus, la bibliothèque JIT de Kinx a une zone de variables locales sur la pile, il est donc plus facile de l'allouer lorsque vous êtes à court.
Considérant sérieusement l'allocation de registre, c'est assez profond, mais dans le cas de JIT, ** l'optimisation ne prend pas beaucoup de temps ** est la théorie, donc cela suffit. Parce que c'est une perte de temps d'optimisation. Dans le cas de la pré-compilation (AOT Compilation), vous n'avez pas à vous soucier du temps de compilation, et plus le temps d'exécution est rapide, meilleure est l'optimisation, mais dans JIT, le temps de compilation est également dans le temps d'exécution, donc ce n'est pas le cas.
Calculons-le maintenant. N'oubliez pas ʻutiliser Jit; `.
using Parsek;
using Jit;
/*réduction*/
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
*/
Il y a. Essayons un autre exemple.
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
*/
Il y a aussi ceci.
Vous pouvez également vider le code de langage de la machine, alors essayons-le.
var code = new Compiler()
.compile(ignore.then(expression)
.parseAll(" 1 + 2 * 3 + 2 * ( 14 - 2 ) ").value);
code.dump();
System.println(code.run());
Sortie sous 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
Lisons-le grossièrement.
rdi sur la ligne 0x12rcx sur la ligne 0x19r8 sur la ligne 0x20rcx * r8 dans le registre r11 sur la ligne 0x27-0x2ardi + r11 au registre rcx sur la ligne 0x2erdi sur la ligne 0x32r8 sur la ligne 0x39r8 --r11 dans le registre rbx sur la ligne 0x40-0x4ardi * rbx dans le registre r8 sur la ligne 0x4d-0x50rcx + r8 au registre rdi sur la ligne 0x54rdi au registre rax sur la ligne 0x58La valeur de retour de la fonction est déterminée comme étant le registre rax dans x64, donc cela retournera le résultat.
Puis dans un autre exemple.
var code = new Compiler()
.compile(ignore.then(expression)
.parseAll("(( 123 ) * 2 * 4 - 3 * ( 12 + 10 )) % 100").value);
code.dump();
System.println(code.run());
C'est également la sortie sous 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
Il y a aussi des résultats de calcul!
Normalement, le système de langage de script convertit AST en son propre code de format intermédiaire (code d'octet) et l'exécute. Il en va de même pour Kinx. Cependant, ce que vous faites n'est pas très différent de ce qui précède. C'est plus comme faire quelque chose de similaire à Compiler et l'exécuter dans votre propre ʻInterpreter. Si vous pouvez convertir en code de langage machine natif, ʻIntrpreter n'est pas nécessaire. Il traite généralement des opérations de longueur et des objets de classe multiples, et les langages typés dynamiquement ne connaissent pas le type avant l'exécution, donc c'est juste un tracas à compiler en langage machine. En particulier, si vous souhaitez prendre en charge x64 (Windows / Linux) / ARM et ainsi de suite, vous devez créer un compilateur pour chacun. Le codage par octets semble donc être la meilleure pratique.
Cela dit, JIT fait de son mieux pour les produits sérieux. Kinx peut également être partiellement converti en JIT avec des fonctions natives. De plus, comme il est réalisé dans la plage qui peut être exprimée par l'assembleur abstrait (SLJIT), il devrait être hautement portable vers diverses plates-formes.
Dans tous les cas, JIT a toujours été un sujet brûlant dans le traitement du langage, alors j'ai pensé que la bibliothèque JIT de Kinx serait un petit jouet amusant. Je te loue. De plus, comme j'ai travaillé dur cette fois pour implémenter un combinateur d'analyseur, je pense que je peux facilement créer mon propre DSL. Je pense que c'est assez amusant, mais qu'en est-il?
Le slogan de la bibliothèque Kinx JIT est ** "N'hésitez pas à JIT" **, n'est-ce pas?
Alors la prochaine fois.