Комбинаторы парсеров: от parsimmon до nom (Typescript → Rust)

В этой статье мы вкратце рассмотрим процесс повторной реализации фиктивного синтаксического анализатора языка запросов, написанного на Typescript. Новая реализация будет на Rust.

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

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

Итак, начнем!

Фиктивный язык запросов

Допустимый синтаксис запросов выглядит таким образом:

1. foo == "hey there" && foo == "eatPizza"

2. foo == "hey there"

Парсер на Typescript

Для фиктивного парсера языка запросов был использован Parsimmon. Загляните в его репозиторий на Github, в его основе интересные функциональные концепции.

Parsimmon  —  это маленькая библиотека для написания больших парсеров, состоящих из множества более мелких парсеров.

Пользовательский API простой. Есть функция parseDummyQL(), которая в качестве входных данных получает строки запроса и в случае допустимого запроса выводит что-то вроде сглаженного дерева, представляющего собой структуру правил языка запросов (своего рода АСД).

let textWithSpaces = `foo == "hey there" && foo == "eatPizza"`;
let output = parseDummyQL(textWithSpaces);
console.log(output);

// [
//   [ 'foo', '==', 'hey there 🍕' ],
//   [ '&&', [ 'foo', '==', 'eatPizza 🍕' ] ]
// ]

То, что здесь выводится, подробнее рассмотрим после того, как разберем реализацию парсера.

Реализация языка запросов

import Parsimmon from 'parsimmon';
const P = Parsimmon;

let MyFooQueryLang = P.createLanguage({
  // `r` eq rules.
  dummy_query: (r) => r.expression.many(),

  expression: (r) => P.alt(r.base, r.sub),

  base: (r) => P.seq(r.field, r.operator, r.value),
  sub: (r) => P.seq(P.alt(r.and, r.or), r.base),

  field: () => P.string('foo').skip(P.optWhitespace).desc('field'),

  operator: () => P.string('==').skip(P.optWhitespace).desc('operator'),

  and: () => P.string('&&').skip(P.optWhitespace).desc('and'),
  or: () => P.string('||').skip(P.optWhitespace).desc('or'),

  value: () =>
    P.string('"')
      .then(P.regex(/[^"]+/))
      .map((lifted) => `${lifted} 🍕`) // fp улет 🤟
      .skip(P.string('"'))
      .skip(P.optWhitespace)
      .desc('value'),
});

export function parseDummyQL<T>(query: string): T {
  return MyFooQueryLang.dummy_query.tryParse(query);
}

Самое интересное здесь  —  это функции небольших парсеров, объединившихся при создании главного парсера.

Не будем вдаваться в слишком подробные объяснения API библиотеки Parsimmon. Нас должна занимать только следующая последовательность в коде.

1. Комбинатор dummy_query() вызывает комбинатор expression() с задействованием many. Это обычный способ указания API парсеров на то, что правило повторяется n раз.
2. Комбинатор expression() приводит к появлению комбинатора alt(), который принимает n парсеров и проверяет, соответствует ли строка во входных данных правилам одного из принимаемых входных парсеров. В других библиотеках это будет комбинатор choice. В нашем случае choices/alternatives будут комбинаторами base() или sub().
3. И base(), и sub() приводят к появлению комбинатора seq() (sequence, т. е. «последовательность»). По правилу base(), порядок получаемых им парсеров такой: сначала field, потом operator, затем value.
4. А последовательность комбинатора sub() выглядит следующим образом: alt (and, or), затем base, т. е. правило парсинга sub начинается либо с and, либо с or, а дальше следует запрос base.
5. Остальные комбинаторы  —  это простые блоки, которые обходятся без других комбинаторов. Например, здесь это operator (который принимает оператор равенства ==) и field (который принимает строку foo) или value (который принимает любую строку внутри двойных кавычек) и т. д.

Теперь проделаем это с Nom

nom  —  это библиотека комбинаторов парсеров, написанная на Rust. Ее цель  —  предоставление инструментов для создания безопасных парсеров без уменьшения скорости или увеличения потребления памяти.

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

Реализация языка запросов

type BaseOutput<'a> = (&'a str, &'a str, &'a str, &'a str, String);

fn parse_quoted(input: &str) -> IResult<&str, String> {
    let seq = recognize(separated_list0(tag("\"\""), many0(none_of("\""))));
    let unquote = escaped_transform(none_of("\""), '\"', tag("\""));
    let res = delimited(tag("\""), map_parser(seq, unquote), tag("\""))(input)?;

    Ok(res)
}

fn and_parser(i: &str) -> IResult<&str, &str> {
    tag("&&")(i)
}
fn or_parser(i: &str) -> IResult<&str, &str> {
    tag("||")(i)
}
fn and_or_choice(i: &str) -> IResult<&str, &str> {
    alt((and_parser, or_parser))(i)
}

fn base_parser(i: &str) -> IResult<&str, BaseOutput, Error<&str>> {
    let f =  tag("foo");
    let eq_op  =  tag("==");
    let value = parse_quoted;
    tuple((f, tag(" "), eq_op, tag(" "), value))(i)
}

fn sub_parser(i: &str) -> IResult<&str, (&str, BaseOutput), Error<&str>> {
    tuple((tag(" "), base_parser))(i)
}

// Главный парсер / точка входа
pub fn dummy_parser(i: &str) -> IResult<&str, (BaseOutput, &str, &str, (&str, BaseOutput)), Error<&str>> {
    tuple((base_parser, tag(" "), and_or_choice, sub_parser))(i)
}

** Обратите внимание:

• Обработка ошибок  —  это то, что мне нравится в Rust, но здесь я проигнорировал потенциальные ошибки, чтобы сосредоточиться на изучении API.
• Функцию parse_quoted я фактически изменил по сравнению с тем, что было в следующем ответе на StackOverflow.
• Я упростил конечный вывод, в отличие от оригинальной реализации, в которой вывод подвергнут преобразованиям.

Информация, касающаяся типов

Парсеры nom  —  это функции, в которых везде используется тип nom::IResult. Тип IResult зависит от типов ввода и вывода и дополнительного типа пользовательской ошибки.

Проверенный запрос выглядит следующим образом:

foo == "jj" && foo == "bazz"

• Field → space → eqOperator → space → value → space → andOrLogicalOperator → space → Field → space → eqOperator → space → value

Общий обзор кода сверху вниз:

1. Точкой входа здесь является dummy_parser() (единственная общедоступная функция в библиотеке). Она принимает в качестве аргумента запрос и возвращает IResult (конечный вывод), а также результат последовательности комбинатора tuple:

tuple((base_parser, tag(" "), and_or_choice, sub_parser))(i)

Tuple объединяет парсеры в цепочку и собирает промежуточные результаты в кортеж. Используется столько дочерних парсеров, сколько элементов помещается в кортеже.

«Базовый элемент» tag распознает определенный набор символов или байтов.

Так что последовательность предельно проста: сначала парсинг входных данных будет выполнен с помощью base_parser, затем пробел, а после and_or_choice, за которым следует sub_parser.

2. And_or_choice возвращает результат комбинатора alt():

alt((and_parser, or_parser))(i)

Комбинатор choice alt попробует список парсеров и вернет результат первого успешного.

3. Sub_parser сочетает пробел с base_parser:

tuple((tag(" "), base_parser))(i)

4. Base_parser выполняет парсинг самого простого запроса:

tuple((f, tag(" "), eq_op, tag(" "), value))(i)

Вывод:

let exp_tuple = (
    (
        "foo",
        " ",
        "==",
        " ",
        "jj",
    ),
    " ",
    "&&",
    (
        " ",
        (
            "foo",
            " ",
            "==",
            " ",
            "bazz",
        ),
    ),
);

Вот и все. Надеюсь, что вам понравилось! Загляните в репозиторий: код со временем наверняка будет улучшаться.

Спасибо за внимание!

Читайте также:

• Понятие об умных указателях Rust
• Асинхронный Rust: проблемы и способы их решения
• Введение в программирование на Rust

Читайте нас в Telegram, VK и Яндекс.Дзен

---

Перевод статьи Liron Hazan: From parsimmon to nom — playing with parser combinators (Typescript → Rust)