Создание парсеров на Rust
Привет, Хабр!
Представьте себе котика, который пытается понять синтаксис человеческого языка. Сначала он разглядывает слова, затем прислушивается к интонациям, а потом решает, что всё это слишком сложно, и отправляется ловить мышей.
Но благо, что у нас, людишек, есть возможность создания инструмента, который может разложить сложные языковые конструкции на простые и понятные части. Как раз об этом и пойдет речь в нашей сегодняшней статье — о создании парсеров на 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::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) -> Option {
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 {
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(""), take_until(""))(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, Box),
Sub(Box, Box),
Mul(Box, Box),
Div(Box, Box),
}
fn expr_parser() -> impl Parser> {
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),
Object(Vec<(String, Json)>),
}
fn json_parser() -> impl Parser> {
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::(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 {
let response = reqwest::get("https://habr.com").await?;
let body = response.text().await?;
Ok(body)
}
fn parser() -> impl Parser, Error = Simple> {
let title_start = 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::()).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. Подробнее в каталоге.
