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

系列前篇：

• 算术表达式解析系列之逆波兰表示法
• 算术表达式解析系列之优先级爬升法

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

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

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

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

文法

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

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

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

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

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

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

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

实现

其实第一次听说 transducer 的概念，是在某个周末时间学习 Clojure 的时候。 一开始觉得概念很复杂，因此就没有深入了解，内部的实现机制并不清楚。

直到后来尝试写一个 JavaScript 的函数式编程的函数库时，才做了一番功课去研究。

本文就是记录我对学习过程的思考和结果。

我们不讲概念，而是从一个简单的问题开始。

问题

假设你现在在检查上个月的开支清单，里面的条目大概如下：

1
const list = [
2
  { type: '早餐', amount: 12 },
3
  { type: '午餐', amount: 18 },
4
  { type: '咖啡', amount: 19 },
5
  { type: '零食', amount: 8 },
6
  { type: '晚餐', amount: 22 },
7
  { type: '水果', amount: 20 },
8
  { type: '早餐', amount: 12 },
9
  { type: '午饭', amount: 20 },
10
  { type: '咖啡', amount: 24 },
11
  { type: '晚饭', amount: 21 },
12
]

如果你现在想知道喝了多少钱的咖啡，按照以往的经验，我们可能会这么做：

1
const filterCoffee = item => item.type === '咖啡'
2
const getAmount = item => item.amount
3
const add = (a, b) => a + b
4

5
list
6
  .filter(filterCoffee)
7
  .map(getAmount)
8
  .reduce(add, 0)
9

10
// 结果为 43

这是一个非常典型的数据处理过程，我们现在来分析，这个过程发生了什么。

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

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

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

下面简单概括下实现：

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

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

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

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

实现 tokenize

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

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

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

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

假如我们有这样的一个需求，接受一个用户录入的算术表达式，解析并计算出结果。

其中，这个表达式中，可以存在：

1. 数，表示参与计算的对象
2. 运算符（可以是自定义的运算符），表示不同的计算
3. 括号，表示对计算顺序的干预

那可以怎么做？

本系列文章，将提供几种不同的解决方案。本篇将介绍一种常见的方案：“逆波兰表示法”。

首先我们先了解一些概念。

中缀表示法

中缀表示法，应该是我们最常接触的算术表示法了。该表示法，操作符位于两个操作数中间，因此而得名。

【例 1】：

1
(10 + 15 - 20) * 30 / 40 ^ 2

这就是一个使用中缀表示法的例子。

在中缀表示法中，括号可以改变一个表达式的计算顺序。

(1 - 1) - 1 和 1 - (1 - 1) 是完全不同的。所以， 1 - 1 - 1 这样的表达式，对于计算机来说，是存在 解析的歧义的，处理起来相对麻烦。

逆波兰表示法

Web Component

写一个 Web Component 很简单，只需要书写一个继承 HTMLElement 的 class 即可，比如我们打算创建一个自定义的按钮元素：

1
class MyButton extends HTMLElement {}

然后为了可以在 HTML 中使用，以及可以使用 document.createElement 来创建元素，我们还需要注册下这个组件，分配一个元素名称。

1
if (!customElements.get('my-button')) {
2
  customElements.define('my-button', MyButton)
3
}

然后试试效果：

1
<my-button>直接在 HTML 中使用</my-button>
2

3
<script>
4
// 或者使用 JavaScript 创建并插入
5
const $p = document.createElement('my-button')
6
$p.innerHTML = '使用 JavaScript 创建并插入'
7
document.body.appendChild($p)
8
</script>

页面上如愿显示出内容：

Shadow DOM

如果只是一个长得不像按钮，光秃秃的自定义元素，那根本就派不上用场。 按钮的功能先不论，首先组件内部总该可以封装自己的内容和样式，这是作为一个组件的最基本的需求之一。 于是，这个时候 Shadow DOM 就可以上场了。

让我们改造下代码，使用 Shadow DOM 为我们的自定义 Button 加上内部 DOM 结构：