开启 WSL 功能

依次进入： 控制面板 > 程序 > 程序和功能

在左侧栏中，找到“启用或关闭 Windows 功能”，点击打开新窗口

在新窗口（Windows 功能）中，拉到最下面，找到“适用于 Linux 的 Windows 子系统”，并勾选上。

确定，稍等片刻就启用完毕。

然后重启电脑。

接着打开应用商店，搜索 “WSL”。

在搜索结果中，找到喜欢的 Linux 发行版，安装。

比如安装的是 Ubuntu 18.04 lts，那么完成后，就可以找到 Ubuntu 这个应用图标。可以用于打开一个 Bash 和 Ubuntu 交互。

配置好源（如清华的 TUNA 源）后（注意选对系统版本），就可以愉快地安装各类环境了。

至此，第一部分准备工作完成。

在开发函数式工具库的过程，引发了对于参数数量的一些思考，本篇博客只是随意发散写写。

map 的参数数量

看一个经典的例子：

1
['123', '123'].map(parseInt)
2
// [123, NaN]

原因在于，map 的回调，会传入三个参数，而 parseInt 函数的签名为 parseInt(string, radix)，第二个参数 radix 为一个 2 ~ 36 之间的基数，代表以什么进制去解析第一个参数 string，而一旦无法解析，则会返回 NaN。这个例子中，map 第二个 123 时，传入 parseInt 的参数为 ('123', 1, ['123', '123'])，所以返回的结果就出乎意料了。

解决这种问题，有两种思路。

第一种，多一层拦截，限制传入 parseInt 的参数。

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

系列前篇：

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

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

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

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

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

文法

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

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

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

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

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。