![Wow. Such Rust. Much macro.](https://habrastorage.org/webt/62/5x/az/625xaz3hyq5q3dtannuipu8rnjw.png)
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 каналах сидят очень дружелюбные люди и они вам всегда постараются вам помочь.
Сценарий работы с лексером выглядит следующим образом:
- Запоминаем позицию лексера;
- Читаем символы и проверяем их в соответствии с правилом;
- Если символ не принимается правилом, откатываемся к начальному состоянию и возвращаем ошибку.
Время реализовать тип выражений нашего АСД.
Выражения
Для выражений я сделал несколько упрощений:
- Я сделал тип выражения перечислением, чего делать сильно не советую в реальном компиляторе. Сколь-нибудь серьезная грамматика делает поддержку унифицированного типа выражений очень сложным процессом. Лучше использовать типажи и имплементации;
- Для чисел я использовал тип
f32
. Числа с плавающей запятой не всегда являются лучшим выбором, но для наших целейf32
нам достаточно; - Я использовал нестабильную фичу
#![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!
. Он используется для отладки парсера (спасибо Капитан).
Мы определим три макроса:
rule!
для генерации функции правила;or!
для генерации функции выбора"|"
;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.