Markdown语法可以用CFG解析吗？

Question

Markdown 支持嵌套列表，由每行开头的空格（缩进）长度指示。这与Python类似。使用上下文无关语法（CFG）来构建一个解析器似乎很困难。语法是上下文敏感而不是上下文无关吗？

Answer 1

有相当多的帖子声称事实并非如此。一个很好看的解释是：https://roopc.net/posts/2014/markdown-cfg/，作者：Roopesh Chander：

考虑强调的情况。

*a*

是 em，

**a**

是强。如果我们以类似 EBNF 的格式为 Markdown 文本运行（即 Markdown 段落的内容）编写一个（非常简化的）CFG，它将如下所示：

text-run    = span text-run | span
span        = strong | em | normal-text
strong      = "**" text-run "**"
em          = "*" text-run "*"
normal-text = [a-zA-Z0-9 ]

这已经存在歧义，因为

**a**

可以通过此语法以两种不同的方式解释：只是一个强运行，或者一个 em 运行在另一个 em 运行中。

但情况变得更糟。我们上面看到的语法会拒绝输入

*a

，它在 Markdown 中应该被解释为普通文本。

a*

、

**a

和

a**

的情况相同。如果我们也想处理这些，我们也需要这些扩展：

normal-text = "*" text-run | "**" text-run |
              text-run "*" | text-run "**"

加上这一点，歧义的数量显着增加且难以控制。

如果我们仔细看看为什么会发生这种情况，我们可以看到，当遇到

*

标记时，语法无法决定它是否应该是 em 限定符或普通文本（或者有时是强限定符）的一部分）。只有在扫描输入的其余部分直到找到匹配的结束语

*

后才能做出该决定。如果没有匹配的结束

*

，只有扫描到文本运行字符串的末尾（这将是段落的末尾），我们才会知道。因此，为了让解析器知道在某个点选择哪个规则，它可能必须向前查看任意数量的标记。

更多相关主题：

• https://news.ycombinator.com/item?id=13871991
• https://talk.commonmark.org/t/vanilla-flavored-markdown-as-basis-for-state-machine-spec/362
• https://news.ycombinator.com/item?id=8268470