实施语法降低语言解析器

Question

我有类似于降价和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等）创建单独的标记，但很明显，随着标记元素数量的增加，这样的组合数量增长过快。

第二个问题是，在强/强调这些lookahead表现非常糟糕的一些糟糕的标记像__._.__*__.__...___._.____.__**___***（大量随机放置的标记符号）的情况下。解析几个这样的随机文本需要几分钟的时间。

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

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调用，这些解析器会更快，但使用起来可能会更棘手;不推荐任何，因为我没有使用它们）。