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)))]);

В статье я буду намеренно упрощать реализации некоторых частей кода и использовать нестабильные особенности (unstable features) ночной сборки Rust. Это, я надеюсь, упростит понимание и улучшит читаемость.

Итак, как уже было сказано, мы будем генерировать LL(*) парсер, который может анализировать одноименное семейство грамматик. Если вам лень читать в чем особенность этого подмножества парсеров, то вкратце, их легче писать руками, но они не могут парсить леворекурсивные грамматики (а нам и не надо).

Дабы простестировать наш парсер, мы используем вышеприведенную грамматику. Она умеет парсить арифметические выражения, она является LL(*) грамматикой и нам ее достаточно для тестов.

Начнем с лексического анализатора (он же "лексер").

Лексический анализатор

Для простоты, наш лексер будет отдавать нам по 1 символу из строки, пропуская пробелы. Мы не будем использовать отдельный тип токенов, а будем работать с символьным типом. По этой же причине, наши числа могуть быть только одноциферными.

Для LL(*) грамматики нам нужен лексический анализатор, который умеет откатываться на произвольное количество символов. На вход лексера мы будем принимать строку, а символы будем отдавать по одному. В дополнение у нас будет функция взятия позиции и отката лексера на позицию.

Лексер мог бы работать со строкой лениво, но для простоты просто преобразуем всю строку в вектор символов:

#[derive(Debug)]
pub struct Lexer {
    /// Input string
    input: Vec<char>,
    /// Lexer position
    position: usize
}

type Position = usize;

impl Lexer {
    pub fn new(input: &str) -> Self {
        // Compiler bug. Can't drain string inplace
        let mut string = String::from(input);
        let vec = string.drain(..).collect();

        Lexer {
            input: vec,
            position: 0
        }
    }

    pub fn position(&self) -> Position {
        self.position
    }

    pub fn next(&mut self) -> Option<char> {
        while let Some(result) = self.input.get(self.position).cloned() {
            self.position += 1;

            if result != ' ' {
                return Some(result)
            }
        }

        None
    }

    pub fn rollback(&mut self, position: Position) {
        self.position = position
    }
}

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

1. Запоминаем позицию лексера;
2. Читаем символы и проверяем их в соответствии с правилом;
3. Если символ не принимается правилом, откатываемся к начальному состоянию и возвращаем ошибку.

Время реализовать тип выражений нашего АСД.

Выражения

Для выражений я сделал несколько упрощений:

1. Я сделал тип выражения перечислением, чего делать сильно не советую в реальном компиляторе. Сколь-нибудь серьезная грамматика делает поддержку унифицированного типа выражений очень сложным процессом. Лучше использовать типажи и имплементации;
2. Для чисел я использовал тип f32. Числа с плавающей запятой не всегда являются лучшим выбором, но для наших целей f32 нам достаточно;
3. Я использовал нестабильную фичу #![feature(box_patterns)]. С этим синтаксисом сравнение по шаблону выглядит красивше понятнее.

Тут же добавлена функция вычисления выражений eval.

Мы будем поддерживать выражения чисел, арифметических операторов и отрицания:

#[derive(Debug)]
pub enum Expression {
    Operator {
        op: Box<Expression>,
        left: Box<Expression>,
        right: Box<Expression>
    },
    Number(f32),
    Token(char),
    Negate(Box<Expression>)
}

impl Expression {
    pub fn eval(self) -> f32 {
        match self {
            Expression::Operator { op: box Expression::Token('+'), left, right } => left.eval() + right.eval(),
            Expression::Operator { op: box Expression::Token('-'), left, right } => left.eval() - right.eval(),
            Expression::Operator { op: box Expression::Token('/'), left, right } => left.eval() / right.eval(),
            Expression::Operator { op: box Expression::Token('*'), left, right } => left.eval() * right.eval(),
            Expression::Number(val) => val,
            Expression::Negate(exp) => -exp.eval(),
            token => panic!("Got token inside an expression {:?}", token)
        }
    }
}

И так, у нас есть лексически анализатор, который выдает нам токены и есть тип выражений. Пора приступать к парсеру, который будет превращать последовательности символов в выражения.

Синтаксический анализатор

Реализация парсера — это наша главная задача.

Все функции разбора будут принимать лексер и возвращать тип Option<Box<expression::Expression>>: Some(expression) если вывод лексера соответствует правилу и None если нет.

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

Две функции используются для разбора числа и сравнения терминалов (символы ()+-.*):

fn num(lexer: &mut lexer::Lexer) -> Option<Box<expression::Expression>> {
    let parser_pos = lexer.position();

    let result = lexer
        .next()
        .map(|c| c as char)
        .and_then(|c| {
                  if c.is_numeric() {
                      Some(Box::new(expression::Expression::Number(c.to_string().parse::<f32>().unwrap())))
                  } else {
                      lexer.rollback(parser_pos);
                      None
                  }});

    result
}

fn token(token_char: char) -> impl FnMut(&mut lexer::Lexer) -> Option<Box<expression::Expression>> {
    move |ref mut lexer| {
        let parser_pos = lexer.position();

        lexer
        .next()
        .map(|c| c as char).and_then(|c| 
            if c == token_char {
                Some(Box::new(expression::Expression::Token(c)))
            } else {
                lexer.rollback(parser_pos);
                None
            })
    }
}

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

fn make_operator(left: Box<expression::Expression>, op: Box<expression::Expression>, right: Box<expression::Expression>) -> Option<Box<expression::Expression>> {
    Some(Box::new(expression::Expression::Operator{
        op,
        left,
        right
    }))
}

Так же, в коде встречается макрос debug_parser!. Он используется для отладки парсера (спасибо Капитан).

Мы определим три макроса:

1. rule! для генерации функции правила;
2. or! для генерации функции выбора "|";
3. and! для генерации функции следования ",".

rule!

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

Макрос довольно прост: он создает функцию, которая в свою очередь при вызове с лексером, возвращает результат переданной функции (звучит сложнее, чем есть на самом деле).

macro_rules! rule {
    ($name: ident, $parse_func:expr) => {
        fn $name(lexer: &mut lexer::Lexer) -> Option<Box<expression::Expression>> {
            debug_parser!("Executing rule {}", stringify!($name));

            $parse_func(lexer)
        }
    };
}

or!

Следующий макрос or!. Он принимает список правил и возвращает неименованную функцию (она же лямбда-функция, она же замыкание), которая при вызове с парсером, поочередно вызывает переданные правила и возвращает первый положительный результат вызова, если такой был. В противном случае возвращает None. Сигнатура возвращаемого замыкания та же что и для правила.

Если вы не знакомы с макросами в Rust, стоит обратить внимание на то, как список правил разворачивается в теле макроса. Для каждого правила, выражение $(...),+ разворачивается один раз. В нашем случает это блок с вызовом функции и проверкой результата. В итоге каждое переданное правило вызовется один раз.

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

macro_rules! or {
    [$($parse_funcs: expr),+] => {
        |lexer: &mut lexer::Lexer| -> Option<Box<expression::Expression>> {
            $(
                let parser_pos = lexer.position();
                let result = $parse_funcs(lexer);

                if result.is_some() {
                    debug_parser!("Or statement rule {} accepted expression {:?}. Lexer state {:?}", stringify!($parse_funcs), result, lexer);
                    return result
                } else {
                    lexer.rollback(parser_pos);
                    debug_parser!("Or statement rule {} didn't accept lexer input {:?}", stringify!($parse_funcs), lexer);
                }
            )+;

            debug_parser!("Or statement fails");
            None
        }
    }
}

and!

И наконец, макрос and!. Его сигнатура немного отличается от or!. Он принимает список правил и функцию обработчик. Макрос возвращает замыкание, которое вызывает переданные правила с лексером и проверяет, что они все вернут некоторое выражение. Если все правила выполняются для лексера, он формирует кортеж результатов и передает его в функцию обработчик. В случае если хотя бы одно правило не выполняется или функция обработчик возвращает None, лексер откатывается в начальное положение. Сигнатура замыкания, по традиции, та же что и у правила.

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

Функция обработчик предается через оператор =>, что бы улучшить читаемость вызова макроса.

macro_rules! and {
    [($($parse_funcs: expr),+) => $nandler_func: expr] => {
        |lexer: &mut lexer::Lexer| -> Option<Box<expression::Expression>> {
            let parser_pos = lexer.position();

            let results = ($(match $parse_funcs(lexer) {
                Some(expression) => {
                    debug_parser!("And statement rule {} accepted expression {:?}. Lexer state {:?}", stringify!($parse_funcs), expression, lexer);
                    expression
                }
                _ => {
                    debug_parser!("And statement rule {} didn't accept lexer input {:?}", stringify!($parse_funcs), lexer);
                    lexer.rollback(parser_pos);
                    return None
                }
            }), +);

            match std::ops::Fn::call(&$nandler_func, results) {
                expression @ Some(_) => {
                    debug_parser!("And handling function successfully handled expression and returned {:?}", expression);
                    expression
                }
                _ => {
                    debug_parser!("And handling function failed to process expressions");
                    lexer.rollback(parser_pos);
                    return None
                }
            }
        }
    };
}

Тут стоит обратить на вызов std::ops::Fn::call. Это нестабильная возможность, но без нее нам пришлось бы передавать кортеж, что заметно менее удобно.

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

// 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)))]);

Результат выглядит довольно неплохо. Если рассматривать только парсер, мы вложились в 65 строк кода. Теперь осталось написать тестовый код и запустить его (да, тестовый код я не особо любитель писать):

fn main() {
    let result0 = expr(&mut lexer::Lexer::new("1 + 2"));
    let result1 = expr(&mut lexer::Lexer::new("(1 + -2)"));
    let result2 = expr(&mut lexer::Lexer::new("(1 + 2) * 3"));
    let result3 = expr(&mut lexer::Lexer::new("1 * (2 - 3)"));
    let result4 = expr(&mut lexer::Lexer::new("1 * -2 + 3 * 4"));
    let result5 = expr(&mut lexer::Lexer::new("(1 * 2 + (-3 + -4))"));

    println!("0. Result {:?}", result0);
    println!("1. Result {:?}", result1);
    println!("2. Result {:?}", result2);
    println!("3. Result {:?}", result3);
    println!("4. Result {:?}", result4);
    println!("5. Result {:?}", result5);

    assert_eq!(result0.unwrap().eval(), 1f32 + 2f32);
    assert_eq!(result1.unwrap().eval(), 1f32 - 2f32);
    assert_eq!(result2.unwrap().eval(), (1f32 + 2f32) * 3f32);
    assert_eq!(result3.unwrap().eval(), 1f32 * (2f32 - 3f32));
    assert_eq!(result4.unwrap().eval(), 1f32 * -2f32 + 3f32 * 4f32);
    assert_eq!(result5.unwrap().eval(), 1f32 * 2f32 + (-3f32 + -4f32));
}

Вывод:

0. Result Some(Operator { op: Token('+'), left: Number(1), right: Number(2) })
1. Result Some(Operator { op: Token('+'), left: Number(1), right: Negate(Number(2)) })
2. Result Some(Operator { op: Token('*'), left: Operator { op: Token('+'), left: Number(1), right: Number(2) }, right: Number(3) })
3. Result Some(Operator { op: Token('*'), left: Number(1), right: Operator { op: Token('-'), left: Number(2), right: Number(3) } })
4. Result Some(Operator { op: Token('+'), left: Operator { op: Token('*'), left: Number(1), right: Negate(Number(2)) }, right: Operator { op: Token('*'), left: Number(3), right: Number(4) } })
5. Result Some(Operator { op: Token('+'), left: Operator { op: Token('*'), left: Number(1), right: Number(2) }, right: Operator { op: Token('+'), left: Negate(Number(3)), right: Negate(Number(4)) } })

Пост скриптум

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

Но разработчики довольно быстро добавляют востребованные возможности, поэтому надежда есть (скоро например добавят HKT и non-lexical scopes).

Весь код можно посмотреть на GitHub.