写点什么

编程能力 —— 解析表达式

用户头像
wendraw
关注
发布于: 2020 年 07 月 10 日

我们在前面的文章 https://www.yuque.com/wendraw/fe/general-knowledge-programming-lang#ZKsVo 中已经学习了「产生式」,并且用 BNF 定义了一个支持括号、四则运算和逻辑运算的表达式。因此我们这篇文章就来完成一个任务。



将一个支持括号、四则运算和逻辑运算的表达式解析成 AST 树(抽象语法树)。



产生式(四则运算,不带括号和逻辑运算)

我们先做简单的四则运算,不带括号和逻辑运算,后面再加上。四则运算的产生式就是这样:

<AdditionExpression> ::=
<MultiplicationExpression> |
<AdditionExpression> "+" <MultiplicationExpression> |
<AdditionExpression> "-" <MultiplicationExpression>

<MultiplicationExpression> ::=
<Number> |
<MultiplicationExpression> "*" <Number> |
<MultiplicationExpression> "/" <Number>

// Number 我们先不搞太复杂,直接用正则来表示吧。
// 只有带小数点和不带小数点两种
<Number> ::= (?:0|[1-9][0-9]*)\.[0-9]*|(?:0|[1-9][0-9]*)



1. 词法分析(Lexical Analysis)

有了产生式之后,我们就要从表达式中拆分出「终结符」,也就是 <Number> 和各种符号(|| && + - * / ())。



在做正式的拆分之前,我们先要来分析一个四则运算还哪些词法。如,1024.1024 * 10 + 25 就有 4 种 Token。

  1. TokenNumber: 0 1 2 3 4 5 6 7 8 9 . 的组合

  2. Operator: + - * / 之一

  3. Whitespace: <SP>

  4. LineTerminator: <LF>、<CR>



这个过程其实就是将一串文本拆分成一个个的单词(Token),也就是「词法分析」。



我们在之前学习了 此处为语雀文档,点击链接查看:https://www.yuque.com/wendraw/fe/fsm 并且在 Toyed Browser 解析了 HTML 文本 ,然后我们又在上一篇学习了 JavaScript 中的 此处为语雀文档,点击链接查看:https://www.yuque.com/wendraw/fe/regular。因此我们就有两种方法拆分终结符。



正则表达式

词法分析如果用正则来做的话,就非常简单了。我们利用正则 () 捕获规则,就可以直接将对应的 Token 直接拆出来。



<script>
let regexp = /((?:0|[1-9][0-9]*)\.[0-9]*|(?:0|[1-9][0-9]*))|([ ]+)|([\r\n]+)|(\+)|(\-)|(\*)|(\/)/g;
const dict = ["Number", "Whitespace", "LineTerminator", "+", "-", "*", "/"];

function tokenize(source) {
let result = null;
let lastIndex = 0;
while (true) {
lastIndex = regexp.lastIndex;
result = regexp.exec(source);

if (!result) break;
// 这次匹配的长度有问题
if (regexp.lastIndex - lastIndex > result[0].length) {
console.log(lastIndex, regexp.lastIndex, result[0].length, result);
throw new Error("Unexpected token \"" +
source.slice(lastIndex, regexp.lastIndex - result[0].length) +
"\"!")
}

for (let i = 0; i < dict.length; i++) {
if (result[i + 1]) {
console.log(dict[i])
}
}
console.log(result[0]);
}
}

tokenize("1024.1024 * 10 + 25");
</script>

正则对应着 dict 数组的 7 中 Token。然后每次执行 regexp.exec 时都会匹配到一种 Token,并且会捕获到对应的位置。最后就能解析出来所有的终结符。



image.png



然后我们就要用解析出来的这些终结符,生成对应的 Token。我们在状态机中是用一个 emit 的函数,在对应的位置调用这个回调函数。其实 JS 中还有一个更优雅的做法,就是用 Generator + Iterator。



<script>
let tokens = tokenize("1024.1024 * 10 + 25")
console.log(tokens);

function tokenize(source) {
let tokens = [];

for (let token of lex(source)) {
if (token.type !== "Whitespace" && token.type !== "LineTerminator") {
tokens.push(token);
}
}
return tokens;

function* lex(source) {
let regexp = /((?:0|[1-9][0-9]*)\.[0-9]*|(?:0|[1-9][0-9]*))|([ ]+)|([\r\n]+)|(\+)|(\-)|(\*)|(\/)/g;
const dict = ["Number", "Whitespace", "LineTerminator", "+", "-", "*", "/"];

let result = null;
let lastIndex = 0;
while (true) {
lastIndex = regexp.lastIndex;
result = regexp.exec(source);

if (!result) break;

// 这次匹配的长度有问题
if (regexp.lastIndex - lastIndex > result[0].length) {
console.log(lastIndex, regexp.lastIndex, result[0].length, result);
throw new Error("Unexpected token \"" +
source.slice(lastIndex, regexp.lastIndex - result[0].length) +
"\"!")
}

let token = {
type: null,
value: null,
}
for (let i = 0; i < dict.length; i++) {
if (result[i + 1]) {
token.type = dict[i];
}
}
token.value = result[0];
yield token;
}
yield { type: "EOF" }
}
}
</script>

我们在 tokenize 内新增 lex() 的 generator 函数,然后每次得到一个终结符,我们就生成一个 Token,并且把它 yield 出去。最后当左右文本都解析完时,还要 yield 一个 EOF 的 token。



然后配合 for...of 就可以直接遍历 yield 出来的 token,而不是不断的的调用 next() 来获取值。最后我们去掉 Whitespace 和 LineTerminator 就得到所有有效的 token。



image.png



有限状态机

这部分的词法工作当然也可以用状态机来做,毕竟正则也是状态机来实现的。不过状态机对于正则来说,我们要写的代码更多,要管理所有的状态。不过管理的所有的状态,我们能做的事情更多,也就更灵活了。本篇文章就不过多介绍状态机的知识了,在 此处为语雀文档,点击链接查看:https://www.yuque.com/wendraw/fe/fsm 聊了很多,不熟悉的可以先去看看。



<script>
let tokens = tokenize(" 1024.1024 * 10 + 25");
console.log(tokens);

function tokenize(source) {
let tokens = [];
lex(source);
return tokens;

function lex(source) {
const EOF = Symbol("EOF"); // End Of File
let currentToken = null;

let state = start;
for (let char of source) {
state = state(char);
}
state = state(EOF);


function emit(token) {
tokens.push(token);
}

function start(c) {
if (c.match(/[ \r\n]/)) {
return start;
} else if (c.match(/[0-9\.]/)) {
currentToken = {
type: 'Number',
value: "",
}
return number(c);
} else {
return start;
}
}

function end(c) {
return end;
}

function number(c) {
if (c === EOF) {
emit(currentToken);
emit({
type: "EOF",
});
return end;
} else if (c.match(/[ \r\n]/)) {
emit(currentToken);
return whitespace;
} else if (c.match(/[0-9\.]/)) {
currentToken.value += c;
return number;
} else if (c === "+") {
emit(currentToken);
return plus;
} else if (c === "-") {
emit(currentToken);
return minus;
} else if (c === "*") {
emit(currentToken);
return multiply;
} else if (c === "/") {
emit(currentToken);
return divide;
} else {
throw new Error("number error");
}
}

function whitespace(c) {
if (c === EOF) {
emit(currentToken);
emit({
type: "EOF",
});
return end;
} else if (c.match(/[ \r\n]/)) {
return whitespace;
} else if (c === "+") {
currentToken = {
type: "+",
value: "+",
}
emit(currentToken);
return plus;
} else if (c === "-") {
currentToken = {
type: "-",
value: "-",
}
emit(currentToken);
return minus;
} else if (c === "*") {
currentToken = {
type: "*",
value: "*",
}
emit(currentToken);
return multiply;
} else if (c === "/") {
currentToken = {
type: "/",
value: "/",
}
emit(currentToken);
return divide;
} else {
throw new Error("whitespace error");
}
}

function plus(c) {
if (c.match(/[ \r\n]/)) {
return plus;
} else if (c.match(/[0-9\.]/)) {
currentToken = {
type: 'Number',
value: "",
}
return number(c);
} else {
throw new Error("plus error");
}
}

function minus(c) {
if (c.match(/[ \r\n]/)) {
return minus;
} else if (c.match(/[0-9\.]/)) {
currentToken = {
type: 'Number',
value: "",
}
return number(c);
} else {
throw new Error("minus error");
}
}

function multiply(c) {
if (c.match(/[ \r\n]/)) {
return multiply;
} else if (c.match(/[0-9\.]/)) {
currentToken = {
type: 'Number',
value: "",
}
return number(c);
} else {
throw new Error("multiply error");
}
}

function divide(c) {
if (c.match(/[ \r\n]/)) {
return divide;
} else if (c.match(/[0-9\.]/)) {
currentToken = {
type: 'Number',
value: "",
}
return number(c);
} else {
throw new Error("divide error");
}
}
}
}
</script>

我们这里的 lex() 就变成一个标准的状态机模版了,传进来的 source 文本用 for...of 拆分成一个个的字符,然后喂给状态机。然后 start 和 end 状态机也是模版式的处理方式。



我这里额外只用了 number、whitespace、plus、minus、multiply、divide 6个状态,然后没有 lineTerminator 状态,并进 whitespace 中了,因为这些都是废字符不需要处理,可以省一些代码。



最后所有的 token 会都通过回调 emit 丢出来。这些状态机都比较简单,就是 emit 调用的时机需要稍微思考一下,就是一种终结符结束了碰到其他符号就要 emit 了。



还有就是会在所有字符都处理完之后给状态机传一个 EOF,不过合法的四则运算表达式的结束符号应该是「number」或者「whitespace」,因此要在这两个状态里面判断 EOF 字符。



最后就得到结果和正则差不多,没有 Whitespace 的 token。



image.png



2. 语法分析(Syntactic Analysis,or Parsing)

有了 Token 之后我们就可以进行「语法分析」了,语法分析就是在词法分析的基础之上得到程序的语法结构。这个结构是一棵树,一般叫做「抽象语法树(Abstract Syntax Tree)」,简称 AST。



既然是要构建一棵树,我们就有两种方法。一种是自顶向下,向下扫描 Token 串,构建它的子节点。另一种是自底向上,先将最下面的叶子节点识别出来,然后再组装上一级节点。



也就是说语法分析一般有两种算法,它们分别对应的就是 LL 和 LR。



LL 分析器是一种处理某些上下文无关文法的自顶向下分析器。因为它从左(Left)到右处理输入,再对句型执行最左推导出语法树(Left derivation,相对于 LR 分析器)。能以此方法分析的文法称为 LL 文法。



LR 分析器是一种自底向上(bottom-up)的上下文无关语法分析器。LR 意指由左(Left)至右处理输入字符串,并以最右边优先派生(Right derivation)的推导顺序(相对于 LL 分析器)建构语法树。能以此方式分析的语法称为 LR 语法。而在 LR(k) 这样的名称中,k 代表的是分析时所需前瞻符号(lookahead symbol)的数量,也就是除了目前处理到的输入符号之外,还得再向右引用几个符号之意;省略 (k)时即视为 LR(1),而非 LR(0)。



理论部分看不懂没关系,我们直接实现 LL 算法来构建 AST 树,从代码出发就能更好的理解 LL 的定义了。



生成 MultiplicationExpression

我们先来生成一个乘法表达式,在前面的产生式中,<Number> 是一个终结符,而 <MultiplicationExpression> 是一个非终结符。

<MultiplicationExpression> ::=
<Number> |
<MultiplicationExpression> "*" <Number> |
<MultiplicationExpression> "/" <Number>



并且它有 3 种分支因此我们在生成 MultiplicationExpression 时,就要考虑 3 种情况。但是我们要记住的是,传进来的 Token 的类型只会有两种 NumberMultiplicationExpression

function buildAst(tokens) {
return multiplicativeExpression(tokens);

function multiplicativeExpression(tokens) {
if (tokens[0].type === "Number") {
let node = {
type: "MultiplicativeExpression",
children: tokens.shift()
}
tokens.unshift(node);
return multiplicativeExpression(tokens);
}

if (tokens[0].type === "MultiplicativeExpression" &&
tokens.length >= 1 &&
tokens[1].type === "*") {
if (tokens.length >= 2 && tokens[2].type === "Number") {
let node = {
type: "MultiplicativeExpression",
children: [tokens.shift(), tokens.shift(), tokens.shift()]
}
tokens.unshift(node);
return multiplicativeExpression(tokens);
} else {
throw new Error("Unexpected token type");
}
}

if (tokens[0].type === "MultiplicativeExpression" &&
tokens.length > 1 &&
tokens[1].type === "/") {
if (tokens.length >= 2 && tokens[2].type === "Number") {
let node = {
type: "MultiplicativeExpression",
children: [tokens.shift(), tokens.shift(), tokens.shift()]
}
tokens.unshift(node);
return multiplicativeExpression(tokens);
} else {
throw new Error("Unexpected token type");
}
}

if (tokens[0].type === "MultiplicativeExpression") {
return tokens[0];
} else {
throw new Error(`Invalid multiplication expression! Start with ${tokens[0].type}`)
}
}
}

multiplicativeExpression() 函数其实是与产生式一一对应的。



if (tokens[0].type === "Number") 分支对应产生式的第一层,就是表示如果来的是一个 Number,直接将它重新包装成一个 MultiplicativeExpression 放进 tokens 中,然后将 tokens 放进 multiplicativeExpression 递归调用,因为 后面还可能有 MultiplicativeExpression,乘法表达式是可以嵌套的。



if (tokens[0].type === "MultiplicativeExpression" && tokens.length > 1 && tokens[1].type === "*") 分支对应产生式的第二层,在 MultiplicativeExpression 之后要跟上一个 *,并且在 * 之后需要是一个 Number,如果不是就表示表达式有误,要抛出错误。



if (tokens[0].type === "MultiplicativeExpression" && tokens.length > 1 && tokens[1].type === "/") 分支对应产生式的第三层,跟第二层的操作一样。



最后 if (tokens[0].type === "MultiplicativeExpression") 就是前面的条件都不满足。



如果进来的 Token 是 MultiplicativeExpression,但是后面的 Token 不认识(不是 * 或者 /),或者后面没有Token。就说明乘法表达式已经构建完成了,并且存在 tokens[0],直接返回即可。



如果进来的第一个 Token 不是 NumberMultiplicativeExpression,那么这个乘法表达式就是不合法的,我们直接抛出错误。



最后执行下面的代码:

let tokens = tokenize("1024.1024 * 10 + 25")
let ast = buildAst(tokens);
console.log(ast);

就得到一个乘法表达式的 AST 树,我们注意到后面 + 没有识别出来,所以就直接返回了前面的乘法表达式。



image.png



生成 AdditiveExpression

有了 MultiplicativeExpression 之后我们就可以来生成 AdditiveExpression(加法表达式)。加法表达式的产生式就是:

<AdditionExpression> ::=
<MultiplicationExpression> |
<AdditionExpression> "+" <MultiplicationExpression> |
<AdditionExpression> "-" <MultiplicationExpression>

其实这个产生式的 <MultiplicationExpression> 还可以展开的,因此一个加法表达式的第一个输入值就有 三种可能 <Number>、<MultiplicationExpression> 和 <AdditionExpression>。



跟乘法表达式一样,我们将 <AdditionExpression> 产生式翻译成代码:

function buildAst(tokens) {
return additiveExpression(tokens);

function additiveExpression(tokens) {
if (tokens[0].type === "Number") {
multiplicativeExpression(tokens);
return additiveExpression(tokens);
}

if (tokens[0].type === "MultiplicativeExpression") {
let node = {
type: "AdditiveExpression",
children: [tokens.shift()]
}
tokens.unshift(node);
return additiveExpression(tokens);
}

if (tokens[0].type === "AdditiveExpression" &&
tokens.length > 1 &&
tokens[1].type === "+") {
let node = {
type: "AdditiveExpression",
children: [tokens.shift(), tokens.shift()]
}
multiplicativeExpression(tokens);
node.children.push(tokens.shift());
tokens.unshift(node);
return additiveExpression(tokens);
}

if (tokens[0].type === "AdditiveExpression" &&
tokens.length > 1 &&
tokens[1].type === "-") {
let node = {
type: "AdditiveExpression",
children: [tokens.shift(), tokens.shift()]
}
MultiplicativeExpression(tokens);
node.children.push(tokens.shift());
tokens.unshift(node);
return additiveExpression(tokens);
}

if (tokens[0].type === "AdditiveExpression") {
return tokens[0];
} else {
throw new Error(`Invalid additive expression! Start with ${tokens[0].type}`)
}
}

// ......
}

首先是 if (tokens[0].type === "Number") 分支,如果进来的是一个 Number,我们直接传给 multiplicativeExpression() 函数,让它来将 Number 及其后面可能的 * / 表达式包装成 <MultiplicativeExpression>。



if (tokens[0].type === "MultiplicativeExpression") 分支就是上面产生式的第一层,遇到这个我们就可以直接将其包装成 AdditiveExpression 的 Token。



if (tokens[0].type === "AdditiveExpression" && tokens.length > 1 && tokens[1].type === "+") 分支对应的就是产生式的第二层,AdditiveExpression 后面跟上了一个 "+" 终结符。这时候我们仍然是生成一个  AdditiveExpression 的 Token,不过 + 后面是要跟上一个 <MultiplicativeExpression>,因此只能先将 AdditiveExpression 和 + 的 token 放到 children 里。+ 后面的 token 再用 multiplicativeExpression() 函数包装成 <MultiplicativeExpression> 再放到 children 里。至此一个 "+" 的 AdditiveExpression 就生成了。



if (tokens[0].type === "AdditiveExpression" && tokens.length > 1 && tokens[1].type === "+") 分支对应的是产生式的第三层,处理方法跟上面是一样的。



最后执行代码就得到了一个加法表达式的 AST。



image.png



生成 Expression

最后就是要生成一个表达式的 AST。因为我们的 Token 其实还剩下 EOF 没有处理,我们要处理到 EOF 这个表达式才算完整。

function buildAst(tokens) {
return expression(tokens);

function expression(tokens) {
if (tokens[0].type === "AdditiveExpression" && tokens[1].type === "EOF") {
let node = {
type: "Expression",
children: [tokens.shift(), tokens.shift()]
}
tokens.unshift(node);
return node;
}
additiveExpression(tokens);
return expression(tokens);
}
// ......
}

这部分的代码其实也比较简单,就是生成整棵树的顶点。



当第一个 token 是 AdditiveExpression 并且第二个 token 是 EOF。那就说明整个表达式解析完了,就直接将它们包装成 Expression 返回即可。如果还没结束就要继续交给 additiveExpression() 函数来生成加法表达式。



最后执行就得到一个完整的表达式 AST。



image.png



这整个语法分析的算法就是从根节点开始,递归的生成子树,这就是 LL 算法。



3. 产生式(带括号和逻辑运算)

我们搞定了四则运算表达式,接下来就要继续升级,在四则运算的基础之上再加入「括号」和「逻辑运算」。那么对应的产生式就是:

<LogicalOrExpression> ::=
<LogicalAndExpression> |
<LogicalExpression> "||" <LogicalAndExpression>

<LogicalAndExpression> ::=
<AdditionExpression> |
<LogicalExpression> "&&" <AdditionExpression>

<AdditionExpression> ::=
<MultiplicationExpression> |
<AdditionExpression> "+" <MultiplicationExpression> |
<AdditionExpression> "-" <MultiplicationExpression>

<MultiplicationExpression> ::=
<PrimaryExpression> |
<MultiplicationExpression> "*" <PrimaryExpression> |
<MultiplicationExpression> "/" <PrimaryExpression>

<PrimaryExpression> ::=
<Number> |
"(" <LogicalOrExpression> ")"

// Number 我们先不搞太复杂,直接用正则来表示吧。
// 只有带小数点和不带小数点两种
<Number> ::= (?:^0|[1-9][0-9]*)\.[0-9]*|(?:^0|[1-9][0-9]*)

可以看到我们这里增加了 <PrimaryExpression> 表示带括号的表达式,由于它的优先级最高跟一个 <Number> 差不多,因此 PrimaryExpression 的产生式第一层就是 <Number>,并且会作为 <MultiplicationExpression> 的基本单元。然后它的特征是带上 "("")" 终结符,在这个括号里可以放入任何表达式,因此括号中间就是一个 <LogicalOrExpression>。



还新增了 <LogicalOrExpression> 和 <LogicalAndExpression>,之所以要把这两个逻辑运算表达式拆开是因为在 JavaScript 中它们的优先级是不一样的,&& 比 || 的优先级更高。因此在最顶层是一个  LogicalOrExpression,然后才是 MultiplicationExpression。



词法分析

表达式的种类变多了对应的终结符也就变多了,词法分析部分的代码我们也就需要修改。



对于正则部分的代码来说,只需要修改正则表达式的内容,增加 || && ( ) 四种终结符的匹配即可。

function* lex(source) {
let regexp = /((?:0|[1-9][0-9]*)\.[0-9]*|(?:0|[1-9][0-9]*))|([ ]+)|([\r\n]+)|(\+)|(\-)|(\*)|(\/)|(\|\|)|(&&)|(\()|(\))/g;
const dict = ["Number", "Whitespace", "LineTerminator", "+", "-", "*", "/", "||", "&&", "(", ")"];
// ......
}

其他部分的代码完全不需要修改,最后执行 tokenize("233 * (1024 - 88) || 0 && 1") 得到结果:



image.png



对于状态机部分的代码,我们需要修改的内容比较多,需要加上对应的 || && ( ) 几种状态机。

function tokenize(source) {
let tokens = [];
lex(source);
return tokens;

function lex(source) {
const EOF = Symbol("EOF"); // End Of File
let currentToken = null;

let state = start;
for (let char of source) {
state = state(char);
}
state = state(EOF);


function emit(token) {
tokens.push(token);
}

function start(c) {
if (c.match(/[ \r\n]/)) {
return start;
} else if (c.match(/[0-9\.]/)) {
currentToken = {
type: 'Number',
value: "",
}
return number(c);
} else if (c === "(") {
currentToken = {
type: '(',
value: "(",
}
emit(currentToken);
return parenthesisLeft;
} else {
return start;
}
}

function end(c) {
return end;
}

function number(c) {
if (c === EOF) {
emit(currentToken);
emit({
type: "EOF",
});
return end;
} else if (c.match(/[ \r\n]/)) {
emit(currentToken);
return whitespace;
} else if (c.match(/[0-9\.]/)) {
currentToken.value += c;
return number;
} else if (c === "+") {
emit(currentToken);
return plus;
} else if (c === "-") {
emit(currentToken);
return minus;
} else if (c === "*") {
emit(currentToken);
return multiply;
} else if (c === "/") {
emit(currentToken);
return divide;
} else if (c === "|") {
emit(currentToken);
return logicOr;
} else if (c === "&") {
emit(currentToken);
return logicAnd;
} else if (c === ")") {
emit(currentToken);
currentToken = {
type: ")",
value: ")",
}
emit(currentToken);
return parenthesisRight;
} else {
throw new Error("number state error");
}
}

function whitespace(c) {
if (c === EOF) {
emit(currentToken);
emit({
type: "EOF",
});
return end;
} else if (c.match(/[ \r\n]/)) {
return whitespace;
} else if (c === "+") {
currentToken = {
type: "+",
value: "+",
}
emit(currentToken);
return plus;
} else if (c === "-") {
currentToken = {
type: "-",
value: "-",
}
emit(currentToken);
return minus;
} else if (c === "*") {
currentToken = {
type: "*",
value: "*",
}
emit(currentToken);
return multiply;
} else if (c === "/") {
currentToken = {
type: "/",
value: "/",
}
emit(currentToken);
return divide;
} else if (c === "|") {
return logicOr;
} else if (c === "&") {
return logicAnd;
} else if (c === "(") {
currentToken = {
type: "(",
value: "(",
}
emit(currentToken);
return parenthesisLeft;
} else if (c === ")") {
currentToken = {
type: ")",
value: ")",
}
emit(currentToken);
return parenthesisRight;
} else {
throw new Error("whitespace state error");
}
}

function plus(c) {
if (c.match(/[ \r\n]/)) {
return plus;
} else if (c.match(/[0-9\.]/)) {
currentToken = {
type: 'Number',
value: "",
}
return number(c);
} else if (c === "(") {
currentToken = {
type: "(",
value: "(",
}
emit(currentToken);
return parenthesisLeft;
} else if (c === ")") {
currentToken = {
type: ")",
value: ")",
}
emit(currentToken);
return parenthesisRight;
} else {
throw new Error("plus state error");
}
}

function minus(c) {
if (c.match(/[ \r\n]/)) {
return minus;
} else if (c.match(/[0-9\.]/)) {
currentToken = {
type: 'Number',
value: "",
}
return number(c);
} else if (c === "(") {
currentToken = {
type: "(",
value: "(",
}
emit(currentToken);
return parenthesisLeft;
} else if (c === ")") {
currentToken = {
type: ")",
value: ")",
}
emit(currentToken);
return parenthesisRight;
} else {
throw new Error("minus state error");
}
}

function multiply(c) {
if (c.match(/[ \r\n]/)) {
return multiply;
} else if (c.match(/[0-9\.]/)) {
currentToken = {
type: 'Number',
value: "",
}
return number(c);
} else if (c === "(") {
currentToken = {
type: "(",
value: "(",
}
emit(currentToken);
return parenthesisLeft;
} else if (c === ")") {
currentToken = {
type: ")",
value: ")",
}
emit(currentToken);
return parenthesisRight;
} else {
throw new Error("multiply state error");
}
}

function divide(c) {
if (c.match(/[ \r\n]/)) {
return divide;
} else if (c.match(/[0-9\.]/)) {
currentToken = {
type: 'Number',
value: "",
}
return number(c);
} else if (c === "(") {
currentToken = {
type: "(",
value: "(",
}
emit(currentToken);
return parenthesisLeft;
} else if (c === ")") {
currentToken = {
type: ")",
value: ")",
}
emit(currentToken);
return parenthesisRight;
} else {
throw new Error("divide state error");
}
}

function logicOr(c) {
if (c === "|") {
currentToken = {
type: "||",
value: "||",
}
emit(currentToken);
return logicOrAfter;
} else {
throw new Error("logicOr state error");
}
}

function logicOrAfter(c) {
if (c.match(/[ \r\n]/)) {
return logicOrAfter;
} else if (c.match(/[0-9\.]/)) {
currentToken = {
type: 'Number',
value: "",
}
return number(c);
} else if (c === "(") {
currentToken = {
type: "(",
value: "(",
}
emit(currentToken);
return parenthesisLeft;
} else if (c === ")") {
currentToken = {
type: ")",
value: ")",
}
emit(currentToken);
return parenthesisRight;
} else {
throw new Error("logicOrAfter state error");
}
}

function logicAnd(c) {
if (c === "&") {
currentToken = {
type: "&&",
value: "&&",
}
emit(currentToken);
return logicAndAfter;
} else {
throw new Error("logicAnd state error");
}
}

function logicAndAfter(c) {
if (c.match(/[ \r\n]/)) {
return logicAndAfter;
} else if (c.match(/[0-9\.]/)) {
currentToken = {
type: 'Number',
value: "",
}
return number(c);
} else if (c === "(") {
currentToken = {
type: "(",
value: "(",
}
emit(currentToken);
return parenthesisLeft;
} else if (c === ")") {
currentToken = {
type: ")",
value: ")",
}
emit(currentToken);
return parenthesisRight;
} else {
throw new Error("logicAndAfter state error");
}
}

function parenthesisLeft(c) {
if (c.match(/[ \r\n]/)) {
return parenthesisLeft;
} else if (c.match(/[0-9\.]/)) {
currentToken = {
type: 'Number',
value: "",
}
return number(c);
} else {
throw new Error("parenthesisLeft state error");
}
}

function parenthesisRight(c) {
if (c === EOF) {
emit(currentToken);
emit({
type: "EOF",
});
return end;
} else if (c.match(/[ \r\n]/)) {
return parenthesisRight;
} else if (c === "+") {
currentToken = {
type: "+",
value: "+",
}
emit(currentToken);
return plus;
} else if (c === "-") {
currentToken = {
type: "-",
value: "-",
}
emit(currentToken);
return minus;
} else if (c === "*") {
currentToken = {
type: "*",
value: "*",
}
emit(currentToken);
return multiply;
} else if (c === "/") {
currentToken = {
type: "/",
value: "/",
}
emit(currentToken);
return divide;
} else if (c === "|") {
return logicOr;
} else if (c === "&") {
return logicAnd;
} else {
throw new Error("parenthesisLeft state error");
}
}
}
}

这部分的代码我就不详细介绍了,其实内容很通俗易懂。就是要考虑的边界条件非常多,也就是每个终结符下一个合法的字符是什么需要考虑全面。最好的方法是做全面的单元测试,都是体力活,我这里就偷懒了。感兴趣的同学可以自己测试修改一下 bug,然后欢迎给我提交代码😉😉。



我们同样执行一下 tokenize("233 * (1024 - 88) || 0 && 1"),最后能得到跟正则一样的答案。



image.png



语法分析

把 token 拆分之后语法部分也需要修改了,这部分改动比较大,不过主要也就是翻译产生式。

function buildAst(tokens) {
return expression(tokens);

function expression(tokens) {
if (tokens[0].type === "LogicalOrExpression" && tokens[1].type === "EOF") {
let node = {
type: "Expression",
children: [tokens.shift(), tokens.shift()]
}
tokens.unshift(node);
return node;
}
logicalOrExpression(tokens);
return expression(tokens);
}

function logicalOrExpression(tokens) {
if (tokens[0].type === "(") {
logicalAndExpression(tokens);
return logicalOrExpression(tokens);
}

if (tokens[0].type === "Number") {
logicalAndExpression(tokens);
return logicalOrExpression(tokens);
}

if (tokens[0].type === "LogicalAndExpression") {
let node = {
type: "LogicalOrExpression",
children: [tokens.shift()]
}
tokens.unshift(node);
return logicalOrExpression(tokens);
}

if (tokens[0].type === "LogicalOrExpression" &&
tokens.length > 1 &&
tokens[1].type === "||") {
let node = {
type: "LogicalOrExpression",
children: [tokens.shift(), tokens.shift()]
}
logicalAndExpression(tokens);
node.children.push(tokens.shift());
tokens.unshift(node);
return logicalOrExpression(tokens);
}

if (tokens[0].type === "LogicalOrExpression") {
return tokens[0];
} else {
throw new Error(`Invalid logical or expression! Start with ${tokens[0].type}`)
}
}

function logicalAndExpression(tokens) {
if (tokens[0].type === "(") {
additiveExpression(tokens);
return logicalAndExpression(tokens);
}

if (tokens[0].type === "Number") {
additiveExpression(tokens);
return logicalAndExpression(tokens);
}

if (tokens[0].type === "AdditiveExpression") {
let node = {
type: "LogicalAndExpression",
children: [tokens.shift()]
}
tokens.unshift(node);
return logicalAndExpression(tokens);
}

if (tokens[0].type === "LogicalAndExpression" &&
tokens.length > 1 &&
tokens[1].type === "&&") {
let node = {
type: "LogicalAndExpression",
children: [tokens.shift(), tokens.shift()]
}
additiveExpression(tokens);
node.children.push(tokens.shift());
tokens.unshift(node);
return logicalAndExpression(tokens);
}

if (tokens[0].type === "LogicalAndExpression") {
return tokens[0];
} else {
throw new Error(`Invalid logical and expression! Start with ${tokens[0].type}`)
}
}

function additiveExpression(tokens) {
if (tokens[0].type === "(") {
multiplicativeExpression(tokens);
return additiveExpression(tokens);
}

if (tokens[0].type === "Number") {
multiplicativeExpression(tokens);
return additiveExpression(tokens);
}

if (tokens[0].type === "MultiplicativeExpression") {
let node = {
type: "AdditiveExpression",
children: [tokens.shift()]
}
tokens.unshift(node);
return additiveExpression(tokens);
}

if (tokens[0].type === "AdditiveExpression" &&
tokens.length > 1 &&
tokens[1].type === "+") {
let node = {
type: "AdditiveExpression",
children: [tokens.shift(), tokens.shift()]
}
multiplicativeExpression(tokens);
node.children.push(tokens.shift());
tokens.unshift(node);
return additiveExpression(tokens);
}

if (tokens[0].type === "AdditiveExpression" &&
tokens.length > 1 &&
tokens[1].type === "-") {
let node = {
type: "AdditiveExpression",
children: [tokens.shift(), tokens.shift()]
}
multiplicativeExpression(tokens);
node.children.push(tokens.shift());
tokens.unshift(node);
return additiveExpression(tokens);
}

if (tokens[0].type === "AdditiveExpression") {
return tokens[0];
} else {
throw new Error(`Invalid additive expression! Start with ${tokens[0].type}`)
}
}

function multiplicativeExpression(tokens) {
if (tokens[0].type === "(") {
primaryExpression(tokens);
return multiplicativeExpression(tokens);
}

if (tokens[0].type === "Number") {
primaryExpression(tokens);
return multiplicativeExpression(tokens);
}

if (tokens[0].type === "PrimaryExpression") {
let node = {
type: "MultiplicativeExpression",
children: [tokens.shift()]
}
tokens.unshift(node);
return multiplicativeExpression(tokens);
}

if (tokens[0].type === "MultiplicativeExpression" &&
tokens.length >= 1 &&
tokens[1].type === "*") {
let node = {
type: "MultiplicativeExpression",
children: [tokens.shift(), tokens.shift()]
}
primaryExpression(tokens);
node.children.push(tokens.shift());
tokens.unshift(node);
return multiplicativeExpression(tokens);
}

if (tokens[0].type === "MultiplicativeExpression" &&
tokens.length > 1 &&
tokens[1].type === "/") {
let node = {
type: "MultiplicativeExpression",
children: [tokens.shift(), tokens.shift()]
}
primaryExpression(tokens);
node.children.push(tokens.shift());
tokens.unshift(node);
return multiplicativeExpression(tokens);
}

if (tokens[0].type === "MultiplicativeExpression") {
return tokens[0];
} else {
throw new Error(`Invalid multiplication expression! Start with ${tokens[0].type}`)
}
}

function primaryExpression(tokens) {
if (tokens[0].type === "Number") {
let node = {
type: "PrimaryExpression",
children: tokens.shift(),
}
tokens.unshift(node);
return primaryExpression(tokens);
}

if (tokens[0].type === "(") {
let node = {
type: "PrimaryExpression",
children: [tokens.shift()],
}
logicalOrExpression(tokens);
if (tokens.length > 1 &&
tokens[0].type === "LogicalOrExpression" &&
tokens[1].type === ")") {
node.children.push(tokens.shift(), tokens.shift());
tokens.unshift(node);
}
return primaryExpression(tokens);
}

if (tokens[0].type === "PrimaryExpression") {
return tokens[0];
} else {
throw new Error(`Invalid primary expression! Start with ${tokens[0].type}`)
}
}
}

不过这里需要注意的是,每个非终结符 <LogicalOrExpression> <LogicalAndExpression> <AdditionExpression> <MultiplicationExpression> 都可以拆到 <Number> 或者 "(",因此对应的函数,进来的第一个 Token 就有可能是这两个,需要加入判断。



最后执行

<script>
let tokens = tokenize("(1024*10) + 123 && 0 || 1");
let ast = buildAst(tokens);
console.log(JSON.stringify(ast, null, 2));
// ......
</script>

就得到一个完整的表达式的 AST。

{
"type": "Expression",
"children": [
{
"type": "LogicalOrExpression",
"children": [
{
"type": "LogicalOrExpression",
"children": [
{
"type": "LogicalAndExpression",
"children": [
{
"type": "LogicalAndExpression",
"children": [
{
"type": "AdditiveExpression",
"children": [
{
"type": "AdditiveExpression",
"children": [
{
"type": "MultiplicativeExpression",
"children": [
{
"type": "PrimaryExpression",
"children": [
{
"type": "(",
"value": "("
},
{
"type": "LogicalOrExpression",
"children": [
{
"type": "LogicalAndExpression",
"children": [
{
"type": "AdditiveExpression",
"children": [
{
"type": "MultiplicativeExpression",
"children": [
{
"type": "MultiplicativeExpression",
"children": [
{
"type": "PrimaryExpression",
"children": {
"type": "Number",
"value": "1024"
}
}
]
},
{
"type": "*",
"value": "*"
},
{
"type": "PrimaryExpression",
"children": {
"type": "Number",
"value": "10"
}
}
]
}
]
}
]
}
]
},
{
"type": ")",
"value": ")"
}
]
}
]
}
]
},
{
"type": "+",
"value": "+"
},
{
"type": "MultiplicativeExpression",
"children": [
{
"type": "PrimaryExpression",
"children": {
"type": "Number",
"value": "123"
}
}
]
}
]
}
]
},
{
"type": "&&",
"value": "&&"
},
{
"type": "AdditiveExpression",
"children": [
{
"type": "MultiplicativeExpression",
"children": [
{
"type": "PrimaryExpression",
"children": {
"type": "Number",
"value": "0"
}
}
]
}
]
}
]
}
]
},
{
"type": "||",
"value": "||"
},
{
"type": "LogicalAndExpression",
"children": [
{
"type": "AdditiveExpression",
"children": [
{
"type": "MultiplicativeExpression",
"children": [
{
"type": "PrimaryExpression",
"children": {
"type": "Number",
"value": "1"
}
}
]
}
]
}
]
}
]
},
{
"type": "EOF"
}
]
}



4. 压缩 AST

我们可以看到 AST 的嵌套的层级非常深,其实很多层级是完全没有必要的。那么我们可以进一步优化一下这个树的结构。



主要的思想就是遍历整棵树,如果当前节点的子节点只有一个,那么就将子节点替代当前节点。由于我们这里需要删除节点,那么就要用到父节点,要通过父节点来删除。最好的做法就是用 DFS 来处理了,因此代码就是比较简单了。



function compress(ast) {
dfs(ast, 0, ast.children[0]);
function dfs(pre, i, root) {
if (!root) return;
if (root.children && Array.isArray(root.children)) {
if (root.children.length === 1) {
if (pre) {
pre.children[i] = root.children[0];
dfs(pre, i, pre.children[i])
}
} else {
for (let i = 0; i < root.children.length; i++) {
dfs(root, i, root.children[i]);
}
}
}
}
}

dfs 函数的  3 个参数,pre 就是父节点,i 就是要删除的节点是第几个 child,root 就是要删除的节点了。



然后就是 AST 有的节点就是一个对象,有个是一个数组。我们这里只压缩数组,对象节点有 EOF、Number、运算符和 PrimaryExpression(这个的数据结构我们后面需要改成数组)。



之后的逻辑就比较简单了,如果 root.children 的长度为 1,那么就删除 root 这个节点。如果不只一个,那么就不需要删除,继续递归的往下找。



最后的 dfs(ast, 0, ast.children[0]); 是考虑到我们的 AST 一定是两个 child,LogicalOrExpressionEOF。而 EOF 是不用管的,所以我们就直接传递 LogicalOrExpression 节点开始处理即可。



我们还要将 PrimaryExpression 的数据结构改一下,当来的是一个 Number 时,我们之前是直接存 Number 这个 Token 对象。这个部分我们的压缩算法会处理不到,因此要把它改成和其他的「非终结符」一样,children 都用数组来存储。

function primaryExpression(tokens) {
if (tokens[0].type === "Number") {
let node = {
type: "PrimaryExpression",
children: [tokens.shift()], // ---> children: tokens.shift()
}
tokens.unshift(node);
return primaryExpression(tokens);
}
// ......
}



最后执行代码

<script>
let tokens = tokenize("(1024*10) + 123 && 0 || 1");
let ast = buildAst(tokens);
compress(ast);
console.log(ast);
// ......
</script>

就得到压缩后的 AST 了,跟上面对比一下会发现少了很多无用的信息。



image.png



5. 计算

我们解析了四则运算表达式,最后当然是要将这个表达式的值给计算出来。



计算这部分的代码核心就是要处理优先级,其实在我们的产生式部分已经考虑了优先级。产生式是一层层嵌套的,那么要想计算上层的表达式,就必须要先算出内层的表达式,直到这个表达式是一个非终结符(一个可以直接使用的值)。



对算法比较敏感的同学应该能一下就想到,这个非常适合使用递归来处理。那么具体应该怎么计算呢?我们有了压缩后的 AST 就能非常清晰的看到所有的表达式(顶层的 Expression 不算),都是 3 个 child 的结构,第一个是左值,第二个是运算符,第三个是右值。当然这里还有一个例外,就是带括号的表达式,它是两个括号包裹一个表达式。



总之我们就可以利用表达式的这个特性来递归的求解。

function calculate(ast) {
let node = ast.children[0];
return dfs(node);
function dfs(root) {
if (root.type === "Number") {
return Number(root.value);
}
if (root.type === "PrimaryExpression") {
return dfs(root.children[1]);
}

let left = dfs(root.children[0]);
let operator = root.children[1];
let right = dfs(root.children[2]);
console.log(left, operator, right);
if (operator.type === "||") {
return left || right;
} else if (operator.type === "&&") {
return left && right;
} else if (operator.type === "+") {
return left + right;
} else if (operator.type === "-") {
return left - right;
} else if (operator.type === "*") {
return left * right;
} else if (operator.type === "/") {
return left / right;
}
}
}



最后执行 calculate(ast) 计算,并且与只用 JS 执行的结果对比。

<script>
let tokens = tokenize("(1024*10) + 123 && 0 || 1");
let ast = buildAst(tokens);
compress(ast);
console.log(ast);
let value = calculate(ast);
console.log("结果:", value);
console.log('直接执行 (1024*10) + 123 && 0 || 1 表达式的结果:', (1024*10) + 123 && 0 || 1)
</script>

可以看到结果完全一致



image.png



总结

本篇文章结合了很多之前学的知识,将一个支持括号、四则运算和逻辑运算的表达式解析成 AST 树(抽象语法树)。最后还压缩了 AST 的结构,并且计算出了表达式最终的值。



到这里其实我们已经完成了「解析代码」 --> 「执行代码」的小闭环。后续还可以加上更多的内容,比如 Statement、Structure,一直可做到 JS。当然有了这些基础也可以设计一个自己专属的小语言。



最后的代码已经上传到 GitHub expression-parsing 欢迎提 bug。觉得还不错有点收获的话,点个小星星呗。



参考

winter 前端进阶训练营

01 | 理解代码:编译器的前端技术

17 | First和Follow集合:用LL算法推演一个实例

18 | 移进和规约:用LR算法推演一个实例

运算符优先级



发布于: 2020 年 07 月 10 日阅读数: 155
用户头像

wendraw

关注

还未添加个人签名 2018.05.07 加入

还未添加个人简介

评论

发布
暂无评论
编程能力 —— 解析表达式