LL(*) парсер с использованием Rust макросов

Автор: cosmrc
Источник: https://habrahabr.ru/post/349054/

Wow. Such Rust. Much macro. © картинка - Твиттер аккаунт Servo

Язык Rust стремительно набирает обороты. Кто-то пророчит ему стать заменой C/C++, кому-то он просто нравится. Я скорее принадлежу ко второй группе. Разработчики стараются сделать его удобным и безопасным. В нем есть конструкции и принципы, которые еще не скоро появятся в "плюсах", ввиду инерции комитета и множества других причин. Поэтому, для всех личных проектов я предпочитаю использовать именно Rust.

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

Однажды, когда я в очередной раз застрял с синтаксическим анализатором (он же "парсер"), я подумал, что уж очень много я пишу однотипного кода. И этот однотипный код один в один ложится на грамматику в форме Бэкуса — Наура (БНФ).

Немного подумав, я решил, что мне надо написать генератор кода на основе грамматики. И для этой задачи как нельзя хорошо подходят макросы в Rust.

В статье описана реализация LL(*) парсера с использованием макросов. И реализован парсер простых математических выражений.

В итоге парсер для БНФ грамматики:

expr ::= sum
sum  ::= mul "+" sum | mul "-" sum | mul
mul  ::= atom "*" mul | atom "/" mul | atom
atom ::= "(" expr  ")" | number | neg;
neg  ::= "-" atom

Можно сгенерировать с помощью серии макросов:

rule!(expr, sum);
rule!(sum, or![
     and![(mul, token('+'), sum) => make_operator],
     and![(mul, token('-'), sum) => make_operator],
     mul
]);
rule!(mul, or![
     and![(atom, token('*'), mul) => make_operator],
     and![(atom, token('/'), mul) => make_operator],
     atom
]);
rule!(atom, or![
    and![(token('('), expr, token(')')) => |_lbrace, stat, _rbrace| Some(stat)],
    num,
    neg
]);
rule!(neg, and![(token('-'), atom) => |_, number| Some(Box::new(expression::Expression::Negate(number)))]);

Читать дальше →