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

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

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

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

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

2. Expr::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 * 2
Tokens:
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 * 2
Tokens:
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 != false
Tokens:
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) * 2
Tokens:
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)

Итог

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

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

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