Источник: Nuances of Programming
В этой статье мы вкратце рассмотрим процесс повторной реализации фиктивного синтаксического анализатора языка запросов, написанного на 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. Нас должна занимать только следующая последовательность в коде.
- Комбинатор dummy_query() вызывает комбинатор expression() с задействованием many. Это обычный способ указания API парсеров на то, что правило повторяется n раз.
- Комбинатор expression() приводит к появлению комбинатора alt(), который принимает n парсеров и проверяет, соответствует ли строка во входных данных правилам одного из принимаемых входных парсеров. В других библиотеках это будет комбинатор choice. В нашем случае choices/alternatives будут комбинаторами base() или sub().
- И base(), и sub() приводят к появлению комбинатора seq() (sequence, т. е. «последовательность»). По правилу base(), порядок получаемых им парсеров такой: сначала field, потом operator, затем value.
- А последовательность комбинатора sub() выглядит следующим образом: alt (and, or), затем base, т. е. правило парсинга sub начинается либо с and, либо с or, а дальше следует запрос base.
- Остальные комбинаторы — это простые блоки, которые обходятся без других комбинаторов. Например, здесь это 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",
),
),
);
Вот и все. Надеюсь, что вам понравилось! Загляните в репозиторий: код со временем наверняка будет улучшаться.
Спасибо за внимание!
Читайте также:
Перевод статьи Liron Hazan: From parsimmon to nom — playing with parser combinators (Typescript → Rust)