Rust实现一个表达式Parser小结

正文

在 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 基本逃不掉这个访问者模式

说在最后

个人感觉很多内容其实都讲的有遗漏或者有不规范的地方, 但是整个编译领域, 光入门的理论知识就太多太多了, 况且笔者只是自己写了个玩具, 而且几乎是个纯编译前端的项目, 也不敢说入门了, 因此就权当是学习笔记的分享了

源码中有大量注释, 个人感觉结合着看会更加清晰, 可以看一下, 在这里可以看