[Перевод] Изучаем объединители парсеров с помощью Rust — часть 2

задняя часть Программа перевода самородков Rust

Изучаем объединители синтаксических анализаторов с помощью Rust — часть 2

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

Начните изучать Functor

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

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

за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Часть очень похожа. Сначала разбираем первый элемент, если его нет, возвращаем ошибку. Затем мы анализируем как можно больше элементов, пока анализатор не столкнется с ошибкой, после чего мы возвращаем массив всех элементов, собранных путем итерации.

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

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, пустая строка представляет только случай 0, что не является ошибкой.

На этом этапе разумно и необходимо подумать о том, как обобщить эти два случая, поскольку один является копией другого, с чем-то просто урезанным. Как показано ниже, это может быть легко использоватьzero_or_moreПредставлятьone_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, я не имею в видуVecТип №consметода, но я знаю, что каждый программист на Лиспе думает об этом, когда читает этот код. На самом деле все гораздо серьезнее: это вопрос собственности.

У нас есть этот синтаксический анализатор, но мы не можем передать аргумент дважды, и компилятор скажет вам, что это не работает: вы пытаетесь удалить значение, которое уже было удалено. Итак, можем ли мы заставить наш комбинатор ссылаться на параметр? Нет, оказывается, из-за строгого механизма проверки заимствования — и нам не нужно сталкиваться с этим прямо сейчас. Поскольку эти синтаксические анализаторы являются просто функциями, они не реализуются напрямую.Clone, было бы проще использовать клон, теперь мы застряли, потому что не можем так легко повторно использовать парсер в комбинаторе.

Но это ничегоБольшойНет. Хотя это означает, что мы не можем использовать комбинаторы для достиженияone_or_more, но на самом деле эти две вещи обычно являются комбинаторами, которые вам нужно использовать, этот комбинатор также должен повторно использовать синтаксический анализатор, и, если вы хотите проявить больше воображения, вы можете использоватьRangeBoundНапишите комбинатор, подключите дополнительный синтаксический анализатор и повторно используйте его в зависимости от области видимости, напримерzero_or_moreиспользоватьrange(0..),правильноone_or_moreиспользоватьrange(1..), на пять или шесть использованийrange(5..=6), во всяком случае, по желанию.

Оставим это в качестве упражнения для читателя. Теперь мы просто должны иметь дело сzero_or_moreиone_or_more.

Еще одно упражнение состоит в том, чтобы попытаться найти решение этих проблем собственности.RcОберните парсер, чтобы его можно было клонировать, что вы думаете об этом подходе?

лицензия

Эта работа защищена авторским правом Bodil Stokke, лицензирована в соответствии с условиями лицензии Creative Commons Attribution-NonCommercial-ShareAlike 4.0. Чтобы просмотреть эту лицензию, пожалуйста, посетитеCreative Commons.org/licenses/не…

сноска

1: Он не твой настоящий дядя. 2: Пожалуйста, не будь таким человеком на вечеринке.

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

Программа перевода самородковэто сообщество, которое переводит высококачественные технические статьи из Интернета сНаггетсДелитесь статьями на английском языке на . Охват контентаAndroid,iOS,внешний интерфейс,задняя часть,блокчейн,продукт,дизайн,искусственный интеллектЕсли вы хотите видеть более качественные переводы, пожалуйста, продолжайте обращать вниманиеПрограмма перевода самородков,официальный Вейбо,Знай колонку.

Категории