手写一个四则运算表达式转换成AST的方法（上）
0 前言
晓强哥在他的上篇文章 Javascript抽象语法树上篇(基础篇) 里介绍了 Javascript 抽象语法树里面「提到获得抽象语法树的过程为：代码 => 词法分析 => 语法分析 => AST」，抱着深究技术细节的目的，我决定研究这里的词法分析和语法分析，写一个简单的四则运算表达式转换成 AST 的方法，于是就有了下面的内容。
1 人类和计算机对于表达式的看法是不同的
人类习惯 a + b 这种表达叫做「中序表达式」，优点是比较简单直观，缺点是要用一堆括号来确定优先级 (a + b) * (c + d)。
这里说简单直观是相对人类的思维结构来说的，对计算机而言中序表达式是非常复杂的结构。
为了计算机计算方便，我们需要将中序表达式转换成树形结构，也就是「抽象语法树 AST」。
2 javascript 与抽象语法树 AST
我们知道，几乎任何语言中，代码在 "编译"（解释型语言在运行时也有编译的过程） 的过程中，都会生成一种树状的中间状态，这就是 AST。有些语言会直接把类似 AST 的语法暴露给程序员（例如：lisp、elixir、python 等）。但是 javascript 并没有这个能力，但是我们可以用 javascript 自身实现这个过程。
获得抽象语法树的过程为：代码（字符串） => 词法分析（Lexer）=> Tokens => 语法分析（Parser） => AST。
3 词法分析（Lexer）
词法分析有点像中文的分词，就是将字符串流根据规则生成一个一个的有具体意义的 Token ，形成 Token 流，然后流入下一步。
我们看一个简单的例子，
1 + 2.3
很明显这个表达式是可以分成三个 Token ，分别是 1 , + , 2.3。
词法分析这里，我们可以用有限状态机来解决。
3.1 有限状态机
绝大多数语言的词法部分都是用状态机实现的，我们下面就画出有限状态机的图形，然后根据图形直观地写出解析代码，总体图大概是这样。
下面拆开细看。
3.2 开始（start）状态
状态机的初始状态是 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;
}
}
3.3 在整数（inInt）状态
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
}
}
3.4 在浮点数（inFloat）状态
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
}
}
3.5 输出的 Token 种类 和定义
我将 「浮点数 Token」 和 「整数 Token」 合并为 [NUMBER Token] , 其他的 Token 还有 「SIGN Token」 和 「EOF Token」。
Token 的 定义：
interface Token{
type:String,
value:String,
}
3.6 完整的 Lexer 代码
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()];
效果如下图：
3.7 小结
自此，我们利用「用有限状态机」成功实现了「词法分析」，后面将进入到「语法分析」。
敬请期待下篇，「手写一个四则运算表达式转换成 AST 的方法（下）」。
腾讯云开发者
