Explorer les analyseurs combinatoires avec Rust

Bonjour, Habr! Je vous présente la traduction de l'article "Apprendre les combinateurs analyseurs avec la rouille" .

Cet article enseigne les bases des analyseurs combinatoires pour les personnes qui connaissent déjà Rust. On suppose qu'aucune autre connaissance n'est requise, et tout ce qui n'est pas directement lié à la rouille, ainsi que certains aspects inattendus de son utilisation, seront expliqués. Cet article ne vous aidera pas à apprendre Rust si vous ne le connaissez pas déjà, et dans ce cas, vous ne comprendrez probablement pas bien les analyseurs combinatoires. Si vous voulez apprendre Rust, je vous recommande le livre "Rust Programming Language" .

Du point de vue du débutant

Dans la vie de chaque programmeur, il arrive un moment où il a besoin d'un analyseur.

Un programmeur débutant demandera: "Qu'est-ce qu'un analyseur?"

Le programmeur de niveau intermédiaire dira: "C'est simple, je vais écrire une expression régulière."

Le maître programmeur dira: "Sortez, je connais lex et yacc."

Un novice pense le mieux.

Non pas que les expressions régulières soient mauvaises. (Mais s'il vous plaît, n'essayez pas d'écrire un analyseur complexe comme une expression régulière.) Non pas qu'il n'y ait aucune joie à utiliser des outils puissants tels que des générateurs d'analyseur et de lexer qui ont été perfectionnés à la perfection depuis des millénaires. Mais apprendre les bases des analyseurs est un plaisir . C'est aussi ce qui vous manquera si vous paniquez lorsque vous utilisez des expressions régulières ou des générateurs d'analyseurs, qui ne sont que des abstractions sur le vrai problème. Dans l'esprit d'un débutant, comme un homme l'a dit , il existe de nombreuses possibilités. Selon l'expert, il n'y a qu'une seule option correcte.

Dans cet article, nous allons apprendre à créer un analyseur à partir de zéro avec
en utilisant une méthode courante dans les langages de programmation fonctionnelle connue sous le nom d' analyseur combinatoire . Ils ont l'avantage d'être étonnamment puissants dès que vous saisissez leur idée de base, tout en restant très proches du principe de base. Parce que les seules abstractions ici seront celles que vous créez vous-même. Les principaux combinateurs que vous utiliserez ici, vous les construirez vous-même.

Comment travailler avec cet article

Il est fortement recommandé de commencer avec un nouveau projet Rust et d'écrire des extraits de code dans src/lib.rs au src/lib.rs que vous le lisez (vous pouvez le coller directement à partir de la page, mais entrez-le mieux, car cela garantit automatiquement que vous le lirez complètement). Toutes les parties du code dont vous avez besoin sont organisées dans l'ordre dans l'article. Gardez à l'esprit que des versions parfois modifiées des fonctions que vous avez écrites précédemment sont introduites, et dans ces cas, vous devez remplacer l'ancienne version par la nouvelle.

Le code a été écrit pour la version 1.34.0 de rustc utilisant l'édition linguistique 2018 . Vous pouvez utiliser n'importe quelle version du compilateur, assurez-vous que vous utilisez une édition qui prend en charge l'édition 2018 (assurez-vous que votre Cargo.toml contient edition = "2018" ). Ce projet n'a pas besoin de dépendances externes.

Pour effectuer les tests présentés dans l'article, comme prévu, cargo test .

Langage de balisage Xcruciator

Nous allons écrire un analyseur pour une version simplifiée de XML. Cela ressemble à ceci:

 <parent-element> <single-element attribute="value" /> </parent-element> 

Les éléments XML sont ouverts avec le caractère < et un identifiant composé d'une lettre suivie d'un nombre quelconque de lettres, de chiffres et de - . Il est suivi d'espaces et d'une liste facultative de paires d'attributs: un autre identifiant tel que défini précédemment, suivi de = et d'une chaîne entre guillemets. Enfin, il y a soit un caractère de fermeture /> pour indiquer un élément sans enfants, soit > pour indiquer l'existence de la prochaine séquence d'éléments enfants, et une balise de fermeture commençant par </ , suivie d'un identifiant qui doit correspondre à la balise d'ouverture et d'un caractère de fermeture > .

C'est tout ce que nous soutiendrons. Il n'y aura pas d'espaces de noms, pas de nœuds de texte et il n'y aura certainement pas de vérification de schéma. Nous n'avons même pas à nous soucier d'échapper aux guillemets pour les chaînes - ils commencent par le premier guillemet double, et ils se terminent par le suivant, et c'est tout.

Nous allons analyser ces éléments dans une structure qui ressemble à ceci:

 #[derive(Clone, Debug, PartialEq, Eq)] struct Element { name: String, attributes: Vec<(String, String)>, children: Vec<Element>, } 

Il n'y a pas de types fantaisistes, juste une chaîne pour le nom (c'est l'identifiant au début de chaque balise), des attributs sous forme de paires de chaînes (identifiant et valeur) et une liste d'enfants qui ressemblent exactement au parent.

(Si vous imprimez, assurez-vous d'inclure la section derive . Vous en aurez besoin plus tard.)

Définition de l'analyseur

Eh bien, il est temps d'écrire un analyseur.

L'analyse est le processus d'obtention de données structurées à partir d'un flux d'informations. Un analyseur est ce qui fait ressortir cette structure.

Dans la discipline que nous allons explorer, l'analyseur, dans sa forme la plus simple, est une fonction qui prend une entrée et retourne soit la sortie analysée avec le reste de l'entrée, soit une erreur disant «Je ne pouvais pas analyser cela».

L'analyseur analyse également ses formes les plus complexes. Vous pouvez compliquer ce que signifient entrée, sortie et erreur, et si vous avez besoin de bons messages d'erreur dont vous avez besoin, mais l'analyseur reste le même: quelque chose qui consomme des entrées et produit une sorte de sortie analysée avec ce que laissé de l'entrée ou vous fait savoir qu'il ne peut pas analyser l'entrée à la sortie.

Écrivons-le comme un type de fonction.

 Fn(Input) -> Result<(Input, Output), Error> 

Plus précisément: dans notre cas, nous voulons remplir les types et obtenir une fonction similaire à celle-ci. Tout ce que nous allons faire, c'est convertir la chaîne en une structure Element . Pour le moment, nous ne voulons pas entrer dans les détails des messages d'erreur, alors renvoyez simplement la partie de la ligne que nous n'avons pas pu analyser. En conséquence, notre fonction ressemblera à ceci:

 Fn(&str) -> Result<(&str, Element), &str> 

Nous utilisons une tranche de chaîne parce qu'elle est un pointeur efficace vers un fragment d'une chaîne, puis nous pouvons la séparer comme nous le souhaitons en «consommant» les données d'entrée, en coupant le fragment analysé et en renvoyant le reste avec le résultat.

Il peut être plus propre d'utiliser &[u8] (une tranche d'octets correspondant aux caractères ASCII) comme type d'entrée, en particulier parce que les tranches de chaîne se comportent un peu différemment de la plupart des tranches - d'autant plus que vous ne pouvez pas les indexer avec une seule input[0] nombres input[0] , vous devez utiliser l' input[0..1] fragment input[0..1] . D'un autre côté, ils ont de nombreuses méthodes utiles pour analyser les chaînes qui n'ont pas de tranches d'octets.

En fait, nous nous appuierons sur des méthodes, pas sur l'utilisation d'index de caractères, car Unicode. En UTF-8, et toutes les chaînes Rust sont des chaînes UTF-8 valides, ces indices ne correspondent pas toujours à des caractères individuels, et il est préférable pour toutes les parties intéressées de demander à la bibliothèque standard de simplement travailler avec elle pour nous.

Notre premier analyseur

Essayons d'écrire un analyseur qui ne regarde que le premier caractère d'une chaîne
et décide s'il s'agit de la lettre a .

 fn the_letter_a(input: &str) -> Result<(&str, ()), &str> { match input.chars().next() { Some('a') => Ok((&input['a'.len_utf8()..], ())), _ => Err(input), } } 

Tout d'abord, regardons les types d'entrée et de sortie: nous prenons une tranche de chaîne en entrée et nous retournons Result avec (&str, ()) , ou une erreur avec &str . La paire (&str, ()) est un point intéressant: comme nous l'avons dit, nous devons retourner un tuple du contenu suivant,
résultat d'analyse et le reste de l'entrée. &str est la prochaine entrée, et le résultat est juste un type de bloc () , car si cet analyseur fonctionne correctement, il ne peut avoir qu'un seul résultat (nous avons trouvé la lettre a ), et nous n'avons pas vraiment besoin de retourner
la lettre a dans ce cas, nous devons simplement indiquer que nous avons réussi à le trouver.

Examinons donc le code de l'analyseur lui-même. Nous n'avons pas plaisanté en nous basant sur la bibliothèque standard pour éviter le mal de tête avec Unicode: nous obtenons un itérateur sur les caractères de la chaîne en utilisant la méthode chars() et prenons le premier caractère. Ce sera un élément de type char encapsulé dans Option , dans lequel None signifiera que nous essayons d'extraire char d'une chaîne vide.

Pour aggraver les choses, le caractère char pas nécessairement ce que vous en pensez en tant que personnage Unicode. C'est probablement ce que Unicode appelle un «cluster de graphèmes» , qui peut être composé de plusieurs caractères, qui sont en fait des «valeurs scalaires» , qui sont deux niveaux en dessous des grappes de graphèmes. Cependant, ce chemin mène à la folie, et pour nos besoins, il est peu probable que nous voyions des chars dehors de ASCII, alors arrêtons-nous là.

Nous mappons sur le modèle Some('a') , qui est le résultat spécifique que nous recherchons, et si cela correspond, nous retournons notre valeur de succès:
Ok((&input['a'.len_utf8()..], ())) . Autrement dit, nous supprimons la partie que nous venons d'analyser ( 'a' ) de la tranche de ligne et renvoyons le reste avec notre valeur analysée, qui est juste vide
() . En se souvenant toujours du monstre Unicode, avant de couper, nous trouvons la longueur en UTF-8 du caractère 'a' dans la bibliothèque standard - c'est 1 (mais n'oubliez jamais le monstre Unicode).

Si nous obtenons un autre Some(char) , ou si nous obtenons None , nous renvoyons une erreur. Comme vous vous en souvenez, notre type d'erreur est simplement une tranche de chaîne, que nous avons passée en input et qui n'a pas pu être analysée. Cela n'a pas commencé par a , c'est donc notre erreur. Ce n'est pas une grosse erreur, mais au moins c'est un peu mieux que juste "quelque chose ne va pas quelque part".

Nous n'avons pas vraiment besoin de cet analyseur pour analyser le XML, mais la première chose que nous aurons à faire est de trouver le caractère d'ouverture < , nous avons donc besoin de quelque chose de très similaire. Nous aurons également besoin d'analyser > , / et = spécifiquement, alors peut-être pouvons-nous créer une fonction qui construit l'analyseur pour le caractère que nous voulons?

Création d'un analyseur

Pensons même à cela: nous allons écrire une fonction qui crée un analyseur pour une chaîne statique de n'importe quelle longueur , et pas seulement un caractère. C'est encore plus simple car le fragment de ligne est déjà une tranche de ligne UTF-8 valide, et nous n'avons pas besoin de penser au monstre Unicode.

 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), } } 

Maintenant, ça a l'air un peu différent.

Tout d'abord, regardons les types. Maintenant, notre fonction prend la chaîne expected comme argument et retourne quelque chose de similaire à un analyseur, au lieu d'être un analyseur lui-même. Il s'agit d'une fonction qui renvoie une fonction d'ordre supérieur . Essentiellement, nous écrivons une fonction qui rend une fonction similaire à notre fonction the_letter_a plus tôt.

Ainsi, au lieu d'effectuer un travail dans le corps de la fonction, nous retournons une fermeture qui effectue ce travail et qui correspond à la signature de notre type pour l'analyseur de la précédente.

La correspondance de motifs est identique, sauf que nous ne pouvons pas faire correspondre directement notre littéral de chaîne, car nous ne savons pas exactement quoi, donc nous utilisons la condition de correspondance if next == expected . Sinon, c'est exactement la même chose qu'avant, juste à l'intérieur du corps du circuit.

Tester notre analyseur

Écrivons un test pour nous assurer que nous avons bien compris.

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

Nous créons d'abord un analyseur: match_literal("Hello Joe!") . Il devrait consommer la chaîne "Hello Joe!" et retourner le reste de la chaîne, ou échouer et renvoyer la chaîne entière.

Dans le premier cas, nous lui passons juste la ligne exacte que nous attendons, et voyons qu'elle renvoie une chaîne vide et la valeur () , ce qui signifie "nous avons analysé la chaîne attendue, et vous n'avez pas besoin qu'elle soit renvoyée".

Dans le second, nous alimentons la chaîne "Hello Joe! Hello Robert!" et on voit qu'il utilise vraiment la chaîne "Hello Joe!" et renvoie le reste de l'entrée: " Hello Robert!" (espace de tête et tout le reste).

Dans le troisième, nous entrons la mauvaise entrée: "Hello Mike!" et notez qu'il rejette vraiment l'entrée avec une erreur. Non pas que Mike se trompe, généralement pas ce que l'analyseur recherchait.

Analyseur pour quelque chose de moins spécifique

Cela nous permet donc d'analyser < , > , = et même </ et /> . Nous avons presque fini!

Le suivant après le caractère d'ouverture < est le nom de l'élément. Nous ne pouvons pas le faire avec une simple comparaison de chaînes. Mais nous pourrions le faire avec regex ...

... mais retenons-nous. Ce sera une expression régulière qui sera très facile à répliquer dans du code simple, et pour cela nous n'avons pas besoin d'utiliser le package regex . Voyons voir si nous pouvons écrire notre propre analyseur pour cela, en utilisant uniquement la bibliothèque Rust standard.

Rappelez-vous la règle pour l'identifiant du nom de l'élément, il ressemble à ceci: un caractère alphabétique, suivi par zéro ou plus de n'importe quel symbole alphabétique,
caractère, nombre ou tiret.

 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)) } 

Comme toujours, nous examinons d'abord le type. Cette fois, nous n'écrivons pas de fonction pour créer un analyseur, nous écrivons simplement l'analyseur lui-même, comme pour la première fois. La différence notable ici est qu'au lieu du type de résultat () nous renvoyons une String dans le tuple avec l'entrée restante. Cette String contiendra l'identifiant que nous venons d'analyser.

Dans cet esprit, nous créons d'abord une String vide et l'appelons matched . Ce sera notre résultat. Nous obtenons également un itérateur pour les caractères en input , que nous allons commencer à fractionner.

La première étape consiste à voir s'il y a un symbole au début. Nous tirons le premier caractère de l'itérateur et vérifions s'il s'agit d'une lettre: next.is_alphabetic() . La bibliothèque Rust standard, bien sûr, nous aidera avec Unicode - elle correspondra aux lettres dans n'importe quel alphabet, et pas seulement en ASCII. S'il s'agit d'une lettre, nous la mettons dans notre chaîne dans la variable matched , et sinon, nous ne regardons pas l'identifiant de l'élément et retournons immédiatement avec une erreur.

Dans la deuxième étape, nous continuons à extraire les caractères de l'itérateur, en les envoyant à la ligne que nous créons jusqu'à ce que nous is_alphanumeric() caractère qui ne satisfait pas la fonction is_alphanumeric() (il est similaire à is_alphabetic() sauf qu'il inclut également des nombres dans n'importe quel alphabet) ou tiret '-' .

Lorsque nous voyons pour la première fois quelque chose qui ne répond pas à ces critères, nous terminons l'analyse, rompons la boucle et renvoyons une String , en nous souvenant de couper le fragment que nous avons utilisé en input . De même, si les caractères se terminent par un itérateur, cela signifie que nous avons atteint la fin de l'entrée.

Il convient de noter que nous ne revenons pas avec une erreur lorsque nous voyons quelque chose qui n'est pas alphanumérique ou des tirets. Nous avons déjà suffisamment pour créer un identifiant valide après avoir correspondu à cette première lettre, et il est tout à fait normal qu'après l'analyse de notre identifiant, il y ait plus d'éléments dans la ligne d'entrée pour l'analyse, nous arrêtons donc l'analyse et renvoyons notre résultat. Ce n'est que si nous ne pouvons même pas trouver cette première lettre, que nous renvoyons en fait une erreur, car dans ce cas il n'y avait certainement pas d'identifiant.

N'oubliez pas que la structure Element est ce dans quoi nous allons analyser notre document XML.

 struct Element { name: String, attributes: Vec<(String, String)>, children: Vec<Element>, } 

En fait, nous venons de terminer l'analyseur pour la première partie, le champ du name . String renvoyée par notre analyseur y va directement. C'est également l'analyseur correct pour la première partie de chaque attribute .

Voyons ça.

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

On voit que dans le premier cas, la chaîne "i-am-an-identifier" analysée complètement, ne laissant qu'une chaîne vide. Dans le second cas, l'analyseur renvoie "not" comme identificateur et le reste de la chaîne est renvoyé comme entrée restante. Dans le troisième cas, l'analyseur échoue immédiatement, car le premier caractère qu'il trouve n'est pas une lettre.

Combinateurs

Maintenant, nous pouvons analyser le caractère d'ouverture < , et nous pouvons analyser l'identificateur suivant, mais nous devons analyser les deux . Par conséquent, l'étape suivante consiste à écrire une autre fonction d'analyseur combinatoire, mais celle qui prend deux analyseurs en entrée et renvoie un nouvel analyseur qui les analyse tous les deux dans l'ordre. En d'autres termes, un combinateur d' analyseur car il combine les deux analyseurs en un nouveau. Voyons voir si nous pouvons le faire.

 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), } } 

Cela devient un peu plus compliqué ici, mais vous savez quoi faire: commencez par regarder les types.

Tout d'abord, nous avons quatre types de variables: P1 , P2 , R1 et R2 . Il s'agit de l' Parser 1 , de l' Parser 2 , du Result 1 et du Result 2 . P1 et P2 sont des fonctions, et vous remarquerez qu'elles suivent un modèle bien établi de fonctions d'analyseur: tout comme la valeur de retour, elles prennent &str en entrée et renvoient Result paire d'entrées et de résultats restants, ou une erreur.

Mais regardez les types de résultats de chaque fonction: P1 est l'analyseur qui donne R1 cas de succès, et P2 donne également R2 . Et le résultat du dernier analyseur renvoyé par notre fonction est (R1, R2) . Ainsi, la tâche de cet analyseur est de démarrer d'abord l'analyseur P1 à l'entrée, d'enregistrer son résultat, puis de démarrer P2 à l'entrée qui a renvoyé P1 , et si les deux fonctionnent, nous combinons les deux résultats en un tuple (R1, R2)

Le code montre que c'est exactement ce qu'il fait. Nous commençons par démarrer le premier analyseur à l'entrée, puis le deuxième analyseur, puis combinons les deux résultats en un tuple et le renvoyons. Si l'un de ces analyseurs échoue, nous reviendrons immédiatement avec l'erreur qu'il a émise.

Ainsi, nous devons être capables de combiner nos deux analyseurs, match_literal et identifier , afin d' match_literal réellement match_literal premier fragment de notre première balise XML. Écrivons un test pour voir si cela fonctionne.

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

Semble fonctionner! Mais regardez ce type de résultat: ((), String) . De toute évidence, nous ne sommes intéressés que par la bonne valeur, String . Cela se produit assez souvent - certains de nos analyseurs ne correspondent qu'aux modèles en entrée sans produire de valeurs, et leur sortie peut donc être ignorée en toute sécurité. Pour nous adapter à ce modèle, nous allons utiliser notre combinateur de pair pour écrire deux autres combinateurs: left , qui rejette le résultat du premier analyseur et ne renvoie que le second, et son opposé est right . Nous avons utilisé un analyseur dans notre test ci-dessus, qui supprime la partie gauche et enregistre uniquement notre String , au lieu de la pair .

Présentation de Functor

Mais avant d'aller aussi loin, introduisons un autre combinateur qui simplifiera grandement l'écriture de ces deux: map .

Ce combinateur a une tâche: changer le type de résultat. , , , ((), 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")); } 

. < . ? .

, , . , .

, , - , : .

( ) . .

— , <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 .

, . , . , , , > /> . , . , , , , .

. .

-. 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> , — ¹ , 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)); } 

, . , , , , . , , , , . , , , , , .

: , ! , , , ² .

, , . !

, , Rust , , - , , , .

, pom , , .

Rust nom , pom ( , ), , .

Rust combine , .

Haskell Parsec .

, « Haskell» , , Haskell.

Licence

Bodil Stokke Creative Commons Attribution-NonCommercial-ShareAlike 4.0. , http://creativecommons.org/licenses/by-nc-sa/4.0/ .

1: .

2: , .

andreevlex funkill