Olá Habr! Apresento a você a tradução do artigo "Learning Parser Combinators With Rust" .
Este artigo ensina os conceitos básicos de analisadores combinatórios para pessoas que já estão familiarizadas com o Rust. Supõe-se que nenhum outro conhecimento seja necessário e tudo o que não esteja diretamente relacionado ao Rust, bem como alguns aspectos inesperados de seu uso, serão explicados. Este artigo não ajudará você a aprender Rust se você ainda não o conhece e, nesse caso, provavelmente não entenderá bem os analisadores combinatórios. Se você quiser aprender Rust, recomendo o livro "Rust Programming Language" .
Do ponto de vista do iniciante
Na vida de todo programador, chega um momento em que ele precisa de um analisador.
Um programador iniciante perguntará: "O que é um analisador?"
O programador de nível médio dirá: "É simples, escreverei uma expressão regular".
O programador mestre dirá: "Afaste-se, eu conheço Lex e Yacc."
Um novato pensa melhor de tudo.
Não que expressões regulares sejam ruins. (Mas, por favor, não tente escrever um analisador complexo como uma expressão regular.) Não que não exista alegria em usar ferramentas poderosas, como geradores de analisador e lexer, aperfeiçoadas por milênios com perfeição. Mas aprender o básico dos analisadores é um prazer . Isso também é o que você sentirá falta se entrar em pânico ao usar expressões regulares ou geradores de analisadores, os quais são apenas abstrações sobre o problema real. Na mente de um iniciante, como um homem disse , existem muitas possibilidades. Segundo o especialista, existe apenas uma opção correta.
Neste artigo, aprenderemos como criar um analisador do zero com
usando um método comum em linguagens de programação funcional conhecido como analisador combinatório . Eles têm a vantagem de serem surpreendentemente poderosos assim que você entender sua idéia básica, mantendo-se muito perto do princípio básico. Porque as únicas abstrações aqui serão aquelas que você mesmo criar. Os principais combinadores que você usará aqui, se desenvolverão.
Como trabalhar com este artigo
É altamente recomendável que você comece com um novo projeto Rust e src/lib.rs trechos de código no src/lib.rs enquanto lê (você pode colá-lo diretamente da página, mas inseri-lo melhor, pois isso garante automaticamente que você o lerá completamente). Todas as partes do código necessárias são organizadas em ordem no artigo. Lembre-se de que algumas vezes são introduzidas versões modificadas das funções que você escreveu anteriormente e, nesses casos, você deve substituir a versão antiga pela nova.
O código foi escrito para rustc versão 1.34.0 usando a edição de 2018 idioma. Você pode usar qualquer versão do compilador, verifique se está usando uma edição compatível com a edição de 2018 (verifique se o Cargo.toml contém edition = "2018" ). Este projeto não precisa de dependências externas.
Para realizar os testes apresentados no artigo, conforme o esperado, cargo test .
Linguagem de marcação Xcruciating
Vamos escrever um analisador para uma versão simplificada do XML. É assim:
<parent-element> <single-element attribute="value" /> </parent-element>
Os elementos XML são abertos com o caractere < e um identificador que consiste em uma letra seguida por qualquer número de letras, números e - . Isso é seguido por espaços e uma lista opcional de pares de atributos: outro identificador, conforme definido anteriormente, seguido por = e uma string entre aspas duplas. Por fim, existe um símbolo de fechamento /> para indicar um elemento sem filhos, ou > para indicar a existência da próxima sequência de elementos filhos e uma marca de fechamento começando com </ , seguida de um identificador que deve corresponder à marca de abertura e um símbolo de fechamento > .
É tudo o que apoiaremos. Não haverá espaços para nome, nós de texto e, certamente, não haverá verificação de esquema. Nós nem precisamos nos preocupar com o escape de aspas para strings - elas começam com a primeira aspas duplas e terminam com a próxima, e é isso.
Vamos analisar esses elementos em uma estrutura que se parece com isso:
#[derive(Clone, Debug, PartialEq, Eq)] struct Element { name: String, attributes: Vec<(String, String)>, children: Vec<Element>, }
Não há tipos sofisticados, apenas uma string para o nome (este é o identificador no início de cada tag), atributos na forma de pares de strings (identificador e valor) e uma lista de filhos que se parecem exatamente com o pai.
(Se estiver imprimindo, inclua a seção derive . Você precisará dela mais tarde.)
Definição de analisador
Bem, então, é hora de escrever um analisador.
A análise é o processo de obtenção de dados estruturados a partir de um fluxo de informações. Um analisador é o que traz essa estrutura.
Na disciplina que estamos prestes a pesquisar, o analisador, em sua forma mais simples, é uma função que recebe alguma entrada e retorna a saída analisada junto com o restante da entrada, ou um erro dizendo "Eu não poderia analisar isso".
O analisador também olha em suas formas mais complexas. Você pode complicar o que entrada, saída e erro significam e, se precisar de boas mensagens de erro, mas o analisador permanece o mesmo: algo que consome entrada e produz algum tipo de saída analisada junto com o que sobra da entrada ou avisa que ela não pode analisar a entrada e a saída.
Vamos escrever como um tipo de função.
Fn(Input) -> Result<(Input, Output), Error>
Mais especificamente: no nosso caso, queremos preencher os tipos e obter uma função semelhante a esta. Tudo o que faremos é converter a string em uma estrutura Element . No momento, não queremos entrar nos detalhes das mensagens de erro; basta retornar a parte da linha que não conseguimos analisar. Como resultado, nossa função ficará assim:
Fn(&str) -> Result<(&str, Element), &str>
Usamos uma fatia de string porque é um ponteiro eficaz para um fragmento de uma string e, em seguida, podemos separá-la como quisermos "consumindo" os dados de entrada, cortando o fragmento analisado e retornando o restante junto com o resultado.
Pode ser mais &[u8] usar &[u8] (uma fatia de bytes que corresponde aos caracteres ASCII) como um tipo de entrada, especialmente porque as fatias de string se comportam um pouco diferente da maioria das fatias - especialmente porque você não pode indexá-las com uma input[0] números input[0] , você deve usar a input[0..1] fragmento input[0..1] . Por outro lado, eles têm muitos métodos que são úteis para analisar seqüências de caracteres que não possuem fatias de bytes.
De fato, confiaremos em métodos, não no uso de índices de caracteres, porque Unicode. No UTF-8, e todas as cadeias Rust são cadeias UTF-8 válidas, esses índices nem sempre correspondem a caracteres individuais, e é melhor para todas as partes interessadas solicitar à biblioteca padrão que trabalhe com ela apenas para nós.
Nosso primeiro analisador
Vamos tentar escrever um analisador que apenas observe o primeiro caractere em uma string
e decide se é a letra a .
fn the_letter_a(input: &str) -> Result<(&str, ()), &str> { match input.chars().next() { Some('a') => Ok((&input['a'.len_utf8()..], ())), _ => Err(input), } }
Primeiro, vejamos os tipos de entrada e saída: pegamos uma fatia de string como entrada e retornamos Result com (&str, ()) ou um erro com &str . O par (&str, ()) é um ponto interessante: como dissemos que deveríamos retornar uma tupla do seguinte conteúdo,
resultado da análise e o restante da entrada. &str é a próxima entrada, e o resultado é apenas um tipo de bloco () , porque se esse analisador funcionar com êxito, ele poderá ter apenas um resultado (encontramos a letra a ) e não precisamos realmente retornar
a letra a , neste caso, basta indicar que conseguimos encontrá-la.
Então, vejamos o código do analisador em si. Não brincamos que, contando com a biblioteca padrão, podemos evitar a dor de cabeça com o Unicode: obtemos um iterador sobre os caracteres da string usando o método chars() e extraímos o primeiro caractere. Este será um elemento do tipo char agrupado em Option , no qual None significa que estávamos tentando extrair char de uma string vazia.
Para piorar, char não char necessariamente o que você pensa dele como um caractere Unicode. Provavelmente, é o que o Unicode chama de "cluster de grafema" , que pode consistir em vários char , que na verdade são "valores escalares" , dois níveis abaixo dos clusters de grafema. No entanto, esse caminho leva à loucura e, para nossos propósitos, é pouco provável que vejamos chars fora do ASCII, então vamos parar por aí.
Mapeamos para o padrão Some('a') , que é o resultado específico que estamos procurando e, se isso corresponder, retornamos nosso valor de sucesso:
Ok((&input['a'.len_utf8()..], ())) . Ou seja, removemos a parte que acabamos de analisar ( 'a' ) da fatia da linha e retornamos o restante junto com o nosso valor analisado, que está vazio
() Sempre lembrando do monstro Unicode, antes de cortar, descobrimos o comprimento em UTF-8 do personagem 'a' na biblioteca padrão - é 1 (mas nunca se esqueça do monstro Unicode).
Se obtivermos algum outro Some(char) ou se obtivermos None , retornamos um erro. Como você se lembra, nosso tipo de erro é simplesmente uma fatia de string, que passamos como input e que não pôde ser analisada. Não começou com a , então esse é o nosso erro. Este não é um grande erro, mas pelo menos é um pouco melhor do que apenas "algo está errado em algum lugar".
Nós realmente não precisamos desse analisador para analisar o XML, mas a primeira coisa que precisamos fazer é encontrar o caractere de abertura < , então precisamos de algo muito semelhante. Também precisaremos analisar > , / e = especificamente, para que possamos criar uma função que construa o analisador para o caractere que queremos?
Criando um Analisador
Vamos até pensar sobre isso: escreveremos uma função que cria um analisador para uma sequência estática de qualquer tamanho , e não apenas um caractere. Isso é ainda mais simples, porque o fragmento de linha já é uma fatia de linha UTF-8 válida e não precisamos pensar no monstro 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), } }
Agora parece um pouco diferente.
Primeiro de tudo, vamos olhar para os tipos. Agora, nossa função toma a string expected como argumento e retorna algo semelhante a um analisador, em vez de ser o próprio analisador. Esta é uma função que retorna uma função de ordem superior . Essencialmente, estamos escrevendo uma função que torna semelhante a nossa função the_letter_a anteriormente.
Assim, em vez de executar um trabalho no corpo da função, retornamos um fechamento que executa esse trabalho e que corresponde à assinatura do nosso tipo para o analisador do analisador anterior.
A correspondência de padrões tem a mesma aparência, exceto que não podemos corresponder diretamente a nossa string literal, porque não sabemos exatamente o que é, portanto, usaremos a condição de correspondência if next == expected . Caso contrário, é exatamente o mesmo de antes, apenas dentro do corpo do circuito.
Testando nosso analisador
Vamos escrever um teste para isso, para garantir que acertemos.
#[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!") ); }
Primeiro, criamos um analisador: match_literal("Hello Joe!") . Ele deve consumir a sequência "Hello Joe!" e retorne o restante da string ou falhe e retorne a string inteira.
No primeiro caso, passamos a linha exata que esperamos e vemos que ela retorna uma sequência vazia e o valor () , o que significa "analisamos a sequência esperada e você não precisa que ela seja retornada".
No segundo, alimentamos a string "Hello Joe! Hello Robert!" e vemos que ele realmente usa a string "Hello Joe!" e retorna o restante da entrada: " Hello Robert!" (espaço principal e tudo mais).
Na terceira, inserimos a entrada errada: "Hello Mike!" e observe que realmente rejeita a entrada com um erro. Não que Mike esteja errado, geralmente não é o que o analisador estava procurando.
Analisador para algo menos específico
Portanto, isso nos permite analisar < , > , = e até </ e /> . Estamos quase terminando!
O próximo após o caractere de abertura < é o nome do elemento. Não podemos fazer isso com uma simples comparação de cadeias. Mas poderíamos fazer isso com regex ...
... mas vamos nos segurar. Essa será uma expressão regular que será muito fácil de replicar em código simples e, para isso, não precisamos usar o pacote regex . Vamos ver se podemos escrever nosso próprio analisador para isso, usando apenas a biblioteca Rust padrão.
Lembre-se da regra para o identificador do nome do elemento, que se parece com isso: um caractere alfabético, seguido por zero ou mais de qualquer símbolo alfabético,
caractere, número ou traço.
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)) }
Como sempre, primeiro analisamos o tipo. Desta vez, não escrevemos uma função para criar um analisador, apenas escrevemos o analisador em si, como pela primeira vez. A diferença notável aqui é que, em vez do tipo de resultado () retornamos uma String na tupla junto com a entrada restante. Essa String conterá o identificador que acabamos de analisar.
Com isso em mente, primeiro criamos uma String vazia e a chamamos de matched . Este será o nosso resultado. Também temos um iterador para os caracteres na input , que vamos começar a dividir.
O primeiro passo é verificar se existe um símbolo no início. Nós puxamos o primeiro caractere do iterador e verificamos se é uma letra: next.is_alphabetic() . A biblioteca Rust padrão, é claro, nos ajudará com Unicode - corresponderá a letras em qualquer alfabeto, e não apenas em ASCII. Se for uma letra, colocamos em nossa string na variável matched e, se não, não examinamos o identificador do elemento e retornamos imediatamente com um erro.
Na segunda etapa, continuamos a puxar os caracteres do iterador, enviando-os para a linha que criamos até is_alphanumeric() caractere que não satisfaça a função is_alphanumeric() (é semelhante a is_alphabetic() exceto que também inclui números em qualquer alfabeto) ou traço '-' .
Quando vemos pela primeira vez algo que não atende a esses critérios, finalizamos a análise, interrompemos o loop e retornamos uma String , lembrando de cortar o fragmento que usamos da input . Da mesma forma, se os caracteres terminam em um iterador, significa que chegamos ao final da entrada.
Vale ressaltar que não retornamos com erro quando vemos algo que não é alfanumérico ou traço. Já temos o suficiente para criar um identificador válido depois de correspondermos à primeira letra, e é normal que, após analisar nosso identificador, haja mais elementos na linha de entrada para análise, portanto, paramos a análise e retornamos o resultado. Somente se não conseguirmos encontrar nem mesmo essa primeira letra, realmente retornaremos um erro, porque nesse caso definitivamente não havia identificador.
Lembre-se de que a estrutura Element é o que vamos analisar em nosso documento XML.
struct Element { name: String, attributes: Vec<(String, String)>, children: Vec<Element>, }
De fato, acabamos de terminar o analisador para a primeira parte, o campo de name . String que nosso analisador retorna vai diretamente para lá. Também é o analisador correto para a primeira parte de cada attribute .
Vamos conferir.
#[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") ); }
Vemos que, no primeiro caso, a cadeia "i-am-an-identifier" analisada completamente, deixando apenas uma cadeia vazia. No segundo caso, o analisador retorna "not" como um identificador e o restante da string é retornado como a entrada restante. No terceiro caso, o analisador falha imediatamente, porque o primeiro caractere encontrado não é uma letra.
Combinadores
Agora podemos analisar o caractere de abertura < e podemos analisar o próximo identificador, mas precisamos analisar os dois . Portanto, a próxima etapa é escrever outra função de analisador combinatório, mas que aceite dois analisadores como entrada e retorne um novo analisador que analise os dois em ordem. Em outras palavras, um combinador de analisador porque combina os dois analisadores em um novo. Vamos ver se podemos fazer isso.
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), } }
Aqui fica um pouco mais complicado, mas você sabe o que fazer: comece examinando os tipos.
Primeiro de tudo, temos quatro tipos de variáveis: P1 , P2 , R1 e R2 . Estes são o Parser 1 , Parser 2 , Result 1 e Result 2 . P1 e P2 são funções, e você observará que elas seguem um padrão bem estabelecido de funções do analisador: assim como o valor de retorno, elas tomam &str como entrada e retornam Result par de entrada e resultado restantes ou um erro.
Mas observe os tipos de resultados de cada função: P1 é o analisador que fornece R1 se for bem-sucedido e P2 também fornece R2 . E o resultado do último analisador retornado de nossa função é (R1, R2) . Assim, a tarefa desse analisador é primeiro iniciar o analisador P1 na entrada, salvar seu resultado, depois iniciar P2 na entrada que retornou P1 e, se ambos funcionarem, combinamos os dois resultados em uma tupla (R1, R2)
O código mostra que é exatamente isso que ele faz. Começamos iniciando o primeiro analisador na entrada, depois o segundo analisador, depois combinamos os dois resultados em uma tupla e retornamos. Se algum desses analisadores falhar, retornaremos imediatamente com o erro que ele emitiu.
Portanto, devemos poder combinar nossos dois analisadores, match_literal e identifier , para match_literal primeiro fragmento de nossa primeira tag XML. Vamos escrever um teste para ver se funciona.
#[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")); }
Parece funcionar! Mas observe este tipo de resultado: ((), String) . Obviamente, estamos interessados apenas no valor certo, String . Isso acontece com bastante frequência - alguns de nossos analisadores correspondem apenas aos padrões da entrada sem produzir valores e, portanto, sua saída pode ser ignorada com segurança. Para se adaptar a esse padrão, usaremos nosso combinador de pair para escrever outros dois combinadores: left , que descarta o resultado do primeiro analisador e retorna apenas o segundo, e seu oposto é o right . Usamos um analisador em nosso teste acima, que descarta a parte esquerda e salva apenas nossa String , em vez de pair .
Introdução ao Functor
Mas antes de irmos tão longe, vamos apresentar outro combinador que simplificará bastante a escrita desses dois: map .
Este combinador tem uma tarefa: alterar o tipo de resultado. , , , ((), 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> , — 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