2015-09-01

Cet article a fait l'objet d'une traduction automatique.

Le travail programmeur

Combinateurs d'analyseurs

Ted Neward Avec la conclusion de la série multiparadigmatic, il a semblé temps s'aventurer hors dans le nouveau motif. Comme sort le voudrait, cependant, certains travaux de client récemment quitté me avec intéressant de matériel qui porte la discussion, a trait à la conception de logiciels, agit comme un autre exemple de l'analyse de la communité/variabilité au cœur de la série multiparadigmatic, et … bien, en fin de compte, c'est vraiment cool.

Le problème.

Le client j'ai est le cou de profondeur dans le monde scientifique neuro-optique et demanda me de travailler avec lui sur un nouveau projet visant à faire des expériences sur le tissu optique plus facile. Plus précisément, je travaille sur un système logiciel de contrôler une plate-forme de microscope qui conduira les divers dispositifs de stimulation (LEDs, lumières, etc.) qui déclenchent des réactions des tissus optique et puis capturer les résultats mesurés par matériel regarder le tissu optique.

Si tout semble vaguement Matrix-y pour vous, vous n'êtes pas entièrement seul. Quand j'ai entendu sur ce projet, ma réaction a été simultanément, « Oh, wow, ce qui est cool! », et « Oh, attente, j'ai juste vomi dans ma bouche un peu. »

Quoi qu'il en soit, une des choses clés sur l'appareil de forage est qu'elle aura une configuration assez complexe associée à chaque expérience exécuter, et qui nous a conduit à envisager comment spécifier que la configuration. D'une part, il a semblé un problème évident pour un fichier XML. Cependant, les gens courir le rig ne vont pas être programmeurs, mais plutôt des scientifiques et des assistants de laboratoire, donc il a semblé un peu lourde de s'attendre à écrire des fichiers XML bien formés (et à bien faire les choses à chaque tournant). La pensée de produire une sorte de système de configuration graphique nous a frappé comme hautement over-engineered, plus particulièrement en se transformerait rapidement en discussions sur la meilleure façon de capturer ouvertes à tous types de données.

En fin de compte, il semblait le plus approprié pour leur donner un format de configuration personnalisée, ce qui signifiait tonnes de l'analyse de texte de ma part. (Pour certains, cela impliquerait que je construis un DSL ; C'est un débat meilleur gauche de philosophes et d'autres individus impliqués dans la tâche grave de la consommation d'alcool). Heureusement, les solutions abondent dans cet espace.

Pensées

Un analyseur sert à deux fins utiles et intéressants : conversion de texte en une forme d'autre, plus significative et de vérifier et de valider le texte suivant une certaine structure (ce qui généralement est partie de l'aide pour la convertir en une forme plus significative). Ainsi, par exemple, un numéro de téléphone, qui est à son cœur juste une séquence de nombres, toujours a une structure à elle qui exige la vérification. Ce format varie d'un continent à l'autre, mais les nombres sont encore des nombres. En fait, un numéro de téléphone est un excellent exemple d'une affaire où la « forme plus significative » n'est pas une valeur entière — les chiffres ne sont pas une valeur entière, ils sont une représentation symbolique qu'est habituellement mieux représentée comme un type de domaine. (Les traitant comme « seulement » un numéro rend difficile d'extraire le code du pays ou la zone de code, par exemple.)

Si un numéro de téléphone est composé de chiffres et sont donc numéros (salaires, employé IDs et ainsi de suite), puis il va être certains chevauchements dans le code où nous analyser et vérifier les chiffres, sauf si nous étendre d'une certaine manière un analyseur. Ensuite, cela implique que nous aimerions quelque analyseur nous construisons pour être ouvertes à tous, permettant à quelqu'un à l'aide de la bibliothèque du parseur de la pour prolonger de différentes manières (codes postaux canadiens, par exemple) sans avoir à modifier la source elle-même. Ceci est connu comme le « principe ouvert-fermé »: entités logicielles doit être ouvertes pour l'extension, mais fermé pour modification.

Solution : Génératif métaprogrammation

Une solution est l'approche traditionnelle « lex et yacc », connu plus officiellement comme un « générateur d'analyseur ». Cela implique spécifiant la syntaxe du fichier de configuration dans un format abstrait — certaines variations sur la Backus-Naur forme habituellement (BNF) syntaxe/grammaire utilisée pour décrire la grammaire formelle, comme quelle utilisation de langues plus programmation — puis exécute un outil pour générer du code pour sélectionner l'entrée de chaîne apart et les céder une sorte d'arbre de structures ou d'objets en conséquence. Généralement, ce processus impliqué est divisé en deux étapes, la « lexing » et « l'analyse », dans lequel le lexer abord transforme la chaîne input en jetons, que les personnages ne constituent en fait des jetons légitimes le long de la voie de la validation. L'analyseur prend les jetons et valide que les jetons apparaissent dans l'ordre approprié et contiennent les valeurs appropriées, et ainsi de suite, habituellement en transformant les jetons en certains type de résumé de structure de l'arbre pour une analyse plus poussée.

Les problèmes avec les générateurs de l'analyseur sont les mêmes pour toute approche métaprogrammation génératif : le code généré devront être régénérés à l'événement que la syntaxe change. Mais plus important encore pour ce genre de scénario, le code généré sera générée par ordinateur, avec tous les merveilleux variable nommage qui vient avec le code généré par ordinateur (quelqu'un prêt à prendre position pour les variables telles que « integer431 » et « string$ $x$ y$ z »?), donc difficile à déboguer.

Solution : fonctionnelle

Dans un certain type de lumière, l'analyse est fondamentalement fonctionnel : il prend d'entrée, effectue une sorte d'opération sur elle et produit un résultat en conséquence. Le perspectives critique, il s'avère, c'est qu'un analyseur syntaxique peut être créé de lots de little parseurs, dont chacun analyse un petit peu de la chaîne en entrée, puis retourne un jeton et une autre fonction d'analyser la prochain peu de chaîne en entrée. Ces techniques, qui selon moi ont été introduits en Haskell, sont officiellement connues comme combinators de l'analyseur, et ils s'avèrent pour être une solution élégante à l'analyse des problèmes de « moyenne » — analyseurs qui ne sont pas nécessairement aussi complexes comme un langage de programmation nécessiterait, mais quelque chose au-delà de ce que peut faire String.Split (ou une série de hacké-up de balayages de regex).

Dans le cas de combinators de l'analyseur syntaxique, l'exigence d'open-pour-extension est réalisée par la création de petites fonctions, puis à l'aide de techniques fonctionnelles « combiner » en grandes fonctions (qui est là où nous avons les « combinators » du nom). Les analyseurs de plus grandes peuvent être constitués par toute personne ayant des compétences suffisantes pour comprendre la composition de la fonction. Cette technique est un général qui porte l'exploration, mais j'économiserez que pour une colonne future.

Il s'avère que, il y a plusieurs bibliothèques de combinateur analyseur disponible pour Microsoft.NET Framework, beaucoup d'entre eux basée sur le module Parsec écrit en Haskell qui sorte de définie la norme pour l'analyseur bibliothèques combinatoire. Deux de ces bibliothèques est FParsec, écrit pour F # et Sprache, écrit en c#. Chacun est open source et relativement bien documenté, telle qu'elles servent le double objectif d'être tous deux utiles hors de la boîte et comme un modèle à partir pour l'étude des idées de design. Je vous laisse également de FParsec pour une colonne future.

« Sprache Sie l'analyse? »

Sprache, disponible à code.google.com/p/sprache, se décrit comme une "simple et léger bibliothèque pour la construction des analyseurs directement dans le code c#," qui "n'est pas rivaliser avec établis de langue"force industrielle". Il se place entre les expressions régulières et un ensemble d'outils complet comme ANTLR. » (ANTLR est un générateur d'analyseurs, ajuster dans la catégorie génératif métaprogrammation, comme lex et yacc).

Pour commencer avec Sprache est simple : Télécharger le code, le projet, puis copiez l'assembly de Sprache.dll dans le répertoire de dépendance de votre projet et ajouter la référence au projet. A partir de là, tout le travail de définition du parseur est fait en déclarant des instances de Sprache.Parser et en les combinant de manière particulière pour créer des instances de Sprache.Parser, qui à son tour peut, si vous le souhaitez (et il est habituellement), retournent des objets de domaine contenant certaines ou toutes les valeurs analysées.

Sprache Simple

D'abord, commençons par un analyseur qui sait comment analyser les numéros de téléphone entrées par l'utilisateur dans un type de domaine PhoneNumber. Pour plus de simplicité, je maintiens avec l'américaine format—(nnn) nnn-nnnn — mais nous voulons expressément reconnaître l'effondrement indicatifs, préfixe et ligne et leur permettre de lettres, de chiffres (donc quelqu'un peut entrer leur numéro de téléphone comme "(800) EAT-NUTS" s'ils le désirent). Idéalement, le type de domaine PhoneNumber convertira entre alpha et formes entièrement numérique à la demande, mais que restera-t-il des fonctionnalités comme un exercice au lecteur (c'est-à-dire, essentiellement, que je ne veux pas s'embêter avec elle).

(Le pédant en moi exige de souligner que simplement convertir tous les alphas aux numéros pas une solution entièrement conforme, en passant. Au Collège, il était commun dans mon cercle d'amis pour tenter de venir avec des numéros de téléphone orthographié "cool" choses — un ex-colocataire est toujours en attente de 1-800-CTHULHU de devenir libre, en fait, donc il peut gagner le jeu pour toute l'éternité.)

Le moyen le plus simple point de départ est avec le type de domaine PhoneNumber :

class PhoneNumber
{
  public string AreaCode { get; set; }
  public string Prefix { get; set; }
  public string Line { get; set; }
}

C'était un type de domaine « réel », indicatif régional, préfixe et ligne aurait code de validation dans leurs méthodes de jeu de propriétés, mais qui conduirait à une répétition du code entre l'analyseur et la classe de domaine (qui, en passant, nous allons corriger avant tout cela).

Ensuite, nous avons besoin de savoir comment créer un analyseur simple qui sait comment analyser n nombre de chiffres :

public static Parser<string> numberParser =
  Parse.Digit.AtLeastOnce().Text();

Il est simple de définir la numberParser. Commencer avec l'analyseur primitif chiffre (une instance d'un analyseur <T> définie sur la classe de Sprache.Parse) et décrire que nous voulons au moins un chiffre dans le flux d'entrée, implicitement consommant soit jusqu'à ce que le flux d'entrée de tous les chiffres s'exécute sec ou l'analyseur rencontre un caractère non chiffres. La méthode de texte convertit le flux des résultats analysés en une chaîne unique pour notre consommation.

Ce test est assez facile — il se nourrissent une chaîne et laissez er rip :

[TestMethod]
public void ParseANumber()
{
  string result = numberParser.Parse("101");
  Assert.AreEqual("101", result);
}
[TestMethod]
public void FailToParseANumberBecauseItHasTextInIt()
{
  string result = numberParser.TryParse("abc").ToString();
  Assert.IsTrue(result.StartsWith("Parsing failure"));
}

Lorsque les exécuter, cela stocke « 101 » dans le résultat. Si la méthode Parse est alimentée une chaîne d'entrée de "abc", il produira une exception. (Si il est préférable de comportement nonthrowing, Sprache possède également une méthode TryParse qui renvoie un objet de résultat qui peut être interrogé au sujet de la réussite ou l'échec.)

La situation de l'analyse de numéro de téléphone est un peu plus compliquée, bien que ; Elle a besoin analyser seulement trois ou quatre chiffres — pas plus, rien de moins. Définir une telle analyseur (l'analyseur à trois chiffres) est un peu plus délicat, mais toujours faisable :

public static Parser<string> threeNumberParser =
  Parse.Numeric.Then(first =>
    Parse.Numeric.Then(second =>
      Parse.Numeric.Then(third =>
        Parse.Return(first.ToString() +
          second.ToString() + third.ToString()))));

L'analyseur numérique prend un caractère et, si c'est un chiffre, avances pour le caractère suivant. Le puis méthode prend une fonction (sous la forme d'une expression lambda) à exécuter. La méthode retour recueille de chacun de ces dans une seule chaîne et, comme son nom l'indique, qui utilise la valeur de retour (voir Figure 1).

La figure 1, l'analyse d'un numéro de téléphone

[TestMethod]
public void ParseJustThreeNumbers()
{
  string result = threeNumberParser.Parse("123");
  Assert.AreEqual("123", result);
}
[TestMethod]
public void ParseJustThreeNumbersOutOfMore()
{
  string result = threeNumberParser.Parse("12345678");
  Assert.AreEqual("123", result);
}
[TestMethod]
public void FailToParseAThreeDigitNumberBecauseItIsTooShort()
{
  var result = threeNumberParser.TryParse("10");
  Assert.IsTrue(result.ToString().StartsWith("Parsing failure"));
}

Réussite. Pour l'instant. (Oui, la définition de threeNumberParser est maladroite — il y a certainement être une meilleure façon de définir ce ! N'ayez pas peur : il y a, mais pour comprendre comment étendre l'analyseur, nous devons plonger plus profondément dans Comment Sprache est construit, et c'est le thème de la prochaine partie de cette série.)

Maintenant, toutefois, nous avons besoin gérer la parens de gauche, la droite -parens et le tiret et tout convertir en un objet PhoneNumber. Il peut sembler un peu délicat avec ce que nous voir pour l'instant, mais regarder ce qui se passe ensuite, comme le montre Figure 2.

La figure 2, conversion d'entrée en un objet PhoneNumber

public static Parser<string> fourNumberParser =
  Parse.Numeric.Then(first =>
    Parse.Numeric.Then(second =>
      Parse.Numeric.Then(third =>
        Parse.Numeric.Then(fourth =>
          Parse.Return("" + first.ToString() +
            second.ToString() + third.ToString() +
              fourth.ToString())))));
public static Parser<string> areaCodeParser =
  (from number in threeNumberParser
  select number).
XOr(
  from lparens in Parse.Char('(')
  from number in threeNumberParser
  from rparens in Parse.Char(')')
  select number);
public static Parser<PhoneNumber> phoneParser =
  (from areaCode in areaCodeParser
  from _1 in Parse.WhiteSpace.Many().Text()
  from prefix in threeNumberParser
  from _2 in (Parse.WhiteSpace.Many().Text()).
Or(Parse.Char('-').Many())
  from line in fourNumberParser
  select new PhoneNumber() { AreaCode=areaCode, Prefix=prefix, Line=line});
Using the parser becomes pretty straightforward at this point:
[TestMethod]
public void ParseAFullPhoneNumberWithSomeWhitespace()
{
  var result = phoneParser.Parse("(425) 647-4526");
  Assert.AreEqual("425", result.AreaCode);
  Assert.AreEqual("647", result.Prefix);
  Assert.AreEqual("4526", result.Line);
}

Mieux, l'analyseur est entièrement extensible, parce qu'il, trop, peut être composé dans un analyseur plus gros qui transforme de saisie de texte dans un objet adresse ou objet InfosContact ou quoi que ce soit d'autre imaginables.

Le Concept de combinatoire

Historiquement, l'analyse de texte a été la province de « chercheurs de langue » et le monde universitaire, principalement en raison de la difficile et compliqué cycle d'edit-générer-compilation-test-debug inhérent des solutions métaprogrammation générative. Essayant de traverser computer -code généré — particulièrement les versions base finie-État-machine qui produiront en série de nombreux générateurs d'analyseur — dans un débogueur est un défi pour les plus de discours développeur. Pour cette raison, la plupart des développeurs ne pense pas que sur les solutions ainsi que l'analyse des lignes lorsque présentée avec un problème de basé sur du texte. Et, en vérité, la plupart du temps, une solution à base d'analyseur-générateur serait overkill drastique.

Combinators analyseur servent une solution in-between nice : assez souple et assez puissant pour gérer certains parsage non trivial, sans exiger un Ph.d. en informatique, pour comprendre comment les utiliser. Fait encore plus intéressant, le concept de la combinatoire est une fascinante et conduit à quelques autres idées intéressantes, que dont certains nous allons explorer plus tard.

Dans l'esprit dans lequel cette colonne est né, s'assurer de garder un « œil » pour mon prochain article (Désolé, n'a pas pu résister), dans lequel je vais étendre Sprache juste une touche, pour réduire la laideur des analyseurs trois et quatre chiffres définis ici.

Bon codage !

Ted Neward est un consultant architectural avec Neudesic LLC. Il a écrit plus de 100 articles et est l'auteur ou coauteur d'une douzaine de livres, dont « Professionnel F # 2.0 » (Wrox, 2010). Il est un MVP c# et parle à des conférences dans le monde entier. Il consulte et mentors régulièrement — le joindre à ted@tedneward.com ou Ted.Neward@neudesic.com si vous êtes intéressé à avoir lui venir travailler avec votre équipe, ou lire son blog à blogs.tedneward.com.

Grâce à l'expert technique suivante pour l'examen de cet article : Luke Hoban

Partager via