Parsing Strategy

解析器算法参考了 Github Flavor Markdown Spec 附录中提到的解析策略, 将整个解析过程分为两部分：

1. 逐行扫描内容，解析块类型的元素

2. 对已经闭合的块数据内容进行解析，得到内联元素

Term

• token: 在 match 阶段得到的数据，包含解析成 Markdown AST node 所需的数据信息。

  本文档中，由 token 构成的树称为 Token Tree

• node: 在 parse 阶段由 token 解析而来的数据，是 Markdown AST 中的节点。

  本文档中，由 node 构成的树即为 Markdown AST.

• tokenizer: 分词器，它有两个处理阶段

  • match: 将 literal text 解析成 token.
  • parse: 将 token 解析成 node

  tokenizer 目前有两种（可依据 Tokenizer.type 进行判断）

  • Block Tokenizer: 负责解析块级结构的节点，如 @yozora/tokenizer-blockquote
  • Inline Tokenizer: 负责解析内联结构的节点，如 @yozora/tokenizer-emphasis

  为方便表述，下文中将不同类型 Tokenizer 产生的 token、node 和 tree 的称呼都加上类型前缀，如 Block Token， Block Node，Block Token Tree，Inline Token 和 Inline Node 等。

• parser: 解析器，驱动 tokenizers 协同工作，它存在四个处理阶段：

  • match-block: 驱动 Block Tokenizers 对 literal texts 进行 match 操作，并组装成一棵 Block Token Tree， （需注意此时得到的 Block Token Tree 中只处理到块级内容，对于内联内容，如 emphasis 此时未得到处理）；

  • parse-block: 自顶向下遍历 Block Token Tree，驱动 Block Tokenizers 对 token 进行 parse 操作， 并组装成一棵 Block Node Tree；

  • match-inline: 驱动 Inline Tokenizers 对 literal texts 进行 match 操作，并组装成一棵 Inline Token Tree，

  • parse-inline: 自顶向下遍历 Inline Token Tree，驱动 Inline Tokenizers 对 token 进行 parse 操作， 并组装成一棵 Inline Node Tree；

  实际处理时，会将 match-inline 和 parse-inline 封装成 parse-block 阶段的 api 交由 Block Tokenizer 在 parse 阶段调用。即在解析 Block Token 时，会调用 match-inline 和 parse-inline api 去解析 Block Token 内部的 literal text，并将其组成 Inline Node Tree，由此构成完整的 Markdown AST.

Preprocessing

持续接收文本字符串，每碰到一个换行或者内容结束时进行如下处理：

• 将字符串转成 INodePoint 列表生成器（参见 createNodePointGenerator）；这里的 codePoint 为字符的 Unicode 编码（由 String.codePointAt() 方法计算 而得），line, column, offset 为字符在文档中的位置信息，该信息定义在 Position | Unist 中。

  export interface INodePoint {
    readonly line: number
    readonly column: number
    readonly offset: number
    readonly codePoint: number
  }

  之所以选择生成器而不是直接生成字符串，是为了提供一个类似协程的 API，以支持动态 追加内容，在解析大文件或者远程异步下载的文件时可以派上用场。

• 在 GFM Spec 中规定前置的 tabs 应视作展开成 $4$ 个 space，（在一些特殊情况中如 GFM#example-6， 一个 tabs 可能被视作 $3$ 个 space，这种情况交由特定 的分词器在解析阶段自行处理），为了防止和其它字符混淆，可以将一个 tab 字符转成 $4$ 个 Virtual Space（参见 createNodePointGenerator）， 这些 Virtual Space 共用同一个位置（即 offset, line, column 相同），待到块级数据扫描完毕后再将 Virtual Space 组装回 tabs

  • 在组装的时候需要从右往左消耗 Virtual Space，因为 tabs 是作为缩进（indentation）时才需要展开成 space.

  • 剩余的 Virtual Space 转成 space.

• 将 \n，\r 或 \r\n 替换为 Virtual Line End。

  • 参见 Line ending | GFM

• 将 \0 替换为 REPLACEMENT CHARACTER (U+FFFD)

  • 参见 Insecure characters | GFM

Phase1: block structure

维护一个单调栈 stateStack 记录当前处于未关闭的块数据节点链。 块数据具有形如 stateStack 中所描述的层级结构，并总是以行为单位进行扫描，且每一 行都应需优先满足此层级结构。

为了描述算法，引入一些概念：

• open 状态： 当前块节点未闭合
• close 状态： 当前块节点已闭合
• $A$ “中断” $B$： 当前位置本来应该继续匹配 $B$ 的（即维系 $B$ 的 open 状态）， 但是此位置还能匹配到一个优先级更高的 $A$，则此时 $B$ 被强制 close，其在 stateStack 中的位置改由 $A$ 占据，这一过程称为 $A$ “中断” $B$ 或 $B$ 被 $A$ 中断了

---

1. 从栈底遍历 stateState，不妨记当前节点为 $o$。尝试匹配 $o$ 的 Continuation Content 以检查当前行是否继续满足 stateStack 结构（即检查 $o$ 是否仍可以保持 open 状态）：

   • 遍历 match-block hooks （由 Block Tokenizer 的 .match() 方法创建的 hook 列表），检查当前 hook 所匹配到新节点 $u$ 是否可以“中断”掉 $o$，比如，如果 $u$ 是一个 Blockquote，而 $o$ 是一个 Paragraph，那么此时，$u$ 可以“中断”掉 $o$

   • 若未被中断，则尝试匹配 $o$ 的 Continuation Content。若匹配到了，则检查 stateState 中的下一个节点；若未匹配到，结束步骤 1，进入到步骤 2

   • 若被中断，则清除 $o$ 及其在栈中位置以上的所有节点，然后把 $u$ 压栈

2. 在完成上一步后，如果当前位置不在栈顶，说明还有节点没有找到满足其维系 open 状态的内容（如果是被“中断”的话，因为有弹栈操作，所以此时当前位置必然在栈顶）， 则检查栈顶元素是否能够匹配 Lazy Continuation Content

   • 若能匹配到 Lazy Continuation Content，则说明 stateStack 结构得到满足， 关于 Lazy Continuation Content 的描述可参见 https://github.github.com/gfm/#lazy-continuation-line

   • 否则，将栈中当前位置以上的所有节点弹栈（同时这些节点的状态被设置为 close）， 检查新的栈顶元素是否为容器节点（即是否可容纳块级子节点，如 Blockquote ），若是，则尝试匹配新的块级节点 $v$，若 $v$ 仍是容器节点，则继续寻找新的 块级节点，直到当前行的内容被消耗完

3. 在完成上一步后，如果当前行还有内容未被消耗，则尝试匹配栈顶元素的 Lazy Continuation Content

HINT

这部分算法源码可参见 createBlockContentProcessor

Phase2: Inline structure

内联数据可以抽象成一个 opener delimiter 和 closer delimiter 包裹的内容， 以及如下规则：

• 存在优先级：如 inlineCode 比 emphasis 具有更高的结合优先级，如

  #487

  yozora

    

  pretty-json

    

  *a `*`*

  1
  *a `*`*

• 链接不能内嵌其它链接

  #526

  yozora

    

  pretty-json

    

  [foo [bar](/uri)](/uri)

  1
  [foo [bar](/uri)](/uri)

• 分隔符具有原子性，越靠左的具有更高的优先级，即便其对应的内容的优先级可能相反； 下面的例子中，<url> 对应的 htmlInline 的优先级比 imageReference 高，但是 ](<url>) 作为 imageReference 的 closer delimiter 比 htmlInline 的要靠左，因此其获得 优先处理权。

  #588

  yozora

    

  pretty-json

    

  

  1
  ![foo](<url>)

除此之外，还存在不同类型的数据匹配相同的分隔符的情况，如 link 和 image 的 closer delimiter 都为 ](xxx)，为处理 这种情况，需要进行预匹配，即有更近地匹配的 opener delimiter 的那一个获得优先处理。

对于 inlineCode 和 htmlInline 这类不包含子内联数据块的类型，可以将 opener delimiter 和 closer delimiter 合并在一起作为一个 full 类型的 delimiter 进行处理。

在处理的时候，维护一个分隔符栈，然后扫描 hooks （实现了 TokenizerMatchInlineHook 的 tokenizers），从当前位置依次找到最近的分隔符：

• 每当遇到一个高优先级的 closer delimiter 时，尝试在栈中找到与其匹对的 opener delimiter，若找到，则将这两个分隔符连同在栈中此 opener delimiter 上方的所有分隔符交给生产此分隔符的分词器进行处理；

  进行弹栈操作

• 每当遇到一个 full delimiter，立即交由此分词器进行处理

• 若遇到多个起始位置相同的分隔符，则进行竞争处理，找到

• 其它情况压栈

新算法

• 首先将所有的 hooks 按照优先级分组，不妨设共有 $g$ 组；从高优先级向低优先级的顺 序遍历分组后的 hooks。每次只处理一个组内的 hooks，即此时处理逻辑中所有的 hook 都是同优先级的，故而无需考虑优先级问题，于是就变成了一个简单的依赖“栈”的算法。

  当处理往当前组内的 hooks 时，必然将原文本字符串分割成含多个 token 的子串列表， 在处理下一组时，要绕过 token，即向下一组 hook 依次传入子串（使用索引标记，这 部分复杂度仍为原串长度），这样就可以避免破坏高优先级 hook 生产的 token 了。

• 其次，将这个算法封装成函数（不妨记为 processor），用于递归处理 token 内部元素， 比如一个 Link 节点，其内部可能有 Emphasis 节点，而 Link 的优先级高于 Emphasis / Strong，根据 DFS 的特性，只要预先准备 $g$ 个可重置的 processor 就 好了，其中第 $i$ 个 processor 内置第 $i+1 \sim g$ 组的 hooks 进行解析（因为高 优先级的总是优先被解析了。

• 这样大幅度降低了代码编写的复杂度，也提升了效率（避免了优先级检测）；但存在一个 问题，这样做无法保证 delimiter 的原子性。如：

  #588

  yozora

    

  pretty-json

    

  

  1
  ![foo](<url>)

  因为 html-inline 的优先级比 image 的要高，所以按照上面描述的算法，这个示例将被错误解析。

  一个简单有效的方法是在匹配 delimiter 时，可以无视由上层 token 组成的边界， 而只关心实际上的 PhrasingContent（即块级节点）的边界就好了，若匹配到这样一个 delimiter 且最终参与构成了一个低优先级的 token，则此时将直接覆盖掉对应的 高优先级 token。（因为这种情况下, 高优先级的 token 的边界落在了 delimiter 内！）

HINT

这部分算法源码可参见 createPhrasingContentProcessor

Related

• Appendix: A parsing strategy | Github Flavor Markdown Spec
• Block processor | Sourcecode
• Inline processor | Sourcecode