java开发简单解释器,实现一个简单的解释器（5）

article/2025/7/27 15:32:46

你如何处理和了解像创建解释器或编译器这样复杂的事情？在开始时，一切看上去都像是一团乱七八糟的纱线，你需要解开缠结才能得到完美的球。

到达那里的方法是将它解开一个线，一次解开一个结。不过有时候，你可能会觉得自己听不懂某些内容，但必须继续前进，我向你保证，如果你足够坚持，它最终将“咔嗒”一声被解开。

在理解如何创建解释器和编译器的过程中，最好的建议之一是阅读文章中的解释，阅读代码，然后自己编写代码，甚至在一段时间里编写相同的代码，使你能完全了解材料和代码，然后继续学习新主题。不要着急，只要放慢脚步，花点时间深刻理解基本概念，这种方法虽然看似很慢，但会在未来获得回报。相信我。

最后，最终将获得完美的毛线球，即使不是那么完美，它也比什么也不做或者快速浏览后的几天内忘掉好多了。

请记住：一步步理解这些知识点，并通过编写代码练习所学的知识：

今天，你将使用前几篇文章中获得的知识，学习如何解析和解释具有任意数量的加，减，乘和除运算的算术表达式，你将编写一个解释器，该解释器将能够对"14 + 2 * 3 - 6 / 2"之类的表达式求值。

在深入学习并编写一些代码之前，我们先讨论一下运算符的结合性(associativity)和优先级(associativity)。

按照惯例7 + 3 + 1与(7 + 3)+ 1相同，而7 - 3 - 1相当于(7 - 3)- 1。我们都了解这些。如果我们将7 - 3 - 1视为7 -(3 - 1)，则结果将会意外的变成5，而不是我们预期的3。

在普通算术和大多数编程语言中，加，减，乘和除是左结合(left-associative)的：

7 + 3 + 1 is equivalent to (7 + 3) + 1

- 3 - 1 is equivalent to (7 - 3) - 1

* 4 * 2 is equivalent to (8 * 4) * 2

/ 4 / 2 is equivalent to (8 / 4) / 2

什么是运算符号的左结合性呢？

当表达式7 + 3 + 1中的3之类的操作数在两侧都带有加号时，我们需要约定来确定哪个运算符适用于3，是左边的加号还是右边的加号？我们说运算符加号左结合，是因为在存在两侧都带有加号的操作数时，此时左边的加号适用于此操作数，因此我们说运算符加号是左结合的(The operator + associates to the left because an operand that has plus signs on both sides belongs to the operator to its left and so we say that the operator + is left-associative.)，所以按照结合性惯例，7 + 3 + 1等于(7 + 3)+ 1。

我们再来看7 + 5 * 2这个表达式，在操作数5的两边都有不同类型的运算符，该表达式等于7 +(5 * 2)还是(7 + 5)* 2呢？我们如何解决这种歧义？

在这种情况下，结合性约定对我们没有帮助，因为它仅适用于加减法(+，-)或乘除法(*，/)这种同一类型的运算符。当我们在同一表达式中具有不同种类的运算符时，我们需要另一种约定来解决歧义。我们需要一个定义运算符相对优先级的约定。

我们说如果运算符乘号在加号之前执行其操作数，则乘号具有更高的优先级(higher precedence)。在我们所使用的运算中，乘法和除法的优先级高于加法和减法，所以表达式7 + 5 * 2等效于7 +(5 * 2)，表达式7 - 8 / 4等效于7-(8 / 4)。

在含有优先级相同的运算符的表达式中，我们仅使用结合性约定并从左到右执行运算符：

7 + 3 - 1 is equivalent to (7 + 3) - 1

/ 4 * 2 is equivalent to (8 / 4) * 2

希望你不要因为这些运算符的结合性和优先级而感到无聊，我们可以利用这些约定来构造算术表达式的语法，以显示算术运算符的结合性和优先级，然后，我们可以按照我在第4部分中概述的准则将语法转换为代码，我们的解释器将能够处理运算符的优先级和结合性约定。

这是我们的优先级表(precedence table)：

从表中可以看出，运算符加号和减号具有相同的优先级，并且它们都是左结合的，还可以看到，运算符乘号和除号也是左结合的，它们之间也具有相同的优先级，但是比加减运算符具有更高的优先级。

以下是有关如何根据优先级表构造语法的规则：

1、为每一类优先级定义一个非终结符。非终极符的产生式主体应包含该类优先级的算术运算符和下一类更高优先级的非终结符。( The body of a production for the non-terminal should contain arithmetic operators from that level and non-terminals for the next higher level of precedence.)

2、为基本的表达单位(在本文下为整数)创建一个附加的非终结符factor。一般规则是，如果具有N类优先级，则总共将需要N + 1个非终结符：每类级别一个非终结符(N个)再加上一个运算基本单位的非终结符factor(1个)。(Create an additional non-terminal factor for basic units of expression, in our case, integers. The general rule is that if you have N levels of precedence, you will need N + 1 non-terminals in total: one non-terminal for each level plus one non-terminal for basic units of expression.)

继续！

让我们遵循规则并构建语法。

根据规则1，我们将定义两个非终结符：一个用于级别2的称为expr的非终结符和一个用于级别1的称为term的非终结符，通过规则2，我们将为算术的基本单位定义一个非终结符factor来表达整数。

新语法的起始符号将为expr，expr的产生式将包含一个表示使用级别2的运算符主体，在本例中为加号和减号，并将包含更高级别优先级的非终结符term。

级别2：