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

    Wow. Such Rust. Much macro.

    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
        }
    }

    По поводу комментария с багом

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


    Я зашел на #rust-beginners IRC канал и мне один из разработчиков языка сказал что это баг. Так что если у вас вдруг какие-то трудности, заходите на канал и смело спрашивайте. На Rust IRC каналах сидят очень дружелюбные люди и они вам всегда постараются вам помочь.


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


    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.

    Поделиться публикацией
    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее
    Реклама
    Комментарии 17
    • +1

      Одна из основных вещей, которые должен уметь компилятор — это нормальные сообщения об ошибках. А в тестах я бы написал тест со строкой ( (только открывающая скобка) одновременно с тестами на правильных выражениях — и точно до того, как считать что‐либо связанное с разбором достаточно законченным для выкладки. Насколько я знаю, отсутствие вменяемых сообщения об ошибках разбора — это одна из проблем различных генераторов парсеров. Как с ошибками здесь? И, в частности, насколько хорошо debug_parser! может сослаться на исходный код? Т.е. к примеру, для https://github.com/alexander-smoktal/rust-macroparser/blob/dde3099d580a6b21db83a7ce88ba292be9e1e921/src/main.rs#L136-L139 может ли debug_parser! понять (вывести в терминал)


      • Где находится вызов rule!?
      • Какой строке определения rule! соответствует вызов debug_parser!?
      • Где находится вызов and!?
      • В какой строке определения and! находится вызов debug_parser!?
      • Где находится код самого определения debug_parser!?
      • +1

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


        Rust содержит макросы file!, line! и column!, которые можно использовать для сохранении информации о вызовах.


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

        • 0

          file!, line! и column! дают только информацию о том, где вызов rule!. Уже предчувствую обычный для C ад отладки макросов (когда весь код, раскрытый из макроса — одна строчка с точки зрения gdb и из всех методик отладки доступен только printf (ну и stepi, но это жутко неудобно)).

          • +2
            В процессе разбора можно сохранять информацию о парсинге. Например использовать монады (тонкая шутка).

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

            Я знаю один действенный вариант отладки анализатора — покрывать все правила тестами. Во всех других случаях отладчик помогает очень слабо.
            • +2
              Немного поискал и нашел cargo-expand. Он позволяет выводить сгенерированный макросами код. При желании, можно сначала разворачивать, а потом включать в проект и отлаживать.
      • +2

        Спасибо за труд!


        Но не думали ли вы скооперироваться с сообществом и написать свой ANTLR рантайм для Rust? Интерес есть, а плюсов много: стабильность, оптимизированность и поддержка фич ANTLR (левая рекурсия, семантические предикаты, большое количество грамматик и другое). Также это по-моему неплохой опыт по Rust + значимая строчка в резюме.

        • 0
          Пожалуйста.

          Не думал. Моего ентузиазма, к сожалению, хватает ненадолго. Если кто-то будет писать, я бы мог вносить вклад. Но если я начну его писать, есть очень большой риск, что разработка затянется.
          • 0
            Ну по крайней мере можно в задаче написать, что типа готов помогать. :) Может и других мотивации станет больше.
            • 0

              А зачем, когда есть, например, rust-peg, да и вообще, уже десятки их

              • 0

                У ANTLR больше всего грамматик и скорее всего самое большое комьюнити.


                Ну и вообще я уже писал выше:


                стабильность, оптимизированность и поддержка фич ANTLR (левая рекурсия, семантические предикаты, большое количество грамматик и другое)
        • +1
          Ещё можно посмотреть вот на это: LR(1) parser generator for Rust.
          • 0
            Спойлер Функции разбора числа и терминалов отформатирован неверно. Поправьте, пожалуйста
            • 0
              Поправил, спасибо.
            • 0

              К слову, в nightly версии компилятора, помимо существующих + и * добавили квантификатор ? для задания опционального шаблона.


              Теперь, например, можно финальную запятую обрабатывать как $(,)?

              • 0
                А можно ли таким образом выполнять нужный код в зависимости от типа параметра? Например иметь разный код для stat и для expr:

                macro_rule! fancy_macro => {
                  [$arg: expr, $($ex: expr),? $($st:stat),?] => {
                    $($expr($arg)),?
                    $(
                        $st;
                        $arg
                     ),?
                  }
                }
                
                • 0
                  Не знаю, надо проверять, но идея интересная. Но мне кажется, что это не соответствует правилам подстановки по образцу.
              • 0
                Результат внешне очень похож на Boost.Spirit, разве что чуть более многословный. Но при этом насколько же проще оно выглядит внутри! Синтаксические макросы безусловно намного более удобный инструмент метапрограммирования в сравнение с шаблонами C++ (что впрочем совсем не удивительно, т.к. при создание шаблонов о МП никто и не думал).

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