Hallo Habr! Ich präsentiere Ihnen die Übersetzung des Artikels "Learning Parser Combinators With Rust" .
Dieser Artikel vermittelt die Grundlagen kombinatorischer Parser für Personen, die bereits mit Rust vertraut sind. Es wird davon ausgegangen, dass keine weiteren Kenntnisse erforderlich sind und dass alles, was nicht direkt mit Rust zusammenhängt, sowie einige unerwartete Aspekte seiner Verwendung erläutert werden. Dieser Artikel hilft Ihnen nicht dabei, Rust zu lernen, wenn Sie ihn noch nicht kennen. In diesem Fall werden Sie kombinatorische Parser höchstwahrscheinlich nicht gut verstehen. Wenn Sie Rust lernen möchten, empfehle ich das Buch "Rust Programming Language" .
Aus der Sicht des Anfängers
Im Leben eines jeden Programmierers kommt eine Zeit, in der er einen Parser braucht.
Ein unerfahrener Programmierer wird fragen: "Was ist ein Parser?"
Der Programmierer der mittleren Ebene wird sagen: "Es ist einfach, ich werde einen regulären Ausdruck schreiben."
Der Master-Programmierer wird sagen: "Geh weg, ich kenne Lex und Yacc."
Ein Neuling denkt am besten.
Nicht dass reguläre Ausdrücke schlecht sind. (Aber bitte versuchen Sie nicht, einen komplexen Parser als regulären Ausdruck zu schreiben.) Nicht, dass es keine Freude macht, leistungsstarke Tools wie Parser- und Lexer-Generatoren zu verwenden, die seit Jahrtausenden perfekt verfeinert wurden. Das Erlernen der Grundlagen von Parsern ist jedoch ein Vergnügen . Dies ist auch das, was Sie vermissen werden, wenn Sie Panik haben, wenn Sie reguläre Ausdrücke oder Parser-Generatoren verwenden, die beide nur Abstraktionen über das eigentliche Problem sind. Im Kopf eines Anfängers gibt es, wie ein Mann sagte , viele Möglichkeiten. Nach Ansicht des Experten gibt es nur eine richtige Option.
In diesem Artikel erfahren Sie, wie Sie einen Parser von Grund auf neu erstellen
unter Verwendung einer Methode, die in funktionalen Programmiersprachen, die als kombinatorischer Parser bekannt sind, üblich ist . Sie haben den Vorteil, überraschend mächtig zu sein, sobald Sie ihre Grundidee verstanden haben, während sie dem Grundprinzip sehr nahe bleiben. Denn die einzigen Abstraktionen hier sind die, die Sie selbst erstellen. Die Hauptkombinatoren, die Sie hier verwenden, werden Sie selbst bauen.
Wie man mit diesem Artikel arbeitet
Es wird dringend empfohlen, mit einem neuen Rust-Projekt zu beginnen und beim Lesen Code-Schnipsel in src/lib.rs schreiben (Sie können es direkt von der Seite einfügen, aber besser eingeben, da dies automatisch garantiert, dass Sie es vollständig lesen). Alle Teile des Codes, die Sie benötigen, sind im Artikel in der richtigen Reihenfolge angeordnet. Beachten Sie, dass manchmal geänderte Versionen von Funktionen eingeführt werden, die Sie zuvor geschrieben haben. In diesen Fällen müssen Sie die alte Version durch die neue ersetzen.
Der Code wurde für rustc Version 1.34.0 mit der Sprachausgabe 2018 geschrieben. Sie können eine beliebige Version des Compilers verwenden. Cargo.toml Sie sicher, dass Sie eine Edition verwenden, die die Edition 2018 unterstützt (stellen Sie sicher, dass Ihre Cargo.toml edition = "2018" ). Dieses Projekt benötigt keine externen Abhängigkeiten.
Um die im Artikel vorgestellten Tests erwartungsgemäß cargo test , wird ein cargo test .
Xcruciating Markup Language
Wir werden einen Parser für eine vereinfachte Version von XML schreiben. Es sieht so aus:
<parent-element> <single-element attribute="value" /> </parent-element>
XML-Elemente werden mit dem Zeichen < und einem Bezeichner geöffnet, der aus einem Buchstaben gefolgt von einer beliebigen Anzahl von Buchstaben, Zahlen und - . Darauf folgen Leerzeichen und eine optionale Liste von Attributpaaren: ein weiterer Bezeichner wie zuvor definiert, gefolgt von = und einer Zeichenfolge in doppelten Anführungszeichen. Schließlich gibt es entweder ein schließendes /> Symbol, um ein Element ohne untergeordnete Elemente anzuzeigen, oder > , um die Existenz der nächsten Folge von untergeordneten Elementen anzuzeigen, und ein schließendes Tag, das mit </ beginnt, gefolgt von einer Kennung, die mit dem öffnenden Tag übereinstimmen muss, und einem schließenden Symbol > .
Das ist alles was wir unterstützen werden. Es wird keine Namespaces geben, keine Textknoten, und mit Sicherheit wird es keine Schemaüberprüfung geben. Wir müssen uns nicht einmal darum kümmern, Anführungszeichen für Zeichenfolgen zu vermeiden - sie beginnen mit dem ersten doppelten Anführungszeichen und enden mit dem nächsten, und das war's.
Wir werden diese Elemente in eine Struktur zerlegen, die so aussieht:
#[derive(Clone, Debug, PartialEq, Eq)] struct Element { name: String, attributes: Vec<(String, String)>, children: Vec<Element>, }
Es gibt keine ausgefallenen Typen, nur eine Zeichenfolge für den Namen (dies ist der Bezeichner am Anfang jedes Tags), Attribute in Form von Zeichenfolgenpaaren (Bezeichner und Wert) und eine Liste von untergeordneten Elementen, die genau wie das übergeordnete Element aussehen.
(Wenn Sie drucken, müssen Sie den derive einschließen. Sie werden ihn später benötigen.)
Parser-Definition
Dann ist es Zeit, einen Parser zu schreiben.
Beim Parsen werden strukturierte Daten aus einem Informationsstrom abgerufen. Ein Parser bringt diese Struktur hervor.
In der Disziplin, die wir untersuchen werden, ist der Parser in seiner einfachsten Form eine Funktion, die einige Eingaben entgegennimmt und entweder die analysierte Ausgabe zusammen mit dem Rest der Eingabe zurückgibt, oder einen Fehler mit der Aufschrift "Ich konnte dies nicht analysieren".
Der Parser sieht auch in seinen komplexeren Formen aus. Sie können die Bedeutung von Eingabe, Ausgabe und Fehler erschweren und wenn Sie gute Fehlermeldungen benötigen, die Sie benötigen, aber der Parser bleibt derselbe: etwas, das Eingaben verbraucht und zusammen mit was eine Art analysierte Ausgabe erzeugt von der Eingabe übrig geblieben oder lässt Sie wissen, dass die Eingabe nicht in die Ausgabe analysiert werden kann.
Schreiben wir es als eine Art Funktion.
Fn(Input) -> Result<(Input, Output), Error>
Genauer gesagt: In unserem Fall möchten wir die Typen ausfüllen und eine ähnliche Funktion erhalten. Alles, was wir tun werden, ist die Zeichenfolge in eine Element konvertieren. Im Moment möchten wir nicht auf die Details von Fehlermeldungen eingehen. Geben Sie einfach den Teil der Zeile zurück, den wir nicht analysieren konnten. Infolgedessen sieht unsere Funktion folgendermaßen aus:
Fn(&str) -> Result<(&str, Element), &str>
Wir verwenden ein String-Slice, da es ein effektiver Zeiger auf ein Fragment eines Strings ist, und können es dann nach Belieben trennen, indem wir die Eingabedaten „verbrauchen“, das analysierte Fragment ausschneiden und den Rest zusammen mit dem Ergebnis zurückgeben.
Es könnte sauberer sein, &[u8] (ein Teil der Bytes, die mit ASCII-Zeichen übereinstimmen) als Eingabetyp zu verwenden, insbesondere weil sich String-Slices etwas anders verhalten als die meisten Slices - insbesondere, weil Sie sie nicht mit einem indizieren können Zahlen input[0..1] input[0] , sollten Sie die Fragmenteingabe input[0..1] . Andererseits verfügen sie über viele Methoden, die zum Parsen von Zeichenfolgen ohne Byte-Slices nützlich sind.
In der Tat werden wir uns auf Methoden verlassen, nicht auf die Verwendung von Zeichenindizes, weil Unicode. In UTF-8 und alle Rust-Zeichenfolgen sind gültige UTF-8-Zeichenfolgen. Diese Indizes entsprechen nicht immer einzelnen Zeichen. Es ist für alle Interessenten besser, die Standardbibliothek zu bitten, nur für uns damit zu arbeiten.
Unser erster Parser
Versuchen wir, einen Parser zu schreiben, der nur das erste Zeichen in einer Zeichenfolge betrachtet
und entscheidet, ob es der Buchstabe a .
fn the_letter_a(input: &str) -> Result<(&str, ()), &str> { match input.chars().next() { Some('a') => Ok((&input['a'.len_utf8()..], ())), _ => Err(input), } }
Schauen wir uns zunächst die Arten der Eingabe und Ausgabe an: Wir nehmen ein String-Slice als Eingabe und geben das Result mit (&str, ()) oder einen Fehler mit &str . Das Paar (&str, ()) ist ein interessanter Punkt: Wie gesagt, wir sollten ein Tupel des folgenden Inhalts zurückgeben:
Analyseergebnis und der Rest der Eingabe. &str ist die nächste Eingabe und das Ergebnis ist nur ein Blocktyp () . Wenn dieser Parser erfolgreich funktioniert, kann er nur ein Ergebnis haben (wir haben den Buchstaben a ) und müssen nicht wirklich zurückkehren
In diesem Fall müssen wir nur angeben, dass wir es geschafft haben, ihn zu finden.
Schauen wir uns also den Code des Parsers an. Wir haben nicht gescherzt, dass wir mit der Standardbibliothek die Kopfschmerzen mit Unicode vermeiden können: Wir erhalten einen Iterator über die Zeichen der Zeichenfolge mit der chars() -Methode und nehmen das erste Zeichen daraus. Dies ist ein Element vom Typ char das in Option ist. Dabei bedeutet None , dass wir versucht haben, char aus einer leeren Zeichenfolge zu ziehen.
Um die Sache noch schlimmer zu machen, ist char nicht unbedingt das, was Sie als Unicode-Charakter betrachten. Dies ist wahrscheinlich das, was Unicode als "Graphemcluster" bezeichnet , das aus mehreren Zeichen bestehen kann, bei denen es sich tatsächlich um "Skalarwerte" handelt , die zwei Ebenen unter den Graphemclustern liegen. Dieser Weg führt jedoch zu Wahnsinn, und für unsere Zwecke ist es ehrlich gesagt unwahrscheinlich, dass wir chars außerhalb von ASCII sehen. Lassen Sie uns also hier aufhören.
Wir ordnen das Some('a') Muster Some('a') zu, das das spezifische Ergebnis ist, nach dem wir suchen, und wenn dies übereinstimmt, geben wir unseren Erfolgswert zurück:
Ok((&input['a'.len_utf8()..], ())) . Das heißt, wir entfernen den Teil, den wir gerade analysiert haben ( 'a' ), aus dem Zeilenabschnitt und geben den Rest zusammen mit unserem analysierten Wert zurück, der gerade leer ist
() . Wenn wir uns immer an das Unicode-Monster erinnern, finden wir vor dem Schneiden in UTF-8 die Länge des Zeichens 'a' in der Standardbibliothek heraus - es ist 1 (aber vergessen Sie niemals das Unicode-Monster).
Wenn wir ein anderes Some(char) oder wenn wir None , geben wir einen Fehler zurück. Wie Sie sich erinnern, ist unser Fehlertyp einfach ein String-Slice, das wir als input und das nicht analysiert werden konnte. Es hat nicht mit a , also ist dies unser Fehler. Dies ist kein großer Fehler, aber zumindest ein bisschen besser als nur "irgendwo stimmt etwas nicht".
Wir brauchen diesen Parser nicht wirklich, um das XML zu analysieren, aber das erste, was wir tun müssen, ist, das Eröffnungszeichen < , also brauchen wir etwas sehr Ähnliches. Wir müssen auch > , / und = speziell analysieren, damit wir vielleicht eine Funktion erstellen können, die den Parser für das gewünschte Zeichen erstellt.
Parser erstellen
Lassen Sie uns sogar darüber nachdenken: Wir werden eine Funktion schreiben, die einen Parser für eine statische Zeichenfolge beliebiger Länge und nicht nur für ein Zeichen erstellt. Dies ist noch einfacher, da das Zeilenfragment bereits ein gültiger UTF-8-Zeilenabschnitt ist und wir nicht an das Unicode-Monster denken müssen.
fn match_literal(expected: &'static str) -> impl Fn(&str) -> Result<(&str, ()), &str> { move |input| match input.get(0..expected.len()) { Some(next) if next == expected => { Ok((&input[expected.len()..], ())) } _ => Err(input), } }
Jetzt sieht es etwas anders aus.
Schauen wir uns zunächst die Typen an. Jetzt nimmt unsere Funktion die expected Zeichenfolge als Argument und gibt etwas zurück, das einem Parser ähnelt, anstatt selbst ein Parser zu sein. Dies ist eine Funktion, die eine Funktion höherer Ordnung zurückgibt. Im Wesentlichen schreiben wir eine Funktion, die eine Funktion ähnlich unserer Funktion the_letter_a früher macht.
Anstatt also Arbeiten im Hauptteil der Funktion auszuführen, geben wir einen Abschluss zurück, der diese Arbeiten ausführt und der Signatur unseres Typs für den Analysator aus dem vorherigen entspricht.
Der Mustervergleich sieht gleich aus, außer dass wir unser Zeichenfolgenliteral nicht direkt abgleichen können, da wir nicht genau wissen, was. Daher verwenden wir die Übereinstimmungsbedingung, if next == expected . Ansonsten ist es genau das gleiche wie zuvor, nur innerhalb des Schaltkreises.
Testen Sie unseren Parser
Schreiben wir einen Test dafür, um sicherzustellen, dass wir es richtig machen.
#[test] fn literal_parser() { let parse_joe = match_literal("Hello Joe!"); assert_eq!( Ok(("", ())), parse_joe("Hello Joe!") ); assert_eq!( Ok((" Hello Robert!", ())), parse_joe("Hello Joe! Hello Robert!") ); assert_eq!( Err("Hello Mike!"), parse_joe("Hello Mike!") ); }
Zuerst erstellen wir einen Parser: match_literal("Hello Joe!") . Es sollte die Zeichenfolge "Hello Joe!" und geben Sie den Rest der Zeichenfolge zurück oder schlagen Sie fehl und geben Sie die gesamte Zeichenfolge zurück.
Im ersten Fall übergeben wir nur die genaue Zeile, die wir erwarten, und stellen fest, dass eine leere Zeichenfolge und der Wert () werden. Dies bedeutet, dass "wir die erwartete Zeichenfolge analysiert haben und sie nicht zurückgegeben werden müssen".
Im zweiten füttern wir den String "Hello Joe! Hello Robert!" und wir sehen, dass er wirklich die Zeichenfolge "Hello Joe!" und gibt den Rest der Eingabe zurück: " Hello Robert!" (führender Raum und alles andere).
Im dritten geben wir die falsche Eingabe ein: "Hello Mike!" und beachten Sie, dass Eingaben mit einem Fehler wirklich abgelehnt werden. Nicht, dass Mike falsch liegt, normalerweise einfach nicht das, wonach der Parser gesucht hat.
Parser für etwas weniger Spezifisches
Auf diese Weise können wir < , > , = und sogar </ und /> analysieren. Wir sind fast fertig!
Das nächste nach dem öffnenden Zeichen < ist der Name des Elements. Wir können dies nicht mit einem einfachen Zeichenfolgenvergleich tun. Aber wir könnten es mit Regex machen ...
... aber lass uns zurückhalten. Dies ist ein regulärer Ausdruck, der sehr einfach in einfachem Code zu replizieren ist. Dafür müssen wir das regex Paket nicht verwenden. Mal sehen, ob wir dafür unseren eigenen Parser schreiben können, indem wir nur die Standard-Rust-Bibliothek verwenden.
Erinnern Sie sich an die Regel für die Kennung des Namens des Elements. Sie sieht folgendermaßen aus: ein alphabetisches Zeichen, gefolgt von null oder mehr eines alphabetischen Symbols,
Zeichen, Zahl oder Bindestrich.
fn identifier(input: &str) -> Result<(&str, String), &str> { let mut matched = String::new(); let mut chars = input.chars(); match chars.next() { Some(next) if next.is_alphabetic() => matched.push(next), _ => return Err(input), } while let Some(next) = chars.next() { if next.is_alphanumeric() || next == '-' { matched.push(next); } else { break; } } let next_index = matched.len(); Ok((&input[next_index..], matched)) }
Wie immer schauen wir uns zuerst den Typ an. Dieses Mal schreiben wir keine Funktion zum Erstellen eines Parsers, sondern schreiben nur den Parser selbst, wie zum ersten Mal. Der bemerkenswerte Unterschied besteht darin, dass anstelle des Ergebnistyps () ein String im Tupel zusammen mit der verbleibenden Eingabe zurückgegeben wird. Dieser String enthält den Bezeichner, den wir gerade analysiert haben.
In diesem Sinne erstellen wir zuerst einen leeren String und nennen ihn matched . Dies wird unser Ergebnis sein. Wir erhalten auch einen Iterator für die input Zeichen, den wir aufteilen werden.
Der erste Schritt besteht darin, zu sehen, ob am Anfang ein Symbol steht. Wir ziehen das erste Zeichen aus dem Iterator und prüfen, ob es sich um einen Buchstaben handelt: next.is_alphabetic() . Die Standard-Rust-Bibliothek hilft uns natürlich bei Unicode - sie entspricht Buchstaben in jedem Alphabet und nicht nur in ASCII. Wenn es sich um einen Buchstaben handelt, fügen wir ihn in unsere Zeichenfolge in der matched Variablen ein. Wenn nicht, sehen wir uns den Bezeichner des Elements nicht an und kehren sofort mit einem Fehler zurück.
Im zweiten Schritt ziehen wir die Zeichen weiter aus dem Iterator und senden sie an die von uns erstellte Zeile, bis wir is_alphanumeric() Zeichen finden, das die Funktion is_alphanumeric() erfüllt (es ähnelt is_alphabetic() , enthält jedoch auch Zahlen in einem beliebigen Alphabet). oder Bindestrich '-' .
Wenn wir zum ersten Mal etwas sehen, das diese Kriterien nicht erfüllt, beenden wir die Analyse, unterbrechen die Schleife und geben einen String , wobei wir daran denken, das von uns verwendete Fragment aus der input . Wenn Zeichen in einem Iterator enden, bedeutet dies ebenfalls, dass wir das Ende der Eingabe erreicht haben.
Es ist erwähnenswert, dass wir nicht mit einem Fehler zurückkehren, wenn wir etwas sehen, das nicht alphanumerisch oder mit Bindestrichen versehen ist. Wir haben bereits genug, um einen gültigen Bezeichner zu erstellen, nachdem wir diesen ersten Buchstaben gefunden haben, und es ist ganz normal, dass nach dem Parsen unseres Bezeichners mehr Elemente in der Eingabezeile für die Analyse vorhanden sind. Wir beenden also einfach das Parsen und geben unser Ergebnis zurück. Nur wenn wir nicht einmal diesen ersten Buchstaben finden können, geben wir tatsächlich einen Fehler zurück, da in diesem Fall definitiv keine Kennung vorhanden war.
Denken Sie daran, dass die Element ist, in das wir unser XML-Dokument analysieren werden.
struct Element { name: String, attributes: Vec<(String, String)>, children: Vec<Element>, }
Tatsächlich haben wir gerade den Analysator für den ersten Teil, das Namensfeld, fertiggestellt. String , den unser Parser zurückgibt, geht direkt dorthin. Es ist auch der richtige Parser für den ersten Teil jedes attribute .
Lass es uns überprüfen.
#[test] fn identifier_parser() { assert_eq!( Ok(("", "i-am-an-identifier".to_string())), identifier("i-am-an-identifier") ); assert_eq!( Ok((" entirely an identifier", "not".to_string())), identifier("not entirely an identifier") ); assert_eq!( Err("!not at all an identifier"), identifier("!not at all an identifier") ); }
Wir sehen, dass im ersten Fall die Zeichenfolge "i-am-an-identifier" vollständig analysiert wird und nur eine leere Zeichenfolge übrig "i-am-an-identifier" . Im zweiten Fall gibt der Parser "not" als Bezeichner zurück, und der Rest der Zeichenfolge wird als verbleibende Eingabe zurückgegeben. Im dritten Fall schlägt der Parser sofort fehl, da das erste gefundene Zeichen kein Buchstabe ist.
Kombinatoren
Jetzt können wir das Eröffnungszeichen < und den nächsten Bezeichner analysieren, aber wir müssen beide analysieren. Daher besteht der nächste Schritt darin, eine weitere kombinatorische Parserfunktion zu schreiben, die jedoch zwei Parser als Eingabe verwendet und einen neuen Parser zurückgibt, der beide nacheinander analysiert. Mit anderen Worten, ein Parser- Kombinator, weil er die beiden Parser zu einem neuen kombiniert. Mal sehen, ob wir das schaffen.
fn pair<P1, P2, R1, R2>(parser1: P1, parser2: P2) -> impl Fn(&str) -> Result<(&str, (R1, R2)), &str> where P1: Fn(&str) -> Result<(&str, R1), &str>, P2: Fn(&str) -> Result<(&str, R2), &str>, { move |input| match parser1(input) { Ok((next_input, result1)) => match parser2(next_input) { Ok((final_input, result2)) => Ok((final_input, (result1, result2))), Err(err) => Err(err), }, Err(err) => Err(err), } }
Hier wird es etwas kniffliger, aber Sie wissen, was zu tun ist: Schauen Sie sich zunächst die Typen an.
Zunächst haben wir vier Arten von Variablen: P1 , P2 , R1 und R2 . Dies sind Parser 1 , Parser 2 , Result 1 und Result 2 . P1 und P2 sind Funktionen, und Sie werden feststellen, dass sie einem gut etablierten Muster von Parserfunktionen folgen: Genau wie der Rückgabewert nehmen sie &str als Eingabe und Rückgabe. Result Paar aus verbleibender Eingabe und Ergebnis oder ein Fehler.
Schauen Sie sich jedoch die Ergebnistypen jeder Funktion an: P1 ist der Parser, der bei Erfolg R1 und P2 auch R2 . Und das Ergebnis des letzten Parsers, der von unserer Funktion zurückgegeben wurde, ist (R1, R2) . Daher besteht die Aufgabe dieses Parsers darin, zuerst den Analysator P1 am Eingang zu starten, sein Ergebnis zu speichern und dann P2 am Eingang zu starten, der P1 hat. Wenn beide funktionieren, kombinieren wir die beiden Ergebnisse zu einem Tupel (R1, R2)
Der Code zeigt, dass er genau das tut. Wir beginnen mit dem Starten des ersten Analysators am Eingang, dann des zweiten Analysators, kombinieren dann die beiden Ergebnisse zu einem Tupel und geben es zurück. Wenn einer dieser Parser fehlschlägt, werden wir sofort mit dem von ihm ausgegebenen Fehler zurückkehren.
Daher müssen wir in der Lage sein, unsere beiden Parser match_literal und identifier zu kombinieren, um match_literal erste Fragment unseres ersten XML-Tags tatsächlich zu match_literal . Schreiben wir einen Test, um zu sehen, ob er funktioniert.
#[test] fn pair_combinator() { let tag_opener = pair(match_literal("<"), identifier); assert_eq!( Ok(("/>", ((), "my-first-element".to_string()))), tag_opener("<my-first-element/>") ); assert_eq!(Err("oops"), tag_opener("oops")); assert_eq!(Err("!oops"), tag_opener("<!oops")); }
Scheint zu funktionieren! Aber schauen Sie sich diese Art von Ergebnis an: ((), String) . Offensichtlich interessiert uns nur der richtige Wert, String . Dies wird ziemlich oft vorkommen - einige unserer Parser stimmen nur mit Mustern in der Eingabe überein, ohne Werte zu erzeugen, und daher kann ihre Ausgabe sicher ignoriert werden. Um uns an dieses Muster anzupassen, werden wir unseren pair , um zwei weitere Kombinatoren zu schreiben: left , der das Ergebnis des ersten Parsers verwirft und nur den zweiten zurückgibt, und das Gegenteil ist right . In unserem obigen Test haben wir einen Parser verwendet, der den linken Teil verwirft und nur unseren String anstelle des pair speichert.
Funktor Einführung
Aber bevor wir so weit gehen, wollen wir einen weiteren Kombinator vorstellen, der das Schreiben dieser beiden map erheblich vereinfacht: map .
Dieser Kombinator hat eine Aufgabe: die Art des Ergebnisses zu ändern. , , , ((), String) , String .
, , . : |(_left, right)| right . , Fn(A) -> B A — , B — .
fn map<P, F, A, B>(parser: P, map_fn: F) -> impl Fn(&str) -> Result<(&str, B), &str> where P: Fn(&str) -> Result<(&str, A), &str>, F: Fn(A) -> B, { move |input| match parser(input) { Ok((next_input, result)) => Ok((next_input, map_fn(result))), Err(err) => Err(err), } }
? P — . A . F — , P , , P , — B A
parser(input) , , result map_fn(result) , A B , .
, , map , Result :
fn map<P, F, A, B>(parser: P, map_fn: F) -> impl Fn(&str) -> Result<(&str, B), &str> where P: Fn(&str) -> Result<(&str, A), &str>, F: Fn(A) -> B, { move |input| parser(input) .map(|(next_input, result)| (next_input, map_fn(result))) }
— , «» Haskell , . A , map , A B , B , . Rust, Option , Result , Iterator Future , . : - Rust, , , , , map .
, , : Fn(&str) -> Result<(&str, Output), &str> . , , , , , , , .
, :
type ParseResult<'a, Output> = Result<(&'a str, Output), &'a str>;
, , , ParseResult<String> . , , Rust . , rustc , , .
'a , , .
. , , . , .
trait Parser<'a, Output> { fn parse(&self, input: &'a str) -> ParseResult<'a, Output>; }
: parse() , : , , .
, , :
impl<'a, F, Output> Parser<'a, Output> for F where F: Fn(&'a str) -> ParseResult<Output>, { fn parse(&self, input: &'a str) -> ParseResult<'a, Output> { self(input) } }
, , , Parser , .
, , . map , .
fn map<'a, P, F, A, B>(parser: P, map_fn: F) -> impl Parser<'a, B> where P: Parser<'a, A>, F: Fn(A) -> B, { move |input| parser.parse(input) .map(|(next_input, result)| (next_input, map_fn(result))) }
: , parser.parse(input) , , P , , Parser , , Parser . , . 'a' , , .
pair , :
fn pair<'a, P1, P2, R1, R2>(parser1: P1, parser2: P2) -> impl Parser<'a, (R1, R2)> where P1: Parser<'a, R1>, P2: Parser<'a, R2>, { move |input| match parser1.parse(input) { Ok((next_input, result1)) => match parser2.parse(next_input) { Ok((final_input, result2)) => Ok((final_input, (result1, result2))), Err(err) => Err(err), }, Err(err) => Err(err), } }
: parser.parse(input) parser(input) .
, pair , map .
fn pair<'a, P1, P2, R1, R2>(parser1: P1, parser2: P2) -> impl Parser<'a, (R1, R2)> where P1: Parser<'a, R1>, P2: Parser<'a, R2>, { move |input| { parser1.parse(input).and_then(|(next_input, result1)| { parser2.parse(next_input) .map(|(last_input, result2)| (last_input, (result1, result2))) }) } }
and_then Result map , , Result , Result . match . and_then , , map , left right .
Left Right
pair map , left right :
fn left<'a, P1, P2, R1, R2>(parser1: P1, parser2: P2) -> impl Parser<'a, R1> where P1: Parser<'a, R1>, P2: Parser<'a, R2>, { map(pair(parser1, parser2), |(left, _right)| left) } fn right<'a, P1, P2, R1, R2>(parser1: P1, parser2: P2) -> impl Parser<'a, R2> where P1: Parser<'a, R1>, P2: Parser<'a, R2>, { map(pair(parser1, parser2), |(_left, right)| right) }
pair , , map , .
, , .
, Parser ParseResult . match_literal :
fn match_literal<'a>(expected: &'static str) -> impl Parser<'a, ()> { move |input: &'a str| match input.get(0..expected.len()) { Some(next) if next == expected => Ok((&input[expected.len()..], ())), _ => Err(input), } }
, , — &'a str , rustc .
identifier , , , :
fn identifier(input: &str) -> ParseResult<String> {
. () . .
#[test] fn right_combinator() { let tag_opener = right(match_literal("<"), identifier); assert_eq!( Ok(("/>", "my-first-element".to_string())), tag_opener.parse("<my-first-element/>") ); assert_eq!(Err("oops"), tag_opener.parse("oops")); assert_eq!(Err("!oops"), tag_opener.parse("<!oops")); }
. < . Was weiter? .
, , . , .
, , - , : .
( ) . .
— , <element attribute="value"/> , . , , .
identifier , . , .
fn one_or_more<'a, P, A>(parser: P) -> impl Parser<'a, Vec<A>> where P: Parser<'a, A>, { move |mut input| { let mut result = Vec::new(); if let Ok((next_input, first_item)) = parser.parse(input) { input = next_input; result.push(first_item); } else { return Err(input); } while let Ok((next_input, next_item)) = parser.parse(input) { input = next_input; result.push(next_item); } Ok((input, result)) } }
, , , A , Vec<A> — A .
identifier . , , . , , .
, : ? :
fn zero_or_more<'a, P, A>(parser: P) -> impl Parser<'a, Vec<A>> where P: Parser<'a, A>, { move |mut input| { let mut result = Vec::new(); while let Ok((next_input, next_item)) = parser.parse(input) { input = next_input; result.push(next_item); } Ok((input, result)) } }
, , .
#[test] fn one_or_more_combinator() { let parser = one_or_more(match_literal("ha")); assert_eq!(Ok(("", vec![(), (), ()])), parser.parse("hahaha")); assert_eq!(Err("ahah"), parser.parse("ahah")); assert_eq!(Err(""), parser.parse("")); } #[test] fn zero_or_more_combinator() { let parser = zero_or_more(match_literal("ha")); assert_eq!(Ok(("", vec![(), (), ()])), parser.parse("hahaha")); assert_eq!(Ok(("ahah", vec![])), parser.parse("ahah")); assert_eq!(Ok(("", vec![])), parser.parse("")); }
: one_or_more , , zero_or_more , .
, , . one_or_more zero_or_more , - :
fn one_or_more<'a, P, A>(parser: P) -> impl Parser<'a, Vec<A>> where P: Parser<'a, A>, { map(pair(parser, zero_or_more(parser)), |(head, mut tail)| { tail.insert(0, head); tail }) }
Rust, cons Vec , , Lisp, , . , : .
, : , . : ( ). , , Clone , , , .
. , one_or_more , , , , , - , , RangeBound : range(0..) zero_or_more , range(1..) one_or_more , range(5..=6) , .
. zero_or_more one_or_more .
, — , Rc ?
, one_or_more zero_or_more .
, . , . , , , > /> . , . , , , , .
. .
Erstens. match_literal , . ? - , Unicode, . Rust, , char is_whitespace , is_alphabetic is_alphanumeric .
-. , , is_whitespace , identifier .
-. , . any_char , char , , pred , , : pred(any_char, |c| c.is_whitespace()) . , , : .
any_char , , UTF-8.
fn any_char(input: &str) -> ParseResult<char> { match input.chars().next() { Some(next) => Ok((&input[next.len_utf8()..], next)), _ => Err(input), } }
pred , , . , . , true , . , .
fn pred<'a, P, A, F>(parser: P, predicate: F) -> impl Parser<'a, A> where P: Parser<'a, A>, F: Fn(&A) -> bool, { move |input| { if let Ok((next_input, value)) = parser.parse(input) { if predicate(&value) { return Ok((next_input, value)); } } Err(input) } }
, , :
#[test] fn predicate_combinator() { let parser = pred(any_char, |c| *c == 'o'); assert_eq!(Ok(("mg", 'o')), parser.parse("omg")); assert_eq!(Err("lol"), parser.parse("lol")); }
, whitespace_char :
fn whitespace_char<'a>() -> impl Parser<'a, char> { pred(any_char, |c| c.is_whitespace()) }
, whitespace_char , , , , , . space1 space0 .
fn space1<'a>() -> impl Parser<'a, Vec<char>> { one_or_more(whitespace_char()) } fn space0<'a>() -> impl Parser<'a, Vec<char>> { zero_or_more(whitespace_char()) }
? , , . identifier ( , any_char pred *_or_more ). match_literal("=") = . , . , , .
fn quoted_string<'a>() -> impl Parser<'a, String> { map( right( match_literal("\""), left( zero_or_more(pred(any_char, |c| *c != '"')), match_literal("\""), ), ), |chars| chars.into_iter().collect(), ) }
, , , , .
map - , , , , , : . map right , right — , : match_literal("\"") . .
right — . left , , left , , , match_literal("\"") — . , — .
pred any_char , , , zero_or_more , :
right left .
, . , zero_or_more ? Vec<A> A . any_char char . , , Vec<char> . map : , Vec<char> String , , String Iterator<Item = char> , vec_of_chars.into_iter().collect() , String .
, , , , , , , , .
#[test] fn quoted_string_parser() { assert_eq!( Ok(("", "Hello Joe!".to_string())), quoted_string().parse("\"Hello Joe!\"") ); }
, , , , .
,
, , = . , .
. , Vec<(String, String)> , (String, String) , zero_or_more . , .
fn attribute_pair<'a>() -> impl Parser<'a, (String, String)> { pair(identifier, right(match_literal("="), quoted_string())) }
! : pair , identifier , String , right = , , quoted_string , String .
zero_or_more , , .
fn attributes<'a>() -> impl Parser<'a, Vec<(String, String)>> { zero_or_more(right(space1(), attribute_pair())) }
: ,
. right .
.
#[test] fn attribute_parser() { assert_eq!( Ok(( "", vec![ ("one".to_string(), "1".to_string()), ("two".to_string(), "2".to_string()) ] )), attributes().parse(" one=\"1\" two=\"2\"") ); }
! !
, , rustc , , . , . , rustc, , , #![type_length_limit = "…some big number…"] , . , #![type_length_limit = "16777216"] , . , !
, , , , NP-. element: , , , zero_or_more , ?
, , . , , , : < , . , (String, Vec<(String, String)>) .
fn element_start<'a>() -> impl Parser<'a, (String, Vec<(String, String)>)> { right(match_literal("<"), pair(identifier, attributes())) }
, , .
fn single_element<'a>() -> impl Parser<'a, Element> { map( left(element_start(), match_literal("/>")), |(name, attributes)| Element { name, attributes, children: vec![], }, ) }
, , — Element !
.
#[test] fn single_element_parser() { assert_eq!( Ok(( "", Element { name: "div".to_string(), attributes: vec![("class".to_string(), "float".to_string())], children: vec![] } )), single_element().parse("<div class=\"float\"/>") ); }
… , .
single_element , , , . , , , — , — .
, , ...
- Rust, , , .
. , :
enum List<A> { Cons(A, List<A>), Nil, }
rustc , List<A> , List::<A>::Cons List<A> , . rustc, , , .
, Rust. , Rust, , , , . , .
, . , List::Cons A A , A A . , , , , List::Cons , . , Rust — Box .
enum List<A> { Cons(A, Box<List<A>>), Nil, }
Box , . , , Box<dyn Parser<'a, A>> .
. ? , - , , . : . . , , SIMD ( ).
, Parser Box , .
struct BoxedParser<'a, Output> { parser: Box<dyn Parser<'a, Output> + 'a>, } impl<'a, Output> BoxedParser<'a, Output> { fn new<P>(parser: P) -> Self where P: Parser<'a, Output> + 'a, { BoxedParser { parser: Box::new(parser), } } } impl<'a, Output> Parser<'a, Output> for BoxedParser<'a, Output> { fn parse(&self, input: &'a str) -> ParseResult<'a, Output> { self.parser.parse(input) } }
, , BoxedParser box . BoxedParser ( BoxedParser , ), BoxedParser::new(parser) , , Box . , Parser , .
Box , BoxedParser Parser , . , , , , , , , , . .
, , , .
, ? , , . quoted_string :
fn quoted_string<'a>() -> impl Parser<'a, String> { map( right( match_literal("\""), left( zero_or_more(pred(any_char, |c| *c != '"')), match_literal("\""), ), ), |chars| chars.into_iter().collect(), ) }
, . Parser ?
, , impl Trait , impl Trait .
… BoxedParser . , impl Parser<'a, A> , , BoxedParser<'a, A> .
, , , Parser .
map , Parser :
trait Parser<'a, Output> { fn parse(&self, input: &'a str) -> ParseResult<'a, Output>; fn map<F, NewOutput>(self, map_fn: F) -> BoxedParser<'a, NewOutput> where Self: Sized + 'a, Output: 'a, NewOutput: 'a, F: Fn(Output) -> NewOutput + 'a, { BoxedParser::new(map(self, map_fn)) } }
'a , , . , — , , impl Trait .
quoted_string :
fn quoted_string<'a>() -> impl Parser<'a, String> { right( match_literal("\""), left( zero_or_more(pred(any_char, |c| *c != '"')), match_literal("\""), ), ) .map(|chars| chars.into_iter().collect()) }
, , .map() right() .
pair , left right , , , , pair . , , map , .
— pred . Parser :
fn pred<F>(self, pred_fn: F) -> BoxedParser<'a, Output> where Self: Sized + 'a, Output: 'a, F: Fn(&Output) -> bool + 'a, { BoxedParser::new(pred(self, pred_fn)) }
quoted_string pred , :
zero_or_more(any_char.pred(|c| *c != '"')),
, , , zero_or_more — « any_char », . , zero_or_more one_or_more .
quoted_string , map single_element :
fn single_element<'a>() -> impl Parser<'a, Element> { left(element_start(), match_literal("/>")).map(|(name, attributes)| Element { name, attributes, children: vec![], }) }
element_start , , , . ...
… , . , .
map pred Box — !
. single_element , , > , /> . , , .
fn open_element<'a>() -> impl Parser<'a, Element> { left(element_start(), match_literal(">")).map(|(name, attributes)| Element { name, attributes, children: vec![], }) }
, ? , , , zero_or_more , ? , , — : , , .
, , : , , . , , , . , , , , , , .
fn either<'a, P1, P2, A>(parser1: P1, parser2: P2) -> impl Parser<'a, A> where P1: Parser<'a, A>, P2: Parser<'a, A>, { move |input| match parser1.parse(input) { ok @ Ok(_) => ok, Err(_) => parser2.parse(input), } }
element , , ( open_element , element ).
fn element<'a>() -> impl Parser<'a, Element> { either(single_element(), open_element()) }
. , , , . , ?
fn close_element<'a>(expected_name: String) -> impl Parser<'a, String> { right(match_literal("</"), left(identifier, match_literal(">"))) .pred(move |name| name == &expected_name) }
pred , ?
, :
fn parent_element<'a>() -> impl Parser<'a, Element> { pair( open_element(), left(zero_or_more(element()), close_element(…oops)), ) }
close_element ? , .
. , parent_element , open_element element parent_element , , XML.
, , and_then ? , . and_then : -, , , , . pair , , , , . , and_then Result Option , , , Result Option , , ( , )).
, .
fn and_then<'a, P, F, A, B, NextP>(parser: P, f: F) -> impl Parser<'a, B> where P: Parser<'a, A>, NextP: Parser<'a, B>, F: Fn(A) -> NextP, { move |input| match parser.parse(input) { Ok((next_input, result)) => f(result).parse(next_input), Err(err) => Err(err), } }
, , P , , A . F , map A B , , and_then A NextP , B . — B , , , NextP .
: , , , , f ( A ), , f(result) , B . . , , , B
: P , , f P , NextP , , .
Parser , map , .
fn and_then<F, NextParser, NewOutput>(self, f: F) -> BoxedParser<'a, NewOutput> where Self: Sized + 'a, Output: 'a, NewOutput: 'a, NextParser: Parser<'a, NewOutput> + 'a, F: Fn(Output) -> NextParser + 'a, { BoxedParser::new(and_then(self, f)) }
, , ?
, pair :
fn pair<'a, P1, P2, R1, R2>(parser1: P1, parser2: P2) -> impl Parser<'a, (R1, R2)> where P1: Parser<'a, R1> + 'a, P2: Parser<'a, R2> + 'a, R1: 'a + Clone, R2: 'a, { parser1.and_then(move |result1| parser2.map(move |result2| (result1.clone(), result2))) }
, : parser2.map() parser2 , Fn , FnOnce , parser2 , . , Rust. , , pair .
, Rust, close_element , , .
:
fn parent_element<'a>() -> impl Parser<'a, Element> { pair( open_element(), left(zero_or_more(element()), close_element(…oops)), ) }
, and_then , close_element .
fn parent_element<'a>() -> impl Parser<'a, Element> { open_element().and_then(|el| { left(zero_or_more(element()), close_element(el.name.clone())).map(move |children| { let mut el = el.clone(); el.children = children; el }) }) }
, and_then open_element() , , close_element . , open_element and_then . , Element open_element , , , .
, map , Element ( el ) . clone() , Fn . ( Vec<Element> ) Element , .
, , element , open_element parent_element , , , , !
"" ?
, , map «» Haskell?
and_then — , Rust, , map . flat_map Iterator , , .
— "". Thing<A> , and_then , A Thing<B> , Thing<B> — .
, , Option<A> , , Some(A) None , , Some(A) , Some(B)
. , Future<A> , and_then Future<B> , Future<B> Future<A> , Future<A> . Future<A> , — 1 , Future<B> . , Future , and_then , Future , . , Future , .
, Rust , , , , , , , . .
, Redux
.
, XML, . , ( , , < div / > , ).
.
fn whitespace_wrap<'a, P, A>(parser: P) -> impl Parser<'a, A> where P: Parser<'a, A>, { right(space0(), left(parser, space0())) }
element , element , , , .
fn element<'a>() -> impl Parser<'a, Element> { whitespace_wrap(either(single_element(), parent_element())) }
!
, ! , .
#[test] fn xml_parser() { let doc = r#" <top label="Top"> <semi-bottom label="Bottom"/> <middle> <bottom label="Another bottom"/> </middle> </top>"#; let parsed_doc = Element { name: "top".to_string(), attributes: vec![("label".to_string(), "Top".to_string())], children: vec![ Element { name: "semi-bottom".to_string(), attributes: vec![("label".to_string(), "Bottom".to_string())], children: vec![], }, Element { name: "middle".to_string(), attributes: vec![], children: vec![Element { name: "bottom".to_string(), attributes: vec![("label".to_string(), "Another bottom".to_string())], children: vec![], }], }, ], }; assert_eq!(Ok(("", parsed_doc)), element().parse(doc)); }
, - , , :
#[test] fn mismatched_closing_tag() { let doc = r#" <top> <bottom/> </middle>"#; assert_eq!(Err("</middle>"), element().parse(doc)); }
, . , , , , . , , , , . , , , , , .
: , ! , , , 2 .
, , . !
, , Rust , , - , , , .
, pom , , .
Rust nom , pom ( , ), , .
Rust combine , .
Haskell Parsec .
, « Haskell» , , Haskell.
Bodil Stokke Creative Commons Attribution-NonCommercial-ShareAlike 4.0. , http://creativecommons.org/licenses/by-nc-sa/4.0/ .
1: .
2: , .
andreevlex funkill