Parsing Strategy
解析器算法参考了 Github Flavor Markdown Spec 附录中提到的解析策略, 将整个解析过程分为两部分:
-
逐行扫描内容,解析块类型的元素
-
对已经闭合的块数据内容进行解析,得到内联元素
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 应视作展开成 个 space,(在一些特殊情况中如 GFM#example-6, 一个 tabs 可能被视作 个 space,这种情况交由特定 的分词器在解析阶段自行处理),为了防止和其它字符混淆,可以将一个 tab 字符转成 个 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。 -
将
\0
替换为 REPLACEMENT CHARACTER (U+FFFD
)
Phase1: block structure
维护一个单调栈 stateStack
记录当前处于未关闭的块数据节点链。
块数据具有形如 stateStack
中所描述的层级结构,并总是以行为单位进行扫描,且每一
行都应需优先满足此层级结构。
为了描述算法,引入一些概念:
open
状态: 当前块节点未闭合close
状态: 当前块节点已闭合- “中断” : 当前位置本来应该继续匹配 的( 即维系 的
open
状态), 但是此位置还能匹配到一个优先级更高的 ,则此时 被强制close
,其在stateStack
中的位置改由 占据,这一过程称为 “中断” 或 被 中断了
-
从栈底遍历
stateState
,不妨记当前节点为 。尝试匹配 的 Continuation Content 以检查当前行是否继续满足stateStack
结构(即检查 是否仍可以保持open
状态):-
遍历 match-block hooks (由 Block Tokenizer 的
.match()
方法创建的 hook 列表),检查当前 hook 所匹配到新节点 是否可以“中断”掉 ,比如,如果 是一个 Blockquote,而 是一个 Paragraph,那么此时, 可以“中断”掉 -
若未被中断,则尝试匹配 的 Continuation Content。若匹配到了,则检查
stateState
中的下一个节点;若未匹配到,结束步骤 1,进入到步骤 2 -
若被中断,则清除 及其在栈中位置以上的所有节点,然后把 压栈
-
-
在完成上一步后,如果当前位置不在栈顶,说明还有节点没有找到满足其维系
open
状态的内容(如果是被“中断”的话,因为有弹栈操作,所以此时当前位置必然在栈顶), 则检查栈顶元素是否能够匹配 Lazy Continuation Content-
若能匹配到 Lazy Continuation Content,则说明
stateStack
结构得到满足, 关于 Lazy Continuation Content 的描述可参见 https://github.github.com/gfm/#lazy-continuation-line -
否则,将栈中当前位置以上的所有节点弹栈(同时这些节点的状态被设置为
close
), 检查新的栈顶元素是否为容器节点(即是否可容纳块级子节点,如 Blockquote ),若是,则尝试匹配新的块级节点 ,若 仍是容器节点,则继续寻找新的 块级节点,直到当前行的内容被消耗完
-
-
在完成上一步后,如果当前行还有内容未被消耗,则尝试匹配栈顶元素的 Lazy Continuation Content
这部分算法源码可参见 createBlockContentProcessor
Phase2: Inline structure
内联数据可以抽象成一个 opener delimiter 和 closer delimiter 包裹的内容, 以及如下规则:
-
存在优先级:如 inlineCode 比 emphasis 具有更高的结合优先级,如
-
链接不能内嵌其它链接
-
分隔符具有原子性,越靠左的具有更高的优先级,即便其对应的内容的优先级可能相反; 下面的例子中,
<url>
对应的 htmlInline 的优先级比 imageReference 高,但是](<url>)
作为imageReference
的 closer delimiter 比 htmlInline 的要靠左,因此其获得 优先处理权。
除此之外,还存在不同类型的数据匹配相同的分隔符的情况,如 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 按照优先级分组,不妨设共有 组;从高优先级向低优先级的顺 序遍历分组后的 hooks。每次只处理一个组内的 hooks,即此时处理逻辑中所有的 hook 都是同优先级的,故而无需考虑优先级问题,于是就变成了一个简单的依赖“栈”的算法。
当处理往当前组内的 hooks 时,必然将原文本字符串分割成含多个 token 的子串列表, 在处理下一组时,要绕过 token,即向下一组 hook 依次传入子串(使用索引标记,这 部分复杂度仍为原串长度),这样就可以避免破坏高优先级 hook 生产的 token 了。
-
其次,将这个算法封装成函数(不妨记为
processor
),用于递归处理 token 内部元素, 比如一个 Link 节点,其内部可能有 Emphasis 节点,而 Link 的优先级高于 Emphasis / Strong,根据 DFS 的特性,只要预先准备 个可重置的processor
就 好了,其中第 个processor
内置第 组的 hooks 进行解析(因为高 优先级的总是优先被解析了。 -
这样大幅度降低了代码编写的复杂度,也提升了效率(避免了优先级检测);但存在一个 问题,这样做无法保证 delimiter 的原子性。如:
因为 html-inline 的优先级比 image 的要高,所以按 照上面描述的算法,这个示例将被错误解析。
一个简单有效的方法是在匹配 delimiter 时,可以无视由上层 token 组成的边界, 而只关心实际上的
PhrasingContent
(即块级节点)的边界就好了,若匹配到这样一个 delimiter 且最终参与构成了一个低优先级的 token,则此时将直接覆盖掉对应的 高优先级 token。(因为这种情况下, 高优先级的 token 的边界落在了 delimiter 内!)
这部分算法源码可参见 createPhrasingContentProcessor