25.06.2024 13:06
badcasedaily1 4 4300 Источник

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

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

Но благо, что у нас, людишек, есть возможность создания инструмента, который может разложить сложные языковые конструкции на простые и понятные части. Как раз об этом и пойдет речь в нашей сегодняшней статье — о создании парсеров на 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. Подробнее в каталоге.

Комментарии (4)


  1. datacompboy
    25.06.2024 13:31
    #26972050
    +2

    За что люблю рекурсивные парзеры, это за то, как их легко использовать для взырва, навроде

    fn main() {
    println!("{:?}", parse_expression("3++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++5"));
}


    1. domix32
      25.06.2024 13:31
      #26975374

      Чай не Regexp c lookahead чтобы взрываться.


      1. datacompboy
        25.06.2024 13:31
        #26975422

        Все рекурсивные взрываются, вопрос формулировки как попросить


        1. domix32
          25.06.2024 13:31
          #26975726

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