Dieser Artikel wurde maschinell übersetzt.
Die Working Programmer
Erstellen von Kombinatoren
.jpg "Ted Neward")
In meinem Artikel vom Dezember (msdn.microsoft.com/magazine/hh580742), ich schaute auf Parser Kombinatoren, Text-Parser, die erstellt werden, durch die Kombination von kleinen, atomare Analyse-Funktionen in größere Funktionen, und diese wiederum in noch größere Funktionen, geeignet für die Analyse nicht trivialen Text-Dateien und Streams. Dies ist eine interessante Technik, eine, die auf einige grundlegende funktionelle Konzepte, aufbaut und es verdient tiefere Exploration.
Leser der früheren Spalte werden sich daran erinnern, dass der Parser wir konstruierten U.S.-Stil Adressen gearbeitet zu behandeln, aber die Implementierung ein bisschen war... sagen wir... schrulligen an Orten. Vor allem die Syntax zum Analysieren von drei und vier Ziffern Kombinationen — nun, um ehrlich zu sein, es clunked. Es funktionierte, aber es war kaum ziemlich, elegant oder in irgendeiner Weise skalierbare.
Als eine Auffrischungskursen ist hier der Telefonnummer Parsercode:
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 });
Der Typ PhoneNumber ist ziemlich erkennbar. Abbildung 1 zeigt die ThreeNumberParser und FourNumberParser, die, insbesondere was "clunk" mit der Gnade von einem defensiven pro Fußball Linienrichter versucht Ballett zum ersten Mal auf einer Bühne mit Entenfett geschmiert.
Abbildung 1 klobig 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())))));
Dies ist kaum die Art von inspirierende Codierung Praxis, die ich hoffe, dass auf diesen Seiten zu vermitteln. Es ist ein eleganter Weg um dies zu konstruieren, aber um es zu beschreiben, müssen wir ein bisschen tiefer eintauchen in Parser Kombinatoren Funktionsweise. Und das ist das Thema dieses Monats. Nicht nur, weil wir eine elegantere Möglichkeit, Parser, wohlgemerkt erstellen müssen, sondern weil die allgemeine Vorgehensweise hilft beschreiben, wie sie arbeiten, und noch wichtiger, wie könnten Sie so etwas wie dies in der Zukunft erstellen.
Von Funktionen auf Funktionen
Der wichtige Punkt zu über Parser Kombinatoren zu erkennen ist, dass ein Parser wirklich "nur" eine Funktion ist: Die Funktion analysiert den Text und dann die Zeichen in etwas anderes verwandeln kann. Was etwas anderes entpuppt sich als ist, natürlich, bis zur Person den Parser implementieren. Könnte es einen abstrakten Syntaxbaum (AST) für die Validierung und Überprüfung des Textes übergeben (und spätere Umwandlung in ausführbaren Code oder vielleicht direkt in einigen Sprachen interpretiert), oder es könnte sein, ein einfaches Domain-Objekt, oder auch nur Werte in einer vorhandenen Klasse, wie ein Wörterbuch mit Name-Wert-Paare angeschlossen.
In Code zu sprechen, dann sieht ein Parser wie folgt:
T Parse<T>(string input);
Mit anderen Worten, ist ein Parser eine generische Funktion, Zeichenfolgen und das Zurückgeben einer Instanz von etwas.
So einfach wie das heißt, obwohl es nicht ganz korrekt ist. Waren, dass die Summe der Geschichte, wir wären zurück zu schreiben, einen vollständigen Parser pro-Funktion, die wirklich für einen Großteil der Wiederverwendung zulässt. Aber wenn wir analysieren als eine Reihe von Funktionen betrachten – mit anderen Worten, ein Parser besteht aus einer Reihe von kleinen Parser, von denen jeder weiß, wie man analysiert nur ein Stück der Eingabe und gibt nur ein Stück des resultierenden Objekts zurück — es ist klar, wir müssen nicht nur das resultierende Objekt, sondern auch den verbleibenden Text, die Analyse erfordert. Und, dass bedeutet, dass das "T" von der vorherigen Deklaration muss erfolgen etwas komplizierter durch Wrappen es in einen "Parser" Ergebnistyp, der "T" und eine Zeichenfolge mit dem verbleibenden enthält Text, analysieren, etwa so:
public class ParseResult<T>
{
public readonly T Result;
public readonly string Rest;
public ParseResult(T r, string i) { this.Result = r; this.Rest = i; }
}
Und da c# natürlich Funktionen wie Typen und Instanzen delegieren verwaltet, deklarieren einen Parser jetzt eine Delegatdeklaration wird:
public delegate ParseResult<T> ParseFn<T>(string input);
Jetzt können wir uns vorstellen, schreiben eine Reihe von kleinen Parser, die wissen, wie man Text in einigen analysieren hilfreich anderen Typs, z. B. eine ParseFn <int> akzeptiert eine Zeichenfolge und einen Int zurückgibt (siehe Abbildung 2), oder eine ParseFn <string> die analysiert bis zum ersten Leerzeichen und So weiter.
Abbildung 2 Analysieren einer Zeichenfolge und einen Int zurückgeben
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);
Beachten Sie, dass die Parser Umsetzung hier eigentlich eine ziemlich wiederholbare ist: um einen Parser schreiben, der Text bis zu ein Whitespace-Zeichen analysiert, alles, was Sie tun müssen ist das IsDigit ihn in ein Anruf IsLetter ändern. Das schreit für eine Umgestaltung mit dem Prädikat <T> Geben Sie einen sogar noch grundlegenderen Parser erstellen, aber das ist eine Optimierung, die wir hier versuchen wird nicht.
Diese Implementierung ist ideal für kleine Dinge wie z. B. ganze Zahlen und einzelne Wörter Parsen, aber bisher scheint es nicht wie zu viel von einer Verbesserung gegenüber der früheren Version. Dies ist jedoch, leistungsfähigeren, weil Sie Funktionen kombinieren können, indem Erstellen von Funktionen, die Funktionen und Funktionen zurück. Dies nennt man Funktionen höherer Ordnung; während die Theorie würde den Rahmen dieses Artikels sprengen, ist nicht zeigen, wie sie in diesem Fall gelten. Der Ausgangspunkt ist, wenn Sie Funktionen, die wissen erstellen, wie zwei Parser-Funktionen und kombinieren in einem booleschen "AND" und "OR" Mode:
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);
}
}
Beide werden als Erweiterungsmethoden für die ParseFn ermöglicht eine "Infix" oder "fluent Interface" Stil der Kodierung Delegattyp, es zu lesbarer am Ende auf der Theorie, dass "parserA.OR(parserB) liest" besser als "OR(parserA, parserB)."
Von Funktionen in LINQ
Bevor wir diesen Satz von kleinen Beispielen verlassen, lassen Sie uns nehmen einen weiteren Schritt und Erstellen von drei Methoden, wie in gezeigt Abbildung 3, dass im Wesentlichen geben wird dem Parser die Fähigkeit, Haken in LINQ, um eine einzigartige Erfahrung beim Schreiben von Code (Dies ist eine Sprache der Funktionen sowie). Die LINQ-Bibliotheken und Syntax sind in enger Sync mit einem anderen, in die der LINQ-Syntax ("von Foo in bar Wählen Sie Quux Q …") ist eng an die Erwartung, dass mehrere Methodensignaturen für Gebrauch vorhanden und verfügbar sind. Insbesondere, wenn eine Klasse auswählen, SelectMany bietet und wo Methoden und LINQ-Syntax mit ihnen verwendet werden kann.
Abbildung 3 Where, Select und SelectMany-Methoden
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);
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);
};
}
}
Dies gibt LINQ die erforderlichen Methoden zum Analysieren von LINQ Ausdrücke, wie z. B. was Sie im vorherigen Artikel gesehen haben.
Ich möchte nicht die Ausübung der (Re-) Design eine Parser Combinator Library hier durchlaufen; Luke Hoban und Brian McNamara haben ausgezeichnete Blogbeiträge zu diesem Thema (bit.ly/ctWfU0 und bit.ly/f2geNy, bzw.), das, ich muss darauf hinweisen, dienen als der Standard gegen die in dieser Spalte geschrieben wird. Ich möchte nur zeigen den Mechanismus, mit dem diese Art der Parser in einer Parser Combinator Library wie Sprache, erstellt werden, weil den Kern der Lösung für die früheren Problem der drei und vier Ziffern Parser im Telefon Nummer Parser enthält. Kurz, brauchen wir einen Parser Kombinator, die genau drei Ziffern liest, und andere, die genau vier Ziffern liest.
Specifice
Angesichts der Tatsache, dass das Problem ist, genau drei Ziffern und genau vier Ziffern zu lesen, liegt es nahe, dass wir eine Funktion, die genau diese Anzahl von Zeichen aus dem Eingabestream gelesen werden soll. Die Sprache-Bibliothek nicht geben uns diese Art von Kombinator — gibt ein Kombinator, die eine sich wiederholende Bildsequenz ein, was auch immer Art von Zeichen gelesen werden, bis es von, dass-Art-von-Charakter läuft, aber das ist eine "Null-zu-n" (daher seinen Namen viele) Produktionsregel, keine bestimmte Anzahl von Zeichen Regel, und so wenig hilfreich. Betrachten seiner Definition kann sein interessant und aufschlussreich, jedoch als Abbildung 4 zeigt.
Abbildung 4 Definition der vielen Kombinator
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);
};
}
Für die meisten Entwickler, der schwierigste Teil dieser Methode (und in der Tat, die gesamte Sprache-Bibliothek) ist, dass der Rückgabewert dieser Funktion eine Funktion — insbesondere eine Lambda-Methode < (immer ein Parser > Denken Sie daran, in irgendeiner Form), nimmt die Zeichenfolge und gibt ein IEnumerable <T> in der Ergebnisstruktur; das Fleisch von der tatsächlichen Parser ist in begraben, die Funktion zurückgegeben wird, bedeutet, dass es jetzt nicht später ausgeführt wird. Dies ist ein langer Weg von nur wieder eine T!
Sobald die Kuriosität behandelt wird, ist der Rest der Funktion ziemlich klar: Imperativ, wir Schritt für Schritt durch, und rufen Sie den übergebenen Parser <T> auszuwerten, was jeder "immer"; und so lange, wie der Parser erfolgreich zurückgegeben wird hält, halten wir Schleifen und Hinzufügen der analysierten Ergebnisse zu einer Liste <T> Ruft zurückgegeben, wenn alles abgeschlossen ist. Dies dient als Vorlage für eine my-Erweiterung in die Bibliothek, das ich zweimal für jetzt, im wesentlichen nenne ausführen einen bestimmten Parser <T> zweimal (und Gewinnung einen Fehler, wenn entweder fehlschlägt verarbeiten), siehe Abbildung 5.
Abbildung 5 die doppelte Funktion
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);
};
}
In der Tat, während es ein bisschen leichter hätte zu schreiben dieser Code durch die Schleife der beiden in nur zwei Sätze von imperative Anweisungen ausrollen, denken Sie daran, nicht zweimal speziell was wir suchen. Wir brauchen Thrice und Quadrice, und das sind nur spezielle Fall Versionen von zweimal, mit "3" und "4" anstelle von "2" im Code, die klingt, als ob wir sie in eine einzelne Methode, die die Anzahl von Zeiten extrahieren können zu analysieren. Ich wähle zum Aufrufen dieser Methode "Specifice," weil wir eine bestimmte Anzahl von Wiederholungen Analyse sind (siehe Abbildung 6).
Abbildung 6 die Specifice-Methode
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);
};
}
So haben wir jetzt erweitert Sprache genau "ct" Anzahl der analysiert (Zeichen, Ziffern, gleich welcher Art des Parsers <T> auszuwerten Wir übergeben), die Sprache für den Einsatz in fester Länge Analyse Szenarien, z. B. die allgegenwärtigen fester Länge Rekord Textdatei, aka der flachen Datei eröffnet.
Einen funktionellen Ansatz
Sprache ist ein Parser-Bibliothek für mittelständische analysieren Projekte, für die reguläre Ausdrücke zu komplex sind und ein ausgewachsenen Parser-Generator (z. B. ANTLR oder Yacc/Lex) ist übertrieben. Es ist nicht perfekt, in diesem Parser Fehler Fehlermeldungen, die schwer generieren zu verstehen sind kann, sobald Sie durch die anfängliche Komplexität bekommen, Sprache jedoch ein nützliches Werkzeug in der Developer-Toolbox.
Mehr noch, aber Sprache veranschaulicht einige der die Kraft und die Fähigkeit bietet einen anderen Ansatz zur Programmierung als was wir gewohnt sind – in diesem Fall aus der funktionalen Welt. Also das nächste Mal jemand fragt, "was gut stammt aus anderen Sprachen lernen, wenn Sie nicht gehen, um ihnen bei der Arbeit verwenden?" gibt es eine einfache Antwort: "Auch wenn Sie eine Sprache direkt verwenden, kann es dir beibringen Techniken und Ideen, die Sie verwenden können."
Aber das ist alles für jetzt. Im nächsten Monat nehmen wir einen Stich auf etwas ganz anderes. Denn es gibt nur so viel Konzept und Theorie, die eine Sprache Kolumnist Publikum auf einmal ausführen kann.
Glücklich Kodierung!
Ted Neward ist ein architektonischer Berater mit Neudesic LLC. Er hat mehr als 100 Artikel geschrieben, ist ein C#-MVP und INETA-Sprecher und hat verfasst und Mitautor von einem Dutzend Bücher, einschließlich der kürzlich veröffentlichten "professionelle F#-2.0" (Wrox). Er berät und Mentoren regelmäßig. Sie erreichen ihn in ted@tedneward.com Wenn Sie interessiert ihn zusammen mit Ihrem Team, oder lesen Sie seinen Blog unter blogs.tedneward.com.
Dank der folgenden technischen Experten für die Überprüfung dieses Artikels: Nicholas Blumhardt