Hola Habr! Les presento la traducción del artículo "Combinadores de analizador de aprendizaje con óxido" .
Este artículo enseña los conceptos básicos de analizadores combinatorios para personas que ya están familiarizadas con Rust. Se supone que no se requiere ningún otro conocimiento, y se explicará todo lo que no esté directamente relacionado con Rust, así como algunos aspectos inesperados de su uso. Este artículo no lo ayudará a aprender Rust si aún no lo sabe, y en este caso, lo más probable es que no comprenda bien los analizadores combinatorios. Si quieres aprender Rust, te recomiendo el libro "Rust Programming Language" .
Desde el punto de vista del principiante
En la vida de cada programador, llega un momento en que necesita un analizador.
Un programador novato preguntará: "¿Qué es un analizador sintáctico?"
El programador de nivel medio dirá: "Es simple, escribiré una expresión regular".
El maestro programador dirá: "Aléjate, sé que Lex y Yacc".
Un novato piensa lo mejor de todo.
No es que las expresiones regulares sean malas. (Pero, por favor, no intente escribir un analizador complejo como una expresión regular). No es que no sea divertido usar herramientas poderosas como generadores de analizador y lexer que se han perfeccionado a la perfección durante milenios. Pero aprender los conceptos básicos de los analizadores sintéticos es un placer . Esto también es lo que extrañará si tiene pánico cuando usa expresiones regulares o generadores de analizadores, los cuales son solo abstracciones sobre el problema real. En la mente de un principiante, como dijo un hombre , hay muchas posibilidades. Según el experto, solo hay una opción correcta.
En este artículo, aprenderemos cómo construir un analizador desde cero con
utilizando un método común en lenguajes de programación funcional conocidos como analizador combinatorio . Tienen la ventaja de ser sorprendentemente poderosos tan pronto como captas su idea básica, mientras permanecen muy cerca del principio básico. Porque las únicas abstracciones aquí serán aquellas que crees tú mismo. Los principales combinadores que usará aquí los construirá usted mismo.
Cómo trabajar con este artículo
Se recomienda encarecidamente que comience con un nuevo proyecto Rust y escriba fragmentos de código en src/lib.rs medida que lo lee (puede pegarlo directamente desde la página, pero src/lib.rs mejor, ya que esto garantiza automáticamente que lo leerá por completo). Todas las partes del código que necesita están organizadas en orden en el artículo. Tenga en cuenta que a veces se introducen versiones modificadas de funciones que escribió anteriormente, y en estos casos debe reemplazar la versión anterior por la nueva.
El código fue escrito para rustc versión 1.34.0 usando la edición de idioma 2018 . Puede usar cualquier versión del compilador, asegúrese de estar usando una versión que admita la edición 2018 (asegúrese de que su Cargo.toml contiene edition = "2018" ). Este proyecto no necesita dependencias externas.
Para realizar las pruebas presentadas en el artículo, como se esperaba, cargo test .
Lenguaje de marcado Xcruciating
Vamos a escribir un analizador para una versión simplificada de XML. Se ve así:
<parent-element> <single-element attribute="value" /> </parent-element>
Los elementos XML se abren con el carácter < y un identificador que consiste en una letra seguida de cualquier número de letras, números y - . Esto es seguido por espacios y una lista opcional de pares de atributos: otro identificador como se definió anteriormente, seguido de = y una cadena entre comillas dobles. Finalmente, hay un símbolo de cierre /> para indicar un elemento sin elementos secundarios, o > para indicar la existencia de la siguiente secuencia de elementos secundarios, y una etiqueta de cierre que comienza con </ , seguida de un identificador que debe coincidir con la etiqueta de apertura y un símbolo de cierre > .
Eso es todo lo que apoyaremos. No habrá espacios de nombres, ni nodos de texto, y ciertamente no habrá verificación de esquema. Ni siquiera tenemos que preocuparnos por escapar de las comillas para las cadenas: comienzan con la primera comilla doble, y terminan con la siguiente, y eso es todo.
Vamos a analizar estos elementos en una estructura que se ve así:
#[derive(Clone, Debug, PartialEq, Eq)] struct Element { name: String, attributes: Vec<(String, String)>, children: Vec<Element>, }
No hay tipos sofisticados, solo una cadena para el nombre (este es el identificador al comienzo de cada etiqueta), atributos en forma de pares de cadenas (identificador y valor) y una lista de elementos secundarios que se ven exactamente como los padres.
(Si está imprimiendo, asegúrese de incluir la sección de derive . La necesitará más adelante).
Definición del analizador
Bueno, entonces es hora de escribir un analizador.
El análisis es el proceso de obtener datos estructurados de un flujo de información. Un analizador es lo que resalta esta estructura.
En la disciplina que vamos a explorar, el analizador, en su forma más simple, es una función que toma alguna entrada y devuelve la salida analizada junto con el resto de la entrada, o un error que dice "No pude analizar esto".
El analizador también se ve en sus formas más complejas. Puede complicar lo que significan entrada, salida y error, y si necesita buenos mensajes de error que necesita, pero el analizador sigue siendo el mismo: algo que consume entrada y produce algún tipo de salida analizada junto con qué sobrante de la entrada o le permite saber que no puede analizar la entrada a la salida.
Escribámoslo como un tipo de función.
Fn(Input) -> Result<(Input, Output), Error>
Más específicamente: en nuestro caso, queremos completar los tipos y obtener una función similar a esta. Todo lo que vamos a hacer es convertir la cadena a una estructura de Element . Por el momento, no queremos entrar en los detalles de los mensajes de error, así que solo devuelva la parte de la línea que no pudimos analizar. Como resultado, nuestra función se verá así:
Fn(&str) -> Result<(&str, Element), &str>
Usamos un segmento de cadena porque es un puntero efectivo a un fragmento de una cadena, y luego podemos separarlo como queramos "consumiendo" los datos de entrada, cortando el fragmento analizado y devolviendo el resto junto con el resultado.
Puede ser más limpio usar &[u8] (un segmento de bytes que coinciden con caracteres ASCII) como tipo de entrada, especialmente porque los segmentos de cadena se comportan de manera un poco diferente a la mayoría de los segmentos, especialmente porque no puede indexarlos con uno números de input[0] , debe utilizar el fragmento de input[0..1] . Por otro lado, tienen muchos métodos que son útiles para analizar cadenas que no tienen segmentos de bytes.
De hecho, confiaremos en métodos, no en el uso de índices de caracteres, porque Unicode. En UTF-8, y todas las cadenas Rust son cadenas UTF-8 válidas, estos índices no siempre corresponden a caracteres individuales, y es mejor que todas las partes interesadas soliciten a la biblioteca estándar que solo trabaje con nosotros.
Nuestro primer analizador
Intentemos escribir un analizador que solo mire el primer carácter de una cadena
y decide si es la letra a .
fn the_letter_a(input: &str) -> Result<(&str, ()), &str> { match input.chars().next() { Some('a') => Ok((&input['a'.len_utf8()..], ())), _ => Err(input), } }
Primero, veamos los tipos de entrada y salida: tomamos un segmento de cadena como entrada y devolvemos el Result con (&str, ()) , o un error con &str . El par (&str, ()) es un punto interesante: como dijimos que deberíamos devolver una tupla del siguiente contenido,
resultado del análisis y el resto de la entrada. &str es la siguiente entrada, y el resultado es solo un tipo de bloque () , porque si este analizador funciona correctamente, solo puede tener un resultado (encontramos la letra a ), y realmente no necesitamos devolver
la letra a en este caso solo necesitamos indicar que logramos encontrarla.
Entonces, veamos el código del analizador en sí. No bromeamos diciendo que confiando en la biblioteca estándar podemos evitar el dolor de cabeza con Unicode: obtenemos un iterador sobre los caracteres de la cadena usando el método chars() y tomamos el primer carácter de él. Este será un elemento de tipo char envuelto en Option , en el que None significará que estamos tratando de extraer char de una cadena vacía.
Para empeorar las cosas, char no char necesariamente lo que piensas de él como un personaje Unicode. Es probable que esto sea lo que Unicode llama un "grupo de grafemas" , que puede consistir en varios caracteres, que en realidad son "valores escalares" , que están dos niveles por debajo de los grupos de grafemas. Sin embargo, este camino conduce a la locura, y para nuestros propósitos, honestamente, es poco probable que veamos chars fuera de ASCII, así que paremos allí.
Asignamos el patrón Some('a') , que es el resultado específico que estamos buscando, y si eso coincide, devolvemos nuestro valor de éxito:
Ok((&input['a'.len_utf8()..], ())) . Es decir, eliminamos la parte que acabamos de analizar ( 'a' ) del segmento de línea y devolvemos el resto junto con nuestro valor analizado, que está vacío
() Siempre recordando el monstruo Unicode, antes de cortar, descubrimos la longitud en UTF-8 del personaje 'a' través de la biblioteca estándar: es 1 (pero nunca se olvide del monstruo Unicode).
Si obtenemos algún otro Some(char) , o si obtenemos None , entonces devolvemos un error. Como recordará, nuestro tipo de error es simplemente un corte de cadena, que pasamos como input y que no se pudo analizar. No comenzó con a , así que este es nuestro error. Esto no es un gran error, pero al menos es un poco mejor que simplemente "algo está mal en alguna parte".
En realidad, no necesitamos este analizador para analizar el XML, pero lo primero que tendremos que hacer es encontrar el carácter de apertura < , por lo que necesitamos algo muy similar. También tendremos que analizar > , / y = específicamente, por lo que tal vez podamos hacer una función que construya el analizador para el carácter que queremos.
Crear un analizador
Pensemos incluso en esto: escribiremos una función que cree un analizador para una cadena estática de cualquier longitud , y no solo un carácter. Esto es aún más simple porque el fragmento de línea ya es un corte de línea UTF-8 válido, y no necesitamos pensar en el monstruo 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), } }
Ahora se ve un poco diferente.
En primer lugar, veamos los tipos. Ahora nuestra función toma la cadena expected como argumento y devuelve algo similar a un analizador, en lugar de ser un analizador en sí. Esta es una función que devuelve una función de orden superior . Esencialmente, estamos escribiendo una función que hace una función similar a nuestra función the_letter_a anteriormente.
Por lo tanto, en lugar de realizar un trabajo en el cuerpo de la función, devolvemos un cierre que realiza este trabajo y que corresponde a la firma de nuestro tipo para el analizador de la anterior.
La coincidencia de patrones se ve igual, excepto que no podemos hacer coincidir nuestro literal de cadena directamente, porque no sabemos exactamente qué, por lo tanto, usamos la condición de coincidencia if next == expected . De lo contrario, es exactamente lo mismo que antes, justo dentro del cuerpo del circuito.
Probar nuestro analizador
Escribamos una prueba para esto para asegurarnos de que lo hacemos bien.
#[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!") ); }
Primero creamos un analizador: match_literal("Hello Joe!") . Debería consumir la cadena "Hello Joe!" y devuelve el resto de la cadena, o falla y devuelve la cadena completa.
En el primer caso, simplemente le pasamos la fila exacta que esperamos, y vemos que devuelve una cadena vacía y el valor () , que significa "hemos analizado la cadena esperada, y no necesita que se devuelva".
En el segundo, alimentamos la cadena "Hello Joe! Hello Robert!" y vemos que realmente usa la cadena "Hello Joe!" y devuelve el resto de la entrada: " Hello Robert!" (liderando el espacio y todo lo demás).
En el tercero, ingresamos la entrada incorrecta: "Hello Mike!" y tenga en cuenta que realmente rechaza la entrada con un error. No es que Mike esté equivocado, generalmente no es lo que buscaba el analizador.
Analizador de algo menos específico
Entonces esto nos permite analizar < , > , = e incluso </ y /> . Ya casi hemos terminado!
El siguiente después del carácter de apertura < es el nombre del elemento. No podemos hacer esto con una simple comparación de cadenas. Pero podríamos hacerlo con regex ...
... pero detengámonos. Esta será una expresión regular que será muy fácil de replicar en código simple, y para esto no necesitamos usar el paquete regex . Veamos si podemos escribir nuestro propio analizador para esto, usando solo la biblioteca estándar Rust.
Recuerde la regla para el identificador del nombre del elemento, se ve así: un carácter alfabético, seguido de cero o más de cualquier símbolo alfabético,
carácter, número o guión.
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 siempre, primero miramos el tipo. Esta vez no escribimos una función para crear un analizador, simplemente escribimos el analizador en sí, como por primera vez. La diferencia notable aquí es que, en lugar del tipo de resultado () devolvemos una String en la tupla junto con la entrada restante. Esta String contendrá el identificador que acabamos de analizar.
Con eso en mente, primero creamos una String vacía y la llamamos matched . Este será nuestro resultado. También obtenemos un iterador para los caracteres de input , que vamos a comenzar a dividir.
El primer paso es ver si hay un símbolo al principio. Extraemos el primer carácter del iterador y verificamos si es una letra: next.is_alphabetic() . La biblioteca estándar de Rust, por supuesto, nos ayudará con Unicode: corresponderá a letras en cualquier alfabeto, y no solo en ASCII. Si es una letra, la ponemos en nuestra cadena en la variable matched , y si no, no miramos el identificador del elemento e inmediatamente regresamos con un error.
En el segundo paso, continuamos sacando los caracteres del iterador, enviándolos a la línea que creamos hasta que is_alphanumeric() carácter que no satisfaga la función is_alphanumeric() (es similar a is_alphabetic() excepto que también incluye números en cualquier alfabeto) o guión '-' .
Cuando vemos por primera vez algo que no cumple con estos criterios, terminamos el análisis, rompemos el ciclo y devolvemos una String , recordando cortar el fragmento que usamos de la input . Del mismo modo, si los caracteres terminan en un iterador, significa que hemos llegado al final de la entrada.
Vale la pena señalar que no regresamos con un error cuando vemos algo que no es alfanumérico o guiones. Ya tenemos suficiente para crear un identificador válido después de que coincidamos con esta primera letra, y es bastante normal que después de analizar nuestro identificador haya más elementos en la línea de entrada para el análisis, por lo que simplemente detenemos el análisis y devolvemos nuestro resultado. Solo si no podemos encontrar incluso esta primera letra, en realidad devolvemos un error, porque en este caso definitivamente no hubo un identificador.
Recuerde que la estructura del Element es en lo que vamos a analizar nuestro documento XML.
struct Element { name: String, attributes: Vec<(String, String)>, children: Vec<Element>, }
De hecho, acabamos de terminar el analizador para la primera parte, el campo de name . String que devuelve nuestro analizador va directamente allí. También es el analizador correcto para la primera parte de cada attribute .
Vamos a verlo
#[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 en el primer caso, la cadena "i-am-an-identifier" analiza por completo, dejando solo una cadena vacía. En el segundo caso, el analizador devuelve "not" como identificador, y el resto de la cadena se devuelve como la entrada restante. En el tercer caso, el analizador falla inmediatamente, porque el primer carácter que encuentra no es una letra.
Combinadores
Ahora podemos analizar el carácter de apertura < , y podemos analizar el siguiente identificador, pero necesitamos analizar ambos . Por lo tanto, el siguiente paso es escribir otra función de analizador combinatorio, pero una que tome dos analizadores como entrada y devuelva un analizador nuevo que los analice a ambos en orden. En otras palabras, un combinador de analizadores sintéticos porque combina los dos analizadores sintácticos en uno nuevo. Veamos si podemos hacer esto.
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), } }
Aquí se vuelve un poco más complicado, pero ya sabes qué hacer: comienza por ver los tipos.
En primer lugar, tenemos cuatro tipos de variables: P1 , P2 , R1 y R2 . Estos son Parser 1 , Parser 2 , Result 1 y Result 2 . P1 y P2 son funciones, y notará que siguen un patrón bien establecido de funciones de analizador: al igual que el valor de retorno, toman &str como entrada y devuelven Result par de la entrada y el resultado restantes, o un error.
Pero observe los tipos de resultados de cada función: P1 es el analizador que da R1 si tiene éxito, y P2 también da R2 . Y el resultado del último analizador devuelto por nuestra función es (R1, R2) . Por lo tanto, la tarea de este analizador es primero iniciar el analizador P1 en la entrada, guardar su resultado, luego iniciar P2 en la entrada que devolvió P1 , y si ambos funcionan, combinamos los dos resultados en una tupla (R1, R2)
El código muestra que esto es exactamente lo que hace. Comenzamos iniciando el primer analizador en la entrada, luego el segundo analizador, luego combinamos los dos resultados en una tupla y lo devolvemos. Si alguno de estos analizadores falla, regresaremos inmediatamente con el error que emitió.
Por lo tanto, debemos poder combinar nuestros dos analizadores, match_literal e identifier , para match_literal realmente match_literal primer fragmento de nuestra primera etiqueta XML. Escribamos una prueba para ver si 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 que funciona! Pero mira este tipo de resultado: ((), String) . Obviamente, solo nos interesa el valor correcto, String . Esto sucederá con bastante frecuencia: algunos de nuestros analizadores solo coinciden con patrones en la entrada sin producir valores, por lo que su salida puede ignorarse de forma segura. Para adaptarnos a este patrón, vamos a utilizar nuestro combinador de pair para escribir otros dos combinadores: left , que descarta el resultado del primer analizador y devuelve solo el segundo, y su opuesto es el right . Usamos un analizador en nuestra prueba anterior, que descarta la parte izquierda y guarda solo nuestra String , en lugar del pair .
Introducción al Functor
Pero antes de ir tan lejos, introduzcamos otro combinador que simplificará en gran medida la escritura de estos dos: map .
Este combinador tiene una tarea: cambiar el 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