本篇是算术是表达式解析系列文章之一。

系列前篇：

建议先阅读上篇，本篇不重复介绍一些基本的概念。

本篇中，大量跟上篇相同代码实现，考虑到篇幅，这里也不再重复给出。

本篇将使用跟上一篇相似的方式，采用递归下降的方式来解析语法。但是对于优先级的处理，将直接从文法层面做处理。这种方式，从学习和理解的角度上来讲，可能会更简单一些。不过在性能方面，会更差一些。

实际上，这系列三篇中介绍的方法，性能方面，是降序排列的。

文法

上一篇中，用了递归下降来解析表达式的语法。

而解析语法的依据，则是我们定制的文法。这就好比如我们的自然语言，也要依照语法规则来组织单词，才能成句一样的道理。

英文有英文的语法规则，中文有中文的语法规则，同样，我们的表达式语言中，也对应着一套规则。

在本篇中，我们的表达式对应的文法大致如下（表示方法并不严谨）：

1
<表达式> = <加减表达式>
2
<加减表达式> = <乘除模表达式><加减表达式尾部>
3
<加减表达式尾部> = <加减运算符><乘除模表达式><加减表达式尾部> | ε
4
<加减运算符> = + | -
5
<乘除模表达式> = <指数表达式><乘除模表达式尾部>
6
<乘除模表达式尾部> = <乘除模运算符><指数表达式><乘除模表达式尾部> | ε
7
<乘除模运算符> = * | / | %
8
<指数表达式> = <取负表达式><指数表达式尾部>
9
<指数表达式尾部> = <指数运算符><取负表达式><指数表达式尾部> | ε
10
<指数运算符> = ^
11
<取负表达式> = <负运算符><主表达式> | <主表达式>
12
<负运算符> = -
13
<主表达式> = (<表达式>) | <数字字面量>
14
<数字字面量> = {1|2|3|4|5|6|7|8|9}

大体上，可以将 = 读作 “由…组成” ，尖括号围绕的代表某种语法成分，| 代表或，ε 代表空。

代码实现中，将会按照这个文法，从上往下调用对应的解析方法。

实现

先看 Parser 的实现代码，再解释。

重点关注 parseExpr 之后的代码，之前部分跟上篇的一致。
代码中，各个子程序入口，都注释上了对应的文法规则。

1
class Parser {
2
  tokenSteam: TokenStream
3

4
  constructor(src: string) {
5
    this.tokenSteam = new TokenStream(src)
6
  }
7

8
  // 抛出语法错误
9
  raiseSyntaxError(start: Position, end: Position, message?: string) {
10
    throw new Error(`Syntax error(${start.row},${start.col}-${end.row},${end.col})${message ? ': ' + message : ''}`)
11
  }
12

13
  // 抛出语义错误
14
  raiseSemanticError(start: Position, end: Position, message?: string) {
15
    throw new Error(`Semantic error(${start.row},${start.col}-${end.row},${end.col})${message ? ': ' + message : ''}`)
16
  }
17

18
  // 读取当前的 Token
19
  peek() {
20
    return this.tokenSteam.peek()
21
  }
22

23
  // 读取下一个 Token
24
  next() {
25
    return this.tokenSteam.next()
26
  }
27

28
  // 消耗一个 Token
29
  consume() {
30
    this.tokenSteam.junk()
31
  }
32

33
  // 检查目标 Token 是否指定的运算符
34
  isOperator(token?: Token, value?: string) {
35
    if (!token || !value) return false
36
    return token.kind === TokenType.Operator && token.value === value
37
  }
38

39
  // 检查指定 Token 是否指定的分解符
40
  isPunctuator(token?: Token, value?: string) {
41
    if (!token || !value) return false
42
    return token.kind === TokenType.Punctuator && token.value === value
43
  }
44

45
  // <表达式> = <加减表达式>
46
  parseExpr(): Ast {
47
    return this.parseAddExpr()
48
  }
49

50
  // <加减表达式> = <乘除模表达式><加减表达式尾部>
51
  parseAddExpr() {
52
    const lhs = this.parseMulExpr()
53
    return this.parseAddTail(lhs)
54
  }
55

56
  // <加减表达式尾部> = <加减运算符><乘除模表达式><加减法尾部> | ε
57
  parseAddTail(lhs) {
58
    const op = this.peek()
59
    // 如果是加减号开头，则说明就是加减法运算
60
    // 解析出右操作数，返回一个二元表达式结点
61
    if (this.isOperator(op, '+') || this.isOperator(op, '-')) {
62
      this.consume()
63
      const rhs = this.parseMulExpr()
64
      const node = Ast.createNode(AstType.BinaryExpression, {
65
        left: lhs,
66
        right: rhs,
67
        op: {
68
          kind: TokenType.Operator,
69
          start: op.start,
70
          end: op.end,
71
          value: op.value,
72
        }
73
      })
74
      // node 整体作为左操作数
75
      return this.parseAddTail(node)
76
    }
77
    // 否则对应空的情况，直接返回左侧结点
78
    return lhs
79
  }
80

81
  // <乘除模表达式> = <指数表达式><乘除模表达式尾部>
82
  parseMulExpr() {
83
    const lhs = this.parseExpExpr()
84
    return this.parseMulTail(lhs)
85
  }
86

87
  // <乘除模尾部> = <乘除模运算符><指数表达式><乘除模表达式尾部> | ε
88
  parseMulTail(lhs) {
89
    const op = this.peek()
90
    // 如果是乘除号开头，说明就是乘除法
91
    // 解析出右操作数，返回一个二元表达式结点
92
    if (this.isOperator(op, '*') || this.isOperator(op, '/')) {
93
      this.consume()
94
      const rhs = this.parseExpExpr()
95
      const node = Ast.createNode(AstType.BinaryExpression, {
96
        left: lhs,
97
        right: rhs,
98
        op: {
99
          kind: TokenType.Operator,
100
          start: op.start,
101
          end: op.end,
102
          value: op.value,
103
        }
104
      })
105
      // node 整体作为左操作数
106
      return this.parseMulTail(node)
107
    }
108
    // 否则对应空的情况，直接返回左侧结点
109
    return lhs
110
  }
111

112
  // <指数表达式> = <取负表达式><指数表达式尾部>
113
  parseExpExpr() {
114
    const lhs = this.parseNegExpr()
115
    return this.parseExpTail(lhs)
116
  }
117

118
  // <指数表达式尾部> = <指数运算符><取负表达式><指数表达式尾部> | ε
119
  parseExpTail(lhs) {
120
    const op = this.peek()
121
    // 如果是脱号开头，说明是指数运算
122
    // 解析出右操作数，返回一个二元表达式结点
123
    if (this.isOperator(op, '^')) {
124
      this.consume()
125
      // 注意，指数运算我们规定为右结合，所以：
126
      // 1. operand 可能作为 op 的右操作数
127
      // 2. operand 可能跟后面紧跟着出现的 `^` 右结合，然后整体作为 op 的右操作数
128
      const operand = this.parseNegExpr()
129
      // 处理右结合
130
      const rhs = this.parseExpTail(operand)
131
      return Ast.createNode(AstType.BinaryExpression, {
132
        left: lhs,
133
        right: rhs,
134
        op: {
135
          kind: TokenType.Operator,
136
          start: op.start,
137
          end: op.end,
138
          value: op.value,
139
        }
140
      })
141
    }
142
    // 否则对应空的情况，直接返回左侧结点
143
    return lhs
144
  }
145

146
  // <取负表达式> = <负运算符><主表达式>|<主表达式>
147
  parseNegExpr() {
148
    const op = this.peek()
149
    if (this.isOperator(op, '-')) {
150
      this.consume()
151
      const argument = this.parsePrimaryExpr()
152
      const prefix = true
153
      return Ast.createNode(AstType.UnaryExpression, {
154
        prefix: true,
155
        op: {
156
          kind: TokenType.Operator,
157
          start: op.start,
158
          end: op.end,
159
          value: op.value,
160
        },
161
        argument
162
      })
163
    }
164
    return this.parsePrimaryExpr()
165
  }
166

167
  // <主表达式> = "("<表达式>")" | <数字>
168
  parsePrimaryExpr(): Ast {
169
    const token = this.peek()
170

171
    // 括号表达式
172
    if (this.isPunctuator(token, '(')) {
173
      this.consume()
174
      // 括号里面可能还是一个表达式
175
      const expression = this.parseExpr()
176

177
      // 必须存在关闭的括号，否则就是括号不匹配的语法错误
178
      const closingParen = this.peek()
179
      if (!this.isPunctuator(closingParen, ')')) {
180
        this.raiseSyntaxError(closingParen.start, closingParen.end, `缺失符号 ')'`)
181
      }
182
      this.consume()
183

184
      return expression
185
    }
186

187
    // 数值字面量表达式
188
    if (token.kind === TokenType.Number) {
189
      this.consume()
190
      return Ast.createNode(AstType.Number, {
191
        value: token.value,
192
        start: token.start,
193
        end: token.end
194
      })
195
    }
196

197
    // 全部不匹配，报告语法错误
198
    this.raiseSyntaxError(token.start, token.end, `无效的符号 ${token.value}`)
199
  }
200
}

从 parseExpr() 开始，就跟上一篇的不一样了。对照着代码中注释的文法规则，应该很容易发现，代码实现，完全就是在翻译开头定义的那套文法。

优先级

仔细查看上面的代码，不难发现，我们从优先级最低的加（减）法运算开始，到优先级最高的括号和单个数字字面量结束。

下面展开分析。

首先入口 parseExpr() -> parseAddExpr()，我们最开始解析的是优先级最低的加减法。
在 parseAddExpr() 解析加减法时，左操作数会调用 parseMulExpr() 子程序去解析。而右操作数在 parseAddTail(lhs) 中，也一样的调了 parseMulExpr()。这意味着，我们将整个乘（除、模）法表达式视作一个整体来作为加（减）法的一个操作数。换句话说，乘除模运算总会优先于加减法进行组合，这就是优先级的体现。
同理，用 parseMulExpr() 解析乘除模运算时，其的左右操作数来自于指数运算解析子程序 parseExpExpr()，所以，指数运算的优先级高于乘除模运算。
再同理，指数运算的操作数，来自于一元取负子程序 parseNegExpr()，所以，一元取负的优先级，高于指数运算。
括号表达式被安排在最后，因此它的优先级是高于所有的运算符的，总是被视作一个整体来解析。而数字表达式已经是原子级别了，不能继续细分，跟括号表达式一起处理即可。

结合性

对于左结合，比较简单，看加减乘除模运算的处理代码应该不难理解。

而右结合则比较绕。

仔细查看上面的指数运算解析子程序 parseExpExpr() 的实现，这里针对右结合做了特殊处理。

在遇到 ^ 运算符时，解析出右操作数 operand，此时，我们还不能确定 operand 是否应该作为该 ^ 的右操作数。考虑下面两种情况：

2 ^ 3 * 4
2 ^ 3 ^ 4

其中，情况 1，operand 为 3，右边不是新的 ^ 运算符，所以，不用考虑结合性，可以直接将 operand 跟前面的 ^ 结合即可。

而情况 2，则需要优先将 3 ^ 4 进行结合，然后将结合的结果作为整体在与前面的 2 结合，相当于 2 ^ (3 ^ 4)。并且这种情况是递归的，考虑：2 ^ 3 ^ 4 ^ 5。

所以，在实现上，就必须在返回 Ast 结点之前，先调用 parseExpTail(lhs) 尝试继续组合 ^ 后续的运算符，如果后续没有出现 ^，则会走直接返回的分支，并没有什么副作用。由此就实现了结合性的控制。

延伸

本篇介绍的这种递归下降的表达式解析方式，灵活性非常高，而且比较容易理解。

对于比较复杂文法规则，甚至是上下文有关的文法，都可以用递归下降的方式来手写实现。

我们这里解析算术表达式，其实是杀鸡用牛刀了。就针对我们这里的使用场景，如果要做扩展，只要注意下优先级和结合性就可以了，基本上都可以很轻松做到。

系列文章完。

算术表达式解析系列之文法规则实现优先级

文法

实现

优先级

结合性

延伸