** "Ressemble à JavaScript, le cerveau (contenu) est Ruby, (la stabilité est AC / DC)" ** Langage de script Kinx ). Cette fois, c'est un combinateur d'analyseur.
La dernière fois, j'ai présenté JIT Library, mais je l'ai terminé par les mots suivants.
Avec cela, si vous l'implémentez et le combinez avec un combinateur parseur, vous pouvez créer un petit système de traitement du langage avec JIT.
Oui, je l'ai fait à la hâte là-bas. Bibliothèque de combinateurs d'analyseur. Son nom est ** Parsek **. Parsek, pas Parsec.
L'interface est basée sur Parsimmon, mais l'implémentation est complètement unique. L'API n'est pas si riche, mais elle peut être utilisée telle quelle. Il est facile d'ajouter des interfaces, alors ajoutons-les au besoin.
Ça va être long, je vais donc diviser l'article en deux parties.
Cette fois, utilisons ceci pour analyser la grammaire arithmétique à quatre règles et créer un AST (Abstract Syntax Tree). La prochaine fois, enfin, j'irai au point de compiler et d'exécuter JIT.
Une bibliothèque pour combiner de petits analyseurs (simples) pour créer un grand analyseur. Je laisserai les détails à d'autres articles, mais comprenons-le en regardant l'exemple ci-dessous.
Cette fois, je vais changer le goût et expliquer à l'aide d'un échantillon. L'échantillon est une opération à quatre règles avec un entier positif (nombre naturel). Les nombres négatifs ne sont pas traités par souci de simplicité (les résultats peuvent être négatifs).
Normalement, nous parlerons de BNF et de PEG ici, mais ignorez-les. Commencez par parcourir l'échantillon.
using Parsek
La bibliothèque combinateur parser n'est pas intégrée en standard, alors utilisons-la. De plus, la bibliothèque est fournie en tant que classe, donc instancions-la.
using Parsek;
var $ = new Parsek();
Vous pouvez utiliser «$» comme nom de variable.
Laissez-moi vous donner un exemple un par un.
Tout d'abord, définissons un entier positif. C'est le premier petit analyseur (simple). Tout d'abord, c'est une expression régulière. Eh bien, ce n'est pas si difficile, donc c'est facile à comprendre.
Le seul inconvénient est que le moteur (= voiture démon) que vous utilisez n'est pas POSIX NFA **, vous devez donc écrire celui qui correspond le plus longtemps. En termes simples, dans l'exemple ci-dessous, "123" "correspond correctement à" 123 "", mais le contraire (/ [0-9] | [1-9] [0-9] * / ) Correspondra au premier écrit [0-9] et arrêtera la recherche, donc ce sera " 1 " et ne correspondra pas à " 23 ". Faisons attention.
var number = $.regex(/[1-9][0-9]*|[0-9]/);
Cet analyseur, number, peut maintenant analyser les nombres (la chaîne dans laquelle ils sont écrits). Faisons le.
L'analyse proprement dite est effectuée par la méthode parseAll (). Il y a aussi parse (), mais c'est une méthode qui réussit même si elle se termine au milieu, et est généralement utilisée en interne. Dans le cas de parseAll (), toute l'analyse est terminée, le post-traitement est effectué et le résultat est retourné.
using Parsek;
var $ = new Parsek();
var number = $.regex(/[1-9][0-9]*|[0-9]/);
System.println(number.parseAll("0")); // => {"position":1,"status":1,"value":"0"}
System.println(number.parseAll("10")); // => {"position":2,"status":1,"value":"10"}
System.println(number.parseAll("129")); // => {"position":3,"status":1,"value":"129"}
System.println(number.parseAll("abc")); // => {"position":0,"status":0,"value":null}
System.println(number.parseAll("0129")); // => {"position":1,"status":0,"value":null}
La valeur de retour «position» est la position de fin de la chaîne de caractères analysée, «status» est le succès / échec (1 est le succès) et «value» est la chaîne de caractères qui a été réellement analysée. Comme vous pouvez le voir, en cas d'échec, «value» est «null».
Mais si vous regardez de plus près, «value» est une chaîne. C'est naturel car il ne fait qu'interpréter une chaîne de caractères. Ici, la méthode qui se convertit en «valeur» est «.map ()». Donnez la fonction de conversion comme suit.
using Parsek;
var $ = new Parsek();
var number = $.regex(/[1-9][0-9]*|[0-9]/).map(&(value) => Integer.parseInt(value));
System.println(number.parseAll("129")); // => {"position":3,"status":1,"value":129}
C'est devenu une valeur numérique. Dans le cas ci-dessus, vous ne faites que passer la valeur, donc passer directement ʻInteger.parseInt` est identique.
var number = $.regex(/[1-9][0-9]*|[0-9]/).map(Integer.parseInt);
C'est plus concis.
Puisque la priorité diffère selon l'opérateur, divisez-la en deux.
+ Ou -* Ou / ou %Un moyen pratique d'interpréter le caractère unique ou est «$ .oneOf ()». Utilisez-le comme suit.
var addsub = $.oneOf("+-");
var muldiv = $.oneOf("*/%");
C'est facile. Essayons-le tout de suite.
using Parsek;
var $ = new Parsek();
var addsub = $.oneOf("+-");
var muldiv = $.oneOf("*/%");
System.println(addsub.parseAll("+")); // => {"position":1,"status":1,"value":"+"}
System.println(addsub.parseAll("-")); // => {"position":1,"status":1,"value":"-"}
System.println(addsub.parseAll("*")); // => {"position":0,"status":0,"value":null}
System.println(muldiv.parseAll("*")); // => {"position":1,"status":1,"value":"*"}
System.println(muldiv.parseAll("/")); // => {"position":1,"status":1,"value":"/"}
System.println(muldiv.parseAll("%")); // => {"position":1,"status":1,"value":"%"}
System.println(muldiv.parseAll("a")); // => {"position":0,"status":0,"value":null}
Comme prévu.
Autre chose, interprétons les parenthèses nécessaires au calcul numérique. L'analyseur qui correspond à une chaîne particulière utilise $ .string (). Ici, il s'agit d'un caractère, mais toute chaîne de caractères est correcte.
var lbr = $.string("(");
var rbr = $.string(")");
Cela fonctionne également très bien si vous l'essayez. Essayons une autre chaîne pour voir l'effet de $ .string ().
using Parsek;
var $ = new Parsek();
var lbr = $.string("(");
var rbr = $.string(")");
var hoge = $.string("hoge");
System.println(lbr.parseAll("(")); // => {"position":1,"status":1,"value":"("}
System.println(lbr.parseAll(")")); // => {"position":0,"status":0,"value":null}
System.println(rbr.parseAll("(")); // => {"position":0,"status":0,"value":null}
System.println(rbr.parseAll(")")); // => {"position":1,"status":1,"value":")"}
System.println(hoge.parseAll("hoge")); // => {"position":4,"status":1,"value":"hoge"}
System.println(hoge.parseAll("fuga")); // => {"position":0,"status":0,"value":null}
Vous pouvez voir que cela correspond correctement.
Vous disposez maintenant d'un petit (simple) outil d'analyse syntaxique.
var number = $.regex(/[1-9][0-9]*|[0-9]/).map(Integer.parseInt);
var addsub = $.oneOf("+-");
var muldiv = $.oneOf("*/%");
var lbr = $.string("(");
var rbr = $.string(")");
Combinons ces derniers. Voici le PEG. BNF est très bien, mais PEG est plus adapté aux combinateurs. Si vous ne montrez pas que la grammaire est comme ça, vous ne saurez pas ce que vous faites. Je vais aborder le sens un par un.
number <- regex(/[1-9][0-9]*|[0-9]/)
addsub <- '+' / '-'
muldiv <- '*' / '/' / '%'
lbr <- '('
rbr <- ')'
expression <- term (addsub term)*
term <- factor (muldiv factor)*
factor <- number / (lbr expression rbr)
Le symbole de sélection prioritaire PEG / et la spécification de division `` / '' sont déroutants, mais vous pouvez les voir en regardant de près.
Il y a à la fois du haut vers le bas et du bas vers le haut, mais ici, nous allons construire l'analyseur de bas en haut.
factor
Le premier est «facteur».
factor <- number / (lbr expression rbr)
«factor» peut être «number» ou «lbr expression rbr». Vous pouvez le déposer dans le programme tel quel. Les méthodes suivantes sont utilisées ici.
n'a pas encore été définie, utilisez $ .lazy () pour la retarder. L'utilisation de $ .lazy ()` créera un analyseur lorsqu'il sera réellement évalué.$ .alt (). Renvoie le résultat du premier analyseur réussi parmi plusieurs.$ .Seq () indique que plusieurs choses sont consécutives, comme lbr expression rbr.Maintenant écrivons. L'expression n'est déclarée qu'à l'avance.
var expression;
var factor = $.lazy(&() => $.alt(number, $.seq(lbr, expression, rbr)));
term
Vient ensuite «term».
term <- factor (muldiv factor)*
Cela signifie que «facteur» est suivi de «(facteur multiple)« 0 fois ou plus. Puisqu'il est autorisé 0 fois, il est normal que rien ne continue. Organiser comme "muldiv factor" signifie qu'il est identique à "lbr expression rbr" précédente et qu'il est continu. La méthode utilisée ici est la suivante.
.many () pour l'analyseur.Définissons-le.
var term = $.seq(factor, $.seq(muldiv, factor).many());
Vous avez maintenant défini «term».
expression
Enfin, «expression». La forme est la même que "term".
expression <- term (addsub term)*
Écrivons-le tel quel.
expression = $.seq(term, $.seq(addsub, term).many());
Vous avez maintenant un analyseur. Essayons d'analyser!
Je mettrai tout le code source une fois. Ce n'est pas tellement.
using Parsek;
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)));
var term = $.seq(factor, $.seq(muldiv, factor).many());
expression = $.seq(term, $.seq(addsub, term).many());
// parse expression!
System.println(expression.parseAll("1+2*3+2*(14-2)"));
// => {"position":14,"status":1,"value":[[1,{}],[["+",[2,[["*",3]]]],["+",[2,[["*",["(",[[14,{}],[["-",[2,{}]]]],")"]]]]]]]}
System.println(expression.parseAll("1+2*3+2*(14-2-)"));
// => {"position":7,"status":0,"value":null}
Le premier se révèle être un succès (quoique long). Il est difficile de lire les résultats, mais façonnons cela plus tard. Et vous pouvez voir que le second échoue. C'est parce que le dernier (14-2-) ne correspond à aucune des règles.
Formalisons ce résultat. Celui qui fonctionne est .map () utilisé dans number.
Tout d'abord, la partie $ .seq (lbr, expression, rbr). $ .seq () renvoie le tableau résultant sous forme de valeur. L'expression entre parenthèses n'a pas besoin de parenthèses comme valeur, et seul le résultat de l'expression à l'intérieur est suffisant. Alors, changez-le comme suit.
var factor = $.lazy(&() => $.alt(number, $.seq(lbr, expression, rbr).map(&(value) => value[1])));
Après modification, le résultat sera le suivant.
System.println(expression.parseAll("1+2*3+2*(14-2)"));
// => {"position":14,"status":1,"value":[[1,{}],[["+",[2,[["*",3]]]],["+",[2,[["*",[[14,{}],[["-",[2,{}]]]]]]]]]]}
C'est un peu plus court.
term、expression
Viennent ensuite «term» et «expression». Ici, formatons-le sous la forme d'AST (Abstract Syntax Tree) pour une analyse ultérieure. Puisqu'il s'agit essentiellement d'un opérateur binaire, créez un objet qui est une combinaison de LHS (côté gauche = côté gauche), RHS (côté droit = côté droit) et opérateur (opérateur).
Maintenant changez pour utiliser $ .seqMap () au lieu de $ .seq (). C'est comme une combinaison de $ .seq () et .map (), une méthode pratique qui prend la liste de résultats comme argument et rappelle la fonction spécifiée comme dernier argument. Je l'utilise comme ça.
var term = $.seqMap(factor, $.seq(muldiv, factor).many(), &(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;
});
«first» est le résultat de «factor» et «rest» est le résultat de «$ .seq (muldiv, factor) .many ()». Donc rest est un tableau de la forme [opérateur, côté droit] pour chaque élément (il peut s'agir d'un tableau vide). Il a la forme d'un AST. En conséquence, quelque chose comme «2 * 3 * 4» »est formaté comme suit.
first est 2reste est [['*', 3], ['*', 4]] contient 2` devient {lhs: 2, op: '*', rhs: 3} `. devient {lhs: {lhs: 2, op: '', rhs: 3}, op: '', rhs: 4} `.L'AST a une forme dans laquelle la branche gauche se développe (c'est ce qu'on appelle la connexion gauche). Tous les opérateurs cette fois sont associatifs à gauche.
Puisque «expression» est également la même, écrivons-la de la même manière. Le contenu est exactement le même, alors faisons-en une fonction et utilisons-la.
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 term = $.seqMap(factor, $.seq(muldiv, factor).many(), makeAST);
expression = $.seqMap(term, $.seq(addsub, term).many(), makeAST);
Je me sens rafraîchi.
Ensuite, c'est un ensemble de programmes. Avec juste cette définition, vous pouvez analyser quatre opérations de règles (avec la priorité de l'opérateur prise en compte). C'est merveilleux!
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));
Le résultat est comme ça. Ça marche!
"lhs": {
"lhs": 1,
"op": "+",
"rhs": {
"lhs": 2,
"op": "*",
"rhs": 3
}
},
"op": "+",
"rhs": {
"lhs": 2,
"op": "*",
"rhs": {
"lhs": 14,
"op": "-",
"rhs": 2
}
}
Vous avez maintenant l'AST souhaité. La prochaine fois, j'interpréterai ceci et le laisserai courir. J'utiliserai également la bibliothèque JIT que j'ai créée!
À la prochaine!