前言
在这篇文章中,咱们将通过 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": ObjectJavascript 在语法中是一个主语名词,其余的是一个没有什么意义的句子叫做谓语,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.tsimport 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.tsexport 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.tsimport { 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