Привет, Хабр!
Представьте себе котика, который пытается понять синтаксис человеческого языка. Сначала он разглядывает слова, затем прислушивается к интонациям, а потом решает, что всё это слишком сложно, и отправляется ловить мышей.
Но благо, что у нас, людишек, есть возможность создания инструмента, который может разложить сложные языковые конструкции на простые и понятные части. Как раз об этом и пойдет речь в нашей сегодняшней статье — о создании парсеров на Rust.
А именно - о двух библиотеках, которые позволяют это сделать. Начнем с первой под названием nom.
Библиотека Nom
В nom парсеры строятся из небольших функций, которые можно комбинировать для создания более сложных парсеров.
nom предоставляет большой набор комбинаторов и функций для построения парсеров. Рассмотрим некоторые из них:
tagиtag_no_case— функции для сопоставления точного значения строки:use nom::bytes::complete::tag; fn parse_hello(input: &str) -> IResult<&str, &str> { tag("hello, habr")(input) }alt— комбинатор для выбора одного из нескольких альтернативных парсеров:use nom::branch::alt; fn parse_bool(input: &str) -> IResult<&str, bool> { alt((value(true, tag("true")), value(false, tag("false"))))(input) }many0иmany1— функции для многократного применения парсера:use nom::multi::many1; use nom::character::complete::digit1; fn parse_digits(input: &str) -> IResult<&str, Vec<&str>> { many1(digit1)(input) }mapиmap_res— функции для преобразования результата парсера:use nom::combinator::map_res; use std::str::FromStr; fn parse_int(input: &str) -> IResult<&str, i32> { map_res(digit1, FromStr::from_str)(input) }do_parseиtuple— макросы для последовательного парсинга:use nom::sequence::tuple; fn parse_tuple(input: &str) -> IResult<&str, (&str, &str)> { tuple((alpha1, digit1))(input) }
Примеры парсеров
Рассмотрим пример парсера для RGB цвета в шестнадцатеричном формате:
use nom::bytes::complete::tag; use nom::character::complete::take_while_m_n; use nom::combinator::map_res; use nom::IResult; fn is_hex_digit(c: char) -> bool { c.is_digit(16) } fn from_hex(input: &str) -> Result<u8, std::num::ParseIntError> { u8::from_str_radix(input, 16) } fn hex_primary(input: &str) -> IResult<&str, u8> { map_res(take_while_m_n(2, 2, is_hex_digit), from_hex)(input) } #[derive(Debug, PartialEq)] struct Color { red: u8, green: u8, blue: u8, } fn hex_color(input: &str) -> IResult<&str, Color> { let (input, _) = tag("#")(input)?; let (input, (red, green, blue)) = (hex_primary, hex_primary, hex_primary).parse(input)?; Ok((input, Color { red, green, blue })) } fn main() { println!("{:?}", hex_color("#2F14DF")); } #[test] fn parse_color() { assert_eq!( hex_color("#2F14DF"), Ok(( "", Color { red: 47, green: 20, blue: 223, } )) ); }
Можно создавать парсеры с использованием рекурсивного спуска, что дает возможность создавать сложные парсеры для различных языков и форматов данных. Реализуем парсер арифметических выражений:
use nom::character::complete::digit1; use nom::combinator::map_res; use nom::sequence::tuple; use nom::IResult; use std::str::FromStr; fn parse_number(input: &str) -> IResult<&str, i64> { map_res(digit1, FromStr::from_str)(input) } fn parse_term(input: &str) -> IResult<&str, i64> { parse_number(input) } fn parse_expression(input: &str) -> IResult<&str, i64> { let (input, (left, _, right)) = tuple((parse_term, tag("+"), parse_term))(input)?; Ok((input, left + right)) } fn main() { println!("{:?}", parse_expression("3+5")); }
При работе с потоками токенов часто используется итератор Peekable, который позволяет заглядывать на следующий элемент без его извлечения. Мастхев при создании парсеров, которые должны принимать решения на основе будущих токенов:
use std::iter::Peekable; use std::str::Chars; fn parse_term(iter: &mut Peekable<Chars>) -> Option<i64> { let mut number = 0; while let Some(&ch) = iter.peek() { if ch.is_digit(10) { number = number * 10 + ch.to_digit(10).unwrap() as i64; iter.next(); } else { break; } } Some(number) } fn main() { let input = "12345"; let mut iter = input.chars().peekable(); let number = parse_term(&mut iter); println!("Parsed number: {:?}", number); }
Пример парсера, который извлекает заголовки статей с главной страницы Хабр:
use nom::bytes::complete::{tag, take_until}; use nom::sequence::delimited; use nom::IResult; use reqwest; async fn fetch_habr() -> Result<String, reqwest::Error> { let response = reqwest::get("https://habr.com").await?; let body = response.text().await?; Ok(body) } fn parse_title(input: &str) -> IResult<&str, &str> { delimited(tag("<a href=\"/ru/post/"), take_until("\">"), take_until("</a>"))(input) } fn parse_titles(input: &str) -> Vec<&str> { let mut titles = Vec::new(); let mut rest = input; while let Ok((remaining, title)) = parse_title(rest) { titles.push(title); rest = remaining; } titles } #[tokio::main] async fn main() { match fetch_habr().await { Ok(body) => { let titles = parse_titles(&body); for title in titles { println!("Title: {}", title); } } Err(e) => eprintln!("Error fetching the page: {}", e), } }
fetch_habr— функция для получения HTML-страницы с Хабра.parse_title— функция для парсинга одного заголовка статьи.parse_titles— функция для извлечения всех заголовков статей с HTML-страницы.
Подробнее с библиотекой можно ознакомиться здесь. А пока мып переходим к следующей библиотеке - Chumsky.
Библиотека Chumsky
Chumsky — еще одна годная библиотеека для создания парсеров на основе комбинаторов в языке Rust. Она предоставляет высокоуровневый API для написания парсеров, которые легко комбинировать и расширять.
Chumsky поддерживает парсинг выражений, что делает её способной обрабатывать все известные контекстно-свободные языки.
Основные комбинаторы для построения парсеров:
just— создает парсер для точного совпадения символа:use chumsky::prelude::*; let parser = just('a');choice— позволяет выбрать один из нескольких альтернативных парсеров:let parser = choice(( just('a').to(1), just('b').to(2), ));repeated— многократно применяет парсер:let parser = just('a').repeated();map— преобразует результат парсера:let parser = just('a').map(|_| 42);recursive— позволяет создавать рекурсивные парсеры:let parser = recursive(|bf| choice(( just('<').to(Instr::Left), just('>').to(Instr::Right), bf.delimited_by(just('['), just(']')).map(Instr::Loop), )).repeated());
Примеры использования
Рассмотрим пример создания парсера для простого языка арифметических выражений с поддержкой операторов и скобок:
use chumsky::prelude::*; use chumsky::primitive::recursive; #[derive(Debug, PartialEq)] enum Expr { Num(i64), Add(Box<Expr>, Box<Expr>), Sub(Box<Expr>, Box<Expr>), Mul(Box<Expr>, Box<Expr>), Div(Box<Expr>, Box<Expr>), } fn expr_parser() -> impl Parser<char, Expr, Error = Simple<char>> { recursive(|expr| { let num = text::int(10).from_str().unwrapped().map(Expr::Num); let atom = num .or(expr.delimited_by(just('('), just(')'))); let op = just('+').to(Expr::Add) .or(just('-').to(Expr::Sub)) .or(just('*').to(Expr::Mul)) .or(just('/').to(Expr::Div)); atom.clone().then(op.then(expr).repeated()).foldl(|lhs, (op, rhs)| op(Box::new(lhs), Box::new(rhs))) }) } fn main() { let parser = expr_parser().then_ignore(end()); let expr = parser.parse("(1 + 2) * 3").unwrap(); println!("{:?}", expr); // Output: Mul(Add(Num(1), Num(2)), Num(3)) }
Для создания парсера JSON можно использовать аналогичные принципы, комбинируя простые парсеры для обработки различных частей JSON-структуры:
use chumsky::prelude::*; use chumsky::primitive::choice; #[derive(Debug, PartialEq)] enum Json { Null, Bool(bool), Number(f64), String(String), Array(Vec<Json>), Object(Vec<(String, Json)>), } fn json_parser() -> impl Parser<char, Json, Error = Simple<char>> { let null = just("null").to(Json::Null); let boolean = choice(( just("true").to(Json::Bool(true)), just("false").to(Json::Bool(false)), )); let number = text::int(10).chain::<char, _, _>(just('.').chain(text::digits(10)).or_not()) .from_str().unwrapped().map(Json::Number); let string = just('"').ignore_then(text::take_until(just('"'))).map(Json::String); let array = json_parser().repeated().delimited_by(just('['), just(']')).map(Json::Array); let pair = string.clone().then_ignore(just(':')).then(json_parser()); let object = pair.repeated().delimited_by(just('{'), just('}')).map(Json::Object); choice((null, boolean, number, string, array, object)) } fn main() { let parser = json_parser().then_ignore(end()); let json = parser.parse(r#"{"key": "value", "array": [null, true, 42.0]}"#).unwrap(); println!("{:?}", json); // Output: Object([("key", String("value")), ("array", Array([Null, Bool(true), Number(42.0)]))]) }
Пример парсера, который извлекает заголовки статей с главной страницы Хабр:
use chumsky::prelude::*; use chumsky::text::{text, TextParser}; use reqwest; async fn fetch_habr() -> Result<String, reqwest::Error> { let response = reqwest::get("https://habr.com").await?; let body = response.text().await?; Ok(body) } fn parser() -> impl Parser<char, Vec<String>, Error = Simple<char>> { let title_start = text::text("<a href=\"/ru/post/").ignored(); let title_end = text::text("\">").ignored(); let title_parser = title_start .clone() .then(text::take_until(title_end.clone())) .map(|((), title): ((), String)| title); title_parser.repeated() } #[tokio::main] async fn main() { match fetch_habr().await { Ok(body) => { let parser = parser(); let titles = parser.parse(body.chars().collect::<String>()).unwrap(); for title in titles { println!("Title: {}", title); } } Err(e) => eprintln!("Error fetching the page: {}", e), } }
fetch_habr— функция для получения HTML-страницы с Хабра.parser— функция для создания парсера, который извлекает заголовки статей.title_startиtitle_end— парсеры для начала и конца заголовка.title_parser— парсер для одного заголовка статьи.repeated— комбинатор для многократного примененияtitle_parser.
Подробнее с библиотекой можно ознакомиться здесь.
А с другими языками программирования инструментами можно ознакомиться в рамках практических онлайн-курсов от моих друзей из OTUS. Подробнее в каталоге.
