status
type
category
tags
slug
summary
date
finished_date
icon
password
代码仓库：github.com/RylanBot/markdown-parser-toy
- 这是一个不成熟的例子，只实现部分语法，无法通过复杂测试，单纯用于实践。
- 这份笔记不解释太多源码，只阐述相关背景流程。我的知识体系比较松散，欢迎有能力的朋友指正文章与代码中的不足之处。
前言
然后某天，知乎给我推送了一个话题：markdown 转 html 用十几行正则就可以为什么要搞那么复杂？
俗话说得好，“造轮子” 是最好的学习方法，于是萌发手搓一个 Markdown 解析器的念头，了解一下底层原理。
So like Linus told us, , even if they don’t have immediate ‘utility’ as a hack, are probably .
相关流程
形式文法
为什么正则无法处理嵌套标签结构？
解析器背后的理论源于 Noam Chomsky 在 1956 年发表的《Three Models for the Description of Language》。
其中描述了四类形式文法的层次结构。从下到到，每个都是上一个的子集，其区别在于验证它们所需的算法的复杂性。
正则
Regular Grammar
这是我们可以构建的最简单的计算模型，可以等价为一个有限自动机 (Deterministic finite automata, DFA)，即的自动机。
比如正则只能匹配有 2 个 0 和 2 个 1，而无法匹配某个字符串是否含有 个 0 和 个1（即相同数量的 0 和 1）。因为 DFA 要求必须有明确的接受状态。
- 许多热门的 Markdown 库（例如 marked.js），它们使用上百行正则，但是后期维护非常困难。
上下文无关
Context-Free Grammar, CFG
这是解析器常使用的模型，可以等价为一个下推自动机 (Pushdown automata, PDA)，即的自动机。
面对刚刚的情况，CFG 则可以用文法 定义，即 可以推出含有 的字符串，从而解决许多嵌套场景，例如匹配各种对称的括号： 。
- 因为 Markdown 标准本身并不统一，语法容易产生歧义。这个概念比较理想化，在实际编码中，并没有严格遵循它。
基本定义
解析器 (Parser) 是什么？
它能将某种格式的文本转为称作 “抽象语法树” (Abstract Structure Tress / AST) 的数据结构。树的每个节点 (Node) 由 Token 构成，Token 是最小的语法单元，含有关键词等信息。
左下是常见的解析流程图，右下是这次定义的化简版 AST。
- Markdown 处理主要是解析 (Parse) 而非编译 (Compile)。编译涉及将源代码转换为机器代码或字节码，供计算机执行。
- Markdown 转换过程一般为 Makdown → Markdown AST → HTML AST → HTML 。
解析策略
标准化
Normalize
在操作所有文本之前，需要抹平各端差异。
换行符
Mac 的每行结尾
\r，Unix 的每行结尾是 \n，Windows 的每行结尾是 \r\n。- 为了方便后期识别，会统一替换为一种写法
r\n?|\n→\n。
- 预处理可以引入简单正则，但后期解析都是利用状态机。
空字符
空字符对应的 Unicode 编码为
\0 ，在一些系统中被视为无效字符。- 一般会替换为
\uFFFD（即 �），方便标识出原始数据中的问题区域。
- 在正式解析的过程中，一般不使用明文进行等于匹配，而是统一使用字符码。
- 例如空格编码为 32，则使用
text.charCodeAt(pos) === 32而非text === ‘ ’。
区块结构
Block
处理输入文本的每一行，以某个特定标志（例如 # 和 - ）为起始符，以换行符为结束符号，遍历扫描 (Scan) 每一个字符，构建文档的块结构，将它们划分为标题、段落、列表项等。
内联结构
Inline
进一步处理上面阶段构建的内容，将标题、段落等的原始字符串内容进行解析。
如何区分不同语法对应的样式 → 定义(Delimiter Stack)
它是一个双向链表，每个元素包含一个指向文本节点的指针，以及：
- 分隔符的类型与数量
- 分隔符是否为潜在的开始符或结束符
如何解决多个嵌套语法 → 使用 (Recursion)
按指定顺序解析出现的语法，首次匹配到强调后，将加粗前后的文本进行拼接，并在 emphasis 内部 ，下次匹配到的规则变为 link。