这里说的语法树，其实是指抽象语法树 AST，它描述了一种求值的机器，只要喂参数进去，就可以得到结果了，比如假设如下函数是一台计算机器：

00var add = (a, b) => a + b;

调用 add(1, 2) 可以得到 3 这里的 add 可以看成是一台计算机器。

# S-Expression ↵

S-表达式描述了一种树结构，它是普通表达式的更加一般的形式：

001 + 2 + 3

而 S-表达式 :

00+ 1 2 3

可能S-表达式把运算符提前写在最前面会令人困惑，但事实上这才是最正确的表达式写法，观察：

005 + 2 * 3 + 4

因为 S-表达式的特殊性，不可能会有运算符优先级的概念，所有优先级由括号决定。

00(+ 5 (* 2 3) 4)

括号结构代表运算优先级使得S-表达式具有描述递归层级结构的能力，而且解析起来也比解析普通表达式容易的多。

而且，这种递归结构完全对应一棵树：（运算符是根结点）

写成 JSON 就是: （运算符是 o 字段，之后跟随的参数用数字从左到右编码）

00var tree = {
01    o: '+', 
02    a: 5, 
03    b: {
04        o: '*', 
05        a: 2, 
06        b: 3
07    },
08    c: 4
09}

我一开始对这种递归结构没有太深刻的体验，直到自己写了 S-表达式运算器之后才发现：

S-表达式里面还有S-表达式
任何一对匹配的括号都是 S-表达式

# S-表达式的递归求值 ↵

一棵 S-表达式 其实就是一台计算机器，递归的对其求值竟然是如此的简单：

00// 假设一个S表达式的参数个数不超过 6 个
01
02var calc = {
03    "*": (a, b) => a * b, 
04    "+": (a, b) => a + b
05}
06
07var eval = tree => {
08    // 如果 tree 不是 S-表达式, 返回 tree 
09    if (typeof tree !== 'object') return tree; 
10
11    // 运算符 
12    var todo = calc[tree.o]; 
13
14    // 没有 o 字段的参数们的键 
15    var keys = Object.keys(tree).filter(key => key !== 'o'); 
16
17    // 键对应的值 即S表达式的参数 
18    var vals = keys.map(e => tree[e]); 
19
20    // 归约递归
21    return vals.reduce((sum, val) => {
22        return todo(sum, eval(val));
23    });
24}

很自然的可以求出结果:

00// tree 是 (+ 5 (* 2 3) 4) 代表的树 
01var res = eval(tree); 
02
03console.log(res); 
04// => 
05// 15

# 运算符拓展 ↵

S-表达式的运算符拓展极为容易：

00var calc = {
01    "*": (a, b) => a * b, 
02    "+": (a, b) => a + b, 
03    "/": (a, b) => a / b
04}

00// (/ 100 2 2)
01var tree = {
02    o: '/', 
03    a: 100, 
04    b: 2, 
05    c: 2
06}
07
08var res = eval(tree); 
09
10console.log(res); 
11// => 
12// 25

S-表达式极其简洁优雅，完美自然，任何的赞美在它面前都显得多余。

# 那模版解释器呢？ ↵

大可以把模版解释器当成计算机器，不过这次它不是对数字处理了，而是对字符串。

原理也是一样，都需要构造语法树，这样求值计算的速度才足够快。

而构造语法树请看下篇详细实现了 tplser