实施语法降低语言解析器
我有类似于降价和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表现非常糟糕的一些糟糕的标记像__._.__*__.__...___._.____.__**___***
(大量随机放置的标记符号)的情况下。解析几个这样的随机文本需要几分钟的时间。
我的语法错了吗?或者我应该使用其他类型的解析器来完成此任务?
如果有一件事包含另一件事,那么通常你会将它们视为单独的标记,然后将它们嵌套在语法中。 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调用,这些解析器会更快,但使用起来可能会更棘手;不推荐任何,因为我没有使用它们)。
请参阅http://*.com/questions/3495019/parsing-latex-like-language-in-java获取类似的解决方案。 – 2010-08-21 16:23:52
[cletus](http://*.com/users/18393/cletus)有一系列帖子,描述了他在解析Markdown [在他的博客]上的工作(http://www.cforcoding.com/search /标签/降价)。他们拥有诸如“Markdown,Block Parsing和通往地狱之路”等标题。你可以在那里找到一些相关的信息或见解。 – 2010-08-21 00:16:37
看看[PyParsing](http://pyparsing.wikispaces.com/) – leoluk 2010-08-21 00:42:57
@Greg这很有趣,感谢分享。不过,他似乎也没有解决内联标记,并且我没有块标记的问题。 – 2010-08-21 00:54:12