Привет, Хабр! Представляю вашему вниманию перевод статьи "Learning Parser Combinators With Rust".

Эта статья учит основам комбинаторных парсеров людей, которые уже знакомы с Rust. Предполагается, что никаких других знаний не требуется, а всё, что не имеет прямого отношения к Rust, а также некоторые неожиданные аспекты его использования, будут объяснены. Эта статья не поможет вам выучить Rust, если вы его ещё не знаете, и в этом случае, вы, вероятнее всего, не поймёте комбинаторные парсеры хорошо. Если вы хотите изучить Rust, я рекомендую книгу "Язык программирования Rust".

С точки зрения новичка

В жизни каждого программиста наступает момент, когда он нуждается в парсере.

Начинающий программист спросит: "Что такое парсер?"

Программист среднего уровня скажет: «Это просто, я напишу регулярное выражение».

Мастер-программист скажет: «Отойди, я знаю lex и yacc».

Новичок мыслит правильнее всех.

Не то, чтобы регулярные выражения плохи. (Но, пожалуйста, не пытайтесь писать сложный парсер как регулярное выражение.) Не то, чтобы не было никакой радости в использовании мощных инструментов, таких как генераторы парсеров и лексеров, которые были отточенные до совершенства на протяжении тысячелетий. Но изучение основ парсеров — это удовольствие. Это также то, что вы будете упускать, если у вас паника при использовании регулярных выражений или генераторов синтаксических анализаторов, оба из которых являются только абстракциями над реальной проблемой. В сознании новичка, как сказал человек, много возможностей. По мнению эксперта, есть только один правильный вариант.

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

Как работать с этой статьёй

Настоятельно рекомендуется начать с нового проекта Rust и писать фрагменты кода в src/lib.rs по мере чтения (вы можете вставить его непосредственно со страницы, но вводить его лучше, так как это автоматически гарантирует вам что вы его прочитайте полностью). Все части кода, которые Вам понадобятся, расположены в статье по порядку. Имейте в виду, что иногда вводятся изменённые версии функций, которые вы написали ранее, и в этих случаях вы должны заменить старую версию на новую.

Код был написан для rustc версии 1.34.0 с использованием 2018 редакции языка. Вы можете использовать любую версию компилятора, убедитесь, что вы используете выпуск с поддержкой 2018 редакции (проверьте, что ваш Cargo.toml содержит edition = "2018"). Для данного проекта не нужны внешние зависимости.

Для выполнения тестов, представленных в статье, как и следовало ожидать, используется cargo test.

Xcruciating язык разметки

Мы собираемся написать парсер для упрощённой версии XML. Это выглядит так:

<parent-element>
  <single-element attribute="value" />
</parent-element>

XML-элементы открываются символом < и идентификатором, состоящим из буквы, за которой следует любое количество букв, цифр и -. За этим следуют пробелы и необязательный список пар атрибутов: другой идентификатор как определено ранее, за которым следуют = и строка в двойных кавычках. Наконец, есть либо закрывающий символ /> для обозначения одного элемента без детей, либо > для обозначения существования следующей последовательности дочерних элементов, и закрывающий тег, начинающийся с </, за которым следует идентификатор, который должен соответствовать открывающему тегу, и закрывающий символ >.

Это все, что мы будем поддерживать. Не будет ни пространств имён, ни текстовых узлов и совершенно точно не будет проверки схемы. Мы даже не будем беспокоиться о поддержке экранирования кавычек для строк — они начинаются с первой двойной кавычки, и они заканчиваются на следующей, и все.

Мы собираемся разобрать эти элементы в структуру, которая выглядит следующим образом:

#[derive(Clone, Debug, PartialEq, Eq)]
struct Element {
    name: String,
    attributes: Vec<(String, String)>,
    children: Vec<Element>,
}

Никаких причудливых типов, только строка для имени (это идентификатор в начале каждого тега), атрибуты в виде пар строк (идентификатор и значение) и список дочерних элементов, которые выглядят точно так же, как родительский.

(Если вы печатаете, убедитесь, что вы включили секцию derive. Она понадобятся вам позже.)

Определение парсера

Ну что ж, пришло время написать парсер.

Разбор — это процесс получения структурированных данных из потока информации. Парсер — это то, что выявляет эту структуру.

В дисциплине, которую мы собираемся исследовать, синтаксический анализатор, в его самой простой форме, является функцией, которая принимает некоторый ввод и возвращает либо проанализированный вывод вместе с оставшейся частью ввода, либо ошибку, говорящую "Я не смог разобрать это".

Так же выглядит синтаксический анализатор в его более сложных формах. Вы можете усложнить, что означают ввод, вывод и ошибка, и если вам нужны хорошие сообщения об ошибках, которые вам понадобятся, но синтаксический анализатор останется прежним: что-то, что потребляет ввод и выдаёт какой-то проанализированный вывод вместе с тем, что осталось от ввода или позволяет вам знать, что он не может проанализировать ввод в вывод.

Давайте запишем это как тип функции.

Fn(Input) -> Result<(Input, Output), Error>

Более конкретно: в нашем случае мы хотим заполнить типы и получить функцию, похожую на эту. Всё, что мы собираемся сделать, это преобразовать строку в структуру Element. В данный момент мы не хотим вдаваться в тонкости сообщений об ошибках, поэтому просто вернём часть строки, которую не смогли разобрать. В результате наша функция будет выглядеть следующим образом:

Fn(&str) -> Result<(&str, Element), &str>

Мы используем строковый срез, потому что это эффективный указатель на фрагмент строки, и далее мы можем разделять его, как нам угодно, «потребляя» входные данные, вырезая проанализированный фрагмент и возвращая остаток вместе с результатом.

Возможно, было бы чище использовать &[u8] (срез байт, соответствующий символам ASCII) в качестве типа ввода, особенно потому что строковые срезы ведут себя немного иначе, чем большинство срезов — особенно в том, что вы не можете индексировать их с помощью одного числа input[0], вы должны использовать фрагмент input[0..1]. С другой стороны, у них есть много методов, которые полезны для разбора строк, которые не имеют срезы байтов.

На самом деле, мы будем полагаться на методы, а не на использование индексов символов, потому что Unicode. В UTF-8, а все строки Rust являются корректными UTF-8 строками, эти индексы не всегда соответствуют отдельным символам, и всем заинтересованным сторонам лучше, чтобы мы попросили стандартную библиотеку просто поработать с этим для нас.

Наш первый парсер

Давайте попробуем написать парсер, который просто смотрит на первый символ в строке
и решает, является ли он буквой a.

fn the_letter_a(input: &str) -> Result<(&str, ()), &str> {
  match input.chars().next() {
      Some('a') => Ok((&input['a'.len_utf8()..], ())),
      _ => Err(input),
  }
}

Во-первых, давайте посмотрим на типы ввода и вывода: мы берём строковый срез как ввод и мы возвращаем Result с (&str, ()), либо ошибку с &str. Пара (&str, ()) — это интересный момент: как мы говорили о том, что мы должны вернуть кортеж следующего содержания,
результат разбора и оставшуюся часть ввода. &str — это следующий вход, и результат — это просто тип блока (), потому что если этот синтаксический анализатор успешно работает, он может иметь только один результат (мы нашли букву a), и нам не особенно нужно возвращать
буква a в этом случае нам просто нужно указать, что нам удалось её найти.

Итак, давайте посмотрим на код самого парсера. Мы не шутили о том, что опираясь на стандартную библиотеку мы сможем избежать появления головной боли с Unicode: мы получаем итератор по символам строки при помощи метода chars() и берём из него первый символ. Это будет элемент типа char, завёрнутый в Option, в котором None будет означать, что мы пытались вытащить char из пустой строки.

Что ещё хуже, char не обязательно даже то, что вы думаете о нем как о символе Unicode. Это, скорее всего, будет то, что Unicode называет "grapheme cluster", который может состоять из нескольких char, которые на самом деле представляют собой "scalar values", который на два уровня ниже кластеров графем. Однако, этот путь ведёт к безумию, и для наших целей мы честно даже вряд ли увидим chars вне ASCII, так что давай остановимся на этом.

Мы сопоставляем с шаблоном Some('a'), что является конкретным результатом, который мы ищем, и если это соответствует, мы возвращаем наше значение успеха:
Ok((&input['a'.len_utf8()..], ())). То есть мы удаляем часть, которую мы только что проанализировали ('a') из среза строки и вернём остальное вместе с нашим анализируемым значением, которое является просто пустым
(). Всегда помня о монстре Unicode, мы перед нарезкой узнаём длину в UTF-8 символа 'a' через стандартную библиотеку — она равна 1 (но никогда не забывайте про монстра Unicode).

Если мы получим любой другой Some(char), или если мы получим None, то возвращаем ошибку. Как вы помните наш тип ошибки просто строковый срез, который мы передали в качестве input и который не удалось разобрать. Он не начинался с a, так что это наша ошибка. Это не большая ошибка, но, по крайней мере, это немного лучше, чем просто "что-то где-то не так".

На самом деле нам не нужен этот парсер для разбора XML, но первое, что мы должны будем сделать, это найти открывающий символ <, так что нам понадобится что-то очень похожее. Нам также нужно будет проанализировать >,/ и = конкретно, так, может быть, мы можем сделать функцию, которая строит парсер для символа, который мы хотим?

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

Давайте даже подумаем об этом: напишем функцию, которая создаёт парсер для статической строки любой длины, а не только одного символа. Это даже проще, потому что фрагмент строки уже является допустимым срезом строки UTF-8, и нам не нужно думать о монстре 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),
    }
}

Теперь это выглядит немного иначе.

Прежде всего, давайте посмотрим на типы. Теперь наша функция принимает expected строку в качестве аргумента и возвращает что-то похожее на парсер, вместо того, чтобы самой быть парсером. Это функция, которая возвращает функцию более высокого порядка. По сути, мы пишем функцию, которая делает функцию, подобную нашей функции the_letter_a ранее.

Таким образом, вместо выполнения работы в теле функции, мы возвращаем замыкание, которое выполняет эту работу и которое соответствует сигнатуре нашего типа для анализатора из предыдущего.

Сопоставление с шаблоном выглядит одинаково, за исключением того, что мы не можем сопоставить наш строковый литерал напрямую, потому что мы не знаем, что именно, поэтому мы используем условие сопоставления if next == expected. В остальном он точно такой же, как и раньше, просто внутри тела замыкания.

Тестирование нашего парсера

Давайте напишем тест для этого, чтобы убедиться, что мы правильно поняли.

#[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!")
    );
}

Сначала мы создаём парсер: match_literal("Hello Joe!"). Он должен потреблять строку "Hello Joe!" и вернуть остаток строки, или завершиться с ошибкой и вернуть всю строку.

В первом случае мы просто передаём ему именно ту строку, которую ожидаем, и видим, что она возвращает пустую строку и значение (), которое означает «мы проанализировали ожидаемую строку, и вам не нужно, чтобы она возвращалась".

Во втором, мы подаём строку "Hello Joe! Hello Robert!" и видим, что он действительно использует строку "Hello Joe!" и возвращает остаток от ввода: " Hello Robert!" (ведущий пробел и всё остальное).

В третьем, мы вводим неверный ввод: "Hello Mike!" и обратите внимание, что он действительно отклоняет ввод с ошибкой. Не то, чтобы Mike не правильно, как правило просто не то, что искал парсер.

Парсер для чего-то менее специфичного

Так что это позволяет нам анализировать <, >, = и даже </ и />. Мы уже практически закончили!

Следующий после открывающего символа < — это имя элемента. Мы не можем сделать это с помощью простого сравнения строк. Но мы могли бы сделать это с помощью регулярного выражения...

… но давайте сдерживаться. Это будет регулярное выражение, которое будет очень легко реплицировать в простом коде, и для этого нам не нужно использовать пакет regex. Давайте посмотрим, сможем ли мы написать собственный парсер для этого, используя только стандартную библиотеку Rust.

Вспомним правило для идентификатора имени элемента, оно выглядит следующим образом: один алфавитный символ, за которым следует ноль или более из любого алфавитного символа,
символ, число или тире -.

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

Как всегда, мы сначала смотрим на тип. На этот раз мы не пишем функцию для создания парсера, мы просто пишем сам парсер, как в первый раз. Заметным отличием здесь является то, что вместо типа результата () мы возвращаем String в кортеже вместе с оставшимися входными данными. Эта String будет содержать идентификатор, который мы только что проанализировали.

Имея это в виду, сначала мы создаём пустую String и называем её matched. Это будет наш результат. Мы также получаем итератор для символов в input, который мы собираемся начать разделять.

Первый шаг — посмотреть, есть ли символ в начале. Мы вытаскиваем первый символ из итератора и проверяем, является ли он буквой: next.is_alphabetic(). Стандартная библиотека Rust, конечно поможет нам с Unicode — она будет соответствовать буквам в любом алфавите, а не только в ASCII. Если это буква, мы помещаем её в нашу строку в переменную matched, а если нет, мы не смотрим на идентификатор элемента и немедленно возвращаемся с ошибкой.

На втором шаге мы продолжаем вытаскивать символы из итератора, отправляя их в создаваемую нами строку до тех пор, пока не встретим символ не удовлетворяющий функцию is_alphanumeric() (она похожа на is_alphabetic() за исключением того, что она также включает числа в любом алфавите) или тире '-'.

Когда мы в первый раз видим что-то, что не соответствует этим критериям, мы заканчиваем синтаксический анализ, прерываем цикл и возвращаем String, не забывая вырезать из input фрагмент, который мы использовали. Аналогично, если в итераторе заканчиваются символы, это означает, что мы достигли конца ввода.

Стоит отметить, что мы не возвращаемся с ошибкой, когда видим что-то не буквенно-цифровое или тире. У нас уже есть достаточно, чтобы создать действительный идентификатор после того, как мы сопоставим эту первую букву, и вполне нормально, что после разбора нашего идентификатора во входной строке будет больше элементов для анализа, поэтому мы просто прекращаем синтаксический анализ и возвращаем наш результат. Только если мы не можем найти даже эту первую букву, мы на самом деле возвращаем ошибку, потому что в этом случае здесь точно не было идентификатора.

Помните, что структура Element — это то, во что мы собираемся разобрать наш XML документ.

struct Element {
    name: String,
    attributes: Vec<(String, String)>,
    children: Vec<Element>,
}

На самом деле мы только что закончили анализатор для первой части, поля name. String, который возвращает наш парсер, идёт прямо туда. Это также правильный парсер для первой части каждого attribute.

Давайте проверим это.

#[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")
    );
}

Мы видим, что в первом случае строка "i-am-an-identifier" анализируется полностью, оставляя только пустую строку. Во втором случае синтаксический анализатор возвращает "not" в качестве идентификатора, а остальная часть строки возвращается в качестве оставшегося ввода. В третьем случае синтаксический анализатор терпит неудачу сразу, потому что первый символ, который он находит, не буква.

Комбинаторы

Теперь мы можем проанализировать открывающий символ <, и мы можем проанализировать следующий идентификатор, но нам нужно проанализировать оба. Поэтому следующим шагом будет написание другой функции комбинаторного синтаксического анализатора, но такой, которая принимает два синтаксических анализатора в качестве входных данных и возвращает новый синтаксический анализатор, который анализирует их обоих по порядку. Другими словами, комбинатор парсеров, потому что он объединяет два парсера в новый. Посмотрим, сможем ли мы это сделать.

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

Здесь становится немного сложнее, но вы знаете, что делать: начните с рассмотрения типов.

Прежде всего, у нас есть четыре типа переменных: P1, P2, R1 и R2. Это Parser 1, Parser 2, Result 1 и Result 2. P1 и P2 являются функциями, и вы заметите, что они следуют хорошо установленному шаблону функций синтаксического анализатора: так же, как и возвращаемое значение, они принимают &str в качестве входных данных и возвращают Result пары оставшихся входных данных и результата, или ошибку.

Но посмотрите на типы результатов каждой функции: P1 — это синтаксический анализатор, который выдаёт R1 в случае успеха, и P2 также выдаёт R2. И результат последнего синтаксического анализатора, который был возвращён из нашей функции, равен (R1, R2). Таким образом, задача этого синтаксического анализатора состоит в том, чтобы сначала запустить анализатор P1 на входе, сохранить его результат, затем запустить P2 на входе, который вернул P1, и если оба из них сработали, мы объединяем два результата в кортеж (R1, R2).

По коду видно, что это именно то, что он делает. Мы начинаем с запуска первого анализатора на входе, затем второго анализатора, затем объединяем два результата в кортеж и возвращаем его. Если какой-либо из этих парсеров завершится ошибкой, мы немедленно вернёмся с ошибкой, которую он выдал.

Таким образом, мы должны иметь возможность объединить два наших анализатора, match_literal и identifier, чтобы фактически проанализировать первый фрагмент нашего первого тега XML. Давайте напишем тест, чтобы увидеть, работает ли он.

#[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"));
}

Кажется, работает! Но посмотрите на этот тип результата: ((), String). Очевидно, что нас интересует только правое значение, String. Это будет иметь место довольно часто — некоторые из наших синтаксических анализаторов сопоставляют только шаблоны во входных данных, не производя значений, и поэтому их выходные данные можно безопасно игнорировать. Чтобы приспособиться к этому шаблону, мы собираемся использовать наш комбинатор pair чтобы написать два других комбинатора: left, который отбрасывает результат первого синтаксического анализатора и возвращает только второй, и его противоположность right. Мы использовали в нашем тесте выше парсер, который отбрасывает левую часть и сохраняет только нашу String, вместо pair.

Ведение в Функтор

Но прежде чем мы зайдём так далеко, давайте представим ещё один комбинатор, который значительно упростит написание этих двух: map.

У этого комбинатора одна задача: изменить тип результата. Например, допустим, у вас есть парсер, который возвращает ((), 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>, и Боб — твой дядя ¹, ты возвращаешь 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));
}

Хорошей новостью является то, что он возвращает несоответствующий закрывающий тег как ошибку. Плохая новость заключается в том, что в действительности это не говорит о том, что проблема заключается в несовпадающем закрывающем теге, именно там, где ошибка. Это лучше, чем ничего, но, честно говоря, по мере появления сообщений об ошибках это все ещё ужасно. Но превращение этого в вещь, которая на самом деле даёт хорошие ошибки, является темой для другой, и, по крайней мере, такой же длинной статьи.

Давайте сосредоточимся на хороших новостях: мы написали парсер с нуля, используя комбинаторные парсеры! Мы знаем, что синтаксический анализатор образует и функтор, и монаду, так что теперь вы можете впечатлять людей на вечеринках своими устрашающими знаниями теории категорий ² .

Самое главное, теперь мы знаем, как комбинаторные синтаксические анализаторы работают с нуля. Никто не может остановить нас сейчас!

Дополнительные ресурсы

Прежде всего, я виновен в том, что объяснил вам монады в строго 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