Lobsters | 📄 原文链接 | 2026-10-27 收录

把 Pratt 解析写成笔记:从调度场算法的显式栈走到调用栈

来源:unix.dog — 2026-10-25

📋 概述

作者想给 C 表达式写一个解析器,先从更简单的调度场算法入手:一个输出流加一个运算符栈,按绑定力决定压栈还是先弹出更高优先级的运算符,尾递归地把中缀式转成后缀式。问题在于它不可扩展——没有递归意义上的子表达式概念,加括号就得给右括号特判,一元运算符、右结合、变参函数都会把逻辑搅乱。Pratt 解析的关键一跃就是把显式运算符栈换成调用栈:只在进入子表达式时嵌套调用,而不是每一级优先级都套一层函数。

🔑 核心要点

💡 金句

the most mainstream mention I know of it is in crafting interpreters
← 返回 Lobsters 首页