基于JavaScript的简单解释器实现(一)——表达式的语法树生成

摘要：语法树这一章主要是完成语法树的生成。其中由于函数声明部分过于简单，没必要生成语法树，打算留到下一章一起处理。主循环结束后数据栈中的第一位元素则为语法树。这是最后生成的语法树总结总之，语法树就算是生成完毕了。

这个系列是关于CodeWars上的一条1Kyu题：Simple Interactive Interpreter。也就是实现一个简单的交互式解释器。
题目地址：http://www.codewars.com/kata/52ffcfa4aff455b3c2000750/train/javascript
github地址：https://github.com/woodensail/SimpleInteractiveInterpreter
本文地址：http://segmentfault.com/a/1190000004044789

11月26日更新：
增加了对左结合运算符的支持。
增加了变量统计功能，用于支持下一步的函数parser
当表达式不符合语法要求时，抛出异常

具体的细节可以参见上面的原题网站，大概的要求如下：
1：支持变量赋值语句

x = 7

2：支持四则运算,表达式中可以使用变量

x = (1 + 2) * y

3：函数声明：

fn add x y => x + y

4：函数调用

z = add a b

5：其他
也就是命名冲突检测，作用域链等，大家自己看吧。

这一章主要是完成语法树的生成。其中由于函数声明部分过于简单，没必要生成语法树，打算留到下一章一起处理。所以只做了表达式的语法树生成。

首先，题目所给的语言结构基本上是前缀表达式和中缀表达式的混杂。所以只需要将语句里面中缀的部分转化为前缀即可得到波兰式。
当然，我为了方便下一步处理还是选择将其进一步转化为语法树的结构。但是实现思路依旧可以参考波兰式生成。

var SPACE = {}, params = [], operatorStack = [], dataStack = [SPACE], expressionFlag = true, lValue, rValue, operator, vars = {};

声明变量：
params 用于存储函数调用的参数，其实这里不需要初始化，但我懒得改了。
operatorStack 运算符栈，用于存储各种操作符
dataStack 存储数据。包括数值，变量以及语法树的节点
expressionFlag 由于改语言中没有逗号，所以没有显式的标志来分割相邻的两个表达式。因此需要自行判断前一个表达式是否结束。
lValue,rValue 类似params, 只不过是给运算符用的，其实可以去掉，但我懒得改。
operator 一个用于存储当前运算符的临时变量

tokens = tokens.slice();
tokens.push(")");
tokens.unshift("(");
while (tokens.length) {
  ……
}
var varList = [];
for (var k in vars) {
    varList.push(k);
}
if (dataStack[0] === SPACE) {
    dataStack.shift();
} else {
    throw "expression error"
}
if (dataStack.length > 1) {
    throw "expression error"
}
return [dataStack[0], varList];

复制token数组，防止修改原始数据。向开头和结尾加上括号，以简化后面的操作。最后就是开始主循环。
主循环结束后数据栈中的第一位元素则为语法树。若数据栈中元素数量多于一个或栈低占位符被取出，说明语句有错。

var next = tokens.pop();

首先取出一个token。需要注意的是这里用的是pop，也就是从后向前扫描。然后根据token类型做不同处理。

1：token为运算符

if (operators[next]) {
    while (true) {
        if (!operatorStack.length) {
            operatorStack.push(next);
            break;
        } else if (operatorStack[operatorStack.length - 1] === ")") {
            operatorStack.push(next);
            break;
        }  else if ((operators[operatorStack[operatorStack.length - 1]] === operators[next] ) && (next !== "=")) {
            operatorStack.push(next);
            break;
        } else if (operators[operatorStack[operatorStack.length - 1]] > operators[next]) {
            operatorStack.push(next);
            break;
        } else {
            operator = operatorStack.pop();
            lValue = dataStack.pop();
            rValue = dataStack.pop();
            dataStack.push([operator, lValue, rValue]);
        }
    }
    expressionFlag = true;
    continue;
}

a:若此时运算符栈为空，则将该运算符入栈。
b:若栈顶运算符为右括号，则将该运算符入栈。
c:若栈顶运算符优先级等于当前运算符且当前运算符不是左结合运算符，则将该运算符入栈。
d:若栈顶运算符优先级小于当前运算符，则将该运算符入栈。
e:若非以上四种情况。则运算符栈出栈存入operator，数据栈出栈两次分别存入lValue,rValue，然后将[operator, lValue, rValue]压入数据栈。并继续循环直到出现前四种情况为止。
前面的循环结束后将expressionFlag设为真，以标志当前表达式未结束。最后调用continue跳过后面的部分。

2：token为左括号

else if (next === "(") {
    next = operatorStack.pop();
    while (next !== ")") {
        if (next === void 0) {
            break
        }
        lValue = dataStack.pop();
        rValue = dataStack.pop();
        dataStack.push([next, lValue, rValue]);
        next = operatorStack.pop();
    }
    continue;
}

持续出栈直到栈顶元素为右括号为止。对于每个出栈的操作符将其存入operator并从数据栈中出栈两次得到lValue和rValue，并将[operator, lValue, rValue]压入数据栈。最后continue跳过后续。

3：expressionFlag的判断

if (expressionFlag) {
    expressionFlag = false;
} else {
    while (operatorStack.length) {
        operator = operatorStack.pop();
        if (operator === ")") {
            operatorStack.push(operator);
            break;
        } else {
            lValue = dataStack.pop();
            rValue = dataStack.pop();
            dataStack.push([operator, lValue, rValue]);
        }
    }
}

若token不是前两种情况，则需要判断expressionFlag。若expressionFlag为真则将其置为假，标准该token处理完后，当前表达式可以结束。
若其为假则说明当前表达式已经结束，需要开始下一个表达式。此时需要将运算符栈重复出栈并与数据栈顶的两位合并后压入数据栈，直到栈顶运算符为右括号为止。

4：token为右括号或其他在函数列表中不存在的内容

if (next === ")") {
    expressionFlag = true;
    operatorStack.push(next);
} else if (!this.functions[next]) {
    if (!this.regexNum.test(next)) {
        vars[next] = 1;
    } else {
        next = Number(next);
    }
    dataStack.push(next);
}

将token入栈，其中若token为右括号，则expressionFlag置真表示表达式未结束。若不为右括号，当next为纯数字时将其转化为Number型，否则在变量表中标记。

5：token在函数表中存在

else {
    params = [next];
    for (var i in this.functions[next].params) {
        params.push(dataStack.pop());
    }
    dataStack.push(params);
}

初始化params并且第一位为当前token。根据函数表中形参的数量，从数据栈中取出同样数量的数据，压入params。
将params压入数据栈

这里用"a*(test q (e+q))-(a+b)/e"做例子来跟踪并展示程序是怎样运行的。
首先tokenize，结果是：

["(","a","*","(","test","q","(","e","+","q",")",")","-","(","a","+","b",")","/","e",")"]

然后开始循环，我会在每个操作的下发依次注明操作完成后的数据栈，运算符栈以及expressionFlag
1：")", 右括号，压入运算符栈。
[] [")"] true
2："e", 非运算符或括号或函数，压入数据栈。
["e"] [")"] false
3："/", 运算符，栈顶为右括号，压入运算符栈。
["e"] [")", "/"] true
4：")", 右括号，压入运算符栈。
["e"] [")", "/", ")"] true
5："b", 非运算符或括号或函数，压入数据栈。
["e", "b"] [")", "/", ")"] false
6："+", 运算符，栈顶为右括号，压入运算符栈。
["e", "b"] [")", "/", ")", "+"] true
7："a", 非运算符或括号或函数，压入数据栈。
["e", "b", "a"] [")", "/", ")", "+"] false
8："a", 左括号，执行运算符出栈操作，直到右括号为止。
["e", ["+","a","b"]] [")", "/"] false
9："-", 运算符，优先级小于栈顶元素，执行运算符出栈操作，然后压入运算符栈。
[["/",["+","a","b"],"e"]] [")", "-"] true
10：")", 右括号，压入运算符栈。
[["/",["+","a","b"],"e"]] [")", "-", ")"] true
11：")", 右括号，压入运算符栈。
[["/",["+","a","b"],"e"]] [")", "-", ")", ")"] true
12："q", 非运算符或括号或函数，压入数据栈。
[["/",["+","a","b"],"e"], "q"] [")", "-", ")", ")"] false
13："+", 运算符，栈顶为右括号，压入运算符栈。
[["/",["+","a","b"],"e"], "q"] [")", "-", ")", ")", "+"] true
14："e", 非运算符或括号或函数，压入数据栈。
[["/",["+","a","b"],"e"], "q", "e"] [")", "-", ")", ")", "+"] false
15："(", 左括号，执行运算符出栈操作，直到右括号为止。
[["/",["+","a","b"],"e"], ["+","e","q"]] [")", "-", ")"] false
16："q", 非运算符或括号或函数，压入数据栈。由于expressionFlag为false，需要提前出栈到右括号为止。
[["/",["+","a","b"],"e"], ["+","e","q"], "q"] [")", "-", ")",] false
17："test", 函数，执行函数出栈程序。由于expressionFlag为false，需要提前出栈到右括号为止。
[["/",["+","a","b"],"e"], ["test","q",["+","e","q"]]] [")", "-", ")"] false
18："(", 左括号，执行运算符出栈操作，直到右括号为止。
[["/",["+","a","b"],"e"], ["test","q",["+","e","q"]]] [")", "-"] false
18："*", 运算符，优先级大于等于栈顶运算符，压入运算符栈。
[["/",["+","a","b"],"e"], ["test","q",["+","e","q"]]] [")", "-", "*"] true
18："a", 非运算符或括号或函数，压入数据栈。
[["/",["+","a","b"],"e"], ["test","q",["+","e","q"]], "a"] [")", "-", "*"] false
18："(", 左括号，执行运算符出栈操作，直到右括号为止。
[["-",["*","a",["test","q",["+","e","q"]]],["/",["+","a","b"],"e"]]] [] false

这是最后生成的语法树：

总之，语法树就算是生成完毕了。上面的代码还有缺陷，主要是没有做异常检查之类的。但是至少对于符合语法的表达式是没什么问题了。下一章会做函数声明的解析和保存。