Thư viện Python phân tích cú pháp regex thành AST?

Question

Để nhấn mạnh, tôi không muốn "phân tích bằng cách sử dụng regex" - Tôi muốn "phân tích cú pháp một regex thành một cây biểu tượng." (Tìm kiếm chỉ đưa lên trước đây ...)

Trường hợp sử dụng của tôi: để tăng tốc tìm kiếm regex trên cơ sở dữ liệu, tôi muốn phân tích cú pháp regex như (foo|bar)baz+(bat)* và kéo tất cả các chất nền PHẢI xuất hiện trong trận đấu. (Trong trường hợp này, nó chỉ là baz vì foo/bar là xen kẽ và dơi có thể xuất hiện 0 lần.)

Để làm điều này, tôi cần một số hiểu biết về toán tử/ngữ nghĩa regex. re.DEBUG đến gần nhất:

In [7]: re.compile('(foo|bar)baz+(bat)', re.DEBUG) 
subpattern 1 
    branch 
    literal 102 
    literal 111 
    literal 111 
    or 
    literal 98 
    literal 97 
    literal 114 
literal 98 
literal 97 
max_repeat 1 4294967295 
    literal 122 
subpattern 2 
    literal 98 
    literal 97 
    literal 116 

Tuy nhiên, nó chỉ in ra và triển khai c không bảo toàn cấu trúc sau đó. Bất kỳ ý tưởng về cách tôi có thể phân tích cú pháp này ra mà không cần viết trình phân tích cú pháp chủ sở hữu của tôi?

Answer 1

Bạn có thể chỉ định một (cổ điển) regex sử dụng một bối cảnh tự do ngữ pháp:

regex = { alternatives }; 
alternatives = primitive { '|' alternatives } ; 
primitive = '(' regex ')' | '[' character_set ']' | ... 

Điều này có nghĩa bạn không thể phân tích một regex sử dụng một regex (Perl là một ngoại lệ, nhưng sau đó nó "regexes "là cách mở rộng vượt ra ngoài" cổ điển ").

Vì vậy, để phân tích cú pháp regex, bạn sẽ cần phải xây dựng trình phân tích cú pháp của riêng bạn và xây dựng một số loại cây (re.Debug đến khá gần) hoặc thư viện ma thuật mà bạn đang hy vọng.

Tôi nghi ngờ đây là phần dễ dàng. Đây không phải là khó khăn để làm cho mình; xem Is there an alternative for flex/bison that is usable on 8-bit embedded systems? cho một sơ đồ đơn giản để tạo các trình phân tích cú pháp như vậy.

Để hiểu được ngữ nghĩa của regex (ví dụ, để tìm ra "chuỗi con cần thiết"), bạn có thể có thể nhận được ngay với việc xây dựng một máy phân tích các tầng lớp xã hội trên cây phân tích cú pháp, và đối với mỗi cây con (dưới lên), tính toán chuỗi chung. Không phải là bạn có thể phải triển khai xây dựng NDFA cổ điển và sau đó đi qua nó hoặc triển khai NDFA để xây dựng DFA và đi bộ qua DFA. Các regex thực có xu hướng chứa nhiều biến chứng lộn xộn như các bộ ký tự tích hợp, các nhóm chụp, v.v.

"Chuỗi chung" có thể không chỉ là một chuỗi ký tự tiếp giáp mặc dù bạn có thể xác định nó rất hẹp. Nó có thể bao gồm một số bản chất không đổi được phân tách bằng khoảng trống độ dài cố định hoặc biến đổi của ký tự, ví dụ: chuỗi con cần thiết của bạn luôn có thể được hiển thị dưới dạng "regex đơn giản" của biểu mẫu:

(<character>+ ?+) <character>+