Реализация парсера для языка уценки

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 и т. Д.), Но, очевидно, количество таких комбинаций растет слишком быстро с увеличением числа элементов разметки.

Вторая проблема заключается в том, что эти взгляды в сильном/аккорде ведут себя очень плохо в некоторых случаях плохой разметки, например, __._.__*__.__...___._.____.__**___*** (много случайно помеченных символов разметки). Требуется несколько минут, чтобы разобрать несколько килобайт такого случайного текста.

Это что-то не так с моей грамматикой, или я должен использовать какой-то другой парсер для этой задачи?

Answer 1

Если в одну вещь входит другая, тогда обычно вы относитесь к ним как к отдельным маркерам, а затем вставляете их в грамматику. Lepl (http://www.acooke.org/lepl, который я написал) и PyParsing (который, вероятно, является самым популярным парсером pure-Python), позволяют вам рекурсивно вставлять вещи.

Так ЮЛППЫ вы могли бы написать код что-то вроде:

# 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.Это будет быстрее, но может оказаться более сложным в использовании, t рекомендую, потому что я их не использовал).