尝试编写一个编译器

起因

Manim 群友 Fran 做了一个 QQ tex bot 并引入了群聊，看起来挺好用的，只需要满足匹配规则的消息就能生成公式的图片。它的依赖是 Fran 自改的 asciimathml 工具，能够使用比较简单的 ASCII 字符来表达比较复杂的公式。

这个原项目其实应该说年代有点久远了，而且源码与 DOM 是强耦合的，导致在 Node.js 环境下会有很多潜在的问题，而且也没有类型提示，所以我就有了重构它的想法。

我想做的其实就只是把 asciimath 格式的字符串转化为 $\LaTeX$ 格式的字符串，并不想去把 asciimathml 这种带标签的字符串转换为 $\LaTeX$ 的 DOM 元素了，毕竟现在也有 KaTeX 和 MathJax 这些工具，也就没有必要再去做这个工作了。

同时，前面也说到，旧代码与 DOM 耦合度非常高，因此，我想要做的，就是纯字符串处理的一个程序，而基本上完全与 DOM 隔离开。

项目编写流程

Tokenize

先看一个例子，下面的数学公式应该被渲染为 $\displaystyle{ \int _{ 0 } ^{ + \infty } \text{e} ^{ - x } {\text{d}x} = 1 }$

int_0^(+oo) "e"^(-x) dx = 1

我们发现，这个公式包含了非常多的关键字，以及一些可以直接作为 $\LaTeX$ 代码字符串的部分，我们需要找出所有的关键字，把它们包装成一些指定的类型（例如普通关键字、带有一个参数的关键字、带有多个参数的关键字等等），形成一个 token 序列，然后把它们传给下一级做进一步处理。

然而，asciimath 中内置的关键字就有 200 多个，而且应当还能添加自定义关键字，如果读取不固定的字符串，与非常大的一个集合去匹配，这样做显然是不明智的。对于这种情况，我们也就理所应当地使用字典树来进行匹配了¹。

构建字典树

我们在算法中认识的字典树，通常每个节点内字符元素的长度是 26，因为我们常用的也就是 26 个英文字母。而在这里，关键字可能包含大小写、一些特殊符号等，所以还必须向节点中额外添加一些元素，以满足当前的要求。

然而，这样又会让由字符找到数组索引较为困难。由于 Ascii 字符也不是很多，因此直接用一个 Map 映射就可以了。当然，应该还有更好的解决方案只是现在代码已经写完了，我也懒得改了。

搜索关键字

其实这棵字典树承担了 Tokenize 的所有工作，包括识别关键字、数字、其他符号等。另外受 markdown 启发，用一个空行来表示换行，因此也就用这种方式来作为 align 环境下的换行符了。

这样我们就有了这样的优先级排序

与此同时，将这些 token 分类，得到一个序列，而后传给下一步骤。

Parse

对于一个扁平的 token 序列，我们肯定需要使用递归才能创建一个树形的结构，而整个程序的流程大概就是这样

function parser(tokens: TokenizedValue[]) {
  const root = createRootNode()
  let current = 0
  while (current < tokens.length) {
    const res = walk(tokens, current) // 读取并处理一个节点
    root.body.push(res.node)          // 将读取到的节点加入序列中
    current = res.current             // 更新当前指针
  }
  return root
}

而最关键的逻辑就在 walk 中了。

简单的 Token 处理方法

对于数字、正体文本、可以单独使用的符号，可以直接简单的创建对应的节点即可，不需要递归处理，这其实也就相当于是递归的一部分终止情况。

被左右括号包裹的情况

我们将 [1,2,3] 这种仅仅包含逗号的序列，直接作为普通的数组来看，因此事实上可以直接依次返回，但我们还是将它包裹为一个节点的序列，将整个节点序列封装为一个新的节点而后返回。

如果这个被括号包裹的序列中出现了分号，那么我们就需要将它处理为矩阵。例如 [1,2;3,4]

这样其实逻辑就很明了了，只需要逐行地去构建矩阵就行了。

然而，我在 asciimath.org 看到了另外的一个用法，我也想把它复刻过来

[1, 2 | 3; 4, 5 | 6]

思路是，在 matrix 环境内再嵌套一个 array 环境，使用 {cc|c} 参数来指定分割线的位置。为了简单化处理，在扫描矩阵的每一行时，每当遇到 | 时，都记录下当前竖线所在矩阵的位置，最后汇总所有竖线应当出现的列数，得到对应的 {cc|c} 参数即可。

综上，这一段程序需要不断向后查找，直到找到匹配的右括号，还需要判断在这一段 token 序列中是否出现了分号，以此来判断要将它处理为数组、矩阵还是其他类型。

被竖线包裹的表达式

竖线作为一个非常特殊的存在，可以作为绝对值两侧的包裹，也可以作为矩阵行列式的左右包裹，还能单独使用，因此也是需要像上面矩阵中说到的那样预先判断，而后才能进一步处理。

有以下这些情况，分别处理即可。

• 单独使用 $\displaystyle{ \left\lbrace \left( x , y \right) \mid x ^{ 2 } + y ^{ 2 } \leqslant 1 \right\rbrace }$
• 绝对值 $\displaystyle{ \left| \ln x \right| }$
• 行列式 $\displaystyle{ \left| \begin{array}{cc} 1 & 2 \\ 3 & 4 \end{array} \right| }$

除法

我们希望用一个 / 符号就能表示除法，并将这个表达式转换为分式 frac 的形式，那么就不得不在读取完当前节点 $\displaystyle{ A }$ 后，立即向后观察是否存在除法。如果存在，那么还需要进一步读取，得到分母 $\displaystyle{ B }$ 后，将它渲染为 \frac{A}{B} 的形式。于是，walk 程序应当这样安排。

function walk(tokens: TokenizedValue[], current: number) {
  // 将当前的 token 处理为 ast 的节点，并使指针前进
  const token = tokens[current]
  let { node, cur } = processCurrentToken(token)
  current = cur
  if (current < tokens.length) {
    const nextToken = tokens[current]
    // 检测下一个 token 是否为除法
    if (nextToken.type === TokenTypes.Div) {
      // 创建一个双参数节点
      const newNode = createNodeWithTwoParams('\\frac')
      current++
      // 读取分母
      const b = walk(tokens, current)
      current = b.current
      // 分子
      newNode.param[0] = node
      // 分母
      newNode.param[1] = b.node
      node = newNode
    }
  }
  return { node, current }
}

当然，有一个优先级也比较高的运算符——阶乘，只不过它不需要继续向后读取了，用更简单的方式处理即可。

带有参数的表达式

上下标

上下标应当是优先级最高的，比除法的优先级更高，应当把 pi^2/6 渲染为 $\displaystyle{ \frac{ \pi ^{ 2 } }{ 6 } }$ 而不是 $\displaystyle{ \pi ^{ \frac{ 2 }{ 6 } } }$

基于这个例子，我们进行这样的分析：在读取完当前的 token 之后，继续向后看一个 token，如果是上下标，那么需要继续向后读取，直到组成一个符合语法的上下标为止。但是考虑到一些优先级的关系，又有下面的情况

• 对于 pi^2 这样简单的式子，无须考虑优先级
• 对于 pi^2/6 带有除法的，读取到上标为止就直接结束，将 pi^2 打包为一个节点，再处理除法
• 对于 a_1^2 既有下标又有上标的，读取到一个下标就结束，将 a_1 打包为一个节点，再处理上标

这样，只需在 look forward 阶段加一个循环，不断将第一个合法的节点包装起来，进入下一个循环继续读取即可。

其他带有一个或两个参数的表达式

例如 sqrt, abs, frac 这类的表达式，它们只需向后读取一个或两个节点，即可依据这些节点，生成一个新的表达式节点，似乎反而不需要考虑优先级了。

Code Generation

在上一步中，我们已经构建好了 AST 树，在代码生成阶段，只需深度优先遍历这棵树即可。上一步生成的节点类型有以下几类，由于类型较少，所以处理起来就相当方便了。

enum NodeTypes {
  Root = 'Root',
  Const = 'Const',       // 可直接生成目标代码的节点
  ParamOne = 'ParamOne', // 带有一个参数的节点
  ParamTwo = 'ParamTwo', // 带有两个参数的节点
  Matrix = 'Matrix',     // 矩阵
  Flat = 'Flat',         // 包裹了一系列节点的节点
}

由于是深度优先遍历，那么就不可避免的需要用到递归。

Const 节点

可以直接查询该节点对应的 tex 代码输出即可。

根节点 & Flat 节点

由于根节点其实跟 Flat 节点没有本质的区别，因此可以用类似的方式处理：直接遍历节点内包裹的系列节点并生成对应的代码即可。

矩阵节点

由于矩阵节点在 parse 阶段被处理成了二维数组，只需遍历就可以翻译成扁平的 $\LaTeX$ 代码了。

带有参数的节点

由于 symbols.ts 的 tex 关键字中，我使用了 $1 和 $2 这样的标识符来占位，因此在代码生成阶段，可以直接使用字符串替换即可传递参数。

完整代码

https://github.com/widcardw/asciimath-parser

参考资料

• Fran 自改的 asciimathml 以及在线公式编辑器
• Asciimathml 原项目及其官网
• 手写一个编译器 - 阿崔 cxr