实现类 Markdown 语言的解析器

Question

我有类似于 markdown 和 SO 使用的标记语言。

遗留解析器基于正则表达式，维护起来简直是噩梦，因此我提出了自己的基于 EBNF 语法的解决方案，并通过 mxTextTools/SimpleParse 实现。

但是，某些令牌可能存在相互包含的问题，并且我没有看到“正确”的方法来做到这一点。

这是我的语法的一部分：

newline          := "\r\n"/"\n"/"\r"
indent           := ("\r\n"/"\n"/"\r"), [ \t]
number           := [0-9]+
whitespace       := [ \t]+
symbol_mark      := [*_>#`%]
symbol_mark_noa  := [_>#`%]
symbol_mark_nou  := [*>#`%]
symbol_mark_nop  := [*_>#`]
punctuation      := [\(\)\,\.\!\?]
noaccent_code    := -(newline / '`')+
accent_code      := -(newline / '``')+
symbol           := -(whitespace / newline)
text             := -newline+
safe_text        := -(newline / whitespace / [*_>#`] / '%%' / punctuation)+/whitespace
link             := 'http' / 'ftp', 's'?, '://', (-[ \t\r\n<>`^'"*\,\.\!\?]/([,\.\?],?-[ \t\r\n<>`^'"*]))+
strikedout       := -[ \t\r\n*_>#`^]+
ctrlw            := '^W'+
ctrlh            := '^H'+
strikeout        := (strikedout, (whitespace, strikedout)*, ctrlw) / (strikedout, ctrlh)
strong           := ('**', (inline_nostrong/symbol), (inline_safe_nostrong/symbol_mark_noa)* , '**') / ('__' , (inline_nostrong/symbol), (inline_safe_nostrong/symbol_mark_nou)*, '__')
emphasis              := ('*',?-'*', (inline_noast/symbol), (inline_safe_noast/symbol_mark_noa)*, '*') / ('_',?-'_', (inline_nound/symbol), (inline_safe_nound/symbol_mark_nou)*, '_')
inline_code           := ('`' , noaccent_code , '`') / ('``' , accent_code , '``')
inline_spoiler        := ('%%', (inline_nospoiler/symbol), (inline_safe_nop/symbol_mark_nop)*, '%%')
inline                := (inline_code / inline_spoiler / strikeout / strong / emphasis / link)
inline_nostrong       := (?-('**'/'__'),(inline_code / reference / signature / inline_spoiler / strikeout / emphasis / link))
inline_nospoiler       := (?-'%%',(inline_code / emphasis / strikeout / emphasis / link))
inline_noast          := (?-'*',(inline_code / inline_spoiler / strikeout / strong / link))
inline_nound          := (?-'_',(inline_code / inline_spoiler / strikeout / strong / link))
inline_safe           := (inline_code / inline_spoiler / strikeout / strong / emphasis / link / safe_text / punctuation)+
inline_safe_nostrong  := (?-('**'/'__'),(inline_code / inline_spoiler / strikeout / emphasis / link / safe_text / punctuation))+
inline_safe_noast     := (?-'*',(inline_code / inline_spoiler / strikeout / strong / link / safe_text / punctuation))+
inline_safe_nound     := (?-'_',(inline_code / inline_spoiler / strikeout / strong / link / safe_text / punctuation))+
inline_safe_nop        := (?-'%%',(inline_code / emphasis / strikeout / strong / link / safe_text / punctuation))+
inline_full           := (inline_code / inline_spoiler / strikeout / strong / emphasis / link / safe_text / punctuation / symbol_mark / text)+
line                  := newline, ?-[ \t], inline_full?
sub_cite              := whitespace?, ?-reference, '>'
cite                  := newline, whitespace?, '>', sub_cite*, inline_full?
code                  := newline, [ \t], [ \t], [ \t], [ \t], text
block_cite            := cite+
block_code            := code+
all                   := (block_cite / block_code / line / code)+

第一个问题是，剧透，强和强调可以以任意顺序相互包含。以后我可能需要更多这样的内联标记。

我当前的解决方案涉及为每个组合（inline_noast、inline_nostrong 等）创建单独的标记，但显然，随着标记元素数量的增加，此类组合的数量增长得太快。

第二个问题是，这些强/强调的前瞻在某些不良标记的情况下表现非常糟糕，例如 __._.__*__.__...___._.____.__**___***（许多随机放置的标记符号）。解析这样几 kb 的随机文本需要几分钟的时间。

我的语法有问题吗？或者我应该使用其他类型的解析器来完成此任务？

Answer 1

如果一件事包含另一件事，那么通常您将它们视为单独的标记，然后将它们嵌套在语法中。 Lepl（我写的http://www.acooke.org/lepl）和PyParsing（这是可能是最流行的纯 Python 解析器）都允许您递归地嵌套事物。

因此，在 Lepl 中，您可以编写类似以下的代码：

# these are tokens (defined as regexps)
stg_marker = Token(r'\*\*')
emp_marker = Token(r'\*') # tokens are longest match, so strong is preferred if possible
spo_marker = Token(r'%%')
....
# grammar rules combine tokens
contents = Delayed() # this will be defined later and lets us recurse
strong = stg_marker + contents + stg_marker
emphasis = emp_marker + contents + emp_marker
spoiler = spo_marker + contents + spo_marker
other_stuff = .....
contents += strong | emphasis | spoiler | other_stuff # this defines contents recursively

然后您可以看到，我希望，内容将如何匹配强、强调等的嵌套使用。

对于您的最终解决方案来说，要做的事情远不止这些，效率可能是一个问题任何纯Python解析器（有一些解析器是用C实现的，但可以从Python调用。这些解析器会更快，但使用起来可能更棘手；我不能推荐任何解析器，因为我没有使用过它们）。