热搜：编程 Python Microsoft 编程语言 C++

Rust如何实现一个表达式Parser小结

发布时间：2024-03-18 19:26:29 来源：互联网

.

正文在 src lib rs 补上一个函数和一个 smoke test, 如下 pub use traversal::{eval, format};pub f

正文

在 src/lib.rs 补上一个函数和一个 smoke test, 如下

pub use traversal::{eval, format};

pub fn build_ast(expr: &str) -> Result<Node, String> {
    let root = syntax(lex(expr)?)?;
    Ok(root)
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn smoke() {
        let expr = "1*2+(3/(4+(-5)))";
        let ast = build_ast(expr).unwrap();

        assert_eq!(-1, eval(&ast));
        assert_eq!("1 * 2 + 3 / (4 + (-5))", format(&ast));
    }
}
复制代码

lexer

Lexer 模块主要围绕 DFA 展开讲了很多, 具体实现的时候其实并没有那么复杂, 主要是需要设计好存储结构, 并理解清楚状态转移表的含义

parser

Parser 模块大部分篇幅都在讲文法和 Parser Combinator, 最后真正实现的时候反而非常简单, 这里有两点需要注意

文法的处理
- 处理优先级
- 消除左递归
Parser Combinator 的封装和设计理念

Parser Combinator 只是一种工具而已, 同类型的还有 Parser Generator, 由于笔者接触不多, 就不好展开讲了

不过这里个人认为, 比起 Parser Combinator 本身, 他的设计理念更值得关注, 尤其是这种相对比较小众的函数式编程思维, 个人觉得很有意思

traversal

Traversal 模块最主要的就是访问者模式了, 根据我查到的资料来看, 普通的 AST 基本只有这一种遍历方式

借助访问者模式, 将所有的 visitor 单独抽离进行实现, 代码可读性和耦合度得到了很大的优化, 笔者最开始其实是希望实现一个最最最简化的表达式解析器, 因此第一版并没有引入访问者模式, 而在实现最后的两个需求时发现代码完全耦合在一起实在很恶心, 就干脆加进来了, 反正遍历 AST 基本逃不掉这个访问者模式