** "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.
Il n'y a pas longtemps, je l'ai exécuté avec Kinx Library-Parser Combinator (Part 2). Quelle est cette fois?
Oui, je voudrais vous présenter l'interface. Je suis désolé, j'ai oublié de le faire la dernière fois.
Parsek
Les instances de la classe Parsek ont les méthodes suivantes: Le «$» dans l'instruction indique l'instance de Parsek réelle qui a été instanciée.
Les analyseurs prédéfinis suivants existent déjà dans l'instance de la classe Parsek.
| Analyseur prédéfini | Contenu |
|---|---|
| $.eof | Un analyseur qui réussit s'il s'agit d'un EOF. |
| $.any | Un analyseur qui réussit avec n'importe quel caractère unique. |
| $.all | Un analyseur qui traite tout jusqu'à la fin et réussit. |
| $.index | Renvoie la position actuelle ({ offset, line, column}). offset est 0 point de départ, ligne/la colonne est un point de départ. |
| $.letter | $.regex(/[a-zA-Z]/)Pareil que. |
| $.letters | $.regex(/[a-zA-Z]*/)Pareil que. |
| $.digit | $.regex(/[0-9]/)Pareil que. |
| $.digits | $.regex(/[0-9]*/)Pareil que. |
| $.whitespace | $.regex(/\s+/)Pareil que. |
| $.optWhitespace | $.regex(/\s*/)Pareil que. |
| $.cr | $.string("\r")Pareil que. |
| $.lf | $.string("\n")Pareil que. |
| $.crlf | $.string("\r\n")Pareil que. |
| $.newline | $.alt($.crlf, $.lf, $.cr)Pareil que. |
| $.end | $.alt($.newline, $.eof)Pareil que. |
Les instances de la classe Parsek ont la capacité de générer des analyseurs à l'aide des méthodes suivantes:
| Fonction de génération d'analyseur | Contenu |
|---|---|
| $.string(str) | strCrée un analyseur qui réussit s'il correspond à la chaîne spécifiée dans. |
| $.regex(re, groupIndex) | reCrée un analyseur qui réussit s'il correspond à l'expression régulière spécifiée dans. La valeur estgroupIndexLe résultat de la capture du groupe spécifié dans est entré. |
| $.succeed(result) | resultPour créer un analyseur qui réussit toujours. |
| $.fail(message) | messageCréez un analyseur qui échoue en laissant un message. |
| $.oneOf(chars) | charsCréez un analyseur qui réussit s'il correspond à un caractère contenu dans. |
| $.noneOf(chars) | charsCréez un analyseur qui réussit s'il ne correspond pas à un caractère contenu dans. |
| $.sepBy(content, separator) | contentUne chaîne qui peut être analysée avecseparatorCréez un analyseur qui renvoie le résultat divisé par le résultat correspondant. |
| $.sepBy1(content, separator) | sepByEst autorisé 0,sepBy1Échoue si au moins un ne correspond pas. |
| $.lazy(description, f) | fSpécifiez une fonction qui renvoie un analyseur à, et générez un analyseur lors de sa première utilisation. |
| $.alt(...parsers) | Crée un analyseur qui réussit s'il correspond à l'un des analyseurs spécifiés. L'application se fait dans l'ordre spécifié. |
| $.takeWhile(predicate) | Le personnage suivant estpredicateCréez un analyseur qui continuera à réussir tant qu'il est vrai. |
| $.seq(...parsers) | Crée un analyseur qui réussit lorsqu'il correspond à plusieurs analyseurs spécifiés dans l'ordre. Les résultats sont renvoyés sous forme de tableau de tous les résultats. |
| $.seqMap(...parsers, mapf) | Crée un analyseur qui réussit lorsqu'il correspond à plusieurs analyseurs spécifiés dans l'ordre. Le résultat est un tableau de tous les résultats, mais il renvoie la valeur renvoyée par la fonction spécifiée par mapf. |
ParsekParser
L'analyseur généré par la méthode de la classe Parsek est une instance de la classe ParsekParser. Cette classe définit les méthodes de chaînage des analyseurs.
Une fois que tous les analyseurs sont prêts, exécutez l'analyse avec la méthode suivante.
| Méthode | Contenu |
|---|---|
| parser.parseAll(target) | targetContreparserExécutez l'analyse avec. |
| Fonction de génération d'analyseur | Contenu |
|---|---|
| parser.desc(description) | parserDéfinissez le message à afficher lorsque l'analyse par échoue. |
| parser.or(nextParser) | parserSi l'analyse parnextParserCréez un analyseur qui essaie. |
| parser.and(nextParser) | parserSi vous réussissez à analyser parnextParserCréez un analyseur à exécuter. Le résultat est renvoyé sous forme de tableau. |
| parser.then(nextParser) | parserSi vous réussissez à analyser parnextParserCréez un analyseur à exécuter. Le résultat estnextParserRenvoyer celuiparserLe résultat de est ignoré. |
| parser.skip(nextParser) | parserSi vous réussissez à analyser parnextParserCréez un analyseur à exécuter. Le résultat estparserRenvoyer celuinextParserLe résultat de est ignoré. |
| parser.many() | parserCréez un analyseur qui analyse l'occurrence de 0 fois ou plus. |
| parser.many1() | parserCréez un analyseur qui analyse les apparitions plus d'une fois. |
| parser.times(min, max) | parserMaisminPlus d'une foismaxCréez un analyseur qui analyse l'apparence à plusieurs reprises pas plus d'une fois. ..maxSi est omis, justeminSuccès en cas de nombre de fois. |
| parser.sepBy(separator) | parserUne chaîne qui peut être analysée avecseparatorCréez un analyseur qui renvoie le résultat divisé par le résultat correspondant. |
| parser.sepBy1(separator) | sepByEst autorisé 0,sepBy1Échoue si au moins un ne correspond pas. |
| parser.map(f) | parserUtilisez le résultat de ce qui précède converti par la fonction f. |
| parser.chain(f) | parserPassez le résultat de à la fonction f et connectez les analyseurs pour utiliser le nouvel analyseur renvoyé par f comme analyseur suivant. |
| parser./(nextParser) | parser.or(nextParser)Un autre nom pour. |
| parser.+(nextParser) | nextParserSans préciserparser.+()Lorsqu'il est utilisé commeparser.many1()Un autre nom pour.nextParserSi vous spécifiezparser.and(nextParser)Un autre nom pour. |
| parser.*() | parser.many()Un autre nom pour. |
Packrat Parsing
Prend en charge l'analyse Packrat.
Les combinateurs d'analyseurs procèdent généralement à une analyse en retour. En d'autres termes, par exemple, dans le cas de «$ .alt (a, b, c)», si l'analyseur de «a» échoue, il procédera comme «b», mais le même analyseur peut être répété plusieurs fois au milieu.
Par conséquent, lors du retour en arrière, une amélioration des performances peut être attendue en mettant en cache certains résultats et en les réutilisant en utilisant la propriété qui ** si elle est analysée au même endroit et dans les mêmes conditions, le même résultat sera obtenu **. .. C'est un mémo.
Parsek prend en charge cette fonctionnalité. Au fait, il peut être désactivé en spécifiant {disablePackratParsing: true} dans le constructeur lors de la création d'une instance Parsek.
Voyons ses performances avec un benchmark. Reportez-vous à ici pour gérer la grammaire qui cause un nombre énorme de retours en arrière. La grammaire est ci-dessous.
S <- A
A <- P "+" A / P "-" A / P
P <- "(" A ")" / "1"
Cela analysera la chaîne suivante:
(((((((((((((1)))))))))))))
L'explication est facile à comprendre, je vais donc la citer telle quelle.
L'essence de cette combinaison de règles et de chaînes est qu'elle doit passer par toutes les combinaisons A et P avant d'être finalement analysée. En d'autres termes, le pire des cas de retour en arrière peut être presque reproduit. Donc, si vous revenez franchement en arrière, le temps de traitement devrait augmenter de façon exponentielle avec le nombre de correspondances entre parenthèses.
Non, c'est incroyable.
Alors, voici le code source du benchmark. L'analyseur lui-même est le même, donc le même test est fait avec l'analyseur $ D avec {disablePackratParsing: true} ʻet l'analyseur $ E` avec celui-ci activé.
using Parsek;
var $E = new Parsek();
var $D = new Parsek({ disablePackratParsing: true });
var tmr = new SystemTimer();
// rule:
// S <- A
// A <- P "+" A / P "-" A / P
// P <- "(" A ")" / "1"
// input:
// (((((((((((((1)))))))))))))
function generateParser($) {
var S, A, P;
S = $.lazy(&() => A);
A = $.lazy(&() => $.alt($.seq(P, $.string('+'), A), $.seq(P, $.string('-'), A), P));
P = $.alt($.seq($.string('('), A, $.string(')')), $.string('1'));
return S;
}
function test($) {
for (var i = 0; i <= 10; ++i) {
tmr.restart();
var r = generateParser($).parseAll(('(' * i) + '1' + (')' * i));
var elapsed = tmr.elapsed();
System.println(["%8.5f" % elapsed, r]);
}
}
test($E);
test($D);
Faisons le!
Si valide
[" 0.00090", {"position":1,"status":1,"value":"1"}]
[" 0.00041", {"position":3,"status":1,"value":["(","1",")"]}]
[" 0.00044", {"position":5,"status":1,"value":["(",["(","1",")"],")"]}]
[" 0.00061", {"position":7,"status":1,"value":["(",["(",["(","1",")"],")"],")"]}]
[" 0.00083", {"position":9,"status":1,"value":["(",["(",["(",["(","1",")"],")"],")"],")"]}]
[" 0.00055", {"position":11,"status":1,"value":["(",["(",["(",["(",["(","1",")"],")"],")"],")"],")"]}]
[" 0.00061", {"position":13,"status":1,"value":["(",["(",["(",["(",["(",["(","1",")"],")"],")"],")"],")"],")"]}]
[" 0.00071", {"position":15,"status":1,"value":["(",["(",["(",["(",["(",["(",["(","1",")"],")"],")"],")"],")"],")"],")"]}]
[" 0.00200", {"position":17,"status":1,"value":["(",["(",["(",["(",["(",["(",["(",["(","1",")"],")"],")"],")"],")"],")"],")"],")"]}]
[" 0.00101", {"position":19,"status":1,"value":["(",["(",["(",["(",["(",["(",["(",["(",["(","1",")"],")"],")"],")"],")"],")"],")"],")"],")"]}]
[" 0.00196", {"position":21,"status":1,"value":["(",["(",["(",["(",["(",["(",["(",["(",["(",["(","1",")"],")"],")"],")"],")"],")"],")"],")"],")"],")"]}]
Lorsqu'il est désactivé
[" 0.00022", {"position":1,"status":1,"value":"1"}]
[" 0.00034", {"position":3,"status":1,"value":["(","1",")"]}]
[" 0.00097", {"position":5,"status":1,"value":["(",["(","1",")"],")"]}]
[" 0.00353", {"position":7,"status":1,"value":["(",["(",["(","1",")"],")"],")"]}]
[" 0.01142", {"position":9,"status":1,"value":["(",["(",["(",["(","1",")"],")"],")"],")"]}]
[" 0.02686", {"position":11,"status":1,"value":["(",["(",["(",["(",["(","1",")"],")"],")"],")"],")"]}]
[" 0.09525", {"position":13,"status":1,"value":["(",["(",["(",["(",["(",["(","1",")"],")"],")"],")"],")"],")"]}]
[" 0.26821", {"position":15,"status":1,"value":["(",["(",["(",["(",["(",["(",["(","1",")"],")"],")"],")"],")"],")"],")"]}]
[" 0.72229", {"position":17,"status":1,"value":["(",["(",["(",["(",["(",["(",["(",["(","1",")"],")"],")"],")"],")"],")"],")"],")"]}]
[" 2.44629", {"position":19,"status":1,"value":["(",["(",["(",["(",["(",["(",["(",["(",["(","1",")"],")"],")"],")"],")"],")"],")"],")"],")"]}]
[" 7.48334", {"position":21,"status":1,"value":["(",["(",["(",["(",["(",["(",["(",["(",["(",["(","1",")"],")"],")"],")"],")"],")"],")"],")"],")"],")"]}]
Si l'analyse Packrat est activée, 10 parenthèses se termineront en 2 millisecondes. En revanche, lorsqu'il est désactivé, cela prend 7,5 secondes lorsque les 10 dernières parenthèses sont atteintes.
Combinateur d'analyseur, c'est pratique d'essayer ceci. Je ne l'ai pas beaucoup utilisé, mais je pense que je vais l'utiliser un peu plus à l'avenir. Vous pouvez facilement analyser des chaînes qui ne peuvent pas être exprimées par des expressions régulières.
Vous pouvez l'utiliser pour créer un système de traitement de la langue. Kinx utilise yacc pour l'analyse syntaxique et l'écriture manuscrite pour l'analyse des phrases.
A l'origine, j'aime l'analyse syntaxique elle-même et l'analyseur descendant récursif manuscrit, mais j'utilise exclusivement yacc car il est difficile de changer la définition de la grammaire. Cependant, le combinateur d'analyseur peut également effectuer une analyse de phrase, ce qui est pratique.
à plus!