前置基礎(chǔ)知識點
Febit Wit 簡介 -- 慣例吹牛時間
Wit 是我 2013 年開始開發(fā)的一個準 JVM 上的語言, 起初的定位是模板引擎,之后慢慢發(fā)現(xiàn), 在語法上可以做的更強大, 于是現(xiàn)在成了一個準腳本引擎.
Wit 語法類似 JavaScript, 在設(shè)計的時候也參考了許多. 另外, 他還支持自定義函數(shù)，全局變量徘六，Lambda 表達式. 因為是當初并沒有把他產(chǎn)品化, 只是將它作為一個與國內(nèi)某開源作者較勁的產(chǎn)物, 每次覺得那些設(shè)計不合適就殘忍地大改. 由此, 自認為這是一個, 核心模塊輕巧，無第三方依賴赊舶，的個人代表作. (
以至于每次發(fā)布都會炫耀一下這個 Jar 包才 310 KB
Wit 采用BSD開源協(xié)議, 托管在 Github, [我是傳送門], Star 少的可憐, 大家多多支持
Show Time
(旁白君: 主演怯(tou)場(lan), 此段跳過, 大家可以移步往期回顧(并沒有) , 或者看看這里有什么好東西 --> wit-toys
語言? 太遠! 先實現(xiàn)個表達式
我們先來看一下 a + b, 計算過程可分為三步:
- 從 a 的地址取實際值 A
- 從 b 的地址取實際值 B
- 執(zhí)行加法運算返回
現(xiàn)在復(fù)雜一點兒, 我們看一下 a + b + 10, 多了一個操作, 且多了新的類型--直接量,歸一化一下,其實可以轉(zhuǎn)換成(a+b) + 10, 在已知條件下, 可以拆解成三步:
- 調(diào)用已知步驟, 得到
(a+b)的結(jié)果 - 取直接量 1 (為什么要取出來? 就像我們切菜, 所有的操作都是要放到砧板上來的)
- 執(zhí)行 "砧板" 上兩個數(shù)的運算, 把結(jié)果返回
好了, 現(xiàn)在問題稍微復(fù)雜一點兒, 我們來擴充到四則運算, 2 * a + b / 3 + 10, 這里涉及到操作符優(yōu)先級, 相信大家都能畫出來一個處理這個表達式的數(shù)形結(jié)構(gòu)
現(xiàn)在我們繼續(xù)嘗試一下歸一化, 上面的可以抽象成兩個概念:
表達式 (Expression, expr): a, b, 1, (a+b), (2 * a), (2 * a + b / 3).... 等等,他們在一個數(shù)中, 都是為他的更上層提供一個最終結(jié)果, 無論是取內(nèi)存取值, 還是加載一個直接量, 或者是某種上層不關(guān)心的操作
操作符(operator, oper): 就像例子中的提到的四則運算, 可以認為是對給定數(shù)據(jù)的一種算法
現(xiàn)在, 我們用 + 指代其他類似操作符, 以上表達式, 無非不過 expr + expr, 如果繼續(xù)擴充的話,
除此之外 = 也可以看成操作符, 只不過它對左邊的表達式要求更高, 必須是一個可賦值的, 如地址引用, 數(shù)組的某個位置, Map 的某個索引位置
因此, 賦值也可以寫成鏈式:
a = b = (c = 1) + 1, 或者if(flag = !disabled) { ... }, 只不過大多數(shù)規(guī)范都不建議這么寫
操作符還根據(jù)需要的數(shù)據(jù)的數(shù)量分, 單目叹螟、二目暂氯、三目運算符..., 就像參數(shù)傳參, 可以傳不同數(shù)量的參數(shù),
單目操作符 如: 取負, 取反, 取非,自增, 自減 等.
二目操作符 較常見
user.name // 屬性操作符
arr[i] // 數(shù)組操作符
a + b // 部分運算符
說到 三目運算符, 必須得舉一個特殊的例子: 條件運算符 exprA ? exprB : exprC , 這個和前面的不同, 不是將三個表達式都算出來之后傳給操作符, 實際的邏輯是:
- 取 exprA 計算值 A
- 如果 A 為真, 執(zhí)行 exprB 并返回結(jié)果
- 否則執(zhí)行并返回 exprC 的結(jié)果
簡單說,就是根據(jù) exprA 的結(jié)果選擇執(zhí)行 exprB 還是 exprC, 其中, 只有一個分支能得到執(zhí)行的機會
當然 exprA 如果拋異常了, 或者中斷退出了, 例如
System.exit(1), 兩者都不執(zhí)行
// 錯誤理解
var A = exprA() // 副作用 A'
var B = exprB() // 副作用 B'
var C = exprC() // 副作用 C'
if(A){
return B
} else {
return C
}
// 實際等價
var A = exprA() // 副作用 A'
if(A){
return exprB() // 副作用 B'
} else {
return exprC() // 副作用 C'
}
最后, 還有個容易被大家忽視的概念, 操作符的結(jié)合性, 這是個擴中內(nèi)容, 也就是大部分常見操作符都是自左向右結(jié)合的, 但有些相反, 是自右向左
還是以條件運算符 exprA ? exprB : exprC
對于 A ? B : C ? D : E 到底是 (A ? B : C) ? D : E 還是 A ? B : (C ? D : E)
"a" ? "b" : "c"
// -> "b"
("a" ? "b" : "c") ? "d" : "e"
// -> "d"
"a" ? "b" : ( "c" ? "d" : "e")
// -> "b"
"a" ? "b" : "c" ? "d" : "e"
// -> "b"
// 結(jié)論: 自右向左
其他的自右向左的操作符我們這里不再展開, 大家可以很容易搜到相關(guān)文章
語句(Statement) 的列表構(gòu)成語法樹
一段能改變上線文的獨立的邏輯, 即產(chǎn)生了副作用, 就可以認為是 語句
一些 表達式 都可以在完結(jié)時產(chǎn)生副作用, 即使丟棄返回值, 這也是語句的一種 -- 表達式語句
像直接量和一些簡單的運算, 都不會產(chǎn)生副作用, 通常都不能當做語句
// 非法語句
1;
1 + 2;
a + b;
arr[1];
// 合法語句: 存在副作用
i ++;
a = 1;
func();
arr[1] ++;
// 非法: 最外層操作不具有副作用
a + func();
除此之外還有一些特殊語法類型的語句,
// 變量聲明
var a, b, c;
var d, e = 1; // 聲明 + 賦值表達式
var [f, g] = [1, 2]; // 聲明 + 賦值表達式
// 控制語法
if(flag) { <語句列表> }
for(var i : arr) { <語句列表>}
while(flag) { <語句列表>}
switch(a) { <語句列表> }
// 語法糖
arr = [1, 2, 3, a + b ];
map = {
id, // 只提供現(xiàn)有的變量名, 取名作為key, 取值作為值, 等同于 map["id"] = id
1 : "a", // 直接量作為 key
[ -1-1 ] : "e", // 表達式作為 key, 使用 [] 內(nèi)的表達式的結(jié)果作為key, 等同于 map[-1-1] = "e"
"x-y-z" : "XYZ", // 支持最后一個元素冗余逗號
};
// 其他特殊語法
{ <語句列表> } // 代碼塊
new_list = native new java.util.ArrayList(); // 導(dǎo)入 java 函數(shù)引用
接下來, 我們看一下一個 demo 的語法樹的全貌
var map = {
id: "9527",
"my name": "Wit",
[101] : 1,
[102] : 2,
[111] : 11
};
var func;
var flag = 0;
func = function(val){
flag ++;
if(true){
echo "aaaa";
return;
}
echo val != "inner";
echo "\n";
return null;
};
不盡興的的話, 大家可以自行斷點調(diào)試, 跟進到 Template 的 ast 字段就可以看到了
如何構(gòu)建語法樹 -- 編譯
為了簡化編譯過程, 我們將其拆成了兩個部分
詞法解析 (Lexer), 將文本按照規(guī)范, 拆成 "單詞"(Token), 例如:
println ( "Hello Wit !" ); 將會拆解成
- 標識符
println - 分隔符
( - 直接量
Hello Wit ! - 分隔符
) - 分隔符
;
語法解析 (Parser) : 將 Token 序列按照語法規(guī)則生成語法樹
例如上面的例子就符合 函數(shù)調(diào)用語句 的語法
funcExecuteExpr ::= expression:funcExpr LPAREN expression[COMMA]:list COMMA? RPAREN
{: return createMethodExecute(%funcExpr%,
StatementUtil.toExpressionArray(%list%),
%funcExpr.line%, %funcExpr.column%); :}
expression_statementable ::= funcExecuteExpr:$
statement ::= expression_statementable:$ SEMICOLON
templateAST ::= statement[]:list ?
這里涉及到 編譯原理 中的很多知識點, 點到為止, 就不展開了
幸運的是, 我們有工具可以直接生成 Lexer 和 Parser, 我們只需要把我們期望的語法規(guī)則描述出來就可以了
Wit 用的是 JFlex + Java CUP (定制版)
大家可以在這里找到語法描述文件, 感興趣的可以看看 , 不需要了解太多編譯原理的知識也能看懂
語法樹的優(yōu)化
冪等節(jié)點消除
這是一個理想的范圍, 但起碼, 我們能夠明確一下幾個場景是可以合并的:
- 只有直接常量參與冪等計算, 如:
1 + 2 - 通過等價變換, 可以滿足上一條的
- 針對模板消除, 提前把文本字符串序列化成目標編碼的字節(jié)流
- 合并相鄰的文本輸出
- 即使有不確定值, 但是在前置信息中即可判斷 True/False 的部分
- 空語句消除
特定場景算子實現(xiàn)
-
ForInvs.ForInNoLoops等 -
Ifvs.IfElsevs.IfNot -
TryCatchFinallyvs.TryFinally
語法樹的執(zhí)行
調(diào)用就更簡單了, 我們讓 Statement 和 Expression 都實現(xiàn)自己的執(zhí)行接口
Object execute(InternalContext context);
例如條件運算符的實現(xiàn):
public final class IfOperator extends Expression {
public Object execute(final InternalContext context) {
return (ALU.isTrue(ifExpr.execute(context))
? leftValueExpr
: rightValueExpr).execute(context);
}
}
大家各司其職, 做好自己的事情之后返回一個結(jié)果, 或者對上下文 Context 做些變更, 整個事情就解決了
可以認為是一個對語法樹的 不完整 的 深度遍歷
小結(jié)
啰嗦了這么多, 我們已經(jīng)明確了可行性, 只要補充上細節(jié)實現(xiàn)就可以了, 我將會在下篇深入展開這些細節(jié), 希望大家繼續(xù)關(guān)注
