深入理解Rust语言表达式求值（从零构建递归下降解析器）

什么是表达式求值？

表达式求值是指将一个字符串形式的数学表达式（如 "3 + 5 * 2"）解析并计算出其数值结果（本例中为 13）。这个过程通常包括两个主要阶段：

• 词法分析（Lexing）：将输入字符串拆分为有意义的“词元”（Token），例如数字、加号、乘号等。
• 语法分析（Parsing）：根据语法规则（如运算符优先级）构建抽象语法树（AST），然后遍历该树进行求值。

在 Rust 中，我们可以利用其强大的类型系统和模式匹配能力，优雅地实现这一过程。这也是学习 Rust语法树 构建的绝佳实践。

第一步：定义 Token 类型

首先，我们需要定义表达式中可能出现的词元类型：

#[derive(Debug, Clone)]pub enum Token {    Number(f64),    Plus,    Minus,    Multiply,    Divide,    LeftParen,    RightParen,}

第二步：词法分析器（Lexer）

接下来，我们编写一个简单的词法分析器，它将字符串转换为 Token 向量：

pub fn tokenize(input: &str) -> Vec<Token> {    let mut tokens = Vec::new();    let mut chars = input.chars().peekable();    while let Some(&c) = chars.peek() {        match c {            '0'..='9' | '.' => {                let mut num_str = String::new();                while let Some(&d) = chars.peek() {                    if d.is_ascii_digit() || d == '.' {                        num_str.push(d);                        chars.next();                    } else {                        break;                    }                }                if let Ok(num) = num_str.parse() {                    tokens.push(Token::Number(num));                }            }            '+' => { tokens.push(Token::Plus); chars.next(); }            '-' => { tokens.push(Token::Minus); chars.next(); }            '*' => { tokens.push(Token::Multiply); chars.next(); }            '/' => { tokens.push(Token::Divide); chars.next(); }            '(' => { tokens.push(Token::LeftParen); chars.next(); }            ')' => { tokens.push(Token::RightParen); chars.next(); }            ' ' | '\t' | '\n' => { chars.next(); } // 忽略空白字符            _ => panic!("未知字符: {}", c),        }    }    tokens}

第三步：构建抽象语法树（AST）

为了正确处理运算符优先级（如先乘除后加减），我们采用递归下降解析法。首先定义 AST 节点：

#[derive(Debug)]pub enum Expr {    Number(f64),    Binary {        left: Box<Expr>,        op: Token,        right: Box<Expr>,    },}

第四步：递归下降解析器

我们实现一个简单的解析器，支持四则运算和括号：

struct Parser {    tokens: Vec<Token>,    pos: usize,}impl Parser {    pub fn new(tokens: Vec<Token>) -> Self {        Self { tokens, pos: 0 }    }    fn peek(&self) -> Option<&Token> {        self.tokens.get(self.pos)    }    fn consume(&mut self) -> Option {        if self.pos < self.tokens.len() {            let token = self.tokens[self.pos].clone();            self.pos += 1;            Some(token)        } else {            None        }    }    pub fn parse(&mut self) -> Expr {        self.parse_expression()    }    fn parse_expression(&mut self) -> Expr {        self.parse_term()    }    fn parse_term(&mut self) -> Expr {        let mut expr = self.parse_factor();        while let Some(op) = self.peek() {            match op {                Token::Plus | Token::Minus => {                    let op = self.consume().unwrap();                    let right = self.parse_factor();                    expr = Expr::Binary {                        left: Box::new(expr),                        op,                        right: Box::new(right),                    };                }                _ => break,            }        }        expr    }    fn parse_factor(&mut self) -> Expr {        let mut expr = self.parse_primary();        while let Some(op) = self.peek() {            match op {                Token::Multiply | Token::Divide => {                    let op = self.consume().unwrap();                    let right = self.parse_primary();                    expr = Expr::Binary {                        left: Box::new(expr),                        op,                        right: Box::new(right),                    };                }                _ => break,            }        }        expr    }    fn parse_primary(&mut self) -> Expr {        if let Some(token) = self.consume() {            match token {                Token::Number(n) => Expr::Number(n),                Token::LeftParen => {                    let expr = self.parse_expression();                    // 消耗右括号                    assert_eq!(self.consume(), Some(Token::RightParen));                    expr                }                _ => panic!("意外的 token: {:?}", token),            }        } else {            panic!("预期一个表达式");        }    }}

第五步：求值函数

有了 AST，求值就变得非常简单：

fn evaluate(expr: &Expr) -> f64 {    match expr {        Expr::Number(n) => *n,        Expr::Binary { left, op, right } => {            let left_val = evaluate(left);            let right_val = evaluate(right);            match op {                Token::Plus => left_val + right_val,                Token::Minus => left_val - right_val,                Token::Multiply => left_val * right_val,                Token::Divide => left_val / right_val,                _ => panic!("无效的操作符"),            }        }    }}

完整示例与测试

现在，我们可以将所有部分组合起来：

fn main() {    let input = "3 + 5 * (2 - 8)";    let tokens = tokenize(input);    let mut parser = Parser::new(tokens);    let ast = parser.parse();    let result = evaluate(&ast);    println!("{} = {}", input, result); // 输出: 3 + 5 * (2 - 8) = -27}

总结

通过本教程，你已经学会了如何用 Rust 实现一个基本的 Rust表达式求值 系统。这不仅加深了你对 Rust递归下降解析器 的理解，也为你日后开发更复杂的解释器或编译器打下基础。记住，Rust语法树 是连接源代码与执行逻辑的桥梁，而整个过程正是 Rust编程教程 中极具价值的实战项目。

提示：你可以尝试扩展此求值器，支持变量、函数调用或更多运算符！