一种新型的Parser方法

Source: Dev.to

引言

Pratt 解析是一种强大的技术，但绑定功率（binding power）和 NUD 等概念可能难以理解。
下面介绍一种替代的解析方法，旨在更简洁，同时提供可比的功能。

总体思路

1. 将表达式标记化，得到一个平铺的项、运算符和分组符号列表。
2. 确定运算符优先级（例如 * 和 / 的优先级高于 + 和 -）。
3. 按照优先级迭代合并相邻项，构建树结构。
4. 在主树构建之前的合并阶段，处理特殊标记类型（如一元与二元运算符、数值字面量、成员访问、函数调用）。

示例

考虑以下表达式：

2 + foo(4, 5) * 4 / 23

标记列表

2, foo(4, 5), *, 4, /, 23, +

树构建

1. 第一遍（乘法）

   • 用 * 合并 foo(4, 5) 与 4 → [foo(4, 5), 4]{*}

2. 第二遍（除法）

   • 用 / 将步骤 1 的结果与 23 合并 → [[foo(4, 5), 4]{*}, 23]{/}

3. 最终遍（加法）

   • 用 + 将 2 与步骤 2 的结果合并 → [2, [[foo(4, 5), 4]{*}, 23]{/}]{+}

生成的 AST（伪代码）

add(
    2,
    divide(
        multiply(
            foo(4, 5),
            4
        ),
        23
    )
)

处理一元/二元运算符和特殊标记

该方法区分了几类核心标记：

合并阶段

在构建 AST 之前，会将相邻标记合并为更高层次的结构：

• 一元负号与其操作数：-u x → -x
• 成员访问：a .m b → a.b
• 带成员访问的函数调用：foo .m bar (c 23, 24 ) → foo.bar(23, 24)

这个小型解析器仅处理函数和少数混合前缀/中缀运算符，剩余的表达式交给主树构建算法处理。

最后说明

合并阶段结束后，解析器在包含项、运算符和分组符号的列表上工作。
对括号的递归解析会生成完整的抽象语法树（AST），随后可用于求值、代码生成或进一步分析。