在Python中如何实现运算符优先级？

Question

假设我想写一种比较简单的编程语言，我想实现一些运算，比如 2 + 3 * 2 = 8。

那么，通常我们应该怎么做呢？

Answer 1

你需要为你那个相对简单的编程语言写一个解析器。如果你想用Python来做这件事，可以先看看Ned Batchelder的博客文章，标题是Python解析工具。

Answer 2

我不太确定你想了解多少细节，但听起来你是想实现一个解析器。通常有两个步骤：

词法分析器会读取文本并把它转换成“标记”。比如，它可能会读取“2 + 3 * 2”，然后把它转换成 INTEGER PLUS INTEGER STAR INTEGER。

语法分析器则会读取这些标记，并尝试把它们与一些规则匹配。比如，你可能会有这样的规则：

Expr := Sum | Product | INTEGER;
Sum := Expr PLUS Expr;
Product := Expr STAR Expr;

它会读取标记，并尝试应用规则，使得起始规则与读取到的标记相对应。在这个例子中，它可能会这样做：

Expr := Sum
Expr := Expr PLUS Expr
Expr := INTEGER(2) PLUS Expr
Expr := INTEGER(2) PLUS Product
Expr := INTEGER(2) PLUS Expr STAR Expr
Expr := INTEGER(2) PLUS Integer(3) STAR Expr
Expr := INTEGER(2) PLUS Integer(3) STAR Integer(2)

解析器有很多种类型。在这个例子中，我是从左到右读取的，并从最初的表达式开始，一直处理到把所有内容都替换成标记为止，所以这就是一个 LL解析器。在进行替换的过程中，它可以生成一个抽象语法树，用来表示数据。这个树可能看起来像这样：

你可以看到，乘法规则是加法规则的子节点，所以乘法会先进行：2 + (3 * 2)。如果这个表达式以不同的方式解析，我们可能会得到这样的树：

现在我们计算的是 (2 + 3) * 2。这完全取决于解析器生成树的方式。

---

如果你真的想解析表达式，可能不想手动编写解析器。现在有解析器生成器，它们会根据一个配置（叫做语法），类似于我上面用的那种，自动生成实际的解析器代码。解析器生成器允许你指定哪个规则应该优先，比如：

Expr := Sum | Product | INTEGER;
Sum := Expr PLUS Expr; [2]
Product := Expr STAR Expr; [1]

我把乘法规则标记为优先级1，加法标记为优先级2，所以在选择时，生成的解析器会优先处理乘法。你也可以设计语法本身，使优先级内置（这是一种更常见的方法）。比如：

Expr := Sum | INTEGER;
Sum := Expr PLUS Product;
Product := Term STAR INTEGER;

这会强制乘法在抽象语法树中位于加法之下。自然，这种语法是非常有限的（例如，它无法匹配 2 * 3 + 2），但可以编写一个全面的语法，仍然能自动嵌入操作顺序。