「 giao-js 」用js写一个js解释器
SegmentFault
共 15225字,需浏览 31分钟
· 2020-11-25
作者:null仔
来源:SegmentFault 思否社区
前言
在这篇文章中,我们将通过 JS 构建我们自己的 JS 解释器,用 JS 写 JS,这听起来很奇怪,尽管如此,这样做我们将更熟悉 JS,也可以学习 JS 引擎是如何工作的!
什么是解释器 (Interpreter) ?
解释器是在运行时运行的语言求值器,它动态地执行程序的源代码。
解释器解析源代码,从源代码生成 AST(抽象语法树),遍历 AST 并逐个计算它们。
解释器 (Interpreter) 工作原理
词法分析 (Tokenization) 语法解析 (Parsing) 求值 (Evaluating)
词法分析 (Tokenization)
Javascript is the best language in the world
+----------------------------------------------------------+
| Javascript | is | the | best | language | in |the |world |
+----------------------------------------------------------+
var a = 1;
[
("var": "keyword"),
("a": "identifier"),
("=": "assignment"),
("1": "literal"),
(";": "separator"),
];
语法解析 (Parsing)
+------------------------------------------+
| Javascript | is | the | best | language |
+------------------------------------------+
"Javascript": Subject
"is the best language": Predicate
"language": Object
Subject(Noun) -> Predicate -> Object
{
type: "Program",
body: [
{
type: "VariableDeclaration",
declarations: [
{
type: "VariableDeclarator",
id: {
type: "Identifier",
name: "sum"
},
init: {
type: "Literal",
value: 30,
raw: "30"
}
}
],
kind: "var"
}
],
}
求值阶段 (Evaluating)
1 + 2
|
|
v
+---+ +---+
| 1 | | 2 |
+---+ +---+
\ /
\ /
\ /
+---+
| + |
+---+
{
lhs: 1,
op: '+'.
rhs: 2
}
{
type: "Program",
body: [
{
type: "ExpressionStatement",
expression: {
type: "BinaryExpression",
left: {
type: "Literal",
value: 1,
raw: "1"
},
operator: "+",
right: {
type: "Literal",
value: 2,
raw: "2"
}
}
}
],
}
实践
实践准备
Acorn.js
A tiny, fast JavaScript parser, written completely in JavaScript. 一个完全使用 javascript 实现的,小型且快速的 javascript 解析器
The Estree Spec
Jest
Rollup
项目初始化
// visitor.ts 创建一个Visitor类,并提供一个方法操作ES节点。
import * as ESTree from "estree";
class Visitor {
visitNode(node: ESTree.Node) {
// ...
}
}
export default Visitor;
// interpreter.ts 创建一个Interpreter类,用于运行ES节点树。
// 创建一个Visitor实例,并使用该实例来运行ESTree节点
import Visitor from "./visitor";
import * as ESTree from "estree";
class Interpreter {
private visitor: Visitor;
constructor(visitor: Visitor) {
this.visitor = visitor;
}
interpret(node: ESTree.Node) {
this.visitor.visitNode(node);
}
}
export default Interpreter;// vm.ts 对外暴露run方法,并使用acorn code->ast后,交给Interpreter实例进行解释。
const acorn = require("acorn");
import Visitor from "./visitor";
import Interpreter from "./interpreter";
const jsInterpreter = new Interpreter(new Visitor());
export function run(code: string) {
const root = acorn.parse(code, {
ecmaVersion: 8,
sourceType: "script",
});
return jsInterpreter.interpret(root);
}
实践第 1 弹: 1+1= ?
Program
interface Program {
type: "Program";
sourceType: "script" | "module";
body: Array;
comments?: Array;
}
ExpressionStatement
interface ExpressionStatement {
type: "ExpressionStatement";
expression: Expression;
}
BinaryExpression
本节实现的重点,简单理解,我们只要拿到 operator 操作符的类型并实现,然后对 left,right 值进行求值即可。
interface BinaryExpression {
type: "BinaryExpression";
operator: BinaryOperator;
left: Expression;
right: Expression;
}
Literal
type Literal = SimpleLiteral | RegExpLiteral;
interface SimpleLiteral {
type: "Literal";
value: string | boolean | number | null;
raw?: string;
}
interface RegExpLiteral {
type: "Literal";
value?: RegExp | null;
regex: {
pattern: string;
flags: string;
};
raw?: string;
}
// standard/es5.ts 实现以上节点方法
import Scope from "../scope";
import * as ESTree from "estree";
import { AstPath } from "../types/index";
const es5 = {
// 根节点的处理很简单,我们只要对它的body属性进行遍历,然后访问该节点即可。
Program(node: ESTree.Program) {
node.body.forEach((bodyNode) => this.visitNode(bodyNode));
},
// 表达式语句节点的处理,同样访问expression 属性即可。
ExpressionStatement(node: ESTree.ExpressionStatement>) {
return this.visitNode(node.expression);
},
// 字面量节点处理直接求值,这里对正则表达式类型进行了特殊处理,其他类型直接返回value值即可。
Literal(node: ESTree.Literal>) {
if ((node).regex) {
const { pattern, flags } = (node).regex;
return new RegExp(pattern, flags);
} else return node.value;
},
// 二元运算表达式节点处理
// 对left/node两个节点(Literal)进行求值,然后实现operator类型运算,返回结果。
BinaryExpression(node: ESTree.BinaryExpression>) {
const leftNode = this.visitNode(node.left);
const operator = node.operator;
const rightNode = this.visitNode(node.right);
return {
"+": (l, r) => l + r,
"-": (l, r) => l - r,
"*": (l, r) => l * r,
"/": (l, r) => l / r,
"%": (l, r) => l % r,
"<": (l, r) => l < r,
">": (l, r) => l > r,
"<=": (l, r) => l <= r,
">=": (l, r) => l >= r,
"==": (l, r) => l == r,
"===": (l, r) => l === r,
"!=": (l, r) => l != r,
"!==": (l, r) => l !== r,
}[operator](leftNode, rightNode);
},
};
export default es5;
// visitor.ts
import Scope from "./scope";
import * as ESTree from "estree";
import es5 from "./standard/es5";
const VISITOR = {
...es5,
};
class Visitor {
// 实现访问节点方法,通过节点类型访问对应的节点方法
visitNode(node: ESTree.Node) {
return {
visitNode: this.visitNode,
...VISITOR,
}[node.type](node);
}
}
export default Visitor;
// variable.ts
export enum Kind {
var = "var",
let = "let",
const = "const",
}
export type KindType = "var" | "let" | "const";
export class Variable {
private _value: any;
constructor(public kind: Kind, val: any) {
this._value = val;
}
get value() {
return this._value;
}
set value(val: any) {
this._value = val;
}
}
import { Variable, Kind, KindType } from "./variable";
class Scope {
// 父作用域
private parent: Scope | null;
// 当前作用域
private targetScope: { [key: string]: any };
constructor(public readonly type, parent?: Scope) {
this.parent = parent || null;
this.targetScope = new Map();
}
// 是否已定义
private hasDefinition(rawName: string): boolean {
return Boolean(this.search(rawName));
}
// var类型变量定义
public defineVar(rawName: string, value: any) {
let scope: Scope = this;
// 如果不是全局作用域且不是函数作用域,找到全局作用域,存储变量
// 这里就是我们常说的Hoisting (变量提升)
while (scope.parent && scope.type !== "function") {
scope = scope.parent;
}
// 存储变量
scope.targetScope.set(rawName, new Variable(Kind.var, value));
}
// let类型变量定义
public defineLet(rawName: string, value: any) {
this.targetScope.set(rawName, new Variable(Kind.let, value));
}
// const类型变量定义
public defineConst(rawName: string, value: any) {
this.targetScope.set(rawName, new Variable(Kind.const, value));
}
// 作用域链实现,向上查找标识符
public search(rawName: string): Variable | null {
if (this.targetScope.get(rawName)) {
return this.targetScope.get(rawName);
} else if (this.parent) {
return this.parent.search(rawName);
} else {
return null;
}
}
// 变量声明方法,变量已定义则抛出语法错误异常
public declare(kind: Kind | KindType, rawName: string, value: any) {
if (this.hasDefinition(rawName)) {
console.error(
`Uncaught SyntaxError: Identifier '${rawName}' has already been declared`
);
return true;
}
return {
[Kind.var]: () => this.defineVar(rawName, value),
[Kind.let]: () => this.defineLet(rawName, value),
[Kind.const]: () => this.defineConst(rawName, value),
}[kind]();
}
}
export default Scope;
实践第 3 弹: var age = 18
VariableDeclaration
declarations 表示声明的多个描述,因为我们可以这样:let a = 1, b = 2;。
interface VariableDeclaration {
type: "VariableDeclaration";
declarations: Array;
kind: "var" | "let" | "const";
}
VariableDeclarator
interface VariableDeclarator {
type: "VariableDeclarator";
id: Pattern;
init?: Expression | null;
}
Identifier
interface Identifier {
type: "Identifier";
name: string;
}
// standard/es5.ts 实现以上节点方法
import Scope from "../scope";
import * as ESTree from "estree";
type AstPath= {
node: T;
scope: Scope;
};
const es5 = {
// ...
// 这里我们定义了astPath,新增了scope作用域参数
VariableDeclaration(astPath: AstPath) {
const { node, scope } = astPath;
const { declarations, kind } = node;
// 上面提到,生声明可能存在多个描述(let a = 1, b = 2;),所以我们这里对它进行遍历:
// 这里遍历出来的每个item是VariableDeclarator节点
declarations.forEach((declar) => {
const { id, init } =declar;
// 变量名称节点,这里拿到的是age
const key = (id).name;
// 判断变量是否进行了初始化 ? 查找init节点值(Literal类型直接返回值:18) : 置为undefined;
const value = init ? this.visitNode(init, scope) : undefined;
// 根据不同的kind(var/const/let)声明进行定义,即var age = 18
scope.declare(kind, key, value);
});
},
// 标识符节点,我们只要通过访问作用域,访问该值即可。
Identifier(astPath: AstPath) {
const { node, scope } = astPath;
const name = node.name;
// walk identifier
// 这个例子中查找的是age变量
const variable = scope.search(name);
// 返回的是定义的变量对象(age)的值,即18
if (variable) return variable.value;
},
};
export default es5;
实践第 4 弹: module.exports = 6
AssignmentExpression
interface AssignmentExpression {
type: "AssignmentExpression";
operator: AssignmentOperator;
left: Pattern | MemberExpression;
right: Expression;
}
MemberExpression
interface MemberExpression {
type: "MemberExpression";
object: Expression | Super;
property: Expression;
computed: boolean;
optional: boolean;
}
import Scope from "./scope";
import Visitor from "./visitor";
import * as ESTree from "estree";
class Interpreter {
private scope: Scope;
private visitor: Visitor;
constructor(visitor: Visitor) {
this.visitor = visitor;
}
interpret(node: ESTree.Node) {
this.createScope();
this.visitor.visitNode(node, this.scope);
return this.exportResult();
}
createScope() {
// 创建全局作用域
this.scope = new Scope("root");
// 定义module.exports
const $exports = {};
const $module = { exports: $exports };
this.scope.defineConst("module", $module);
this.scope.defineVar("exports", $exports);
}
// 模拟commonjs,对外暴露结果
exportResult() {
// 查找module变量
const moduleExport = this.scope.search("module");
// 返回module.exports值
return moduleExport ? moduleExport.value.exports : null;
}
}
export default Interpreter;
// standard/es5.ts 实现以上节点方法
import Scope from "../scope";
import * as ESTree from "estree";
type AstPath= {
node: T;
scope: Scope;
};
const es5 = {
// ...
// 这里我们定义了astPath,新增了scope作用域参数
MemberExpression(astPath: AstPath) {
const { node, scope } = astPath;
const { object, property, computed } = node;
// property 是表示属性名称,computed 如果为 false,property 应该为一个 Identifier 节点,如果 computed 属性为 true,即 property 是一个 Expression 节点
// 这里我们拿到的是exports这个key值,即属性名称
const prop = computed
? this.visitNode(property, scope)
: (property).name;
// object 表示对象,这里为module,对module进行节点访问
const obj = this.visitNode(object, scope);
// 访问module.exports值
return obj[prop];
},
// 赋值表达式节点
(astPath: AstPath) {
const { node, scope } = astPath;
const { left, operator, right } = node;
let assignVar;
// LHS 处理
if (left.type === "Identifier") {
// 标识符类型 直接查找
const value = scope.search(left.name);
assignVar = value;
} else if (left.type === "MemberExpression") {
// 成员表达式类型,处理方式跟上面差不多,不同的是这边需要自定义一个变量对象的实现
const { object, property, computed } = left;
const obj = this.visitNode(object, scope);
const key = computed
? this.visitNode(property, scope)
: (property).name;
assignVar = {
get value() {
return obj[key];
},
set value(v) {
obj[key] = v;
},
};
}
// RHS
// 不同操作符处理,查询到right节点值,对left节点进行赋值。
return {
"=": (v) => {
assignVar.value = v;
return v;
},
"+=": (v) => {
const value = assignVar.value;
assignVar.value = v + value;
return assignVar.value;
},
"-=": (v) => {
const value = assignVar.value;
assignVar.value = value - v;
return assignVar.value;
},
"*=": (v) => {
const value = assignVar.value;
assignVar.value = v * value;
return assignVar.value;
},
"/=": (v) => {
const value = assignVar.value;
assignVar.value = value / v;
return assignVar.value;
},
"%=": (v) => {
const value = assignVar.value;
assignVar.value = value % v;
return assignVar.value;
},
}[operator](this.visitNode(right, scope));
},
};
export default es5;
// __test__/es5.test.ts
import { run } from "../src/vm";
describe("giao-js es5", () => {
test("assign", () => {
expect(
run(`
module.exports = 6;
`)
).toBe(6);
});
}
实践第 5 弹: for 循环
var result = 0;
for (var i = 0; i < 5; i++) {
result += 2;
}
module.exports = result;
ForStatement
这三个属性都可以为 null,即 for(;;){}。
interface ForStatement {
type: "ForStatement";
init?: VariableDeclaration | Expression | null;
test?: Expression | null;
update?: Expression | null;
body: Statement;
}
UpdateExpression
interface UpdateExpression {
type: "UpdateExpression";
operator: UpdateOperator;
argument: Expression;
prefix: boolean;
}
BlockStatement
interface BlockStatement {
0;
type: "BlockStatement";
body: Array;
innerComments?: Array;
}
// standard/es5.ts 实现以上节点方法
import Scope from "../scope";
import * as ESTree from "estree";
type AstPath= {
node: T;
scope: Scope;
};
const es5 = {
// ...
// for 循环语句节点
ForStatement(astPath: AstPath) {
const { node, scope } = astPath;
const { init, test, update, body } = node;
// 这里需要注意的是需要模拟创建一个块级作用域
// 前面Scope类实现,var声明在块作用域中会被提升,const/let不会
const forScope = new Scope("block", scope);
for (
// 初始化值
// VariableDeclaration
init ? this.visitNode(init, forScope) : null;
// 循环判断条件(BinaryExpression)
// 二元运算表达式,之前已实现,这里不再细说
test ? this.visitNode(test, forScope) : true;
// 变量更新语句(UpdateExpression)
update ? this.visitNode(update, forScope) : null
) {
// BlockStatement
this.visitNode(body, forScope);
}
},
// update 运算表达式节点
// update 运算表达式节点,即 ++/--,和一元运算符类似,只是 operator 指向的节点对象类型不同,这里是 update 运算符。
UpdateExpression(astPath: AstPath) {
const { node, scope } = astPath;
// update 运算符,值为 ++ 或 --,配合 update 表达式节点的 prefix 属性来表示前后。
const { prefix, argument, operator } = node;
let updateVar;
// 这里需要考虑参数类型还有一种情况是成员表达式节点
// 例: for (var query={count:0}; query.count < 8; query.count++)
// LHS查找
if (argument.type === "Identifier") {
// 标识符类型 直接查找
const value = scope.search(argument.name);
updateVar = value;
} else if (argument.type === "MemberExpression") {
// 成员表达式的实现在前面实现过,这里不再细说,一样的套路~
const { object, property, computed } = argument;
const obj = this.visitNode(object, scope);
const key = computed
? this.visitNode(property, scope)
: (property).name;
updateVar = {
get value() {
return obj[key];
},
set value(v) {
obj[key] = v;
},
};
}
return {
"++": (v) => {
const result = v.value;
v.value = result + 1;
// preifx? ++i: i++;
return prefix ? v.value : result;
},
"--": (v) => {
const result = v.value;
v.value = result - 1;
// preifx? --i: i--;
return prefix ? v.value : result;
},
}[operator](updateVar);
},
// 块语句节点
// 块语句的实现很简单,模拟创建一个块作用域,然后遍历body属性进行访问即可。
BlockStatement(astPath: AstPath) {
const { node, scope } = astPath;
const blockScope = new Scope("block", scope);
const { body } = node;
body.forEach((bodyNode) => {
this.visitNode(bodyNode, blockScope);
});
},
};
export default es5;
test("test for loop", () => {
expect(
run(`
var result = 0;
for (var i = 0; i < 5; i++) {
result += 2;
}
module.exports = result;
`)
).toBe(10);
});
var result = 0;
for (var i = 0; i < 5; i++) {
result += 2;
break; // break,continue,return
}
module.exports = result;
结语
评论
用 Shader 实现旗帜飘扬动画效果
我觉得对于刚入门 3D 编程的朋友来说,如果能够完成代码创建模型数据->创建材质->编写Shader动画这一系列,想必会有满满的成就感。今天就用 Cocos Creator 的 utils.MeshUtils.createMesh 接口,带大家感受一下这个流程。这个流程不仅可以用于新手学
COCOS
2
盘点一个使用超级鹰识别验证码并自动登录的案例
点击上方“Python共享之家”,进行关注回复“资源”即可获赠Python学习资料今日鸡汤江上几人在,天涯孤棹还。大家好,我是皮皮。一、前言前几天在Python钻石交流群【静惜】问了一个Python实现识别验证码并自动登录的问题,提问截图如下:验证码的截图如下所示:二、实现过程这里大家激烈的探讨,【
IT共享之家
0
Eiten 一个构建投资组合的好帮手
Eiten是Tradytics的一个开源工具包,它实现了各种统计和算法投资策略,如Eigen组合、最小方差组合、最大夏普比率组合和基于遗传算法的组合。Eiten允许你用自己的股票组合建立自己的投资组合。Eiten中自带的严格测试框架使你能够对你的投资组合更有自信。1.准备开始之前,你要确保Pytho
Python实用宝典
0
delorean,一个超级实用的 Python 库!
作者通常周更,为了不错过更新,请点击上方“Python碎片”,“星标”公众号大家好,今天为大家分享一个超级实用的 Python 库 - delorean。Github地址:https://github.com/myusuf3/delorean/时间在计算机科学和软件开发中是一个至关重要的概念。Pyt
Python 碎片
0
我用这10招,能减少了80%的BUG
将Python客栈设为“星标⭐”第一时间收到最新资讯前言对于大部分程序员来说,主要的工作时间是在开发和修复BUG。有可能修改了一个BUG,会导致几个新BUG的产生,不断循环。那么,有没有办法能够减少BUG,保证代码质量,提升工作效率?答案是肯定的。如果能做到,我们多出来的时间,多摸点鱼,做点自己喜欢
Python客栈
0
如何动手做出一个 CPU,很简单
将Python客栈设为“星标⭐”第一时间收到最新资讯来源:无聊的闪客纯手工打造一个 CPU 这个事儿。在电子专业的同学眼里,很容易。在计算机专业的同学眼里,稍稍有点复杂,有的专业课的实验课可能会带着同学做一个,或者用 Logisim 这样的仿真软件去模拟实现一个。在非计算机专业的同学眼里,就有点不敢
Python客栈
0
CleverCSV,一个神奇的 python 库!
我的小册:(小白零基础用Python量化股票分析小册) ,原价299,限时特价2杯咖啡,满100人涨10元。来源丨网络介绍CleverCSV 是一个基于 Python 的库,旨在提供比标准库 csv 更智能和灵活的方法来处理 CSV 文件。该库使用机器学习算法来探测 CSV 文件的正确拨号结构,从而
菜鸟学Python
0
一个小公司的技术开发心酸事(已倒闭)
往期热门文章:1、JetBrains 如何看待自己的软件在中国被频繁破解?2、程序员因Bug被要求归还4万多年终奖,网友:不还!3、一套万能通用的异步处理方案4、微服务全做错了!谷歌提出新方法,成本直接降9倍!5、IntelliJ IDEA 2024 首个大版本发布,好用到爆!作者:qiuwww来源
Java后端技术
1