本篇是算术是表达式解析系列文章之一，上篇：算术表达式解析系列之逆波兰表示法

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

再这篇文章里面，将介绍一种完全不同的解决方案，Precedence Climbing Method，下称优先级攀爬算法。这种算法，在手写一些表达式解析器的时候，经常会使用。

下面简单概括下实现：

解析录入的原始字符串，输出 token 流
逐个读取 token，根据算符不同，执行不同的操作

下面开始实现，代码使用 ts 做演示。

目标跟上一篇的相似，提供一样的运算符，不过再几个方面做了强化：

数值支持更多的形式，例如： 10, -10, 0.5e2 等等等等
提供完整的 Tokenize 实现，直接录入原始表达式字符串，即可运算出结果
提供更友好的错误提示，包括指示出错误出现的行号列号

实现 tokenize

tokenize 是将原始字符串录入，转换成一个个 token 的过程。

转换成 token 的目的，是为了简化后续的处理步骤。

实现 tokenize 有很多方法，这里使用手工实现，遍历读取字符进行分析。

首先实现一个简单的流抽象类，用于后续读取原始输入和 tokens。

流

1
abstract class Stream<T> {
2
  // 当前流过的位置
3
  private _count = 0
4

5
  get count() {
6
    return this._count
7
  }
8

9
  set count(n: number) {
10
    this._count = n
11
  }
12

13
  /**
14
   * 获取缓冲数据抽象方法
15
   */
16
  abstract buffer(): any
17

18
  /**
19
   * 是否流干
20
   */
21
  drained(): boolean {
22
    return this.peek() == null
23
  }
24

25
  /**
26
   * 流到下一个元素
27
   */
28
  junk(): void {
29
    this.count += 1
30
  }
31

32
  /**
33
   * 流到下一个元素，返回当前元素
34
   */
35
  next(): T {
36
    const e = this.peek()
37
    if (e != null) this.junk()
38
    return e
39
  }
40

41
  /**
42
   * 当前元素
43
   */
44
  peek(): T {
45
    return this.buffer()[this.count]
46
  }
47

48
  /**
49
   * 读 N 个元素（不移动当前位置）
50
   * @param n
51
   */
52
  npeek(n: number): T[] {
53
    const count = this.count
54
    const list = []
55
    while (n--) {
56
      list.push(this.next())
57
    }
58
    this.count = count
59
    return list
60
  }
61
}

实现一个字符流，接受表达式源码，返回一个流对象，方便管理对字符的读取。

1
class CharStream extends Stream<string> {
2
  // 字符缓冲
3
  private _buffer: string
4
  // 当前行号
5
  private _row = 0
6
  // 当前列号
7
  private _col = 0
8

9
  constructor(buffer: string) {
10
    super()
11
    this._buffer = buffer || ''
12
  }
13

14
  get row() {
15
    return this._row
16
  }
17

18
  get col() {
19
    return this._col
20
  }
21

22
  /**
23
   * @override
24
   */
25
  buffer(): string {
26
    return this._buffer
27
  }
28

29
  /**
30
   * @override
31
   */
32
  npeek(n: number): string[] {
33
    const { row, col } = this
34
    const chars = super.npeek(n)
35
    this._row = row
36
    this._col = col
37
    return chars
38
  }
39

40
  /**
41
   * @override
42
   */
43
  junk(): void {
44
    super.junk()
45
    if (this.peek() === '\n') {
46
      this._row += 1
47
      this._col = 0
48
    }
49
    else {
50
      this._col += 1
51
    }
52
  }
53

54
  /**
55
   * 在当前位置开始的子串中，执行正则匹配
56
   */
57
  execRegExp(regexp: RegExp, n?: number) {
58
    return regexp.exec(this._buffer.substr(this.count, n))
59
  }
60
}

接着，根据我们的需要，定义一批 Token 的类型。我们目前只需要三类 Token，分别为数字、操作符、分界符。

1
const enum TokenType {
2
  Number = 'Number',
3
  Operator = 'Operator',
4
  Punctuator = 'Punctuator',
5
}

确定类型之后，就可以实现一个 Token 类用来存储解析过程遇到的各种类型的单词信息。

我们计划在 Token 中存记录以下信息：

类型，即 TokenType
Token 位于原始表达式输入的起始位置，用于出错时，友好地提示。
token 的值是什么。

根据这些要求，我们写出以下代码：

1
// 原始输入的表达式的位置
2
interface Position {
3
  row: number
4
  col: number
5
}
6

7
// Token 的实例化参数
8
interface TokenOptions {
9
  kind: TokenType
10
  start: Position
11
  end: Position
12
  value?: string
13
}
14

15
// 类实现
16
class Token {
17
  kind: TokenType
18
  start: Position
19
  end: Position
20
  value?: string
21
  constructor({ kind, value, start, end }: TokenOptions) {
22
    Object.assign(this, { kind, value, start, end })
23
  }
24
}

有了以上准备后，我们就可以着手开始 Token 流的实现了，使用统一的抽象方式，简化后续的处理。

1
// 工具函数，检查输入的字符是否数字
2
const isDigit(char) => /^[0-9]/.test(char)
3

4
// 类实现
5
class TokenStream extends Stream<Token> {
6
  private _buffer: any = []
7
  private _srcStream: CharStream
8

9
  constructor(source: string) {
10
    super()
11
    this._srcStream = new CharStream(source.trim())
12
  }
13

14
  /**
15
   * @override
16
   */
17
  buffer(): Token[] {
18
    return this._buffer
19
  }
20

21
  /**
22
   * @override
23
   */
24
  peek() {
25
    while (this.buffer().length <= this.count && !this._srcStream.drained()) {
26
      this.force()
27
    }
28
    return super.peek()
29
  }
30

31
  // 获取当前读取到的字符所处的位置
32
  pos() {
33
    return {
34
      row: this._srcStream.row,
35
      col: this._srcStream.col
36
    }
37
  }
38

39
  // 抛出词法错误
40
  raiseLexicalError(message?: string) {
41
    const { row, col } = this.pos()
42
    throw new Error(`Lexical error(${row}, ${col})${message ? ': ' + message : ''}`)
43
  }
44

45
  // 原始输入中，往前推进 n 个字符
46
  srcJunk(n = 1) {
47
    while (n--) {
48
      this._srcStream.junk()
49
    }
50
  }
51

52
  // 从原始输入流中解析出下一个 token
53
  force() {
54
    if (this._srcStream.drained()) return null
55

56
    while (!this._srcStream.drained()) {
57
      const start = this.pos()
58
      const ch = this._srcStream.peek()
59

60
      // 读取到空格或换行，此处直接移除
61
      if (ch === '\n' || ch === ' ') {
62
        this.srcJunk()
63
        continue
64
      }
65

66
      // 读取到数字或小数点，说明这是一个数字 token 的开始
67
      if (isDigit(ch) || ch === '.') {
68
        const number = this.slurpNumber()
69
        if (!number) this.raiseLexicalError('invalid number')
70
        const end = this.pos()
71
        const token = new Token({ kind: TokenType.Number, value: number, start, end })
72
        this._buffer.push(token)
73
        return token
74
      }
75

76
      // 分界符，“(”，“)” 用于分组
77
      if (['(', ')'].includes(ch)) {
78
        this.srcJunk()
79
        const end = this.pos()
80
        const token = new Token({ kind: TokenType.Punctuator, value: ch, start, end })
81
        this._buffer.push(token)
82
        return token
83
      }
84

85
      // 二元运算符
86
      if (['+', '-', '*', '/', '%', '^'].includes(ch)) {
87
        this.srcJunk()
88
        const end = this.pos()
89
        const token = new Token({ kind: TokenType.Operator, value: ch, start, end })
90
        this._buffer.push(token)
91
        return token
92
      }
93

94
      this.raiseLexicalError('无效的符号')
95
    }
96
  }
97

98
  // 尝试提取数字
99
  maybeNumber() {
100
    const reg = /^\d+\.\d+(?:e[\+\-]?\d+)?|^\d+\.?(?:e[\+\-]?\d+)?|^\.\d+(?:e[\+\-]?\d+)?/i
101
    const matched = this._srcStream.execRegExp(reg)
102
    const number = matched ? matched[0] : ''
103
    return number
104
  }
105

106
  // 从原始输入流中，提取数字
107
  slurpNumber() {
108
    const number = this.maybeNumber()
109
    if (!number) this.raiseLexicalError()
110
    this.srcJunk(number.length)
111
    return number
112
  }
113
}

通过上面的实现代码，我们做到了每一次调用 next() 方法，就能自动读取出下一个 token。

如此一来，我们就可以将 Tokenize 的动作，整合进语法分析的过程之中，而无需做一遍词法分析的独立过程。

语法分析

在这之前，需要先定义好运算符的优先级和结合性。

1
const Precedence = Object.freeze({ L1: 1, L2: 2, L3: 3 })
2
const enum Associativity { Left, Right }

我们此处的实现，只有三个优先级。而结合性，只存在左结合和右结合之分。

然后开始定义我们希望支持的运算符，指定它们的优先级和结合性。

1
// 二元运算符优先级以及结合性
2
const BINARY_OP_INFO = Object.freeze({
3
  // 加减
4
  '+': [Precedence.L1, Associativity.Left],
5
  '-': [Precedence.L1, Associativity.Left],
6

7
  // 乘除
8
  '*': [Precedence.L2, Associativity.Left],
9
  '/': [Precedence.L2, Associativity.Left],
10
  '%': [Precedence.L2, Associativity.Left],
11

12
  // 指数运算
13
  '^': [Precedence.L3, Associativity.Left],
14
})

定制好运算符后，就可以准备实现语法分析类。语法分析类，接受一个原始表达式字符串作为输入，生成对应的语法分析器对象。执行对象上的分析逻辑，即可输出该表达式的 AST。

所以，我们还得准备下，先定义好必要的 AST 结点。

首先是结点的类型定义，我们使用一个枚举来定义。

1
const enum AstType {
2
  Number = 'Number',
3
  BinaryExpression = 'BinaryExpr',
4
  UnaryExpression = 'UnaryExpr',
5
}

可能存在三种结点，分别是

数字
二元表达式
一元表达式（负数，例如 -1）

然后实现 AST 节点类。

1
class Ast {
2
  kind: AstType
3
  [key: string]: any
4

5
  static createNode(kind, options) {
6
    return new Ast(kind, options)
7
  }
8

9
  constructor(kind, options) {
10
    this.kind = kind
11
    Object.assign(this, options)
12
  }
13
}

现在，万事俱备，不欠东风，可以开始分析语法了。下面使用递归下降的方式手写一个简单的语法分析器。关于二元运算符的的优先级和结合性的处理，重点关注 parseBinaryExpr() 方法中的注释。

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
    const expression = this.parseBinaryExpr(Precedence.L1)
48
    return expression
49
  }
50

51
  // 解析二元表达式
52
  parseBinaryExpr(minPrec): Ast {
53
    let lhs = this.parseUnaryExpr()
54

55
    // 此处使用优先级攀爬（Precedence climbing）算法处理二元表达式
56
    while (true) {
57
      // 读取当前 Token，假设是运算符
58
      let op = this.peek()
59

60
      // 若读取到的 Token 为空，或者运算符定义中找不到，或新运算符的优先级达不到要求的最低优先级
61
      // 则不再与后续的运算符结合，结束本次循环，直接返回当前已经组装的 ast 子树
62
      if (!op || !BINARY_OP_INFO[op.value] || BINARY_OP_INFO[op.value][0] < minPrec) {
63
        return lhs
64
      }
65

66
      // 获取运算符的优先级和结合性，算出递归调用时传入的最小优先级数值
67
      // 此处是关键点，通过指定最小优先级，解决不同优先级运算符的结合情况
68
      // 而右结合的情况，也通过 `+1` 巧妙地转换成优先级一样的处理逻辑了
69
      const [prec, assoc] = BINARY_OP_INFO[op.value]
70
      const nextMinPrec = assoc === Associativity.Left ? prec + 1 : prec
71

72
      // 消耗掉当前的 token，并准备下一个 token，用于下轮递归
73
      this.consume()
74
      const rhs = this.parseBinaryExpr(nextMinPrec, isArgComma)
75

76
      // 使用新值更新 lhs
77
      lhs = Ast.createNode(AstType.BinaryExpression, {
78
        op: {
79
          kind: TokenType.Operator,
80
          start: op.start,
81
          end: op.end,
82
          value: op.value,
83
        },
84
        left: lhs,
85
        right: rhs
86
      })
87
    }
88
  }
89

90
  // 处理一元表达式，即处理一元取负运算符
91
  parseUnaryExpr(): Ast {
92
    const op = this.peek()
93
    if (this.isOperator(op, '-')) {
94
      this.consume()
95
      const argument = this.parsePrimaryExpr()
96
      return Ast.createNode(AstType.UnaryExpression, {
97
        prefix: true,
98
        op: {
99
          kind: TokenType.Operator,
100
          start: op.start,
101
          end: op.end,
102
          value: op.value,
103
        },
104
        argument
105
      })
106
    }
107
    return this.parsePrimaryExpr()
108
  }
109

110
  // 处理主表达式，包括数字这种不可再细分的语法成分。而括号分组也在此处视作一个整体对待。
111
  parsePrimaryExpr(): Ast {
112
    const token = this.peek()
113

114
    // 括号表达式
115
    if (this.isPunctuator(token, '(')) {
116
      this.consume()
117
      // 括号里面可能还是一个表达式
118
      const expression = this.parseExpr()
119

120
      // 必须存在关闭的括号，否则就是括号不匹配的语法错误
121
      const closingParen = this.peek()
122
      if (!this.isPunctuator(closingParen, ')')) {
123
        this.raiseSyntaxError(closingParen.start, closingParen.end, `缺失符号 ')'`)
124
      }
125
      this.consume()
126

127
      return expression
128
    }
129

130
    // 数值字面量表达式
131
    if (token.kind === TokenType.Number) {
132
      this.consume()
133
      return Ast.createNode(AstType.Number, {
134
        value: token.value,
135
        start: token.start,
136
        end: token.end
137
      })
138
    }
139

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

上面 100 多行的代码，即可实现我们这个简单的解析器的工作。使用方式如下：

1
const parser = new Parser('1+1')
2
const ast = parser.parseExpr()
3
// ast 即为目标抽象语法树，数据结构大概如下：
4
//
5
// {
6
//   "kind": "BinaryExpr",
7
//   "op": {
8
//     "kind": "Operator",
9
//     "start": {
10
//       "row": 0,
11
//       "col": 1
12
//     },
13
//     "end": {
14
//       "row": 0,
15
//       "col": 2
16
//     },
17
//     "value": "+"
18
//   },
19
//   "left": {
20
//     "kind": "Number",
21
//     "value": "1",
22
//     "start": {
23
//       "row": 0,
24
//       "col": 0
25
//     },
26
//     "end": {
27
//       "row": 0,
28
//       "col": 1
29
//     }
30
//   },
31
//   "right": {
32
//     "kind": "Number",
33
//     "value": "1",
34
//     "start": {
35
//       "row": 0,
36
//       "col": 2
37
//     },
38
//     "end": {
39
//       "row": 0,
40
//       "col": 3
41
//     }
42
//   }
43
//  }
44
//

实现了 AST 输出之后，即可实现计算逻辑，这部分就非常简单了，就是树遍历的过程。

注，在我们的例子中 AST 的生成其实不是必须的，在分析的过程中，已经可以执行相应的计算语义了。

下面给出一个简单的计算方法实现。

先定义一个运行时库，包含各种运算符的计算逻辑

1
const runtime = {
2
  operators: {
3
    '+': (a: number, b: number) => a + b,
4
    '-': (a: number, b: number) => a - b,
5
    '*': (a: number, b: number) => a * b,
6
    '/': (a: number, b: number) => a / b,
7
    '%': (a: number, b: number) => a % b,
8
    '^': (a: number, b: number) => Math.pow(a, b),
9
    'neg': (a: number) => -a,
10
  }
11
}

接着实现树遍历计算即可。

1
function evaluateAst(ast: Ast) {
2
  switch (ast.kind) {
3
    // 二元表达式
4
    case AstType.BinaryExpression: {
5
      // 提取运行时中的操作方法
6
      const calc = runtime.operators[ast.op.value]
7
      // 递归计算出左操作数
8
      const lhs = evaluateAst(ast.left)
9
      // 递归计算出右操作数
10
      const rhs = evaluateAst(ast.right)
11
      // 返回计算结果
12
      return calc(lhs, rhs)
13
    }
14

15
    // 一元表达式
16
    case AstType.UnaryExpression: {
17
      const arg = evaluateAst(ast.argument)
18
      return runtime.operators.neg(arg)
19
    }
20

21
    // 数字字面量，直接字符串转数字即可
22
    case AstType.Number: {
23
      return JSON.parse(ast.value)
24
    }
25
  }
26
}

综合上面所有的实现，最终可以封装一个计算 API，提供给外部使用。

1
function evaluate(src: string) {
2
  return evaluateAst(new Parser(src).parseExpr())
3
}

调用

1
evaluate('(10 + 15 - 20) * 30 / 40 ^ 2')
2
// 输出：0.09375

跟上一篇的方法，完全一样的输出。

下篇预告

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

算术表达式解析系列之优先级爬升法

实现 tokenize

流

语法分析

下篇预告