晓强哥在他的上篇文章 Javascript抽象语法树上篇(基础篇) 里介绍了 Javascript 抽象语法树里面「提到获得抽象语法树的过程为:代码 => 词法分析 => 语法分析 => AST」,抱着深究技术细节的目的,我决定研究这里的词法分析和语法分析,写一个简单的四则运算表达式转换成 AST 的方法,于是就有了下面的内容。
人类习惯 a + b
这种表达叫做「中序表达式」,优点是比较简单直观,缺点是要用一堆括号来确定优先级 (a + b) * (c + d)
。
这里说简单直观是相对人类的思维结构来说的,对计算机而言中序表达式是非常复杂的结构。
为了计算机计算方便,我们需要将中序表达式转换成树形结构,也就是「抽象语法树 AST」。
我们知道,几乎任何语言中,代码在 "编译"(解释型语言在运行时也有编译的过程) 的过程中,都会生成一种树状的中间状态,这就是 AST。有些语言会直接把类似 AST 的语法暴露给程序员(例如:lisp、elixir、python 等)。但是 javascript 并没有这个能力,但是我们可以用 javascript 自身实现这个过程。
获得抽象语法树的过程为:代码(字符串) => 词法分析(Lexer)=> Tokens => 语法分析(Parser) => AST。
词法分析有点像中文的分词,就是将字符串流根据规则生成一个一个的有具体意义的 Token ,形成 Token 流,然后流入下一步。
我们看一个简单的例子,
1 + 2.3
很明显这个表达式是可以分成三个 Token ,分别是 1
, +
, 2.3
。
词法分析这里,我们可以用有限状态机来解决。
绝大多数语言的词法部分都是用状态机实现的,我们下面就画出有限状态机的图形,然后根据图形直观地写出解析代码,总体图大概是这样。
下面拆开细看。
状态机的初始状态是 start
。
start
状态下输入数字(0 ~ 9)就会迁移到 inInt
状态。
start
状态下输入符号(.)就会迁移到 inFloat
状态。
start
状态下输入符号(+ - * /)就会输出 「符号 Token」
,并回到 start
状态。
start
状态下输入 EOF 就会输出 「EOF Token」
,并回到 start
状态。
代码大概是这个样子:
start(char) {
// 数字
if (["0","1","2","3","4","5","6","7","8","9"].includes(char)) {
this.token.push(char);
return this.inInt;
}
// .
if (char === "."){
this.token.push(char);
return this.inFloat;
}
// 符号
if (["+","-","*","/"].includes(char)) {
this.emmitToken("SIGN", char);
return this.start;
}
// 结束符
if (char === EOF){
this.emmitToken("EOF", EOF);
return this.start;
}
}
start
状态下输入输入数字(0 ~ 9)就会迁移到 inInt
状态。
inInt
状态下输入输入符号(.)就会迁移到 inFloat
状态。
inInt
状态下输入数字(0 ~ 9)就继续留在 inInt
状态。
inInt
状态下输入非数字和.(0 ~ 9 .)就会就会输出 「整数 Token」
,并迁移到 start
状态。
代码:
inInt(char) {
if (["0","1","2","3","4","5","6","7","8","9"].includes(char)) {
this.token.push(char);
return this.inInt;
} else if (char === '.') {
this.token.push(char);
return this.inFloat;
} else {
this.emmitToken("NUMBER", this.token.join(""));
this.token = [];
return this.start(char); // put back char
}
}
start
状态下输入符号(.)就会迁移到 inFloat
状态。
inInt
状态下输入输入符号(.)就会迁移到 inFloat
状态。
inFloat
状态下输入数字(0 ~ 9)就继续留在 inFloat
状态。
inFloat
状态下输入非数字(0 ~ 9 )就会就会输出 「浮点数 Token」
,并迁移到 start
状态。
代码:
inFloat(char) {
if (["0","1","2","3","4","5","6","7","8","9"].includes(char)) {
this.token.push(char);
return this.inFloat;
} else if (char === ".") {
throw new Error("不能出现`..`");
} else {
if (this.token.length === 1 && this.token[0] === ".") throw new Error("不能单独出现`.`");
this.emmitToken("NUMBER", this.token.join(""));
this.token = [];
return this.start(char); // put back char
}
}
我将 「浮点数 Token」
和 「整数 Token」
合并为 [NUMBER Token]
, 其他的 Token 还有 「SIGN Token」
和 「EOF Token」
。
Token 的 定义:
interface Token{
type:String,
value:String,
}
const EOF = Symbol('EOF');
class Lexer {
constructor(){
this.token = []; // 临时 token 字符存储
this.tokens = []; // 生成的正式 token
// state 默认是 start 状态,后面通过 push 函数实现状态迁移
this.state = this.start;
}
start(char) {
// 数字
if (["0","1","2","3","4","5","6","7","8","9"].includes(char)) {
this.token.push(char);
return this.inInt;
}
// .
if (char === "."){
this.token.push(char);
return this.inFloat;
}
// 符号
if (["+","-","*","/"].includes(char)) {
this.emmitToken("SIGN", char);
return this.start;
}
// 结束符
if (char === EOF){
this.emmitToken("EOF", EOF);
return this.start;
}
}
inInt(char) {
if (["0","1","2","3","4","5","6","7","8","9"].includes(char)) {
this.token.push(char);
return this.inInt;
} else if (char === '.') {
this.token.push(char);
return this.inFloat;
} else {
this.emmitToken("NUMBER", this.token.join(""));
this.token = [];
return this.start(char); // put back char
}
}
inFloat(char) {
if (["0","1","2","3","4","5","6","7","8","9"].includes(char)) {
this.token.push(char);
return this.inFloat;
} else if (char === ".") {
throw new Error("不能出现`..`");
} else {
if (this.token.length === 1 && this.token[0] === ".") throw new Error("不能单独出现`.`");
this.emmitToken("NUMBER", this.token.join(""));
this.token = [];
return this.start(char); // put back char
}
}
emmitToken(type, value) {
this.tokens.push({
type,
value,
})
}
push(char){
// 每次执行 state 函数都会返回新的状态函数,实现状态迁移
this.state = this.state(char);
return this.check();
}
end(){
this.state(EOF);
return this.check();
}
check(){
// 检测是否有 token 生成并返回。
const _token = [...this.tokens];
this.tokens = [];
return _token;
}
clear(){
this.token = [];
this.tokens = [];
this.state = this.start;
}
}
const lexer = new lexer();
const input = `1 + 2.3`;
let tokens = [];
for (let c of input.split('')){
tokens = [...tokens,...lexer.push(c)];
}
tokens = [...tokens,...lexer.end()];
效果如下图:
自此,我们利用「用有限状态机」成功实现了「词法分析」,后面将进入到「语法分析」。
敬请期待下篇,「手写一个四则运算表达式转换成 AST 的方法(下)」。