基于JavaScript的簡單解釋器實(shí)現(xiàn)(一)——表達(dá)式的語法樹生成

DataPipeline 發(fā)布于2019-08-19 17:06 / 535人閱讀

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

前言

這個系列是關(guān)于CodeWars上的一條1Kyu題：Simple Interactive Interpreter。也就是實(shí)現(xiàn)一個簡單的交互式解釋器。
題目地址：http://www.codewars.com/kata/52ffcfa4aff455b3c2000750/train/javascript
github地址：https://github.com/woodensail/SimpleInteractiveInterpreter
本文地址：http://segmentfault.com/a/1190000004044789

補(bǔ)充

11月26日更新：
增加了對左結(jié)合運(yùn)算符的支持。
增加了變量統(tǒng)計(jì)功能，用于支持下一步的函數(shù)parser
當(dāng)表達(dá)式不符合語法要求時，拋出異常

實(shí)現(xiàn)要求

具體的細(xì)節(jié)可以參見上面的原題網(wǎng)站，大概的要求如下：
1：支持變量賦值語句

x = 7

2：支持四則運(yùn)算,表達(dá)式中可以使用變量

x = (1 + 2) * y

3：函數(shù)聲明：

fn add x y => x + y

4：函數(shù)調(diào)用

z = add a b

5：其他
也就是命名沖突檢測，作用域鏈等，大家自己看吧。

語法樹

這一章主要是完成語法樹的生成。其中由于函數(shù)聲明部分過于簡單，沒必要生成語法樹，打算留到下一章一起處理。所以只做了表達(dá)式的語法樹生成。

首先，題目所給的語言結(jié)構(gòu)基本上是前綴表達(dá)式和中綴表達(dá)式的混雜。所以只需要將語句里面中綴的部分轉(zhuǎn)化為前綴即可得到波蘭式。
當(dāng)然，我為了方便下一步處理還是選擇將其進(jìn)一步轉(zhuǎn)化為語法樹的結(jié)構(gòu)。但是實(shí)現(xiàn)思路依舊可以參考波蘭式生成。

準(zhǔn)備工作

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

聲明變量：
params 用于存儲函數(shù)調(diào)用的參數(shù)，其實(shí)這里不需要初始化，但我懶得改了。
operatorStack 運(yùn)算符棧，用于存儲各種操作符
dataStack 存儲數(shù)據(jù)。包括數(shù)值，變量以及語法樹的節(jié)點(diǎn)
expressionFlag 由于改語言中沒有逗號，所以沒有顯式的標(biāo)志來分割相鄰的兩個表達(dá)式。因此需要自行判斷前一個表達(dá)式是否結(jié)束。
lValue,rValue 類似params, 只不過是給運(yùn)算符用的，其實(shí)可以去掉，但我懶得改。
operator 一個用于存儲當(dāng)前運(yùn)算符的臨時變量

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];

復(fù)制token數(shù)組，防止修改原始數(shù)據(jù)。向開頭和結(jié)尾加上括號，以簡化后面的操作。最后就是開始主循環(huán)。
主循環(huán)結(jié)束后數(shù)據(jù)棧中的第一位元素則為語法樹。若數(shù)據(jù)棧中元素數(shù)量多于一個或棧低占位符被取出，說明語句有錯。

主循環(huán)

var next = tokens.pop();

首先取出一個token。需要注意的是這里用的是pop，也就是從后向前掃描。然后根據(jù)token類型做不同處理。

1：token為運(yùn)算符

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:若此時運(yùn)算符棧為空，則將該運(yùn)算符入棧。
b:若棧頂運(yùn)算符為右括號，則將該運(yùn)算符入棧。
c:若棧頂運(yùn)算符優(yōu)先級等于當(dāng)前運(yùn)算符且當(dāng)前運(yùn)算符不是左結(jié)合運(yùn)算符，則將該運(yùn)算符入棧。
d:若棧頂運(yùn)算符優(yōu)先級小于當(dāng)前運(yùn)算符，則將該運(yùn)算符入棧。
e:若非以上四種情況。則運(yùn)算符棧出棧存入operator，數(shù)據(jù)棧出棧兩次分別存入lValue,rValue，然后將[operator, lValue, rValue]壓入數(shù)據(jù)棧。并繼續(xù)循環(huán)直到出現(xiàn)前四種情況為止。
前面的循環(huán)結(jié)束后將expressionFlag設(shè)為真，以標(biāo)志當(dāng)前表達(dá)式未結(jié)束。最后調(diào)用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;
}

持續(xù)出棧直到棧頂元素為右括號為止。對于每個出棧的操作符將其存入operator并從數(shù)據(jù)棧中出棧兩次得到lValue和rValue，并將[operator, lValue, rValue]壓入數(shù)據(jù)棧。最后continue跳過后續(xù)。

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為真則將其置為假，標(biāo)準(zhǔn)該token處理完后，當(dāng)前表達(dá)式可以結(jié)束。
若其為假則說明當(dāng)前表達(dá)式已經(jīng)結(jié)束，需要開始下一個表達(dá)式。此時需要將運(yùn)算符棧重復(fù)出棧并與數(shù)據(jù)棧頂?shù)膬晌缓喜⒑髩喝霐?shù)據(jù)棧，直到棧頂運(yùn)算符為右括號為止。

4：token為右括號或其他在函數(shù)列表中不存在的內(nèi)容

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置真表示表達(dá)式未結(jié)束。若不為右括號，當(dāng)next為純數(shù)字時將其轉(zhuǎn)化為Number型，否則在變量表中標(biāo)記。

5：token在函數(shù)表中存在

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

初始化params并且第一位為當(dāng)前token。根據(jù)函數(shù)表中形參的數(shù)量，從數(shù)據(jù)棧中取出同樣數(shù)量的數(shù)據(jù)，壓入params。
將params壓入數(shù)據(jù)棧

運(yùn)行分析：

這里用"a*(test q (e+q))-(a+b)/e"做例子來跟蹤并展示程序是怎樣運(yùn)行的。
首先tokenize，結(jié)果是：

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

然后開始循環(huán)，我會在每個操作的下發(fā)依次注明操作完成后的數(shù)據(jù)棧，運(yùn)算符棧以及expressionFlag
1：")", 右括號，壓入運(yùn)算符棧。
[] [")"] true
2："e", 非運(yùn)算符或括號或函數(shù)，壓入數(shù)據(jù)棧。
["e"] [")"] false
3："/", 運(yùn)算符，棧頂為右括號，壓入運(yùn)算符棧。
["e"] [")", "/"] true
4：")", 右括號，壓入運(yùn)算符棧。
["e"] [")", "/", ")"] true
5："b", 非運(yùn)算符或括號或函數(shù)，壓入數(shù)據(jù)棧。
["e", "b"] [")", "/", ")"] false
6："+", 運(yùn)算符，棧頂為右括號，壓入運(yùn)算符棧。
["e", "b"] [")", "/", ")", "+"] true
7："a", 非運(yùn)算符或括號或函數(shù)，壓入數(shù)據(jù)棧。
["e", "b", "a"] [")", "/", ")", "+"] false
8："a", 左括號，執(zhí)行運(yùn)算符出棧操作，直到右括號為止。
["e", ["+","a","b"]] [")", "/"] false
9："-", 運(yùn)算符，優(yōu)先級小于棧頂元素，執(zhí)行運(yùn)算符出棧操作，然后壓入運(yùn)算符棧。
[["/",["+","a","b"],"e"]] [")", "-"] true
10：")", 右括號，壓入運(yùn)算符棧。
[["/",["+","a","b"],"e"]] [")", "-", ")"] true
11：")", 右括號，壓入運(yùn)算符棧。
[["/",["+","a","b"],"e"]] [")", "-", ")", ")"] true
12："q", 非運(yùn)算符或括號或函數(shù)，壓入數(shù)據(jù)棧。
[["/",["+","a","b"],"e"], "q"] [")", "-", ")", ")"] false
13："+", 運(yùn)算符，棧頂為右括號，壓入運(yùn)算符棧。
[["/",["+","a","b"],"e"], "q"] [")", "-", ")", ")", "+"] true
14："e", 非運(yùn)算符或括號或函數(shù)，壓入數(shù)據(jù)棧。
[["/",["+","a","b"],"e"], "q", "e"] [")", "-", ")", ")", "+"] false
15："(", 左括號，執(zhí)行運(yùn)算符出棧操作，直到右括號為止。
[["/",["+","a","b"],"e"], ["+","e","q"]] [")", "-", ")"] false
16："q", 非運(yùn)算符或括號或函數(shù)，壓入數(shù)據(jù)棧。由于expressionFlag為false，需要提前出棧到右括號為止。
[["/",["+","a","b"],"e"], ["+","e","q"], "q"] [")", "-", ")",] false
17："test", 函數(shù)，執(zhí)行函數(shù)出棧程序。由于expressionFlag為false，需要提前出棧到右括號為止。
[["/",["+","a","b"],"e"], ["test","q",["+","e","q"]]] [")", "-", ")"] false
18："(", 左括號，執(zhí)行運(yùn)算符出棧操作，直到右括號為止。
[["/",["+","a","b"],"e"], ["test","q",["+","e","q"]]] [")", "-"] false
18："*", 運(yùn)算符，優(yōu)先級大于等于棧頂運(yùn)算符，壓入運(yùn)算符棧。
[["/",["+","a","b"],"e"], ["test","q",["+","e","q"]]] [")", "-", "*"] true
18："a", 非運(yùn)算符或括號或函數(shù)，壓入數(shù)據(jù)棧。
[["/",["+","a","b"],"e"], ["test","q",["+","e","q"]], "a"] [")", "-", "*"] false
18："(", 左括號，執(zhí)行運(yùn)算符出棧操作，直到右括號為止。
[["-",["*","a",["test","q",["+","e","q"]]],["/",["+","a","b"],"e"]]] [] false