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

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

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

Монолог новичка

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

Начинающий программист может спросить: «Что такое синтаксический анализатор?»

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

Старшие программисты скажут: «Уйди с дороги, я знаю».lexиyacc.

Менталитет Сяобая правильный.

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

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

Как хорошо изучить эту статью

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

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

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

XML-текст

Мы будем упрощенной версией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>,
}

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

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

Определить парсер

Итак, пора приступить к написанию парсера.

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

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

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

мы помечаем его как тип функции

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

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

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

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

Итак, давайте посмотрим на код самого парсера. Сначала получите первый символ ввода:input.chars().next(). Мы не пытаемся полагаться на стандартную библиотеку, чтобы избежатьUnicodeПроблема - мы называем это предоставленным для символов строкиchars()迭代器，然后从其中取出第一个单元。 этоcharэлемент типа и поOptionупакованный, т.е.Option<char>,еслиNoneТипOptionЭто означает, что мы получаем пустую строку.

Что еще хуже, аcharТип не может даже не представитьUnicodeПерсонажи в. Это, вероятно,Unicodeсередина "Алфавитная коллекция, который может состоять из несколькихcharтип символов, которые на самом деле означают "скалярное значение«Что примерно на 2 уровня ниже« набор букв ». Тем не менее, это немного радикально думать таким образом, и для наших целей мы вряд ли увидели персонажей за пределами набора символов ASCII, так что игнорируйте это на данный момент.

МыSome('a')Выполните сопоставление с образцом, это конкретный результат, который мы ищем, и если совпадение будет успешным, мы вернем успехOk((&input['a'.len_utf8]()..], ())). То есть мы удаляем проанализированный элемент ('a') из фрагмента строки и возвращаем оставшиеся символы вместе с проанализированным значением, которое()тип.考虑到 Unicode 字符集问题，在对字符串 range 处理前，我们用标准库中的方法查询一下字符'a'Длина в UTF-8. Длина равна 1, поэтому у вас не возникнет проблем с символами Unicode, о которых мы думали ранее.

Если мы получим другие типы результатовSome(char),илиNoneМы вернем исключение. Как упоминалось ранее, тип исключения у нас только что имел ломтик строки при удалении анализа, который является входом, который мы прошли. Нет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. Это будет значение нашего результата. Мы также получаем итератор через входную строку, которая разделяет символы один за другим через итератор.

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

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

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

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

Помните, что мы собираемся анализировать XML-документ какElementСтруктурировать?

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. Это анализатор 1, анализатор 2, результат 1, результат 2.P1иP2являются функциями, вы заметите, что они следуют установленному шаблону функций парсера: как и возвращаемые значения, они начинаются с&strв качестве входных данных и вернуть оставшиеся входные данные и результат синтаксического анализа или вернуть исключение.

Но посмотрите на тип результата каждой функции:P1это анализатор, который, если успешно, будет генерироватьR1,P2также будет генерироватьR2.最终的解析器的结果是 —— 即函数的返回值 —— 是(R1, R2).因此，这个解析器的逻辑是首先在输入上运行解析器P1Сохранил свои результаты, тоP1Возвращен в качестве ввода для запускаP2Если эти два метода работают правильно, мы объединяем эти два результата в кортеж.(R1, R2).

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

В этом случае мы можем объединить два предыдущих парсера,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.大部分情况 —— 我们的一些解析器只匹配输入中的模式，而不产生值，因此可以放心地忽略这种输出。为了适应这种场景，我们要用我们的pairCombiner для написания еще двух объединителей:left, который отбрасывает результат первого синтаксического анализатора и возвращает второй синтаксический анализатор и соответствующее число,right, что мы и хотим использовать в нашем тесте выше вместоpair- отбрасывает левый(), оставив только нашString.

лицензия

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

сноска

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

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

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

Категории