Il presente articolo è stato tradotto automaticamente.

Il lavoro programmatore

Combinatori parser

Ted Neward

Ted NewardCon la conclusione della serie multiparadigmatic, sembrava il tempo di avventurarsi fuori nel nuovo terreno. Come destino l'avrebbe, tuttavia, qualche lavoro di client recentemente mi ha lasciato con interessante materiale che reca la discussione, si riferisce al design del software, agisce come un altro esempio dell'analisi comunanza/variabilità il nucleo della serie multiparadigmatic, e … Beh, alla fine, è solo davvero cool.

Il problema

Il client che ho è collo profonda nel mondo scientifico neuro-ottico e ha chiesto a lavorare con lui su un nuovo progetto progettato per rendere più facile il conducendo esperimenti sul tessuto ottico. In particolare, sto lavorando su un sistema di software per il controllo di un impianto di microscopio che guiderà i vari dispositivi stimolo (LED, luci e così via) che innescano risposte dal tessuto ottico e quindi acquisire i risultati misurati dall'hardware guardando il tessuto ottico.

Se tutto suona vagamente Matrix-y a voi, non siete completamente soli. Quando ho sentito su questo progetto, la mia reazione fu contemporaneamente, "Oh, wow, che è cool!" e, "Oh, aspetta, ho appena vomitato nella mia bocca un po'."

In ogni caso, una delle cose principali su rig è quella che avrà una configurazione abbastanza complessa connesso con ogni esperimento eseguito, e che ci ha portato a contemplare come specificare che la configurazione. Da un lato, sembrava un problema evidente per un file XML. Tuttavia, la gente che correva l'impianto non stanno andando essere programmatori di computer, ma piuttosto gli scienziati e gli assistenti di laboratorio, così è sembrato un po' pesante aspettarsi loro di scrivere file XML ben formati (e farlo bene ad ogni turno). Il pensiero di produrre una sorta di sistema di configurazione basata su GUI ci ha colpito come altamente over-engineered, in particolare, come sarebbe rapidamente trasformarsi in discussioni del modo migliore per catturare a tempo indeterminato tipi di dati.

Alla fine, è sembrato più appropriato dare loro un formato di configurazione personalizzata, che significava tonnellate di analisi del testo da parte mia. (Per alcuni, ciò implicherebbe che sto costruendo una linea DSL; Questo è un dibattito migliore sinistra ai filosofi e altre persone coinvolte nel grave compito di consumo di alcol). Fortunatamente, soluzioni abbondano in questo spazio.

Pensieri

Un parser serve a due scopi utili e interessanti: conversione di testo in qualche forma di altri, più significativo e il testo per la verifica e il convalida segue una certa struttura (che in genere è parte di aiutare a convertirlo in una forma più significativa). Così, ad esempio, un numero di telefono, che è nel suo cuore solo una sequenza di numeri, ancora ha una struttura ad esso che richiede la verifica. Tale formato varia da un continente a altro, ma i numeri sono ancora numeri. In realtà, un numero di telefono è un grande esempio di un caso in cui il "modulo più significativo" non è un valore integer — le cifre non sono un valore integer, sono una rappresentazione simbolica che di solito è meglio rappresentata come un tipo di dominio. (Trattarli come "solo" un numero rende difficili da estrarre il codice paese o il codice di zona, per esempio.)

Se un numero di telefono è costituito da cifre e così sono i numeri (salari, employee ID e così via), quindi ci sta per essere alcuni doppioni in codice dove abbiamo analizzare e verificare le cifre, a meno che in qualche modo estendiamo un parser. Questo implica, quindi, che vorremmo qualunque parser costruiamo per essere a tempo indeterminato, permettendo a qualcuno usando la libreria/parser di estendere in modi diversi (Canadian codici postali, per esempio) senza dover modificare l'origine stessa. Questo è conosciuto come il "principio di apertura-chiusura": Entità software dovrebbe essere aperta per estensione, ma chiuso per la modifica.

Soluzione: Generativa metaprogrammazione

Una soluzione è l'approccio tradizionale "lex/yacc", noto più formalmente un "generatore di parser." Questo comporta specificando la sintassi del file di configurazione in un formato astratto — solitamente alcune variazioni su Backus-Naur formare sintassi/grammatica (BNF) utilizzato per descrivere la grammatica formale, come ad esempio quello che uso di lingue più programmazione — poi eseguire uno strumento per generare codice per raccogliere l'input della stringa a pezzi e resa una sorta di struttura ad albero di oggetti o di strutture di conseguenza. In generale, questo processo coinvolto è suddiviso in due fasi, "lexing" e "analisi", in cui la lexer prima trasforma la stringa di input in gettoni, convalida che i personaggi infatti formano legittimo token lungo la strada. Il parser prende i token e convalida i token stanno comparendo in ordine appropriato e contengono i valori appropriati, e così via, solitamente trasformando i token in alcune specie di astrarre la struttura ad albero per un'ulteriore analisi.

I problemi con i generatori di parser sono gli stessi per qualsiasi approccio metaprogrammazione generativa: Il codice generato dovranno essere rigenerato nel caso in cui la sintassi cambia. Ma ancora più importante per questo tipo di scenario, il codice generato sarà generato al computer, con tutte le meravigliose variabile denominazione che viene fornito con il codice generato dal computer (qualcuno pronto a lottare per variabili come "integer431" e "string$ $x$ y$ z"?), così difficile eseguire il debug.

Soluzione: Funzionale

In un certo tipo di luce, l'analisi è fondamentalmente funzionale: Prende in input, esegue una sorta di operazione su di esso e produce un output di conseguenza. La comprensione critica, scopre, è che è possibile creare un parser di un sacco di piccoli parser, ognuna delle quali analizza un pochino di input della stringa, quindi restituisce un token e un'altra funzione di analizzare il prossima po ' di input della stringa. Queste tecniche, che credo che furono introdotte nel Haskell, sono formalmente conosciute come combinatori parser e risultano essere una soluzione elegante per "medie", l'analisi di problemi — parser che non sono necessariamente così complesso come richiederebbe un linguaggio di programmazione, ma qualcosa di là di ciò che può fare String (o una serie di hacked-up di scansioni regex).

Nel caso di combinatori parser, l'obbligo di aprire per estensione è realizzato creando piccole funzioni, quindi utilizzando tecniche funzionali per "combinare" in funzioni più grandi (che è dove otteniamo i combinatori"nome"). Parser più grandi possono essere composti da chiunque con sufficiente abilità di comprendere la composizione di funzioni. Questa tecnica è una generale che porta l'esplorazione, ma che risparmia per una colonna di futura.

Come si scopre, ci sono diverse librerie di combinator parser disponibile per Microsoft.NET Framework, molti dei quali basati sul modulo Parsec scritto in Haskell che sorta di impostare lo standard per parser librerie combinatore. Due di tali librerie sono FParsec, scritto per F # e Sprache, scritto in c#. Ciascuno è open source e relativamente ben documentati, tale che essi servono il duplice scopo di essere entrambi utili dalla scatola e come un modello da cui studiare le idee di design. Vi lascio anche FParsec per un articolo futuro.

"Sprache Sie l'analisi?"

Sprache, disponibile presso code.google.com/p/sprache, si descrive come un "semplice, leggero library per la costruzione di parser direttamente nel codice c#," che "non gareggerà con banchi di lingua «forza industriale». Si adatta da qualche parte tra le espressioni regolari e un set di strumenti completo come ANTLR." (ANTLR è un generatore di parser, montaggio nella categoria Metaprogramming generativa, come lex/yacc).

Guida introduttiva a Sprache è semplice: Scarica il codice, compilare il progetto, poi copiare l'assembly Sprache.dll nella directory di dipendenza del tuo progetto e aggiungere il riferimento al progetto. Da qui, tutto il lavoro di definizione di parser è fatto dichiarando Sprache.Parser istanze e combinandole in particolari modi per creare istanze di Sprache.Parser, che a sua volta può, se lo si desidera (e di solito è), restituiscono oggetti di dominio contenente alcuni o tutti i valori analizzati.

Sprache semplice

Per iniziare, iniziamo con un parser che sa come analizzare i numeri di telefono immessi dall'utente in un tipo di dominio del numero di telefono. Per semplicità, attaccherò con la U.S.-stile format—(nnn) nnn-nnnn — ma vogliamo specificamente riconoscere la ripartizione in codici di zona, prefisso e linea e consentire per le lettere al posto delle cifre (in modo che qualcuno entrare il loro numero di telefono come "(800) EAT-noci" se lo desiderano). Idealmente, il tipo di dominio PhoneNumber convertirà fra alfa e forme numeriche su richiesta, ma che funzionalità sarà lasciato come esercizio per il lettore (che significa, in sostanza, che non voglio perdere tempo con esso).

(Il pedante in me chiede a precisare che non semplicemente conversione tutti l'alfa in numeri è una soluzione completamente compatibile, tra l'altro. In collegio, era comune nel mio cerchio di amici per cercare di venire con numeri di telefono che precisano le cose "cool" — un ex-coinquilino è ancora in attesa di 1-800-CTHULHU a diventare libero, in realtà, così può vincere il gioco per tutta l'eternità.)

Il posto più semplice per iniziare è con il tipo di dominio del numero di telefono:

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

Questo era un tipo di dominio "reale", prefisso locale, prefisso e linea avrebbe il codice di convalida in loro metodi set di proprietà, ma che porterebbe ad una ripetizione del codice tra il parser e la classe di dominio (che, tra l'altro, noi ti fissare prima che questo è tutto fatto).

Successivamente, abbiamo bisogno di sapere come creare un semplice parser che sa come analizzare n numero di cifre:

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

Definire il numberParser è semplice. Iniziare con il parser primitivo Digit (un'istanza di un Parser <T> definito nella classe Sprache.Parse) e descrivere che vogliamo almeno una cifra nel flusso di input, implicitamente consumare tutte le cifre fino al flusso di input o corre secco o il parser rileva un carattere non numerico. Il metodo di testo converte il flusso di risultati analizzati in una singola stringa per il nostro consumo.

Questo test è piuttosto facile — alimentargli una stringa e lasciare ' 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"));
}

Quando esegue, archiviati "101" nel risultato. Se il metodo Parse è alimentato una stringa di input di "abc", produrranno un'eccezione. (Se nonthrowing comportamento è preferito, Sprache ha anche un metodo TryParse che restituisce un oggetto risultato che può essere interrogato per quanto riguarda il successo o il fallimento.)

La situazione di analisi del numero di telefono è un po' più complicata, però; ha bisogno di analizzare solo tre o quattro cifre — non più né meno. Definire una tale parser (il parser di tre cifre) è un po' più complicato, ma ancora fattibile:

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()))));

Il parser numerico assume un carattere e, se si tratta di una cifra, avanza per il carattere successivo. L'allora metodo accetta una funzione (in forma di un'espressione lambda) da eseguire. Il metodo Return raccoglie ciascuno di questi in un'unica stringa e, come suggerisce il nome, che utilizza come valore restituito (vedere Figura 1).

Figura 1 l'analisi di un numero di telefono

[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"));
}

Riuscita. Finora. (Sì, la definizione di threeNumberParser è imbarazzante — sicuramente ci deve essere un modo migliore per definire questo! Non temere: c'è, ma per capire come estendere il parser, dobbiamo tuffarsi più profondo come Sprache è costruito, e questo è l'oggetto della parte successiva in questa serie.)

Ora, tuttavia, abbiamo bisogno di gestire la parentesi sinistra, destra -­parens e cruscotto e convertire il tutto in un oggetto PhoneNumber. Potrebbe sembrare un po' scomodo con che cosa abbiamo vedere così lontano, ma guarda che cosa succede dopo, come mostrato nella Figura 2.

Figura 2 conversione di Input in un oggetto 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);
}

Meglio di tutti, il parser è interamente estensibile, perché essa, troppo, può essere composti in un parser più grande che trasforma input di testo in un oggetto di indirizzo o ContactInfo oggetto o niente altro che si possa immaginare.

Il concetto di calcolo combinatorio

Storicamente, analisi del testo è stata autonoma di "ricercatori di lingua" e mondo accademico, in gran parte dovuto il ciclo complicato e difficile modifica-generare-compilazione-prova-debug inerente con soluzioni metaprogrammazione generative. Cercando di camminare attraverso computer -­codice generato — in particolare le finita-macchina-basate sullo stato versioni che molti generatori di parser sfornano — in un debugger è una sfida allo sviluppatore anche il più hard-morso. Per questo motivo, maggior parte degli sviluppatori non pensare a soluzioni lungo l'analisi righe quando presentato con un problema basati su testo. E, in verità, la maggior parte del tempo, una soluzione basata su generatore di parser sarebbe eccessivo drastica.

Combinatori parser serviscono come una bella soluzione intermedia: abbastanza flessibile e potente a sufficienza per gestire alcune analisi non banale, senza richiedere un Ph.d. in informatica per capire come usarli. Ancora più interessante, il concetto di calcolo combinatorio è un affascinante e porta ad altre idee interessanti, che alcune delle quali esploreremo più tardi.

Nello spirito in cui è nato in questa colonna, rendere sicuri di tenere "occhio" per il mio prossimo articolo (Siamo spiacenti, non poteva resistere), in cui potrai estendere Sprache basta un tocco, per ridurre la bruttezza del parser di tre e quattro cifre definito qui.

Codifica felice!

Ted Neward * è un consulente architettonico con Neudesic LLC. Ha scritto più di 100 articoli e autore o coautore di una dozzina di libri, tra cui "Professional F # 2.0" (Wrox, 2010). Egli è un MVP di c# e parla a conferenze in tutto il mondo. Egli consulta e mentors regolarmente — contattarlo al ted@tedneward.com o Ted.Neward@neudesic.com se siete interessati ad avere lui venire a lavorare con il vostro team, o leggere il suo blog a indirizzo blogs.tedneward.com.*

Grazie all'esperto tecnica seguente per la revisione di questo articolo: Luke Hoban