2 * 3 + 4
,我们会得到类似下面的输出:2 * (3 + 4)
,而表达式 2 * 3 + 4
的结构应为:2 * 3 + 4
对应的结构图发现,具有较高优先级的表达式(*
),将作为较低优先级的表达式(+
)的操作数,即子节点。而是什么造就了图中的层次结构呢?就是我们的语法,语法规则和其待展开项,经过我们的 Top-Down 解析器的解析,就会体现为父子节点的关系。num > "*/" > "+-"
,因此我们可以得到:A = expr
α = "+" term
β = term
parseExpr
和 parseTerm
的内容差不多,所以我们理解一下 parseExpr
的实现内容:let left = this.parseTerm()
对应 expr
规则的最左边第一个非终结符的解析+
或 -
+
或 -
,我们就调用 parseTerm
来解析运算符右边的子节点1 + 2 - 3
,解析后的结构为:2 * 3 + 4
,我们会得到下面的输出:**
,这个运算符就是 JS 中的指数运算符。该运算符含有两个字符,而我们目前的运算符还只是单个字符,除了这点不同之外,它还具有比 */
运算符更高的优先级。**
运算符的优先级为 15
,而 */
的优先级为 14
。因此为了在语法中包含这个运算规则,我们需要将现有的规则修改成如下的形式:parseExpo
方法,并将 parseTerm
中原本调用 parseFactor
的地方替换为 parseExpo
,而在 parseExpo
中,我们调用 parseFactor
。这些修改都是一一对应了我们的语法规则的变动。2 ** 3 ** 4
,我们会得到下面的输出:(2 ** 3) ** 4
。但是我们知道,在 JS 中,表达式 2 ** 3 ** 4
实际上等于 2 ** (3 ** 4)
,大家动手试一试。a OP b OP c
而言:OP
相同,即具有相同的优先级,此时我们需要考虑 OP
的结合性OP
为左结合的,那么 b
将先和左边的 a
一起,执行 OP
运算,运算的结果再和 c
一起,做右边的 OP
运算。OP
为右结合的,那么 b
将先和右边的 c
一起,执行 OP
运算,运算的结果再和 a
一起,做左边的 OP
运算。a ** b ** c ** d
,对应的结构应为:parseExpo
进行修改,以解析具有右结合性的操作符 **
。+
当做右结合性来解析的结果。为什么能有这样的效果,我们来看当时的语法:parseExpr1
方法中,对于右边节点的处理,总是调用 parseExpr
:parseExpr
内部,它先读取一个操作数,然后将其作为参数继续调用 parseExpr1
,在未来某一时刻 parseExpr1
返回时,此前被传入的操作数,成为了返回的节点的左边子节点;这样的间接递归形式,使得所有的操作数都和它右边的操作符结合到了一起,刚好符合了我们需要对右结合性的处理需求。**
处理方法修改成:node.right = this.parseExpo();
,我们将原本 parseFactor
换成了 parseExpo
。虽然我们这里使用的是直接递归,但是不必担心,我们在 parseExpo
中总是会先读取 factor,从而消耗掉一部分输入,因此不会陷入无限循环。2 ** 3 ** 4 ** 5
。我们可以得到下面的输出:1 + 2 ** 3 * 5
。我们可以得到下面的输出: