In computer science, an abstract syntax tree (AST), or just syntax tree, is a tree representation of the abstract syntactic structure of source code written in a programming language.Each node of the tree denotes a construct occurring in the source code.
A compiled language is a programming language whose implementations are typically compilers (translators that generate machine code from source code), and not interpreters (step-by-step executors of source code, where no pre-runtime translation takes place).
An interpreted language is a type of programming language for which most of its implementations execute instructions directly and freely, without previously compiling a program into machine-language instructions. The interpreter executes the program directly, translating each statement into a sequence of one or more subroutines, and then into another language (often machine code).
The ESTree Spec: AST语法树规范,一位Mozilla工程师在Firefox中创建了一个API,将SpiderMonkey引擎的JavaScript解析器公开为JavaScript API。所述工程师记录了它产生的格式,这种格式作为操纵JavaScript源代码的工具的通用语言,现在遵循这个规范的parser有Esprima、acorn、espree、@babel/parser
SpiderMonkey Parser API
SpiderMonkey is Mozilla's JavaScript engine written in C and C++. It is used in various Mozilla products, including Firefox, and is available under the MPL2.
function tokenizer(input) {
// 定义一个current变量,像光标一样记录我们字符串代码的位置
let current = 0;
// 定义一个tokens数组
let tokens = [];
// 我们从一个while循环开始,然后让current变量自增
// 我们这样做的目的是要在单次循环中,通过current自增获取到整个tokens数组
while (current < input.length) {
// 读取字符串code
let char = input[current];
// 我们将要做的第一件事就是检查是否有扣号。因为括号会用于后面的函数调用,但是现在我们只需要关系括号这个符号
if (char === '(') {
// If we do, we push a new token with the type `paren` and set the value
// to an open parenthesis.
tokens.push({
type: 'paren',
value: '(',
});
// Then we increment `current`
current++;
// And we `continue` onto the next cycle of the loop.
continue;
}
// Next we're going to check for a closing parenthesis. We do the same exact
// thing as before: Check for a closing parenthesis, add a new token,
// increment `current`, and `continue`.
if (char === ')') {
tokens.push({
type: 'paren',
value: ')',
});
current++;
continue;
}
// 接下来我们将检查空白字符,这很有趣,因为我们需要关系空白字符是否是分割符,但是在实际生成token的时候没有什么用
// 所以我们需要检查是否是空白字符,如果是则跳过
let WHITESPACE = /\s/;
if (WHITESPACE.test(char)) {
current++;
continue;
}
// 接下来的类型是number,这与我们之前见到的不一样,因为数字可以是任意数量的字符。我们希望将整个字符序列捕获为一个令牌token
//
// (add 123 456)
// ^^^ ^^^
// Only two separate tokens
//
// So we start this off when we encounter the first number in a sequence.
let NUMBERS = /[0-9]/;
if (NUMBERS.test(char)) {
// We're going to create a `value` string that we are going to push
// characters to.
let value = '';
// 我们将要循环遍历数值之后的字符,直到不是数字为止,然后继续下一次遍历
while (NUMBERS.test(char)) {
value += char;
char = input[++current];
}
// After that we push our `number` token to the `tokens` array.
tokens.push({ type: 'number', value });
// And we continue on.
continue;
}
// 我们还将职称使用双引号引用的任何文本
//
// (concat "foo" "bar")
// ^^^ ^^^ string tokens
//
// We'll start by checking for the opening quote:
if (char === '"') {
// Keep a `value` variable for building up our string token.
let value = '';
// We'll skip the opening double quote in our token.
char = input[++current];
// 我们将遍历每个字符,直到到达另一个双引号为止。
while (char !== '"') {
value += char;
char = input[++current];
}
// Skip the closing double quote.
char = input[++current];
// And add our `string` token to the `tokens` array.
tokens.push({ type: 'string', value });
continue;
}
// 最后的token类型为name,这是一串有序的字母而不是数字,它代表了lisp语法中的函数名
//
// (add 2 4)
// ^^^
// Name token
//
let LETTERS = /[a-z]/i;
if (LETTERS.test(char)) {
let value = '';
// Again we're just going to loop through all the letters pushing them to
// a value.
while (LETTERS.test(char)) {
value += char;
char = input[++current];
}
// And pushing that value as a token with the type `name` and continuing.
tokens.push({ type: 'name', value });
continue;
}
// 最后,如果没有匹配上上面的任意条件则抛出错误
throw new TypeError('I dont know what this character is: ' + char);
}
// 最后返回一个tokens数组
return tokens;
}
function parser(tokens) {
// 我们使用一个current变量,像光标一样来描述我们的位置
let current = 0;
// 但是这一次我们将要使用递归来代替while循环,我们定义一个walk函数
function walk() {
// 根据current读取对应的token
let token = tokens[current];
// 我们将把每种类型的令牌分成不同的代码路径,从number类型的token开始
// We test to see if we have a `number` token.
if (token.type === 'number') {
// If we have one, we'll increment `current`.
current++;
// And we'll return a new AST node called `NumberLiteral` and setting its
// value to the value of our token.
return {
type: 'NumberLiteral',
value: token.value,
};
}
// If we have a string we will do the same as number and create a
// `StringLiteral` node.
if (token.type === 'string') {
current++;
return {
type: 'StringLiteral',
value: token.value,
};
}
// 我们将要根据左括号来定义,函数调用表达式节点
if (
token.type === 'paren' &&
token.value === '('
) {
// 直接跳过括号,因为在AST中我们不在乎括号
token = tokens[++current];
// 我们接着创建一个函数调用表达式节点,然后将左括号的后一个token作为函数名
let node = {
type: 'CallExpression',
name: token.value,
params: [],
};
// 然后我们继续自增,后去函数名之后的token
token = tokens[++current];
// 我们将继续遍历每一个token,每一个token作为函数调用表达式的参数,直到右括号
// 现在这就是递归的来源。与其尝试解析可能无限嵌套的节点集,不如依靠递归来解决它。
// 为了解释这个,我们看下Lisp的代码,你能看到函数add后面跟来数字参数及一个嵌套的包含两个数字参数的函数调用表达式
//
// (add 2 (subtract 4 2))
//
// You'll also notice that in our tokens array we have multiple closing
// parenthesis.
// 你也能够注意到,我们的tokens数组中有多个右括号
//
// [
// { type: 'paren', value: '(' },
// { type: 'name', value: 'add' },
// { type: 'number', value: '2' },
// { type: 'paren', value: '(' },
// { type: 'name', value: 'subtract' },
// { type: 'number', value: '4' },
// { type: 'number', value: '2' },
// { type: 'paren', value: ')' }, <<< Closing parenthesis
// { type: 'paren', value: ')' }, <<< Closing parenthesis
// ]
//
// 我们将要通过walk函数来及自增的crurrent变量来解析任何嵌套的函数调用表达式
// 所以我们将要创建一个while循环,当type为为右括号时结束循环
while (
(token.type !== 'paren') ||
(token.type === 'paren' && token.value !== ')')
) {
// we'll call the `walk` function which will return a `node` and we'll
// push it into our `node.params`.
// 调用walk函数生成新的节点作为params的元素
node.params.push(walk());
token = tokens[current];
}
// 最后通过自增来跳过右括号
current++;
// And return the node.
return node;
}
// Again, if we haven't recognized the token type by now we're going to
// throw an error.
throw new TypeError(token.type);
}
// 我们创建一个ast对象,该对象包含一个Program的根节点
let ast = {
type: 'Program',
body: [],
};
// 我们使用walk方法生成节点,然后将节点push到ast.body内
// 我们在循环内执行此操作的原因是因为我们的程序可以一个接一个的拥有CallExpression而不是嵌套的。
//
// (add 2 2)
// (subtract 4 2)
//
while (current < tokens.length) {
ast.body.push(walk());
}
// At the end of our parser we'll return the AST.
return ast;
}
目录
什么是AST
AST(Abstract Syntax Tree,抽象语法树)在 Wikipedia 的定义如下:
JavaScript属于哪种类型语言
计算机语言按类型分可以分为编译型语言及解释型语言
编译型语言
编译:将高级语言翻译成汇编语言or机器语言的过程
编译器:将高级语言翻译成汇编语言or机器语言的程序
编译流程,一般包含以下几个步骤
解释型语言
解释型语言和编译型语言没有明确的界限,因为理论上任何编程语言都可以被解释或编译。
常见的程序设计语言,如 C/C++ 、 Pascal 、 FORTRAN 等都是编译型语言,用这些语言编写的源程序,都需要进行编译、连接,才能生成可执行程序。这对于大型程序、系统程序、支持程序来说是十分有利的,虽然编译时花费了不少时间,但程序的执行效率是很高的。不过,在有些场合,对程序的执行效率要求不高的场合,没有必要在编译上花费大量的时间,可以对高级语言源程序采取解释执行的方式。
解释执行需要有一个解释器 (Interpreter) ,它将源代码逐句读入。第一步先作词法分析,建立内部符号表;再作语法和语义分析,并作类型检查 ( 解释语言的语义检查一般比较简单,因为它们往往采用无类型或动态类型系统 ) 。完成检查后把每一语句压入执行堆栈,并立即解释执行。因为解释执行时只看到一个语句,无法对整个程序进行优化。但是解释执行占用空间很少。操作系统的命令、Visual Basic、Python、JavaScript 都是解释执行的 ( 其中有些语言也可以编译执行 ) 。解释器不大,工作空间也不大,不过,解释型应用占用更多的内存和CPU资源。这是由于,为了运行解释型语言编写的程序,相关的解释器必须首先运行。解释器是复杂的,智能的,大量消耗资源的程序并且它们会占用很多CPU周期和内存,另外解释型应用的decode-fetch-execute(解码-抓取-执行)的周期,它们比编译型程序慢很多
JavaScript 是一门解释型语言,所以其解释过程如下所示,解释器则是浏览器JavaScript引擎(V8, Chakra, SpiderMonkey, Nitro, etc.)
The ESTree specification
The ESTree Spec: AST语法树规范,一位Mozilla工程师在Firefox中创建了一个API,将SpiderMonkey引擎的JavaScript解析器公开为JavaScript API。所述工程师记录了它产生的格式,这种格式作为操纵JavaScript源代码的工具的通用语言,现在遵循这个规范的parser有Esprima、acorn、espree、@babel/parser
SpiderMonkey Parser API
SpiderMonkey 提供来了一系列可供Js操作的API,如Reflect.parse(src[, options]),通过给parse传递js源代码,最后生成被解析的抽象语法树(AST)的程序对象;
默认情况下, Reflect.parse() 生成Node对象, 即普通的JavaScript对象 (它们的原型来自标准的Object原型). 所有的节点类型都实现了以下的接口
什么是接口,在TypeScript中的定义为,核心原则之一是对值所具有的结构进行类型检查。 它有时被称做“鸭式辨型法”或“结构性子类型化”。 在TypeScript里,接口的作用就是为这些类型命名和为你的代码或第三方代码定义契约
举个例子
使用接口来重写
更多有关接口的内容,可以直接查看ts文档
AST中主要有以下接口
程序,一个完整的程序源代码树。一般就是一个单独的js文件
如图所示,以Esprima为例,因为Esprima,因为Esprima语法树格式源自Mozilla Parser API的原始版本,然后将其形式化并扩展为ESTree规范
函数接口
任意语句接口
空语句接口,一个空语句,也就是,一个孤立的分号
块语句接口,也就是由大括号包围的语句序列.
表达式语句接口,一个表达式语句,也就是,仅有一个表达式组成的语句
一个if语句接口
一个标签语句接口,也就是, a statement prefixed by a break/continue label
一个break语句接口
一个continue语句接口
一个with语句接口
一个switch语句接口
一个return语句接口
一个throw语句接口
一个try语句接口
一个while语句接口
一个do/while语句接口
一个for语句接口
一个for/in语句接口, or, if each is true, a for each/in 语句.
一个let语句接口
一个debugger语句接口
声明接口
一个函数声明接口
一个变量声明接口,可以通过var, let, 或const
一个变量声明符接口
任意表达式接口
一个this表达式接口
一个数组表达式接口
一个对象表达式接口
一个函数表达式接口
一个序列表达式接口,也就是一个由逗号分割的表达式序列
一元运算符表达式接口
一个二元运算符表达式接口
赋值表达式接口
自增自减表达式接口
逻辑运算符表达式接口
条件运算符表达式接口
new操作符表达式接口
函数调用表达式接口
属性表达式接口
yield表达式接口
generator表达式接口
let表达式接口
模式接口
对象结构赋值模式接口
数组结构赋值模式接口
case模式接口
catch字句接口
标识符。标识符可以是表达式或解构模式。
字面标记。字面可以是表达式
一元操作符
二元操作符
逻辑运算符
赋值运算符
自增自减操作符
ES6新增的接口
箭头函数接口
Class类接口
常用的Javascript Parser
Esprima 经典的AST解析器,文档齐全; UglifyJS 最初的代码代码压缩工具,自带AST解析器,但没有遵守The ESTree Spec UglifyJS2 UglifyJS重构后的版本,自带AST解析器,一样没有遵守The ESTree Spec acorn 借鉴了Esprima内的一些实现思路,相对于esprima、UglifyJS2性能更优 espree eslint内置的parser,基于Esprima一个分支创建的parser @babel/parser babel内置的parser,基于acorn
各个 parser解析的速度对比可以参见 Speed Comparison
Esprima的使用方式
怎样生成AST
以the-super-tiny-compiler来分析
AST在JavaScript内的应用场景
在明白了js代码最终是被生成AST,然后被解释执行之后,那么只要涉及到代码处理的场景,都可以运用AST来帮助我们处理对应的场景; 如:代码压缩(uglify)、代码检查(eslint)、代码转化(babel)、代码格式化(prettier)、构建打包(webpack、rollup)、IDE只能提示、代码混淆等
总结
随着近年来JavaScript的快速发展,前段开发越来越自动化,工程化,而AST在这其中扮演着一个重要的角色,它帮助开发来很多提高开发效率的工具,而当我们掌握来AST之后,我们自己也可以去任何可以提高我们工作效率的工具;
在线demo链接 https://astexplorer.net/#/gist/660493971bb8114cf17e9eacdd26c153/ed03f1df9b6eb48444ec81f5ba76a0babc4f33f3
参考链接 https://eslint.org/blog/2014/12/espree-esprima http://marijnhaverbeke.nl/blog/acorn.html http://lisperator.net/blog/should-you-switch-to-uglifyjs2/ http://lisperator.net/blog/uglifyjs-why-not-switching-to-spidermonkey-ast/ https://github.com/estree/estree https://esprima.readthedocs.io/en/4.0/syntax-tree-format.html https://juejin.im/entry/5a76b569f265da4e7f357629 https://hacks.mozilla.org/2017/02/a-crash-course-in-just-in-time-jit-compilers/ https://developer.mozilla.org/en-US/docs/Mozilla/Projects/SpiderMonkey/Parser_API https://github.com/jamiebuilds/the-super-tiny-compiler