前置基础知识点
Febit Wit 简介 -- 惯例吹牛时间
Wit 是我 2013 年开始开发的一个准 JVM 上的语言, 起初的定位是模板引擎,之后慢慢发现, 在语法上可以做的更强大, 于是现在成了一个准脚本引擎.
Wit 语法类似 JavaScript, 在设计的时候也参考了许多. 另外, 他还支持自定义函数，全局变量，Lambda 表达式. 因为是当初并没有把他产品化, 只是将它作为一个与国内某开源作者较劲的产物, 每次觉得那些设计不合适就残忍地大改. 由此, 自认为这是一个, 核心模块轻巧，无第三方依赖，的个人代表作. (
以至于每次发布都会炫耀一下这个 Jar 包才 310 KB
Wit 采用BSD开源协议, 托管在 Github, [我是传送门], Star 少的可怜, 大家多多支持
Show Time
(旁白君: 主演怯(tou)场(lan), 此段跳过, 大家可以移步往期回顾(并没有) , 或者看看这里有什么好东西 --> wit-toys
语言? 太远! 先实现个表达式
我们先来看一下 a + b, 计算过程可分为三步:
- 从 a 的地址取实际值 A
- 从 b 的地址取实际值 B
- 执行加法运算返回
a_b.png
现在复杂一点儿, 我们看一下 a + b + 10, 多了一个操作, 且多了新的类型--直接量,归一化一下,其实可以转换成(a+b) + 10, 在已知条件下, 可以拆解成三步:
- 调用已知步骤, 得到
(a+b)的结果 - 取直接量 1 (为什么要取出来? 就像我们切菜, 所有的操作都是要放到砧板上来的)
- 执行 "砧板" 上两个数的运算, 把结果返回
a_b_10.png
好了, 现在问题稍微复杂一点儿, 我们来扩充到四则运算, 2 * a + b / 3 + 10, 这里涉及到操作符优先级, 相信大家都能画出来一个处理这个表达式的数形结构
2a_b3_10.png
现在我们继续尝试一下归一化, 上面的可以抽象成两个概念:
表达式 (Expression, expr): a, b, 1, (a+b), (2 * a), (2 * a + b / 3).... 等等,他们在一个数中, 都是为他的更上层提供一个最终结果, 无论是取内存取值, 还是加载一个直接量, 或者是某种上层不关心的操作
操作符(operator, oper): 就像例子中的提到的四则运算, 可以认为是对给定数据的一种算法
现在, 我们用 + 指代其他类似操作符, 以上表达式, 无非不过 expr + expr, 如果继续扩充的话,
expr_expr.png
除此之外 = 也可以看成操作符, 只不过它对左边的表达式要求更高, 必须是一个可赋值的, 如地址引用, 数组的某个位置, Map 的某个索引位置
因此, 赋值也可以写成链式:
a = b = (c = 1) + 1, 或者if(flag = !disabled) { ... }, 只不过大多数规范都不建议这么写
操作符还根据需要的数据的数量分, 单目、二目、三目运算符..., 就像参数传参, 可以传不同数量的参数,
单目操作符 如: 取负, 取反, 取非,自增, 自减 等.
二目操作符 较常见
user.name // 属性操作符
arr[i] // 数组操作符
a + b // 部分运算符
说到 三目运算符, 必须得举一个特殊的例子: 条件运算符 exprA ? exprB : exprC , 这个和前面的不同, 不是将三个表达式都算出来之后传给操作符, 实际的逻辑是:
- 取 exprA 计算值 A
- 如果 A 为真, 执行 exprB 并返回结果
- 否则执行并返回 exprC 的结果
简单说,就是根据 exprA 的结果选择执行 exprB 还是 exprC, 其中, 只有一个分支能得到执行的机会
当然 exprA 如果抛异常了, 或者中断退出了, 例如
System.exit(1), 两者都不执行
// 错误理解
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'
}
最后, 还有个容易被大家忽视的概念, 操作符的结合性, 这是个扩中内容, 也就是大部分常见操作符都是自左向右结合的, 但有些相反, 是自右向左
还是以条件运算符 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"
// 结论: 自右向左
其他的自右向左的操作符我们这里不再展开, 大家可以很容易搜到相关文章
语句(Statement) 的列表构成语法树
一段能改变上线文的独立的逻辑, 即产生了副作用, 就可以认为是 语句
一些 表达式 都可以在完结时产生副作用, 即使丢弃返回值, 这也是语句的一种 -- 表达式语句
像直接量和一些简单的运算, 都不会产生副作用, 通常都不能当做语句
// 非法语句
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, // 只提供现有的变量名, 取名作为key, 取值作为值, 等同于 map["id"] = id
1 : "a", // 直接量作为 key
[ -1-1 ] : "e", // 表达式作为 key, 使用 [] 内的表达式的结果作为key, 等同于 map[-1-1] = "e"
"x-y-z" : "XYZ", // 支持最后一个元素冗余逗号
};
// 其他特殊语法
{ <语句列表> } // 代码块
new_list = native new java.util.ArrayList(); // 导入 java 函数引用
接下来, 我们看一下一个 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;
};
ast-tree.png
不尽兴的的话, 大家可以自行断点调试, 跟进到 Template 的 ast 字段就可以看到了
如何构建语法树 -- 编译
为了简化编译过程, 我们将其拆成了两个部分
词法解析 (Lexer), 将文本按照规范, 拆成 "单词"(Token), 例如:
println ( "Hello Wit !" ); 将会拆解成
- 标识符
println - 分隔符
( - 直接量
Hello Wit ! - 分隔符
) - 分隔符
;
语法解析 (Parser) : 将 Token 序列按照语法规则生成语法树
例如上面的例子就符合 函数调用语句 的语法
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, 我们只需要把我们期望的语法规则描述出来就可以了
Wit 用的是 JFlex + Java CUP (定制版)
大家可以在这里找到语法描述文件, 感兴趣的可以看看 , 不需要了解太多编译原理的知识也能看懂
语法树的优化
幂等节点消除
这是一个理想的范围, 但起码, 我们能够明确一下几个场景是可以合并的:
- 只有直接常量参与幂等计算, 如:
1 + 2 - 通过等价变换, 可以满足上一条的
- 针对模板消除, 提前把文本字符串序列化成目标编码的字节流
- 合并相邻的文本输出
- 即使有不确定值, 但是在前置信息中即可判断 True/False 的部分
- 空语句消除
特定场景算子实现
-
ForInvs.ForInNoLoops等 -
Ifvs.IfElsevs.IfNot -
TryCatchFinallyvs.TryFinally
语法树的执行
调用就更简单了, 我们让 Statement 和 Expression 都实现自己的执行接口
Object execute(InternalContext context);
例如条件运算符的实现:
public final class IfOperator extends Expression {
public Object execute(final InternalContext context) {
return (ALU.isTrue(ifExpr.execute(context))
? leftValueExpr
: rightValueExpr).execute(context);
}
}
大家各司其职, 做好自己的事情之后返回一个结果, 或者对上下文 Context 做些变更, 整个事情就解决了
可以认为是一个对语法树的 不完整 的 深度遍历
小结
啰嗦了这么多, 我们已经明确了可行性, 只要补充上细节实现就可以了, 我将会在下篇深入展开这些细节, 希望大家继续关注
网友评论