前言
在这篇文章中, 咱们将通过 JS 构建咱们本人的 JS 解释器, 用 JS 写 JS, 这听起来很奇怪, 尽管如此, 这样做咱们将更相熟 JS, 也能够学习 JS 引擎是如何工作的!
什么是解释器 (Interpreter) ?
解释器是在运行时运行的语言求值器, 它动静地执行程序的源代码。
解释器解析源代码, 从源代码生成 AST(形象语法树), 遍历 AST 并一一计算它们。
解释器 (Interpreter) 工作原理
- 词法剖析 (Tokenization)
- 语法解析 (Parsing)
- 求值 (Evaluating)
词法剖析 (Tokenization)
将源代码合成并组织成一组有意义的单词, 这一过程即为词法剖析(Token)。
在英语中, 当咱们遇到这样一个语句时:
Javascript is the best language in the world
咱们会下意识地把句子分解成一个个单词:
+----------------------------------------------------------+
| Javascript | is | the | best | language | in |the |world |
+----------------------------------------------------------+
这是剖析和了解句子的第一阶段。
词法剖析是由 词法分析器 实现的, 词法分析器会扫描 (scanning) 代码, 提取词法单元。
var a = 1;
[("var": "keyword"),
("a": "identifier"),
("=": "assignment"),
("1": "literal"),
(";": "separator"),
];
词法分析器将代码分解成 Token 后, 会将 Token 传递给解析器进行解析, 咱们来看下解析阶段是如何工作的。
语法解析 (Parsing)
将词法分析阶段生成的 Token 转换为形象语法树(Abstract Syntax Tree), 这一过程称之为语法解析(Parsing)。
在英语中,Javascript is the best language 被合成为以下单词:
+------------------------------------------+
| Javascript | is | the | best | language |
+------------------------------------------+
这样咱们就能够筛选单词并造成语法结构:
"Javascript": Subject
"is the best language": Predicate
"language": Object
Javascript 在语法中是一个主语名词, 其余的是一个没有什么意义的句子叫做谓语,language 是动作的接受者, 也就是宾语。构造是这样的:
Subject(Noun) -> Predicate -> Object
语法解析是由 语法解析器 实现的, 它会将上一步生成的 Token, 依据语法规定, 转为形象语法树(AST)。
{
type: "Program",
body: [
{
type: "VariableDeclaration",
declarations: [
{
type: "VariableDeclarator",
id: {
type: "Identifier",
name: "sum"
},
init: {
type: "Literal",
value: 30,
raw: "30"
}
}
],
kind: "var"
}
],
}
求值阶段 (Evaluating)
解释器将遍历 AST 并计算每个节点。- 求值阶段
1 + 2
|
|
v
+---+ +---+
| 1 | | 2 |
+---+ +---+
\ /
\ /
\ /
+---+
| + |
+---+
{
lhs: 1,
op: '+'.
rhs: 2
}
解释器解析 Ast, 失去 LHS 节点, 接着收集到操作符 (operator) 节点 +,+ 操作符示意须要进行一次加法操作, 它必须有第二个节点来进行加法操作. 接着他收集到 RHS 节点。它收集到了有价值的信息并执行加法失去了后果,3。
{
type: "Program",
body: [
{
type: "ExpressionStatement",
expression: {
type: "BinaryExpression",
left: {
type: "Literal",
value: 1,
raw: "1"
},
operator: "+",
right: {
type: "Literal",
value: 2,
raw: "2"
}
}
}
],
}
实际
后面咱们曾经介绍了解释器的工作原理, 接下来咱们来动动手松松筋骨吧, 实现一个 Mini Js Interpreter~
实际筹备
- Acorn.js
A tiny, fast JavaScript parser, written completely in JavaScript. 一个齐全应用 javascript 实现的, 小型且疾速的 javascript 解析器
本次实际咱们将应用 acorn.js , 它会帮咱们进行词法剖析, 语法解析并转换为形象语法树。
Webpack/Rollup/Babel(@babel/parser) 等第三方库也是应用 acorn.js 作为本人 Parser 的根底库。(站在伟人的肩膀上啊!)
- The Estree Spec
最开始 Mozilla JS Parser API 是 Mozilla 工程师在 Firefox 中创立的 SpiderMonkey 引擎输入 JavaScript AST 的标准文档, 文档所形容的格局被用作操作 JAvaScript 源代码的通用语言。
随着 JavaScript 的倒退, 更多新的语法被退出, 为了帮忙倒退这种格局以跟上 JavaScript 语言的倒退。The ESTree Spec 就诞生了, 作为参加构建和应用这些工具的人员的社区规范。
acorn.js parse 返回值合乎 ESTree spec 形容的 AST 对象, 这里咱们应用 @types/estree 做类型定义。
- Jest
号称令人欢快的 JavaScript 测试 … 咱们应用它来进行单元测试.
- Rollup
Rollup 是一个 JavaScript 模块打包器, 咱们应用它来打包, 以 UMD 标准对外裸露模块。
我的项目初始化
// 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=?
咱们这节来实现 1+1 加法的解释。首先咱们通过 AST explorer, 看看 1+1 这段代码转换后的 AST 构造。
咱们能够看到这段代码中存在 4 种节点类型, 上面咱们简略的介绍一下它们:
Program
根节点, 即代表一整颗形象语法树,body 属性是一个数组, 蕴含了多个 Statement 节点。
interface Program {
type: "Program";
sourceType: "script" | "module";
body: Array<Directive | Statement | ModuleDeclaration>;
comments?: Array<Comment>;
}
ExpressionStatement
表达式语句节点,expression 属性指向一个表达式节点对象
interface ExpressionStatement {
type: "ExpressionStatement";
expression: Expression;
}
BinaryExpression
二元运算表达式节点,left 和 right 示意运算符左右的两个表达式,operator 示意一个二元运算符。
本节实现的重点, 简略了解, 咱们只有拿到 operator 操作符的类型并实现, 而后对 left,right 值进行求值即可。
interface BinaryExpression {
type: "BinaryExpression";
operator: BinaryOperator;
left: Expression;
right: Expression;
}
Literal
字面量, 这里不是指 [] 或者 {} 这些, 而是自身语义就代表了一个值的字面量, 如 1,“hello”, true 这些, 还有正则表达式, 如 /\d?/。
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 ((<ESTree.RegExpLiteral>node).regex) {const { pattern, flags} = (<ESTree.RegExpLiteral>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;
就这样, 一般的二元运算就搞定啦!!!
实际第 2 弹: 怎么找到变量?
Javascript 的作用域与作用域链的概念想必大家都很相熟了, 这里就不再啰嗦了~
是的, 咱们须要通过实现作用域来拜访变量, 实现作用域链来搜查标识符。
在这之前, 咱们先实现 Variable 类, 实现变量的存取方法。
// 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
变量申明,kind 属性示意是什么类型的申明,因为 ES6 引入了 const/let。
declarations 示意申明的多个形容,因为咱们能够这样:let a = 1, b = 2;。
interface VariableDeclaration {
type: "VariableDeclaration";
declarations: Array<VariableDeclarator>;
kind: "var" | "let" | "const";
}
VariableDeclarator
变量申明的形容,id 示意变量名称节点,init 示意初始值的表达式,能够为 null。
interface VariableDeclarator {
type: "VariableDeclarator";
id: Pattern;
init?: Expression | null;
}
Identifier
顾名思义, 标识符节点, 咱们写 JS 时定义的变量名, 函数名, 属性名, 都归为标识符。
interface Identifier {
type: "Identifier";
name: string;
}
理解了对应节点的含意后, 咱们来进行实现:
// standard/es5.ts 实现以上节点办法
import Scope from "../scope";
import * as ESTree from "estree";
type AstPath<T> = {
node: T;
scope: Scope;
};
const es5 = {
// ...
// 这里咱们定义了 astPath, 新增了 scope 作用域参数
VariableDeclaration(astPath: AstPath<ESTree.VariableDeclaration>) {const { node, scope} = astPath;
const {declarations, kind} = node;
// 下面提到, 生申明可能存在多个形容(let a = 1, b = 2;), 所以咱们这里对它进行遍历:
// 这里遍历进去的每个 item 是 VariableDeclarator 节点
declarations.forEach((declar) => {const { id, init} = <ESTree.VariableDeclarator>declar;
// 变量名称节点, 这里拿到的是 age
const key = (<ESTree.Identifier>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<ESTree.Identifier>) {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
咱们先来看看 module.exports = 6 对应的 AST。
从语法树中咱们又看到两个生疏的节点类型, 来看看它们别离代表什么意思:
AssignmentExpression
赋值表达式节点,operator 属性示意一个赋值运算符,left 和 right 是赋值运算符左右的表达式。
interface AssignmentExpression {
type: "AssignmentExpression";
operator: AssignmentOperator;
left: Pattern | MemberExpression;
right: Expression;
}
MemberExpression
成员表达式节点, 即示意援用对象成员的语句,object 是援用对象的表达式节点,property 是示意属性名称,computed 如果为 false, 是示意 . 来援用成员,property 应该为一个 Identifier 节点, 如果 computed 属性为 true, 则是 [] 来进行援用, 即 property 是一个 Expression 节点, 名称是表达式的后果值。
interface MemberExpression {
type: "MemberExpression";
object: Expression | Super;
property: Expression;
computed: boolean;
optional: boolean;
}
咱们先来定义 module.exports 变量。
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;
ok, 上面咱们来实现以上节点函数~
// standard/es5.ts 实现以上节点办法
import Scope from "../scope";
import * as ESTree from "estree";
type AstPath<T> = {
node: T;
scope: Scope;
};
const es5 = {
// ...
// 这里咱们定义了 astPath, 新增了 scope 作用域参数
MemberExpression(astPath: AstPath<ESTree.MemberExpression>) {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)
: (<ESTree.Identifier>property).name;
// object 示意对象, 这里为 module, 对 module 进行节点拜访
const obj = this.visitNode(object, scope);
// 拜访 module.exports 值
return obj[prop];
},
// 赋值表达式节点
(astPath: AstPath<ESTree.>) {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)
: (<ESTree.Identifier>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;
ok, 实现结束, 是时候验证一波了, 上 jest 大法。
// __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
for 循环语句节点,属性 init/test/update 别离示意了 for 语句括号中的三个表达式,初始化值,循环判断条件,每次循环执行的变量更新语句(init 能够是变量申明或者表达式)。
这三个属性都能够为 null,即 for(;;){}。
body 属性用以示意要循环执行的语句。
interface ForStatement {
type: "ForStatement";
init?: VariableDeclaration | Expression | null;
test?: Expression | null;
update?: Expression | null;
body: Statement;
}
UpdateExpression
update 运算表达式节点,即 ++/–,和一元运算符相似,只是 operator 指向的节点对象类型不同,这里是 update 运算符。
interface UpdateExpression {
type: "UpdateExpression";
operator: UpdateOperator;
argument: Expression;
prefix: boolean;
}
BlockStatement
块语句节点,举个例子:if (…) {// 这里是块语句的内容},块里边能够蕴含多个其余的语句,所以有一个 body 属性,是一个数组,示意了块里边的多个语句。
interface BlockStatement {
0;
type: "BlockStatement";
body: Array<Statement>;
innerComments?: Array<Comment>;
}
废话少说, 盘它!!!
// standard/es5.ts 实现以上节点办法
import Scope from "../scope";
import * as ESTree from "estree";
type AstPath<T> = {
node: T;
scope: Scope;
};
const es5 = {
// ...
// for 循环语句节点
ForStatement(astPath: AstPath<ESTree.ForStatement>) {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<ESTree.UpdateExpression>) {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)
: (<ESTree.Identifier>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<ESTree.BlockStatement>) {const { node, scope} = astPath;
const blockScope = new Scope("block", scope);
const {body} = node;
body.forEach((bodyNode) => {this.visitNode(bodyNode, blockScope);
});
},
};
export default es5;
上 jest 大法验证一哈~
test("test for loop", () => {
expect(
run(`
var result = 0;
for (var i = 0; i < 5; i++) {result += 2;}
module.exports = result;
`)
).toBe(10);
});
你认为这样就完结了吗? 有没有想到还有什么状况没解决? for 循环的中断语句呢?
var result = 0;
for (var i = 0; i < 5; i++) {
result += 2;
break; // break,continue,return
}
module.exports = result;
感兴趣的小伙伴能够本人入手试试, 或者戳源码地址
结语
giao-js 目前只实现了几个语法, 本文只是提供一个思路。
有趣味的同学能够查看残缺代码。
感觉有帮忙到你的话, 点个 star 反对下作者 ❤️ ~
参考
bramblex/jsjs
应用 Acorn 来解析 JavaScript
Build a JS Interpreter in JavaScript Using Acorn as a Parser