Il presente articolo è stato tradotto automaticamente.
Il lavoro programmatore
Sviluppo di combinatori
.jpg "Ted Neward")
Nel mio articolo di dicembre (msdn.microsoft.com/magazine/hh580742), ho guardato combinatori parser, parser di testo che vengono creati combinando piccolo, atomico, l'analisi di funzioni in più funzioni e quelli a sua volta in funzioni ancora più grande, adatte per l'analisi di file di testo non banale e flussi. Questa è una tecnica interessante, uno che si basa su alcuni concetti fondamentali funzionale, e che merita più profonda esplorazione.
I lettori della colonna precedente ricorderanno che il parser che abbiamo costruito per gestire i numeri di telefono di stile U.S. ha lavorati, ma l'implementazione è stato un po' … diciamo … eccentrico in luoghi. In particolare, la sintassi per l'analisi di combinazioni di tre e quattro cifre — bene, per essere onesti, clunked. Ha funzionato, ma era quasi bello, elegante o in qualsiasi modo scalabile.
Come rinfresco, ecco il codice del parser di numero di telefono:
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 });
Il tipo di numero di telefono è abbastanza da indovinare. Figura 1 mostra threeNumberParser e fourNumberParser, che, in particolare, sono ciò che "clack" con tutta la grazia di un calcio pro difensiva lineman tentativo balletto per la prima volta su un palco unta di grasso d'anatra.
Figura 1 goffo parser
public static Parser<string> threeNumParser =
Parse.Numeric.Then(first =>
Parse.Numeric.Then(second =>
Parse.Numeric.Then(third =>
Parse.Return("" + first.ToString() +
second.ToString() + third.ToString()))));
public static Parser<string> fourNumParser =
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())))));
Questo è difficilmente il tipo di inspirational pratica codifica che spero di trasmettere all'interno di queste pagine. C'è un modo più elegante per costruire queste, ma per descriverlo, abbiamo bisogno di tuffarsi un po ' più profondo come lavoro combinatori parser. E che è oggetto di mese questo. Non solo perché abbiamo bisogno di un modo più elegante per costruire il parser, intendiamoci, ma perché la tecnica generale aiuta a descrivere come funzionano e più importante, come si potrebbe costruire qualcosa di simile in futuro.
Dalle funzioni alle funzioni
Il punto importante da realizzare su combinatori parser è che un parser è davvero "solo" una funzione: La funzione analizza il testo e poi può trasformare i caratteri in qualcos'altro. Che cosa che qualcos'altro scopre di essere è, naturalmente, fino alla persona attuando il parser. Potrebbe essere un albero di sintassi astratta (AST) per la validazione e verifica del testo passato (e la successiva conversione in codice eseguibile o forse interpretata direttamente, come in alcune lingue), o potrebbe essere un oggetto semplice dominio, o anche soli valori collegati a una classe esistente, come un dizionario delle coppie nome / valore.
Parlando nel codice, quindi, un parser è simile al seguente:
T Parse<T>(string input);
In altre parole, un parser è una funzione generica, prendendo stringhe e restituendo un'istanza di qualcosa.
Semplice come che è, però, non è tutto esatto. Erano che la somma totale della storia, saremmo torna a scrivere un parser completo per funzione, che davvero non consente per molto in termini di riutilizzo. Ma se guardiamo l'analisi di una serie di funzioni — in altre parole, un parser è costituito da un mazzo di little parser, ognuno dei quali conosce come analizzare solo un pezzo di input e restituire solo un pezzo di oggetto risultante — è chiaro che dobbiamo restituire non solo l'oggetto risultante, ma anche il testo rimanente che richiede l'analisi. E che significa "T" dalla precedente dichiarazione deve essere resa leggermente più complicata da avvolgendolo in un tipo di "Parser risultato" che contiene sia "T" e una stringa con il restante analizza il testo, in questo modo:
public class ParseResult<T>
{
public readonly T Result;
public readonly string Rest;
public ParseResult(T r, string i) {
this.Result = r; this.Rest = i;
}
}
E dato che c# naturalmente gestisce le funzioni come delegato tipi e istanze, che dichiara un parser ora diventa una dichiarazione di delegato:
public delegate ParseResult<T> ParseFn<T>(string input);
Ora, possiamo immaginare scrivendo una serie di piccoli parser che sanno come analizzare il testo in alcuni utili altro tipo, come ad esempio un ParseFn <int> che accetta una stringa e restituisce un int (vedere Figura 2), o un ParseFn <string> che analizza fino al primo carattere whitespace e così via.
Figura 2 analisi di una stringa e tornando Int
ParseFn<int> parseInt = delegate(string str)
{
// Peel off just numbers
int numCount = 0;
foreach (char ch in str)
{
if (Char.IsDigit(ch))
numCount++;
else
break;
}
// If the string contains no numbers, bail
if (numCount == 0)
return null;
else
{
string toBeParsed = str.Substring(0, numCount);
return new ParseResult<int>(
Int32.Parse(toBeParsed), str.Substring(numCount));
}
};
Assert.AreEqual(12, parseInt("12").Result);
Si noti che l'implementazione di parser qui è in realtà uno che è abbastanza ripetibili: per scrivere un parser che analizza il testo fino a un carattere whitespace, tutto quello che si avrebbe bisogno di fare è cambiare la chiamata IsDigit a una chiamata IsLetter. Questo urla per un refactoring per utilizzare il predicato <T> digitare per creare un parser ancor più fondamentale, ma che è un'ottimizzazione che non tentiamo qui.
Questa implementazione è grande per l'analisi di piccole cose come valori integer e singole parole, ma finora non sembra come troppo di un miglioramento rispetto alla versione precedente. Questo è più potente, tuttavia, perché è possibile combinare le funzioni mediante la creazione di funzioni che funzioni e nella restituiscono di funzioni. Questi sono chiamati funzioni di ordine superiore; mentre la teoria esula dallo scopo di questo articolo, mostrando come si applicano in questo caso specifico non è. Il punto di partenza è quando è creare funzioni che sanno prendere due funzioni relative al parser e combinarli in un booleano "AND" e moda "O":
public static class ParseFnExtensions
{
public static ParseFn<T> OR<T>(this ParseFn<T> parser1,
ParseFn<T> parser2)
{
return input => parser1(input) ?? parser2(input);
}
public static ParseFn<T2> AND<T1, T2>(this ParseFn<T1> p1,
ParseFn<T2> p2)
{
return input => p2(p1(input).Rest);
}
}
Entrambi questi sono forniti come metodi di estensione sul ParseFn delegano tipo per consentire un "infisso" o di "interfaccia" stile di codifica, per renderlo più leggibile alla fine, sulla teoria che "parserA.OR(parserB)" legge meglio di "OR(parserA, parserB)."
Dalle funzioni a LINQ
Prima che lasceremo questo insieme di piccoli esempi, prendiamo un altro passo e creare tre metodi, come illustrato nel Figura 3, essenzialmente che darà il parser la capacità di gancio in LINQ, per fornire un'esperienza unica, quando si scrive codice (questo è una delle caratteristiche di Sprache pure). Le librerie LINQ e sintassi sono nella sincronizzazione stretta con uno a altro, in quanto la sintassi LINQ ("da foo nella barra selezionare quux q …") è strettamente legata all'attesa che le firme del metodo diversi siano presenti e disponibili per l'uso. In particolare, se una classe fornisce Select, SelectMany e dove metodi, quindi la sintassi LINQ può essere utilizzato con loro.
Figura 3 dove, Select e SelectMany metodi
public static class ParseFnExtensions {
public static ParseFn<T> Where<T>(
this ParseFn<T> parser,
Func<T, bool> pred)
{
return input => {
var res = parser(input);
if (res == null || !pred(res.Result)) return null;
return res;
};
}
public static ParseFn<T2> Select<T, T2>(
this ParseFn<T> parser,
Func<T, T2> selector)
{
return input => {
var res = parser(input);
if (res == null) return null;
return new ParseResult<T2>(selector(
res.Result),res.Rest);
};
}
public static ParseFn<T2> SelectMany<T, TIntermediate, T2>(
this ParseFn<T> parser,
Func<T, ParseFn<TIntermediate>> selector,
Func<T, TIntermediate, T2> projector)
{
return input => {
var res = parser(input);
if (res == null) return null;
var val = res.Result;
var res2 = selector(val)(res.Rest);
if (res2 == null) return null;
return new ParseResult<T2>(projector(
val, res2.Result),res2.Rest);
};
}
}
Questo dà LINQ i metodi necessari per analizzare le espressioni LINQ, come ad esempio quello che avete visto nel precedente articolo.
Non voglio passare attraverso l'esercizio di (ri) progettazione di una libreria di combinator parser qui; Luke Hoban sia Brian McNamara hanno eccellente blog post sull'argomento (bit.ly/ctWfU0 e bit.ly/f2geNy, rispettivamente), che, devo sottolineare, servono come lo standard contro il quale è scritto in questa colonna. Voglio solo dimostrare il meccanismo mediante il quale questi tipi di parser sono costruiti in una libreria di combinator parser come Sprache, perché che fornisce il nucleo della soluzione per il problema prima dei parser a tre e a quattro cifre nel parser di numero di telefono. In breve, abbiamo bisogno di combinator di un parser che legge esattamente tre cifre e un altro che legge esattamente quattro cifre.
Specifico
Dato che il problema è quello di leggere precisamente tre cifre e precisamente di quattro cifre, com'è ovvio che noi vogliamo una funzione che legge esattamente che il numero di caratteri dal flusso di input. La libreria Sprache non darci quel tipo di combinator — c'è un combinatore che leggerà una sequenza ripetuta di qualunque cosa tipo-del personaggio fino a quando non si esaurisce che tipo-del personaggio, ma che è un "zero-a-molti" (da qui il suo nome, molti) regola di produzione, non una regola specifico numero di personaggi e quindi inutile. Guardando la sua definizione può essere interessante e penetranti, tuttavia, come Figura 4 mostra.
Figura 4 definizione di Combinator molti
public static Parser<IEnumerable<T>> Many<T>(
this Parser<T> parser)
{
if (parser == null)
throw new ArgumentNullException("parser");
return i =>
{
var remainder = i;
var result = new List<T>();
var r = parser(i);
while (r is ISuccess<T>)
{
var s = r as ISuccess<T>;
if (remainder == s.Remainder)
break;
result.Add(s.Result);
remainder = s.Remainder;
r = parser(remainder);
}
return new Success<IEnumerable<T>>(result, remainder);
};
}
Per la maggior parte degli sviluppatori, la parte più difficile di questo metodo (e, in effetti, l'intera libreria di Sprache) è che il valore restituito da questa funzione è una funzione — in particolare, un metodo lambda < (sempre un Parser > di una qualche forma, ricordo) che accetta la stringa e restituisce un oggetto IEnumerable <T> nella sua struttura risultato; la carne del parser effettivo è sepolto all'interno che ha restituito la funzione, il che significa che verrà eseguito successivamente, non ora. Questa è una lunga strada da semplicemente restituendo una T!
Una volta che stranezza viene affrontato, il resto della funzione è abbastanza chiaro: in modo imperativo, ci passo attraverso e chiamare il Parser passati nella <T> per analizzare ogni "qualunque cosa"; e fino a quando il parser mantiene tornando con successo, noi continuiamo loop e aggiungendo i risultati analizzati a una lista di <T> che viene restituito quando tutto viene completata. Questo serve come modello per la mia estensione alla biblioteca, che chiamerò Twice per ora, essenzialmente l'esecuzione di un Parser dato <T> due volte (e producendo un errore se sia analizzare fallisce), come illustrato nella Figura 5.
Figura 5 la funzione due volte
public static Parser<IEnumerable<T>> Twice<T>(
this Parser<T> parser)
{
if (parser == null)
throw new ArgumentNullException("parser");
return i =>
{
var remainder = i;
var result = new List<T>();
var r = parser(i);
var c = 0;
while (c < 2 && r is ISuccess<T>)
{
var s = r as ISuccess<T>;
if (remainder == s.Remainder)
break;
result.Add(s.Result);
remainder = s.Remainder;
r = parser(remainder);
c++;
}
return new Success<IEnumerable<T>>(result, remainder);
};
}
Infatti, mentre sarebbe stato un po' più facile da scrivere questo codice da srotolava il ciclo di due in due insiemi di istruzioni imperative, ricordo, non due volte è specificamente ciò che stiamo cercando. Abbiamo bisogno di Thrice e Quadrice, e quelli sono solo in casi particolari versioni di due volte, con "3" e "4" invece di "2" nel codice, che suona come se noi li possiamo estrarre in un solo metodo che accetta il numero di volte per analizzare. Ho scelto di chiamare questo metodo "Specifico", perché noi stiamo l'analisi di un determinato numero di volte (vedere Figura 6).
Figura 6 il metodo specifico
public static Parser<IEnumerable<T>> Twice<T>(
this Parser<T> parser) {
return Specifice(parser, 2); }
public static Parser<IEnumerable<T>> Thrice<T>(
this Parser<T> parser) {
return Specifice(parser, 3); }
public static Parser<IEnumerable<T>> Quadrice<T>(
this Parser<T> parser) {
return Specifice(parser, 4);
}
public static Parser<IEnumerable<T>> Quince<T>(
this Parser<T> parser) {
return Specifice(parser, 5);
}
public static Parser<IEnumerable<T>> Specifice<T>(
this Parser<T> parser, int ct)
{
if (parser == null)
throw new ArgumentNullException("parser");
return i =>
{
var remainder = i;
var result = new List<T>();
var r = parser(i);
var c = 0;
while (c < ct && r is ISuccess<T>)
{
var s = r as ISuccess<T>;
if (remainder == s.Remainder)
break;
result.Add(s.Result);
remainder = s.Remainder;
r = parser(remainder);
c++;
}
return new Success<IEnumerable<T>>(result, remainder);
};
}
Così, ora abbiamo esteso Sprache analizzare esattamente "ct" numero di analizza (caratteri, cifre, qualunque tipo di Parser <T> Passiamo), che si apre di Sprache per l'utilizzo in scenari di analisi a lunghezza fissa, ad esempio il file onnipresente testo record a lunghezza fissa, aka file flat.
Un approccio funzionale
Sprache è una libreria di parser per medie, l'analisi di progetti, per i quali le espressioni regolari sono troppo complesse e un generatore di parser conclamata (ad esempio ANTLR o lex/yacc) è eccessivo. È non perfetto, in quanto gli errori del parser generano messaggi di errore che possono essere difficili da capire, ma una volta che hai ottenuto attraverso la complessità iniziale, Sprache può essere uno strumento utile nella vostra cassetta degli attrezzi dello sviluppatore.
Più, però, Sprache vengono illustrati alcuni della potenza e le funzionalità offerte da un diverso approccio alla programmazione rispetto a cui siamo abituati — in questo caso, dal mondo funzionale. Così la prossima volta che qualcuno ti chiede, "cosa buona deriva dal conoscere altre lingue se non si sta per utilizzarli sul posto di lavoro?" c'è una risposta facile: "Anche se non si utilizza direttamente una lingua, può insegnare tecniche e idee, che è possibile utilizzare."
Ma questo è tutto per ora. Il mese prossimo, ci prenderemo una pugnalata a qualcosa di completamente diverso. Perché c'è così tanto concetto e teoria pubblico di un editorialista lingua può prendere in una sola volta.
Codifica felice!
Ted Neward è un consulente architettonico con Neudesic LLC. Ha scritto più di 100 articoli, è un oratore c# MVP e INETA e ha l'autore e coautore di una dozzina di libri, tra cui il recentemente rilasciato "Professional F # 2.0" (Wrox). Egli consulta e mentors regolarmente. Contattarlo al ted@tedneward.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: Nicholas Blumhardt