Создание парсеров на Rust

Привет, Хабр!

Представьте себе котика, который пытается понять синтаксис человеческого языка. Сначала он разглядывает слова, затем прислушивается к интонациям, а потом решает, что всё это слишком сложно, и отправляется ловить мышей.

Но благо, что у нас, людишек, есть возможность создания инструмента, который может разложить сложные языковые конструкции на простые и понятные части. Как раз об этом и пойдет речь в нашей сегодняшней статье — о создании парсеров на Rust.

А именно — о двух библиотеках, которые позволяют это сделать. Начнем с первой под названием nom.

Библиотека Nom

В nom парсеры строятся из небольших функций, которые можно комбинировать для создания более сложных парсеров.

nom предоставляет большой набор комбинаторов и функций для построения парсеров. Рассмотрим некоторые из них:

1. tag и tag_no_case — функции для сопоставления точного значения строки:

   use nom::bytes::complete::tag;  fn parse_hello(input: &str) -> IResult<&str, &str> {     tag("hello, habr")(input) }

2. alt — комбинатор для выбора одного из нескольких альтернативных парсеров:

   use nom::branch::alt;  fn parse_bool(input: &str) -> IResult<&str, bool> {     alt((value(true, tag("true")), value(false, tag("false"))))(input) }

3. many0 и many1 — функции для многократного применения парсера:

   use nom::multi::many1; use nom::character::complete::digit1;  fn parse_digits(input: &str) -> IResult<&str, Vec<&str>> {     many1(digit1)(input) }

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

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

1. fetch_habr — функция для получения HTML-страницы с Хабра.

2. parse_title — функция для парсинга одного заголовка статьи.

3. parse_titles — функция для извлечения всех заголовков статей с HTML-страницы.

Подробнее с библиотекой можно ознакомиться здесь. А пока мып переходим к следующей библиотеке — Chumsky.

Библиотека Chumsky

Chumsky — еще одна годная библиотеека для создания парсеров на основе комбинаторов в языке Rust. Она предоставляет высокоуровневый API для написания парсеров, которые легко комбинировать и расширять.

Chumsky поддерживает парсинг выражений, что делает её способной обрабатывать все известные контекстно-свободные языки.

Основные комбинаторы для построения парсеров:

1. just — создает парсер для точного совпадения символа:

   use chumsky::prelude::*;  let parser = just('a');

2. choice — позволяет выбрать один из нескольких альтернативных парсеров:

   let parser = choice((     just('a').to(1),     just('b').to(2), ));

3. repeated — многократно применяет парсер:

   let parser = just('a').repeated();

4. map — преобразует результат парсера:

   let parser = just('a').map(|_| 42);

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

1. fetch_habr — функция для получения HTML-страницы с Хабра.

2. parser — функция для создания парсера, который извлекает заголовки статей.

3. title_start и title_end — парсеры для начала и конца заголовка.

4. title_parser — парсер для одного заголовка статьи.

5. repeated — комбинатор для многократного применения title_parser.

Подробнее с библиотекой можно ознакомиться здесь.

А с другими языками программирования инструментами можно ознакомиться в рамках практических онлайн-курсов от моих друзей из OTUS. Подробнее в каталоге.