如何用Chumsky组合子写出完整的表达式解析器：Savage parse.rs 源码深度解析

如何用Chumsky组合子写出完整的表达式解析器Savage parse.rs 源码深度解析【免费下载链接】savageA primitive computer algebra system项目地址: https://gitcode.com/gh_mirrors/sa/savageSavage 是一个用纯 Rust 编写的开源计算机代数系统它的表达式解析器仅用约 250 行代码就完整支持了运算符优先级、递归嵌套、函数调用、向量与矩阵。本文带你逐层拆解 parse.rs 的实现思路帮你快速掌握用 Chumsky 组合子编写 Rust 表达式解析器的核心技巧。 先认识一下 Savage 这个项目Savage 追求三个目标按优先级排序正确性、简洁性、易用性。整个系统编译后是一个无运行时依赖、仅 2.5 MB 的可执行文件。它目前提供任意精度整数、有理数、复数运算符号表达式的输入、简化与求值一等公民的向量与矩阵元素可以是任意表达式带语法高亮、多行输入的 REPL 交互环境基于宏的函数定义系统整个项目由三个 crate 组成解析器的全部逻辑集中在 savage_core/src/parse.rs 中解析产出的表达式树定义在 savage_core/src/expression.rs依赖声明见 savage_core/Cargo.toml其中chumsky 0.8.0就是解析器的发动机。 为什么表达式解析器适合用 Chumsky 写手写递归下降解析器代码冗长且容易出错而 Yacc/Bison 类工具需要额外工具链。Chumsky 是一种组合子解析器库它的核心思想是把匹配一个字符当作最小零件然后用声明式的方式一层层拼装出完整语法。作者也提到对比了当时所有 Rust 解析器库后Chumsky 的 API 最直观见 README.md 致谢部分。理解 parse.rs 之前先认识几个最核心的组合子组合子作用直白理解just(a)匹配指定字符这里必须有个 aor依次尝试取第一个成功的先试这个不行再试那个chain()两个解析器顺序拼接先匹配前者再接后者then()顺序匹配并返回元组两者都要结果一起给我separated_by(,)逗号分隔的列表解析 a, b, c 这样的序列delimited_by((, ))加左右定界符外面包一层括号padded()自动跳过空白空格随便写不影响repeated()重复 0 次或多次有就一直匹配or_not()让前面的内容可选有更好没有也行recursive()声明递归解析器语法可以套自己 核心架构9 层优先级一层套一层parse.rs 最聪明的地方是用9 个优先级层次组织了整个文法每一层包裹前一层从最原子到最宽松依次是层由内到外解析的语法源码位置1. atomic_expression变量、数字、向量/矩阵、括号表达式parse.rs#L82-L872. function_or_elementf(a, b)函数调用、v[i]、m[i, j]取值parse.rs#L89-L1283. power^乘方右结合parse.rs#L130-L1414. negation一元-、逻辑非!parse.rs#L143-L1505. product_or_quotient_or_remainder*、/、%左结合parse.rs#L152-L1686. sum_or_difference、-左结合parse.rs#L170-L1847. comparison、!、、、、parse.rs#L186-L2108. conjunctionparse.rs#L212-L2229. disjunction\|\|parse.rs#L224-L234这个结构直接复刻了数学的运算优先级1 2 / 3中加法层第 6 层先整体看到1 …右侧再交给乘除层第 5 层解析出2 / 3——优先级天然体现在谁包裹谁里不需要任何额外的优先级计算。每一层还都加了.labelled(power)这样的标签解析失败时错误信息会指向具体是哪一层出了问题对调试非常友好。 逐层精读5 个关键技巧1️⃣ 小数解析or_not()的妙用let number text::int(10) .chain(just(.).ignore_then(text::digits(10)).or_not())先匹配整数部分然后小数点小数部分整体是可选的or_not()。更妙的是后面的映射1.5不会存成浮点数而是精确的有理数 3/2分子15、分母10再约分100.000则直接是 100/1。解析器和任意精度运算在这里完美衔接。2️⃣ 无限嵌套括号recursive()一招解决括号可以无限套娃(((a)))。如果不用递归你得写 100 层才能支持 100 层嵌套。Chumsky 的recursive()让解析器引用自己.or(expression.clone().delimited_by(just((), just())))整个 parser() 函数 就包在一个recursive里。测试用例中专门用 0~20 层嵌套的括号做验证parse.rs#L388-L396。顺带一提CHANGELOG.md 里记录了早期版本曾修复过解析器的指数级爆炸问题这也是学习递归文法设计时的经典坑。3️⃣ 左结合运算foldl左折叠1 / 2 / 3应该等于(1/2)/3而不是1/(2/3)这靠左结合实现.then(just(*).or(just(/)).or(just(%)).then(negation).repeated()) .foldl(|a, (operator, b)| match operator { * a * b, / a / b, % a % b, _ unreachable!(), })repeated()收集到[(/, 2), (/, 3)]这样的操作符序列foldl从左往右逐个折叠结合方式自动正确。加法和比较层都是同一套路。4️⃣ 右结合运算.rev().reduce反向归约乘方是右结合的1^2^3应等于1^(2^3)。实现与左结合相反——把序列反转后再归约function_or_element .separated_by(just(^)) .at_least(1) .map(|expressions| { expressions.into_iter().rev().reduce(|a, b| pow(b, a)).unwrap() })左结合用foldl、右结合用rev().reduce两行代码就是两种结合性的全部秘密非常值得记住。5️⃣ 函数调用还是元素访问一个or搞定f(a, b)、v[1]、m[2, 3]长得都很像源码用两个可选分支 or区分括号分支任意个参数 → 构造函数调用f()空参也合法方括号分支at_least(1).at_most(2)限制 1~2 个下标 → 1 个下标是向量元素2 个是矩阵元素都不匹配时.or_not()兜底原子表达式就原样保留。测试里f(g(a), h(b))这种嵌套调用、(f g)(a)这种表达式再调用都能正确解析parse.rs#L268-L284。另外向量/矩阵共用一套方括号语法parse.rs#L53-L80[1, 2, 3]是向量如果每个元素本身是等长的向量就自动升级成矩阵[[1, 2], [3, 4]]即 2×2 矩阵。 解析之后一棵表达式树parse.rs 的产出是 expression.rs 中的Expression枚举共 23 个变体Variable、Sum、Difference、Product、Power、Vector、Matrix、And等。例如1 2 / 3解析为Sum(1, Quotient(2, 3))。之后 evaluate.rs 负责求值变量可赋值、错误如除零有专门类型simplify.rs 负责代数化简——解析、求值、化简各司其职模块边界清晰。 动手跑起来最快体验路径克隆仓库后一条命令即可运行 REPLgit clone https://gitcode.com/gh_mirrors/sa/savage cargo run --manifest-path savage/Cargo.toml试几条最能体现解析器功力的输入in: 1.1 ^ 100 out: 13780.612339822270184118337172089636776264331200038466433146477552154985209... in: [[1, 2], [3, 4]] * [5, 6] out: [17, 39] in: 1 ^ 2 ^ 3 out: 65536在 Rust 程序里当库用时更简单FromStr实现parse.rs#L240-L246让你一行搞定a b.parse::Expression()。 进阶彩蛋解析器如何驱动 REPL 多行输入REPL 的 input.rs 把解析器用出了花输入按回车时先尝试解析如果错误原因是意外到达输入末尾ErrorReason::Unexpected就说明用户还没写完比如括号没闭合于是自动等待续行同时它还做语法高亮和括号匹配提示。一个解析器同时服务了解析、校验、高亮三件事。✅ 全文总结Savage 的 parse.rs 是一份极佳的组合子解析器入门范本核心经验浓缩为 4 条用层级包裹表达优先级9 层结构谁包谁谁就后算零额外逻辑用recursive()表达嵌套括号、函数调用无限嵌套一行解决用foldl/rev().reduce区分结合性左结合、右结合各有两行公式用oror_not()处理可选语法小数部分、参数列表、下标都是可选的。建议阅读顺序先看上文优先级总表 → 精读原子层与数字层 → 对比左/右结合两处实现 → 最后看 REPL 的复用方式。读完这一个文件你就具备了为任何计算器、DSL 或编程语言写出表达式解析器的能力。【免费下载链接】savageA primitive computer algebra system项目地址: https://gitcode.com/gh_mirrors/sa/savage创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考