實施語法降低語言解析器

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調用，這些解析器會更快，但使用起來可能會更棘手;不推薦任何，因爲我沒有使用它們）。