编程能力 —— 解析表达式

关注
发布于: 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。
TokenNumber: 0 1 2 3 4 5 6 7 8 9 . 的组合
Operator: + - * / 之一
Whitespace: <SP>
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 的类型只会有两种 Number 和 MultiplicationExpression。
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 不是 Number 或 MultiplicativeExpression，那么这个乘法表达式就是不合法的，我们直接抛出错误。
﻿
最后执行下面的代码：
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，LogicalOrExpression 和 EOF。而 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算法推演一个实例
运算符优先级
﻿