Создание своего языка программирования на Rust #2: Парсер выражений

Привет, Хабр!

Что будем делать?

Мы напишем парсер для примерно таких выражений: 1+2*(2+8)*2*a+3. Сначало мы добавим парсер для арифметических выражений, а после сразу же займемся сравнениями и логическими операциями. Как писал ранее, мы будем парсить методом рекурсивного спуска, и там у нас будет поддержка приоритета операторов. Сначало */, а потом +-. В результате будет такая цепочка: primary -> unary -> additive -> multiplicative -> comparison -> logical.

Сами обьекты выражений будут типа enum Expr. Будут такие типы:

1. Expr::Num(f64) — простое число, определяется в primary

2. Εxpr::Bool(bool) — логическое значение, определяется в primary

3. Expr::Str(String) — литерал строки, определяется в primary

4. Expr::Id(String) — идентификатор, определяется в primary

5. Expr::Unary(UnaryOp, Box<Expr>) — унарнвя операция и новое перечисление — UnaryOp: Neg (-) и Not (!). Определяется в unary.

6. Expr::Arith(Box<Expr>, ArithOp, Box<Expr>) — арифметические выражения. Тут мы созданим еще одно перечисление — ArithOp: Add, Sub, Mul и Div. Определяется в multiplicative и additive

7. Expr::Comp(Box<Expr>, CompOp, Box<Expr>) — сравнение. Структура та же, но в качестве оператора новое перечисление — CompOp: Gt (>), Ge (>=), Lt (<), Le (<=), Eq (==), Ne (!=). Определяется в comparison.

8. Expr::Logic(Box<Expr>, LogicOp, Box<Expr>) — логическое выражение. Тут также новое перечтсление — LogicOp: And (&&) и Or (||). Определяется в logical

В прошлой статье я упомянул, но повторюсь.

primary — определяем, может ли этот токег быть значением я выражении. Это можгут быть: числа, строки, идентификаторы, вызовы функций, скобки (Точнее, их содержимое). Возвращаем Num, Str, Id. Считая скобки, мы можем получить любое выражение.

unary — тут мы берем текущий токен, если это, например, !, то пропускаем его, вызвваем primary, чтобы получить выражение, и возвращаем выражение. Возвращаем Expr::Unary.

multiplicative — тут находим все выражения с умножением и делением и возвращаем выраэение. Возвращаем Expr::Arith

additive — находим выражения сложения и вычитания. Возвращаем Expr::Arith

Начинаем писать!

Создаем новый модуль — parser. Там нам нужны файлы expr.rs, parser.rs и mod.rs. Сначало, конечно же, напишем mod.rs. (Неожиданно, да?)

Покажу сразу итоговый.

pub mod expr;mod parser;pub use parser::Parser;#[derive(Debug, Clone)]pub struct Info {    pub line: usize,    pub offset: usize,    pub len: usize,}#[macro_export]macro_rules! info {    ($line:expr, $offset:expr, $len:expr) => {        $crate::parser::Info {            line: $line,            offset: $offset,            len: $len,        }    };    ($tkn:expr) => {        info!($tkn.line, $tkn.offset, $tkn.len)    };}

Для Expr, нам тоже понадобится отладочная информация, и для этого у нас есть структура Info. С помощью ее, мы будет делать отладку в интерпритаторе, а так как и стейтменты будут структурами, я решил поместить его в mod.rs. Также тут у нас будет макрос, он просто создает обьект Info. А длинный, где мы в ручную передаем параметры, мы оставим для стейтментов, чтобы и их отлаживать.

use super::Info;pub type BExpr = Box<Expr>;#[derive(Debug, Clone)]pub enum Expr {    Num(f64, Info),    Str(String, Info),    Id(String, Info),    Bool(bool, Info),    Unary(UnaryOp, BExpr, Info),    Arith(BExpr, ArithOp, BExpr, Info),    Comp(BExpr, CompOp, BExpr, Info),    Logic(BExpr, LogicOp, BExpr, Info),}impl Expr {    pub fn info(&self) -> Info {        match self {            Expr::Str(_, info) => info.clone(),            Expr::Num(_, info) => info.clone(),            Expr::Id(_, info) => info.clone(),            Expr::Bool(_, info) => info.clone(),            Expr::Arith(_, _, _, info) => info.clone(),            Expr::Comp(_, _, _, info) => info.clone(),            Expr::Logic(_, _, _, info) => info.clone(),            Expr::Unary(_, _, info) => info.clone(),        }    }}#[derive(Debug, Clone)]pub enum ArithOp {    Add, // +    Sub, // -    Mul, // *    Div, // /}#[derive(Debug, Clone)]pub enum CompOp {    Gt, // >    Ge, // >=    Lt, // <    Le, // <=    Eq, // ==    Ne, // !=}#[derive(Debug, Clone)]pub enum LogicOp {    And, // &&    Or,  // ||}#[derive(Debug, Clone)]pub enum UnaryOp {    Not, // !    Neg, // -}

Я создал тип BExpr, чтобы каждый раз не писать Box<Expr>. Как видите тут есть перечисления операторов: ArithOp, CompOp, LogicOp. Также самое главное печисление — Expr. Я ранее уже рассказывал для чего это, так что повторяться не буду. Метод info тут просто копирует инфо текущего ввражения, чтобы потом можно быстро строить их удобнее. (Увидити вообщем)

Теперь создаем стуктуру Parser.

use super::expr::{ArithOp, BExpr, CompOp, Expr, LogicOp};use crate::lexer::token::{TKind, Token};pub struct Parser<'a> {    pos: usize,    tokens: Vec<Token>,    lines: Vec<&'a str>,}impl<'a> Parser<'a> {    pub fn new(tokens: Vec<Token>, source: &'a str) -> Self {        let lines: Vec<&str> = source.lines().collect();        Self {            tokens,            pos: 0,            lines,        }    }}

Заранее импортируем Expr и его операторы, а также Token и TKind (всевдоним TokenKind). В метод new мы передаем токены, из которых будем строить AST (Abstract Syntax Tree) и исходник, из которого мы получаем все строки. lines нам нужен также для ошибок, как и в лексере.

Теперь напишем вспомогательные методы. Их будет меньше и буду проще (на данном этапе).

use std::mem::discriminant;...fn check(&mut self, kind: TKind) -> bool {    if discriminant(&self.peek(0).kind) == discriminant(&kind) {        self.advance(1);        true    } else {        false    }}fn error(&self, msg: &str, token: Token) -> String {    let line = self.lines[token.line];    let header = format!("Error in {}:{} - {msg}", token.line, token.offset);    let err_line = format!("{} | {line}", token.line);    let point = format!(        "{} | {}{}",        " ".repeat(token.line.to_string().len()),        " ".repeat(token.offset),        "^".repeat(token.len),    );    format!("{header}\n{err_line}\n{point}\n")}fn peek(&self, offset: i8) -> Token {    let idx = self.pos + offset as usize;    self.tokens.get(idx).unwrap().clone()}fn advance(&mut self, offset: u8) {    self.pos += offset as usize;}

В advance мы обновляем только self.pos.

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

В error мы будем передовать токен, и будем брать информацию из него.

check проверяет, соответствует ли тип текущего токена переданому, в случае успеха пропускаем его и возвращаем true, а в ином случае просто возвращаем false. discriminant нам нужен, чтобы сранивать только тип токена, а не его содержимое.

Начинаем писать парсинг!

Начнем с primary.

fn primary(&mut self) -> Expr {    let current = self.peek(0);    match current.kind {        TKind::NumLit(n) => {            self.advance(1);            Expr::Num(n, info!(current))        }        TKind::StrLit(s) => {            self.advance(1);            Expr::Str(s, info!(current))        }        TKind::Id(id) => {            self.advance(1);            Expr::Id(id, info!(current))        }        TKind::Bool(truth) => {            self.advance(1);            Expr::Bool(truth, info!(current))        }        _ => panic!("{}", self.error("Unexpected token in primary", current)),    }}

Мы берем текущий токен и проверяем его. Если он может быть значением в выражении, то пропускаем его и создаем соответствующий обьект Expr. В случае не валидного токена паникуем на неожиданный токен. Скобки также будут обрабатываться здесь, но добавим их позже.

fn unary(&mut self) -> Expr {    let current = self.peek(0);    match current.kind {        TKind::Minus => {            self.advance(1);            let primary = self.primary();            let info = primary.info();            let info = info!(info.line, info.offset - 1, info.len + 1);            Expr::Unary(UnaryOp::Neg, Box::new(primary), info)        }        TKind::Bang => {            self.advance(1);            let primary = self.primary();            let info = primary.info();            let info = info!(info.line, info.offset - 1, info.len + 1);            Expr::Unary(UnaryOp::Not, Box::new(primary), info)        }        _ => self.primary(),    }}

Тут смотрим на текущий токен. Если это — или !, то соотаетственно обрабатываем и возвращаем Expr::Unary, в ином случае возвращаем обычный primary. Для примерв возмем вариант с TKind::Minus.

TKind::Minus => {    self.advance(1);    let primary = self.primary();    let info = primary.info();    let info = info!(info.line, info.offset - 1, info.len + 1);    Expr::Unary(UnaryOp::Neg, Box::new(primary), info)}

Мы пропускаем текущий токен (минус) и берем primary. Далее нам нужно создать Info. Просто взять info!(primary) не получится, так как минус тоже должен выходить в Info. Так что берем Info из primary, в макрос передаем номер строки, отступ от начала строки — 1. Отнимаем 1, так как primary начинается сразу после унарного оператора, и там мы захватим и сам оператор. В длинну передаем длинну primary + 1, чтобы выровнять. В конце возвращаем негативный primary и Info, который мы создали. С TKind логика схожа, просто используем UnaryOp::Not.

Теперь и multiplicative.

fn multiplicative(&mut self) -> Expr {    let mut left = self.unary();    loop {        let op_token = self.peek(0);        let op = match op_token.kind {            TKind::Star => ArithOp::Mul,            TKind::Slash => ArithOp::Div,            _ => break,        };        self.advance(1);        let right = self.unary();        left = Expr::Arith(Box::new(left), op, Box::new(right), info!(op_token))    }    left}

Создаем left, куда помещаем self.unary, это будет левым операндом. Далее в бесконечном цикле: проверяем текущий токен, если это знак умножения или деления, то возвощаем соответствующий ArithOp, в случае, если это любой другой токен, просто выходим из цикла и возвращаем left.

В случае, если это подходящий оператор, пропускаем его и парсим правый операнд. После переопределяем left, как левый операнд используем сам left, а для правого наш недавно спаршеный right. В info я решил класть позицию оператора. Так будет меньше замарочек по поводу выделения ошибок, и меньше кода.

У additive логика абсолютно та же, просто заменяем операторы на соответствующие.

fn additive(&mut self) -> Expr {    let mut left = self.multiplicative();    loop {        let op_token = self.peek(0);        let op = match op_token.kind {            TKind::Plus => ArithOp::Add,            TKind::Minus => ArithOp::Sub,            _ => break,        };        self.advance(1);        let right = self.multiplicative();        left = Expr::Arith(Box::new(left), op, Box::new(right), info!(op_token))    }    left}

Для обобщения создаем метод expr, туда мы, возможно, добавим тернарный оператор, но пока без него:

fn expr(&mut self) -> Expr {    self.additive()}

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

pub fn parse_exprs(&mut self) -> Vec<Expr> {    let mut exprs = vec![];    while self.peek(0).kind != TKind::Eof {        let expr = self.expr();        exprs.push(expr);    }    exprs}

Ну и собственно создаем новый тест в папке tests — parsert.rs

use guidzy::lexer::Lexer;use guidzy::parser::Parser;#[test]fn main() {    let source = "2 + 2 * 2"    .trim();    let tokens = Lexer::new(source).tokenize();    println!("Source: {}\nTokens:", source);    for tkn in &tokens {        println!("{:?}", tkn);    }    let exprs = Parser::new(tokens, source).parse_exprs();    println!("Expressions:");    for ex in exprs {        println!("{:?}", ex);    }}

Для запуска теста с выводом используем cargo test — —nocapture. Вывод будет таковым:

Source: 2 + 2 * 2Tokens:Token { kind: NumLit(2.0), len: 1, pos: 0, line: 0, offset: 0 }Token { kind: Plus, len: 1, pos: 2, line: 0, offset: 2 }Token { kind: NumLit(2.0), len: 1, pos: 4, line: 0, offset: 4 }Token { kind: Star, len: 1, pos: 6, line: 0, offset: 6 }Token { kind: NumLit(2.0), len: 1, pos: 8, line: 0, offset: 8 }Token { kind: Eof, len: 1, pos: 9, line: 0, offset: 9 }Expressions:Arith(Num(2.0, Info { line: 0, offset: 0, len: 1 }), Add, Arith(Num(2.0, Info { line: 0, offset: 4, len: 1 }), Mul, Num(2.0, Info { line: 0, offset: 8, len: 1 }), Info { line: 0, offset: 6, len: 1 }), Info { line: 0, offset: 2, len: 1 })

Согласитесь, довольно нечитаемый вывод? Чтобы сделать его читаемым, реализуем трейт fmt::Display для Expr и всех операторов:

use std::fmt;...impl fmt::Display for ArithOp {    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {        match self {            ArithOp::Add => write!(f, "+"),            ArithOp::Sub => write!(f, "-"),            ArithOp::Mul => write!(f, "*"),            ArithOp::Div => write!(f, "/"),        }    }}impl fmt::Display for CompOp {    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {        match self {            CompOp::Gt => write!(f, ">"),            CompOp::Ge => write!(f, ">="),            CompOp::Lt => write!(f, "<"),            CompOp::Le => write!(f, "<="),            CompOp::Eq => write!(f, "=="),            CompOp::Ne => write!(f, "!="),        }    }}impl fmt::Display for LogicOp {    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {        match self {            LogicOp::And => write!(f, "&&"),            LogicOp::Or => write!(f, "||"),        }    }}impl fmt::Display for UnaryOp {    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {        match self {            UnaryOp::Neg => write!(f, "-"),            UnaryOp::Not => write!(f, "!"),        }    }}impl fmt::Display for Expr {    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {        match self {            Expr::Num(n, _) => write!(f, "{n}"),            Expr::Str(s, _) => write!(f, "\"{s}\""),            Expr::Id(id, _) => write!(f, "{id}"),            Expr::Bool(b, _) => write!(f, "{b}"),            Expr::Arith(l, op, r, _) => write!(f, "({l} {op} {r})"),            Expr::Comp(l, op, r, _) => write!(f, "({l} {op} {r})"),            Expr::Logic(l, op, r, _) => write!(f, "({l} {op} {r})"),            Expr::Unary(op, expr, _) => write!(f, "{op}{expr}"),        }    }}

Я реализовал форматирование сразу для всего, чтобы потос не возвращаться к этому. Вывод теперь таков:

Source: 2 + 2 * 2Tokens:Token { kind: NumLit(2.0), len: 1, pos: 0, line: 0, offset: 0 }Token { kind: Plus, len: 1, pos: 2, line: 0, offset: 2 }Token { kind: NumLit(2.0), len: 1, pos: 4, line: 0, offset: 4 }Token { kind: Star, len: 1, pos: 6, line: 0, offset: 6 }Token { kind: NumLit(2.0), len: 1, pos: 8, line: 0, offset: 8 }Token { kind: Eof, len: 1, pos: 9, line: 0, offset: 9 }Expressions:(2 + (2 * 2))

Добавляем операторы сравнения

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

fn logical(&mut self) -> Expr {    let mut left = self.comparison();    loop {        let op_token = self.peek(0);        let op = match op_token.kind {            TKind::And => LogicOp::And,            TKind::Or => LogicOp::Or,            _ => break,        };        self.advance(1);        let right = self.comparison();        left = Expr::Logic(Box::new(left), op, Box::new(right), info!(op_token))    }    left}fn comparison(&mut self) -> Expr {    let mut left = self.additive();    loop {        let op_token = self.peek(0);        let op = match op_token.kind {            TKind::Gt => CompOp::Gt,            TKind::Ge => CompOp::Ge,            TKind::Lt => CompOp::Lt,            TKind::Le => CompOp::Le,            TKind::Eq => CompOp::Eq,            TKind::Ne => CompOp::Ne,            _ => break,        };        self.advance(1);        let right = self.additive();        left = Expr::Comp(Box::new(left), op, Box::new(right), info!(op_token))    }    left}

use guidzy::lexer::Lexer;use guidzy::parser::Parser;#[test]fn main() {    let source = "2 + 2 * 2 > 4 / 2 + 2 && true != false"    .trim();    let tokens = Lexer::new(source).tokenize();    println!("Source: {}\nTokens:", source);    for tkn in &tokens {        println!("{:?}", tkn);    }    let exprs = Parser::new(tokens, source).parse_exprs();    println!("Expressions:");    for ex in exprs {        println!("{}", ex);    }}

Вывод будет таким:

Source: 2 + 2 * 2 > 4 / 2 + 2 && true != falseTokens:Token { kind: NumLit(2.0), len: 1, pos: 0, line: 0, offset: 0 }Token { kind: Plus, len: 1, pos: 2, line: 0, offset: 2 }Token { kind: NumLit(2.0), len: 1, pos: 4, line: 0, offset: 4 }Token { kind: Star, len: 1, pos: 6, line: 0, offset: 6 }Token { kind: NumLit(2.0), len: 1, pos: 8, line: 0, offset: 8 }Token { kind: Gt, len: 1, pos: 10, line: 0, offset: 10 }Token { kind: NumLit(4.0), len: 1, pos: 12, line: 0, offset: 12 }Token { kind: Slash, len: 1, pos: 14, line: 0, offset: 14 }Token { kind: NumLit(2.0), len: 1, pos: 16, line: 0, offset: 16 }Token { kind: Plus, len: 1, pos: 18, line: 0, offset: 18 }Token { kind: NumLit(2.0), len: 1, pos: 20, line: 0, offset: 20 }Token { kind: And, len: 2, pos: 22, line: 0, offset: 22 }Token { kind: Bool(true), len: 6, pos: 25, line: 0, offset: 25 }Token { kind: Ne, len: 2, pos: 30, line: 0, offset: 30 }Token { kind: Bool(false), len: 7, pos: 33, line: 0, offset: 33 }Token { kind: Eof, len: 1, pos: 38, line: 0, offset: 38 }Expressions:(((2 + (2 * 2)) > ((4 / 2) + 2)) && (true != false))

На последок добавим скобки. В primary добавляем новую проверку:

TKind::LParen => {    self.advance(1);    let expr = self.expr();    if !self.check(TKind::RParen) {        panic!(            "{}",            self.error(&format!("Expected ')', found {:?}", current), current)        );    }    expr}

Тут пропускаем левую скобку, после скобки парсим полноценное выражение и проверяем токен на закрывающую скобку. Если это не закрывающая скобка, то вызываем ошибку, в ином случае возвращаем выражение.

use guidzy::lexer::Lexer;use guidzy::parser::Parser;#[test]fn main() {    let source = "2 + 2 * 2 > 4 / 2 + 2 && true != false(2 + 2) * 2"    .trim();    let tokens = Lexer::new(source).tokenize();    println!("Source: {}\nTokens:", source);    for tkn in &tokens {        println!("{:?}", tkn);    }    let exprs = Parser::new(tokens, source).parse_exprs();    println!("Expressions:");    for ex in exprs {        println!("{}", ex);    }}

И теперь вывод такой:

Source: 2 + 2 * 2 > 4 / 2 + 2 && true != false(2 + 2) * 2Tokens:Token { kind: NumLit(2.0), len: 1, pos: 0, line: 0, offset: 0 }Token { kind: Plus, len: 1, pos: 2, line: 0, offset: 2 }Token { kind: NumLit(2.0), len: 1, pos: 4, line: 0, offset: 4 }Token { kind: Star, len: 1, pos: 6, line: 0, offset: 6 }Token { kind: NumLit(2.0), len: 1, pos: 8, line: 0, offset: 8 }Token { kind: Gt, len: 1, pos: 10, line: 0, offset: 10 }Token { kind: NumLit(4.0), len: 1, pos: 12, line: 0, offset: 12 }Token { kind: Slash, len: 1, pos: 14, line: 0, offset: 14 }Token { kind: NumLit(2.0), len: 1, pos: 16, line: 0, offset: 16 }Token { kind: Plus, len: 1, pos: 18, line: 0, offset: 18 }Token { kind: NumLit(2.0), len: 1, pos: 20, line: 0, offset: 20 }Token { kind: And, len: 2, pos: 22, line: 0, offset: 22 }Token { kind: Bool(true), len: 6, pos: 25, line: 0, offset: 25 }Token { kind: Ne, len: 2, pos: 30, line: 0, offset: 30 }Token { kind: Bool(false), len: 7, pos: 33, line: 0, offset: 33 }Token { kind: LParen, len: 1, pos: 39, line: 1, offset: 0 }Token { kind: NumLit(2.0), len: 1, pos: 40, line: 1, offset: 1 }Token { kind: Plus, len: 1, pos: 42, line: 1, offset: 3 }Token { kind: NumLit(2.0), len: 1, pos: 44, line: 1, offset: 5 }Token { kind: RParen, len: 1, pos: 45, line: 1, offset: 6 }Token { kind: Star, len: 1, pos: 47, line: 1, offset: 8 }Token { kind: NumLit(2.0), len: 1, pos: 49, line: 1, offset: 10 }Token { kind: Eof, len: 1, pos: 50, line: 1, offset: 11 }Expressions:(((2 + (2 * 2)) > ((4 / 2) + 2)) && (true != false))((2 + 2) * 2)

Итог

Теперь у нас есть парсер, который парсит выражения со скобками и приоритетом операторов 😀

В следующей статье уже будем добавлять парсер для стейтментов.

Результаты текущей статьи можно посмотреть в этом репозитории.