Thực hiện phân tích cú pháp cho ngôn ngữ giống như đánh dấu

Question

Tôi có ngôn ngữ đánh dấu tương tự như đánh dấu và ngôn ngữ được SO sử dụng.

Trình phân tích cú pháp cũ dựa trên regex và hoàn toàn là cơn ác mộng để duy trì, vì vậy tôi đã đưa ra giải pháp của riêng mình dựa trên ngữ pháp EBNF và được triển khai thông qua mxTextTools/SimpleParse.

Tuy nhiên, có vấn đề với một số mã thông báo có thể bao gồm nhau và tôi không thấy cách 'thực hiện'.

Dưới đây là một phần của ngữ pháp của tôi:

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

Vấn đề đầu tiên là, spoiler, mạnh mẽ và nhấn mạnh có thể bao gồm nhau theo thứ tự tùy ý. Và có khả năng là sau này tôi sẽ cần thêm nhiều đánh dấu nội tuyến như vậy.

Giải pháp hiện tại của tôi liên quan đến việc tạo mã thông báo riêng biệt cho từng kết hợp (inline_noast, inline_nostrong, v.v.), nhưng rõ ràng, số lượng kết hợp như vậy tăng quá nhanh với số yếu tố đánh dấu ngày càng tăng.

Vấn đề thứ hai là những vẻ ngoài mạnh mẽ/nhấn mạnh này hoạt động kém trên một số trường hợp đánh dấu kém như __._.__*__.__...___._.____.__**___*** (nhiều ký hiệu đánh dấu được đặt ngẫu nhiên). Phải mất vài phút để phân tích cú pháp vài kb của văn bản ngẫu nhiên như vậy.

Có vấn đề gì với ngữ pháp của tôi hay tôi nên sử dụng một số loại trình phân tích cú pháp khác cho tác vụ này?

Answer 1

Nếu có một thứ khác, thì thông thường bạn coi chúng là các mã thông báo riêng biệt và sau đó lồng chúng vào ngữ pháp. Lepl (http://www.acooke.org/lepl mà tôi đã viết) và PyParsing (có lẽ là trình phân tích cú pháp tinh khiết-Python phổ biến nhất) cho phép bạn lồng ghép mọi thứ một cách đệ quy.

Vì vậy, trong Lepl bạn có thể viết mã một cái gì đó như:

# 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 

Sau đó, bạn có thể thấy, tôi hy vọng, làm thế nào nội dung sẽ phù hợp lồng sử dụng mạnh mẽ, nhấn mạnh vv

Có nhiều hơn điều này để làm cho giải pháp cuối cùng của bạn, và hiệu quả có thể là một vấn đề trong bất kỳ trình phân tích cú pháp tinh khiết-Python nào (Có một số trình phân tích cú pháp được thực hiện trong C nhưng có thể gọi được từ Python. t đề nghị bất kỳ vì tôi đã không sử dụng chúng).