Skip to main content
Version: 2.x.x

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 进行判断)

    为方便表述,下文中将不同类型 Tokenizer 产生的 tokennodetree 的称呼都加上类型前缀,如 Block TokenBlock NodeBlock Token TreeInline TokenInline 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-inlineparse-inline 封装成 parse-block 阶段的 api 交由 Block Tokenizer 在 parse 阶段调用。即在解析 Block Token 时,会调用 match-inlineparse-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 应视作展开成 44space,(在一些特殊情况中如 GFM#example-6, 一个 tabs 可能被视作 33space,这种情况交由特定 的分词器在解析阶段自行处理),为了防止和其它字符混淆,可以将一个 tab 字符转成 44Virtual Space(参见 createNodePointGenerator), 这些 Virtual Space 共用同一个位置(即 offset, line, column 相同),待到块级数据扫描完毕后再将 Virtual Space 组装回 tabs

  • \n\r\r\n 替换为 Virtual Line End

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

Phase1: block structure

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

为了描述算法,引入一些概念:

  • open 状态: 当前块节点未闭合
  • close 状态: 当前块节点已闭合
  • AA “中断” BB: 当前位置本来应该继续匹配 BB 的(即维系 BBopen 状态), 但是此位置还能匹配到一个优先级更高的 AA,则此时 BB 被强制 close,其在 stateStack 中的位置改由 AA 占据,这一过程称为 AA “中断” BBBBAA 中断了

  1. 从栈底遍历 stateState,不妨记当前节点为 oo。尝试匹配 ooContinuation Content 以检查当前行是否继续满足 stateStack 结构(即检查 oo 是否仍可以保持 open 状态):

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

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

    • 若被中断,则清除 oo 及其在栈中位置以上的所有节点,然后把 uu 压栈

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

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

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

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

HINT

这部分算法源码可参见 createBlockContentProcessor

Phase2: Inline structure

内联数据可以抽象成一个 opener delimitercloser delimiter 包裹的内容, 以及如下规则:

  • 存在优先级:如 inlineCodeemphasis 具有更高的结合优先级,如

      
      
  • 链接不能内嵌其它链接

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

    #588
      
      

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

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

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

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

    进行弹栈操作

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

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

  • 其它情况压栈

新算法

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

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

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

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

    #588
      
      

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

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

HINT

这部分算法源码可参见 createPhrasingContentProcessor