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

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

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

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

объединитель решений

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

Очевидно, что компилятор rustcList<A>выдает сообщение об ошибке, что он имеет бесконечный размер, потому что в каждомList::<A>::Consможет иметь другой внутриList<A>,это означает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.

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Включи логику. Как уже упоминалось, это означает перемещение синтаксического анализатора Box в кучу и необходимость удаления указателя на эту область кучи, что может быть дорогостоящим.наносекундывремя, поэтому мы могли бы сначала заключить его без Boxвсе данные. Достаточно просто обернуть некоторые из наиболее активных данных комбинатора в Box.

лицензия

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

сноска

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

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

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

Категории