Implementando un analizador para lenguaje similar a markdown

Tengo un lenguaje de marcado que es similar a markdown y el que usa SO.

El analizador Legacy se basaba en expresiones regulares y era una pesadilla completa de mantener, por lo que he encontrado mi propia solución basada en la gramática EBNF e implementada a través de mxTextTools / SimpleParse.

Sin embargo, hay problemas con algunos tokens que pueden incluirse entre sí, y no veo una manera “correcta” de hacerlo.

Aquí está parte de mi gramática:

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)+ 

El primer problema es, spoiler, strong y énfasis pueden incluirse en orden arbitrario. Y es posible que más adelante necesite más marcas en línea.

Mi solución actual implica simplemente crear un token separado para cada combinación (inline_noast, inline_nostrong, etc.), pero obviamente, el número de tales combinaciones crece demasiado rápido con un número creciente de elementos de marcado.

El segundo problema es que estos lookaheads en fuerte / énfasis se comportan MUY mal en algunos casos de marcado incorrecto como __._.__*__.__...___._.____.__**___*** (muchas posiciones al azar símbolos de marcado). Se tarda minutos en analizar unos pocos kb de dicho texto aleatorio.

¿Hay algún problema con mi gramática o debo usar algún otro tipo de analizador para esta tarea?

Si una cosa incluye otra, entonces normalmente las tratas como fichas separadas y luego las anidas en la gramática. Lepl ( http://www.acooke.org/lepl, que escribí) y PyParsing (que probablemente sea el analizador de Python puro más popular) te permiten anidar cosas de forma recursiva.

Así que en Lepl podrías escribir código algo como:

 # 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 

Entonces puede ver, espero, cómo los contenidos coincidirán con el uso nested de fuerte, énfasis, etc.

Hay mucho más que esto por hacer para su solución final, y la eficiencia podría ser un problema en cualquier analizador de Python puro (hay algunos analizadores que se implementan en C pero que se pueden recuperar desde Python. Estos serán más rápidos, pero pueden ser más difíciles de usar ; No puedo recomendar ninguna porque no las he usado).