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

Программа перевода самородков Rust

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

возможность проявить себя

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

Помните последний парсер, который мы написали? Поскольку наши комбинаторы являются независимыми функциями, когда мы вкладываем некоторые «комбинаторы», наш код становится немного трудным для понимания. Вспомните наши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))
}

давайте использоватьpredвызов переписатьquoted_stringСтрока в следующем виде:

zero_or_more(any_char.pred(|c| *c != '"')),

Так читать немного лучше, и я думаю, что это следует сохранитьzero_or_more- читается как "Ноль или большеany_charи применил приведенное ниже решение», что звучит для меня правильно. Вы также можете продолжать помещатьzero_or_moreиone_or_moreПерейдите к чертам.

Помимо переписыванияquoted_stringВ дополнение к ремонтуsingle_elementсерединаmap:

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——иУ нас есть лучшие правила сленга!

С дочерними элементами

Теперь давайте напишем парсер для начального тега родительского элемента. за исключением>вместо/>Кроме концовки, другие почти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рабочая проблема, мы можем реализовать новыйparent_elementзаменятьelementв парсереopen_elementplaceholder, и вот так мы реализовали полнофункциональный анализатор XML.

Помните, когда я сказал, что мы вернемся позжеand_then? вернулся сейчас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тип парсера, в случае успеха начинаем с парсераPРезультат вызова функции в качестве аргументаfчтобы получить наш следующий тип как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, поэтому не разрешается использоватьparser2Parser, мы можем только ссылаться на него. Другими словами, это проблема 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Конструкция внутри закрытия. Кроме того, поскольку закрытие сейчасopen_elementизElementЕдинственный получатель результата, анализатор, который мы возвращаем, также должен передавать эту информацию дальше.

Мы на сгенерированном парсереmapВнутреннее закрытие можно сослаться на внешнее закрытиеElement(el). Так как мыFnНа него можно ссылаться только один раз вclone()Это. Мы берем результат внутреннего синтаксического анализатора (дочерний элементVec<Element>) и добавляем его в наш клонElementи вернуть его как окончательный результат.

Все, что нам нужно сделать сейчас, это вернуться кelementпарсер и убедитесь, чтоopen_elementизменить наparent_element, так что он анализирует всю структуру элемента, а не только ее начало, я думаю, мы закончили с комбинатором парсера!

Вы спрашиваете, нужно ли заканчивать слово, начинающееся на М?

Помните, как мы говорили о том, какmapНа планете Haskell паттерны называются «функторами»?

and_thenШаблоны — это еще одна вещь, которую вы время от времени будете видеть в Rust, и они часто связаны сmapпоявляются в одном и том же месте. это в迭代器（Iterator）известный какflat_map, но это тот же шаблон, что и Rest.

Это причудливое слово — «монада». если у тебя есть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>функция результата, а боб твой дядя[1], ты получишьFuture<B>. Другими словами, вFutureслучае, вы можете перейти кand_thenфункционировать какПерезвони, потому что он будет вызван с первоначальным будущим результатом, когда он завершится. Это также более интересно, потому что возвращаетновый Future, он может быть или не быть проанализирован, так что этосоединятьМетод будущего состояния.

Однако, как и функторы, система типов Rust еще не может выражать монады, поэтому нам просто нужно помнить, что этот шаблон называется монадами, и довольно разочаровывает то, что вопреки тому, что было описано в Интернете, это то же самое, что и буррито. не важно. Давайте двигаться дальше.

космос, финал

Последняя вещь.

Теперь у нас должен быть синтаксический анализатор, способный анализировать некоторый 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));
}

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

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

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

щенок победы

больше ресурсов

Во-первых, я очень строго объясняю вам монады в строгих терминах Rusty, я знаю, если я не указал вам наего основополагающая статья, то Фил Уодлер будет очень расстроен мной, потому что статья более захватывающая — в ней рассказывается, как они связывают комбинаторы парсеров.

Идея этой статьи иpomИдея комбинаторов парсеров очень похожа, и я очень рекомендую ее, если вы хотите использовать комбинаторы парсеров в том же стиле.

Современное состояние среди комбинаторов парсеров Rust по-прежнемуnom, в той мере, в какой упоминалось ранееpomПо-видимому, это производное название (нет лучшего комплимента). Но для этого потребовался совершенно иной подход, чем тот дизайн, который мы имеем здесь сегодня.

Еще одна популярная библиотека комбинаторов парсеров для Rust —combine, тоже стоит посмотреть.

Основополагающая библиотека комбинаторов синтаксических анализаторов HaskellParsec.

Наконец, моя книга о Грэме ХаттонеПрограммирование на ХаскелеЯ впервые узнал о комбинаторах синтаксических анализаторов в , эту книгу стоит прочитать, и она может рассказать вам о Haskell.

протокол

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

сноска

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

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

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

Категории