[Из песочницы] Изучение комбинаторных парсеров с Rust27.09.2019 18:19

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

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

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

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

Для этого мы передаём ему функцию, которая знает, как преобразовать исходный тип в новый. В нашем примере это просто: |(_left, right)| right. Более обобщённо, это выглядело бы как Fn(A) -> B где A — исходный тип результата парсера, а B — новый.

fn map(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(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 или подобное. Мы добавили туда время жизни, потому что объявление типа требует этого, но большую часть времени компилятор 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
,
{
    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 {

А теперь тест. () отсутствует в результате. Чего мы и добивались.

#[test]
fn right_combinator() {
    let tag_opener = right(match_literal("<"), identifier);
    assert_eq!(
        Ok(("/>", "my-first-element".to_string())),
        tag_opener.parse("")
    );
    assert_eq!(Err("oops"), tag_opener.parse("oops"));
    assert_eq!(Err("!oops"), tag_opener.parse("

fn one_or_more<'a, P, A>(parser: P) -> impl Parser<'a, Vec>
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))
    }
}

fn zero_or_more<'a, P, A>(parser: P) -> impl Parser<'a, Vec>
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(""));
}

fn one_or_more<'a, P, A>(parser: P) -> impl Parser<'a, Vec>
where
    P: Parser<'a, A>,
{
    map(pair(parser, zero_or_more(parser)), |(head, mut tail)| {
        tail.insert(0, head);
        tail
    })
}