实现类似Markdown语言的解析器
我有一种标记语言，跟markdown和Stack Overflow用的那种很像。
之前的解析器是基于正则表达式的，维护起来简直是个噩梦，所以我想出了自己的解决方案，基于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等等），但显然，随着标记元素数量的增加，这样的组合数量增长得太快了。
第二个问题是，在处理一些糟糕的标记时，比如__._.__*__.__...___._.____.__**___***（里面有很多随机放置的标记符号），这些前瞻的表现非常糟糕。解析几千字节的这种随机文本可能需要几分钟。
这是不是我的语法有问题，还是我应该用其他类型的解析器来完成这个任务呢？
1 个回答
6
如果一个东西包含另一个东西，通常你会把它们当作不同的部分来处理，然后在语法中把它们嵌套在一起。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调用。这些解析器会更快，但使用起来可能会更复杂；我不能推荐任何，因为我没有使用过它们）。