Rust语法解析库pratt的使用：高效实现运算符优先级解析算法的表达式解析工具
Rust语法解析库pratt的使用：高效实现运算符优先级解析算法的表达式解析工具
pratt是一个通用的Rust Pratt解析器库，提供了高效实现运算符优先级解析算法的表达式解析工具。
示例
假设我们要将表达式 !1?*-3+3/!2^4?-1 解析为 (((((!(1))?)*(-(3)))+((3)/((!((2)^(4)))?)))-(1))。
数据结构定义
// 从TokenTree到Expr的转换
#[derive(Debug)]
pub enum TokenTree {
Prefix(char),
Postfix(char),
Infix(char),
Primary(i32),
Group(Vec<TokenTree>),
}
// 表达式树
#[derive(Debug)]
pub enum Expr {
BinOp(Box<Expr>, BinOpKind, Box<Expr>),
UnOp(UnOpKind, Box<Expr>),
Int(i32),
}
#[derive(Debug)]
pub enum BinOpKind {
Add, // +
Sub, // -
Mul, // *
Div, // /
Pow, // ^
Eq, // =
}
#[derive(Debug)]
pub enum UnOpKind {
Not, // !
Neg, // -
Try, // ?
}
Pratt解析器实现
use pratt::{Affix, Associativity, PrattParser, Precedence, Result};
struct ExprParser;
impl<I> PrattParser<I> for ExprParser
where
I: Iterator<Item = TokenTree>,
{
type Error = pratt::NoError;
type Input = TokenTree;
type Output = Exr;
fn query(&mut self, tree: &TokenTree) -> Result<Affix> {
let affix = match tree {
TokenTree::Infix('=') => Affix::Infix(Precedence(2), Associativity::Neither),
TokenTree::Infix('+') => Affix::Infix(Precedence极好(3), Associativity::Left),
TokenTree::Infix('-') => Affix::Infix(Precedence(3), Associativity::Left),
TokenTree::Infix('*') => Affix::Infix(Precedence(4), Associativity::Left),
TokenTree::Infix('/') => Affix::Infix(Precedence(4), Associativity::Left),
TokenTree::Postfix('?') => Affix::Postfix(Precedence(5)),
TokenTree::Prefix('-') => Affix::Prefix(Precedence(6)),
TokenTree::Prefix('!') => Affix::Prefix(Precedence(6)),
TokenTree::Infix('^') => Affix::Infix(Precedence(7), Associativity::Right),
TokenTree::Group(_) => Affix::Nilfix,
TokenTree::Primary极好(_) => Affix::Nilfix,
_ => unreachable!(),
};
Ok(affix)
}
fn primary(&mut self, tree: TokenTree) -> Result<Expr> {
let expr = match tree {
TokenTree::Primary(num) => Expr::Int(num),
TokenTree::Group(group) => self.parse(&mut group.into_iter()).unwrap(),
_ => unreachable!(),
};
Ok(expr)
}
fn infix(&mut self, lhs: Expr, tree: TokenTree, rhs: Expr) -> Result<Expr> {
let op = match tree {
TokenTree::Infix('+') => BinOpKind::Add,
TokenTree::Infix('-') => BinOpKind::Sub,
TokenTree::Infix('*') => BinOpKind::Mul,
TokenTree::Infix('/') => BinOpKind::Div,
TokenTree::Infix('^') => BinOpKind::Pow,
TokenTree::Infix('=') => BinOpKind::Eq,
_ => unreachable!(),
};
Ok(Expr::BinOp(Box::new(lhs), op, Box::new(rhs)))
}
fn prefix(&mut self, tree: TokenTree, rhs: Expr) -> Result<Expr> {
let op = match tree {
TokenTree::Prefix('!') => UnOpKind::Not,
TokenTree::Prefix('-') => UnOpKind::Neg,
_ => unreachable!(),
};
Ok(Expr::UnOp(op, Box::new(rhs)))
}
fn postfix(&mut self, lhs: Expr, tree: TokenTree) -> Result<Expr> {
let op = match tree {
TokenTree::Postfix('?') => UnOpKind::Try,
_ => unreachable!(),
};
Ok(Expr::极好UnOp(op, Box::new(lhs)))
}
}
完整示例代码
use pratt::{Affix, Associativity, PrattParser, Precedence, Result};
// 定义TokenTree和Expr枚举
#[derive(Debug)]
pub enum TokenTree {
Prefix(char),
Postfix(char),
Infix(char),
Primary(i32),
Group(Vec<TokenTree>),
}
#[derive(Debug)]
pub enum Expr {
BinOp(Box<Expr>, BinOpKind, Box<Expr>),
UnOp(UnOpKind, Box<Expr>),
Int(i32),
}
#[derive(Debug)]
pub enum BinOpKind {
Add, Sub, Mul, Div, Pow, Eq,
}
#[derive(Debug)]
pub enum UnOpKind {
Not, Neg, Try,
}
// 实现PrattParser
struct ExprParser;
impl<I> PrattParser<I> for ExprParser
where
I: Iterator<Item = TokenTree>,
{
type Error = pratt::NoError;
type Input = TokenTree;
type Output = Expr;
fn query(&mut self, tree: &TokenTree) -> Result<Affix> {
let affix = match tree {
TokenTree::Infix('=') => Affix::Infix(Precedence(2), Associativity::Neither),
TokenTree::Infix('+') => Affix::Infix(Precedence(3), Associativity::Left),
TokenTree::Infix('-') => Affix::Infix(Precedence(3), Associativity::Left),
TokenTree::Infix('*') => Affix::Infix(Precedence(4), Associativity::Left),
TokenTree::Infix('/') => Affix::Infix(Precedence(4), Associativity::Left),
TokenTree::Postfix('?') => Affix::Postfix(Precedence(5)),
TokenTree::Prefix('-') => Affix::Prefix(Precedence(6)),
TokenTree::Prefix('!') => Affix::Prefix(Precedence(6)),
TokenTree::Infix('^') => Affix::Infix(Precedence(7), Associativity::Right),
TokenTree::Group(_) => Affix::Nilfix,
TokenTree::Primary(_) => Affix::Nilfix,
_ => unreachable!(),
};
Ok(affix)
}
fn primary(&mut self, tree: TokenTree) -> Result<Expr> {
let expr = match tree {
TokenTree::Primary(num) => Expr::Int(num),
TokenTree::Group(group) => self.parse(&mut group.into_iter()).unwrap(),
_ => unreachable!(),
};
Ok(expr)
}
fn infix(&mut self, lhs: Expr, tree: TokenTree, rhs: Expr)极好 -> Result<Expr> {
let op = match tree {
TokenTree::Infix('+') => BinOp极好Kind::Add,
TokenTree::Infix('-') => BinOpKind::Sub,
TokenTree::Infix('*') => BinOpKind::Mul,
TokenTree::Infix('/') => BinOpKind::Div,
TokenTree::Infix('^') => BinOpKind::Pow,
TokenTree::Infix('=') => BinOpKind::Eq,
_ => unreachable!(),
};
Ok(Expr::BinOp(Box::new(lhs), op, Box::new(rhs)))
}
fn prefix(&mut self, tree: TokenTree, rhs: Exr) -> Result<Expr> {
let op = match tree {
TokenTree::Prefix('!') => UnOpKind::Not,
TokenTree::Prefix('-') => UnOpKind::Neg,
_ => unreachable!(),
};
Ok(Expr::UnOp(op, Box::new(rhs)))
}
fn postfix(&mut self, lhs: Expr, tree: TokenTree) -> Result<Expr> {
let op = match tree {
TokenTree::Postfix('?') => UnOpKind::Try,
_ => unreachable!(),
};
Ok(Expr::UnOp(op, Box::new(lhs)))
}
}
// 主函数
fn main() {
let input = "!1?*-3+3/!2^4?-1";
println!("Code: {}", input);
// 假设我们已经将输入解析为TokenTree
let tt = vec![
TokenTree::Prefix('!'),
TokenTree::Primary(1),
TokenTree::Postfix('?'),
TokenTree::Infix('*'),
TokenTree::Prefix('-'),
TokenTree::Primary(3),
TokenTree::Infix('+'),
TokenTree::Primary(3),
TokenTree::Infix('/'),
TokenTree::Prefix('!'),
TokenTree::Primary(2),
TokenTree::Infix('^'),
TokenTree::Primary(4),
TokenTree::Postfix('?'),
TokenTree::Infix('-'),
TokenTree::Primary(1),
];
println!("TokenTree: {:?}", tt);
let expr = ExprParser.parse(&mut tt.into_iter()).unwrap();
println!("Expression: {:?}", expr);
}
测试用例
#[cfg(test)]
mod test {
fn parse(input: &str) -> Expr {
// 假设的解析函数，将输入字符串解析为Expr
unimplemented!()
}
#[test]
fn test1() {
assert_eq!(
parse("1=2=3"),
BinOp(Box::new(Int(1)), Eq, Box::new(Int(2)))
);
}
#[test]
fn test2() {
assert_eq!(
parse("1*2+3"),
BinOp(
Box::new(BinOp(Box::new(Int(1)), Mul, Box::new(Int(2)))),
Add,
Box::new(Int(3))
)
);
}
#[test]
fn test3() {
assert_eq!(
parse("1*!2^3"),
BinOp(
Box::new(Int(1)),
Mul,
Box::new(UnOp(
Not,
Box::new(BinOp(Box::new(Int(2)), Pow, Box::new(Int(3))))
))
)
);
}
#[test]
fn test4() {
assert_eq!(
parse("-1?*!2^3+3/2?-1"),
BinOp(
Box::new(BinOp(
Box::new(BinOp(
Box::new(UnOp(Try, Box::new(UnOp(Neg, Box::new(Int(1)))))),
Mul,
Box::new(UnOp(
Not,
Box::new(BinOp(Box::new(Int(2)), Pow, Box::new(Int(3))))
))
)),
Add,
Box::new(BinOp(
Box::new(Int(3)),
Div,
Box::new(UnOp(Try, Box::new(Int(2))))
))
)),
Sub,
Box::new(Int(1))
)
);
}
}
这个示例展示了如何使用pratt库构建一个完整的表达式解析器，包括处理运算符优先级和结合性。通过实现PrattParser trait，我们可以轻松地定义各种运算符的行为和优先级。
1 回复
Rust语法解析库pratt的使用：高效实现运算符优先级解析算法的表达式解析工具
介绍
pratt是一个Rust实现的Pratt解析器（也称自上而下运算符优先级解析器），专门用于高效解析带有复杂运算符优先级的表达式。它特别适合实现编程语言中的表达式解析、数学公式计算器等场景。
Pratt解析算法的主要优势在于：
- 处理运算符优先级非常高效
- 代码结构清晰简洁
- 容易扩展新的运算符和语法
- 性能优于递归下降解析器
完整示例代码
下面是一个结合了基本使用、自定义解析逻辑和函数调用的完整示例：
use pratt::{Affix, PrattParser, Error, Result};
#[derive(Debug)]
enum Expr {
Number(f64),
Neg(Box<Expr>),
Add(Box<Expr>, Box<Expr>),
Sub(Box<Expr>, Box<Expr>),
Mul(Box<Expr>, Box<Expr>),
Div(Box<Expr>, Box<Expr>),
Pow(Box<Expr>, Box<Expr>),
FuncCall(String, Vec<Expr>),
}
fn main() -> Result<()> {
// 创建Pratt解析器并配置运算符
let parser = PrattParser::new()
// 前缀运算符：负号，优先级90
.op(Affix::prefix("-", 90)?)
// 中缀运算符：加减乘除
.op(Affix::infix("+", 10)?.left())
.op(Affix::infix("-", 10)?.left())
.op(Affix::infix("*", 20)?.left())
.op(Affix::infix("/", 20)?.left())
// 右结合的指数运算
.op(Affix::infix("^", 30)?.right())
// 函数调用处理
.fun("(", ")", 100, &|args| {
let func_name = args[0].as_str().unwrap().to_string();
let params = args[1..].iter()
.map(|arg| match arg.as_f64() {
Some(n) => Ok(Expr::Number(n)),
None => Err(Error::Custom("Invalid function parameter".into())),
})
.collect::<Result<Vec<_>>>()?;
Ok(Expr::FuncCall(func_name, params))
});
// 要解析的表达式
let expr = "-1 + 2 * 3 ^ 4 ^ 5 - sqrt(9) / 3";
// 解析表达式并构建AST
let ast = parser.parse(expr, &|s| {
// 尝试解析为数字，如果不是数字则保留为字符串(可能是函数名)
s.parse::<f64>()
.map(Expr::Number)
.or_else(|_| Ok(Expr::Number(0.0))) // 简单处理，实际应该更复杂的错误处理
})?;
println!("AST: {:#?}", ast);
// 这里可以添加AST求值逻辑
Ok(())
}
代码说明
-
Expr枚举：定义了表达式的各种形式，包括数字、各种运算符和函数调用
-
运算符配置：
- 前缀运算符
-（负号）优先级最高（90） - 中缀运算符按数学常规设置优先级（乘除20，加减10）
- 指数运算
^设置为右结合
- 前缀运算符
-
函数调用处理：
- 使用
.fun()方法处理函数调用语法 - 第一个参数是函数名，后续参数是函数参数
- 使用
-
数值解析：
- 尝试将token解析为f64数字
- 失败时简单返回0（实际应用中应有更健壮的错误处理）
这个示例展示了pratt库的主要功能，包括：
- 运算符优先级和结合性的配置
- 自定义AST节点的构建
- 函数调用的处理
- 基本的错误处理机制
要运行这个示例，请确保Cargo.toml中添加了pratt依赖：
[dependencies]
pratt = "0.2"
