摘要：語法樹這一章主要是完成語法樹的生成。其中由于函數聲明部分過于簡單，沒必要生成語法樹，打算留到下一章一起處理。主循環結束后數據棧中的第一位元素則為語法樹。這是最后生成的語法樹總結總之，語法樹就算是生成完畢了。

這個系列是關于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

這是最后生成的語法樹：

總之，語法樹就算是生成完畢了。上面的代碼還有缺陷，主要是沒有做異常檢查之類的。但是至少對于符合語法的表達式是沒什么問題了。下一章會做函數聲明的解析和保存。