上一节我完成了S-表达式的的解析求值，最后完成了 Q 函数来解析 Q-lang

00Q('(+ 1 1)'); 
01// => 2 
02
03Q('(* 2 (+ 3 4))'); 
04// => 14

这一篇主要完成变量的声明和引用，然后去完成基本的作用域。（提到变量就不能回避作用域、提到函数也是如此）

为声明变量引入 let 关键字并期望能这样使用变量：

00Q('((let [x 1]) (+ 1 x))'); 
01// => 2

# 堆栈实现一个作用域 ↵

JavaScript 使用的是词法作用域，遇到变量的时候是从最内层开始寻找，一层一层往外找，直到找到为止。

00var a = 0; 
01
02function findA(){
03    console.log(a); 
04}

比如如果执行上面的 findA 那么 JS引擎将先创建一个新作用域并放置在作用域链的最前端，然后执行函数体，里面需要访问 变量a 就会遍历作用域链从最前端开始查找，直到找到为止，这种作用域叫做词法作用域

Q-lang 也会有作用域，可能选择词法作用域，也可能选择动态作用域（具体见下篇）。

以下是实现

00var scopes = [
01    {   // 最内层是全局对象
02        '+': ap => bp => ap + bp, 
03        '-': as => bs => as - bs,
04        '*': am => bm => am * bm,
05        '/': ad => bd => ad / bd,
06        'doubleSum': a => b => a*2 + b*2,
07        '++': d => d+1,
08        a: 123,
09        f: 0,
10        b: 44
11    },
12    {   // 预设一个函数执行环境
13        a: 12 // 将会覆盖全局变量 
14    }
15];

你可能注意到了，我把 四则运算 放到了全局对象里，而且作为函数引用，因为 四则运算 的本质也是函数比如 (+ 1 1) 实际上就是调用函数 + 把两个 1 作为参数传递进去得到结果。

以下是基本操作

00// 查找 
01var find = key => {
02    let val; 
03
04    if (typeof key === 'number') return key; 
05
06    for (let i = scopes.length - 1; i >= 0; i--){
07        let scope = scopes[i]; 
08
09        if (typeof scope[key] !== 'undefined'){
10            val = scope[key]; 
11            break; 
12        }
13    }
14
15    if (typeof val !== 'undefined') return val 
16    else throw new Error(`${key} is not defined` ); 
17}
18
19// 在当前作用域内声明变量 
20var add = (key, val) => {
21    let top = scopes.pop(); 
22    top[key] = val; 
23    scopes.push(top); 
24}
25
26// 压入一个新作用域 
27var push = () => {
28    scopes.push({
29        // 空 
30    }); 
31}

几个测试用例

00find('a'); 
01// => 12
02
03find('+')(1)(2);  
04// => 3
05
06find('b'); 
07// => 44

# 重写 parseToArr ↵

上一篇讨论过这个，这个可以把 每条语句 的不同部分抽离成一个数组，比如 (+ 1 1) 变成 ["(", "+", "1", "1", ")"]

然而上一篇写的不太好（不能提取出变量名称和关键字），现在重写了

以下是新代码：

00var parseToArr = str => str.split('\t').join(' ').split('').reduce((acc, cur) => {
01    // 这一步 reduce 是对 ()[] 四个字符的两端填充空格
02    // "(+ 1 1)" 将会变成 " ( + 1 1 ) "
03    if (cur === '(' || cur === '['){
04        acc.push(' '); 
05        acc.push(cur); 
06        acc.push(' '); 
07        return acc;
08    } else if (cur === ')' || cur === ']') {
09        acc.push(' '); 
10        acc.push(cur); 
11        acc.push(' '); 
12    } else {
13        acc.push(cur); 
14    }
15
16    return acc; 
17}, []).join('').split(' ').map(ch => {
18    // 利用 .split(' ') 把多余空格去掉
19    // 利用 map 把 数字 parseInt 成 number 而其他字符不动  
20    if (!Number.isNaN(parseInt(ch))){
21        return parseInt(ch); 
22    } else {
23        return ch; 
24    }
25}).filter(e => e !== '' && e!== '\n'); 
26// filter 过滤空字符和回车符 （连续两个以上的空格会变成多个空字符串）
27// 请查看 "           ".split(' ') 的执行结果

简单的测试

00parseToArr('(+ 1 2)'); 
01parseToArr('(+ x 2)'); 
02parseToArr('((let [x 1]) (+ 1 2))');

第二版测试结果

# 重写 _parse ↵

接下来的部分很重要，之前写的 _parse 不能识别 let 关键字现在要改写，而且之前的实现太晦涩，我现在选择了更彻底的递归去求值。

我重新观察了一下 S-表达式 的结构：

最简的 S-表达式形如这样： (函数常数常数…) 常数可以很长也可以没有
也可能是这样 (函数 S-表达式 S-表达式)

因此应该递归的处理 S-表达式：

得到 S-表达式 的直接后代数组 tokens： [函数, 左S, 右S ... ]

然后再递归的处理 左S 右S 得到 AST

以下是具体实现

00var keysTo = [
01    'o', 'a', 'b', 'c', 'd', 'e', 'f', 'g'
02];
03
04// 这里的 arr 需要 parseToArr 的结果 
05var _parse = arr => {
06    var deep = 0; 
07    var temp = []; 
08    var tokens = []; 
09    // 如果 arr 长度为 1 说明是 常数 或者 变量
10    // 直接将其作为 S-表达式 的值返回
11    if (arr.length === 1) return arr[0]; 
12
13    arr.forEach((ch, idx, its) => {
14        if (ch === '(') { 
15            deep ++ ; 
16            if (deep === 2){
17                temp.push(idx); 
18            }
19        } else if (ch === ')') {
20            deep -- ; 
21            if (deep === 1){
22                let pre = temp.pop(); 
23                tokens.push({
24                    from: pre, 
25                    to: idx
26                }); 
27            }
28        } else {
29            // 除了括号 其他都是 标识符 或者 立即数 
30            if (deep === 1){
31                tokens.push({
32                    from: idx, 
33                    to: idx
34                }); 
35            }
36        }
37    }); 
38
39    // tokens 形如： [函数, 左S, 右S ... ] 这样 
40    return tokens.reduce((acc, cur, idx) => {
41        // from to 代表当前S-表达式在 arr的范围 需要用 slice 截取 
42        let block = arr.slice(cur.from, cur.to + 1);
43
44        // 递归的处理 
45        acc[keysTo[idx]] = _parse(block); 
46
47        return acc; 
48    }, Object.create(null)); 
49}
50
51// 封装 
52var parse = str => _parse(parseToArr(str));

引入了 keysTo 做索引可见每一条S-表达式的直接子代的最大长度不能超过 keysTo.length

以下是简单的测试:

00var ast_a = parse('(+ 1 1)'); 
01var ast_b = parse('(+ (* 2 3) 4)');
02var ast_c = parse('(+ (* 2 3) (- 10 5))');
03
04console.log(ast_a);
05console.log(ast_b);
06console.log(ast_c);

测试结果

上面是不带 let关键字 的时候的结果现在我们来测试一下加上关键字之后会是怎么样

parse ((let [x 1]) (+ x 1)) 的结果是：

执行结果

用代码就是如下结果

00{
01    "o": {
02        "o": "let",
03        "a": "[",
04        "b": "x",
05        "c": 1,
06        "d": "]"
07    },
08    "a": {
09        "o": "+",
10        "a": "x",
11        "b": 1
12    }
13}

可以看到原本应该是运算符的 o 被换成 (let [x 1]) 因为这时候在构建 AST 因此不能继续处理，到给 AST 求值的时候再来解析变量声明，并把变量添加到 scopes 上

# 遍历 AST ↵

上一步的操作引入了一些复杂性。不过写个 if 就可以解决。

这个遍历步骤很重要，因此我写了很多注释

以下是我的实现

00// 从语法树得到值 
01// 遍历 
02var calc = tree => {
03    let oType = typeof tree.o;
04
05    if (oType === 'object'){ // 说明该节点不是表达式 而是声明 
06        // 这里修改作用域 
07        // tree.o 原本应该是函数名 应该 typeof 出来是 string 
08        // 这里是 object 说明应该是 let 关键字 
09        // 调用 scopeCalc 去处理作用域 
10        scopeCalc(tree.o); 
11        
12        // 如果存在下一个S-表达式 则继续递归树 
13        if (tree.a) return calc(tree.a);
14    } else if (oType === 'string') {
15        // 以下的代码可能有些晦涩 
16        // 主要是实现多参函数而写的 
17        // 简单的四则运算都是两个参数 都是函数 被定义在全局上 
18        // 但是实际情况中 o 的参数列表可能不只两个 
19        // 因此要把 tokens 第二个元素之后的所有值求出来 再应用到 o 上 
20
21        let o = find(tree.o); 
22
23        // 这段执行完后得到结果是 vals 
24        // vals 的结构类似这样： [函数, 值, 值, 值 .... ] 长度取决于 keysTo.length 
25        // 注意有 .slice(1) 
26        var vals = keysTo.slice(1).filter(key => tree[key]).map((cur, idx, its) => {
27            // 取出键名 比如 tree.a tree.b 等等 
28            let t = tree[cur]
29                // is_ns: t 是数字或者变量吗？ 
30              , is_ns = typeof t === 'number' || typeof t === 'string'
31                // its 是这样的： ['a', 'b', 'c', 'd' .... ] 
32                // 这里从tree取出 tree.a tree.b 这些 
33              , keyInTree = tree[its[idx]]
34
35            return is_ns ? find(keyInTree) : calc(keyInTree); 
36        }); 
37
38        // 从这里可以看出一个一个参数的传递 
39        // 换言之 Q-lang 只接受柯里化的函数 
40
41        return vals.reduce((acc, val) => {
42            return acc(val); 
43        }, o); 
44    }
45}

可以看到我把变量作用域的动态修改放到 scopeCalc 里

以下是 scopeCalc 的实现

00var scopeCalc = todo => {
01    // p 是参数列表 比如这样 x 1 y 2
02    // 注意 slice(1) 
03    var p = keysTo.slice(1).reduce((acc, cur) => {
04        if (todo[cur]) acc.push(todo[cur]); 
05        
06        return acc; 
07    }, []).filter(e => e !== '[' && e !== ']'); 
08    // 而且过滤掉 [ 和 ] 
09
10    // 如果标识符是 let 
11    if (todo.o === 'let') {
12        p.forEach((item, idx, its) => {
13            // 偶数是变量名 奇数是值 
14            if (idx % 2 === 0){ 
15                let key = item
16                  , val = its[idx + 1]; 
17
18                // 添加到作用域上 
19                // key键 val值
20                add(key, val); 
21            }
22        })
23    }
24}

以下是测试用例：

00var a = Q('((let [x 4]) (+ 1 x))'); 
01var b = Q('((let [y 4 z 1]) (+ y z))'); 
02var c = Q(`
03    (
04        (let [a 4 b 1]) 
05        (+ a b))
06`); 
07
08console.log(a); 
09console.log(b); 
10console.log(c);
11 
12// 再引用一个不存在的变量
13Q('(+ XXX 2)');

测试结果

可以看到 a b c 都是期望的 5 而且引用不存在的变量会 报错

# 下一步做什么 ↵

尽管可以使用变量了，但是我并没有写出 销毁作用域 的代码，因为没有函数调用和函数声明，这些作用域操作显得不那么重要。

因此限于篇幅，准备下一篇实现 函数 和 较为完善的作用域

( 本次写的代码都已注入本页面打开浏览器 F12 即可使用 Q )