Làm cách nào để mở rộng một mẫu hữu hạn vào tất cả các kết quả phù hợp có thể có của nó?

Question

Ví dụ, đưa ra mô hình

[a-zA-Z]_[0-9]{2} 

một chức năng sẽ lấy mẫu và trả về một mảng hoặc danh sách có chứa

a_00, a_01, a_02, ... , a_98, a_99, ... , z_98, z_99 

Chỉ số và chữ (và các nhóm hữu hạn của chúng) cần được mở rộng. Tôi sẽ đi đâu để tới đó? Một ví dụ trong Python hoặc Perl sẽ được ưu tiên. Cảm ơn bạn!

Answer 1

Đầu tiên, phân tích cú pháp biểu thức và xây dựng một cây phản ánh cấu trúc cú pháp của cụm từ thông dụng và bao gồm nút đầu cuối xuất hiện một cách hợp lý ở cuối. Ví dụ: trong ký hiệu lisp, ví dụ của bạn có thể trông giống như sau:

(concat 
    (repeat 2 
    (concat 
     (charset 
     (range a z) 
     (range A Z)) 
     (literal _) 
     (charset 
     (range 0 9)))) 
    terminator) 

Tiếp theo, tạo chủ đề để bạn có thể sử dụng đệ quy để tạo mở rộng tổ hợp. Bằng cách đó, tôi có nghĩa là ví dụ các nút a..z trong (concat a .. z) tất cả cần phải có con trỏ từ điểm này đến điểm tiếp theo, vì vậy a trỏ đến b, v.v. và chính nút concat trỏ đến người kế nhiệm của nó. Ý tưởng là bạn có thể tạo ra một phiên bản của phần tử hiện tại trong phần mở rộng, và recurse vào phần tử tiếp theo, và khi phần tử tiếp theo trả về, bạn có thể thử phiên bản tiếp theo của phần tử hiện tại, v.v. bạn quay trở lại người gọi của bạn (người tiền nhiệm hoặc cha mẹ). Luồng này được thực hiện dễ dàng nhất với một chồng và một sự di chuyển sau của cây. Nếu bạn cẩn thận đẩy các nút trong quá trình truyền tải thứ tự sau, phần đầu của ngăn xếp sẽ là phần tử tiếp theo theo thứ tự.

(Một thay thế cho luồng là cấu trúc cây để các phần tử tiếp theo trong mỗi concat nút là con của nút trước đó, và trẻ em repeat nút điểm trở lại nút lặp lại.)

Sau đó viết một thường trình (hoặc tập hợp các thói quen sử dụng đối sánh mẫu hoặc các phương thức ảo nếu các nút trong cây được thực hiện bằng cách sử dụng đa hình trong một ngôn ngữ hướng đối tượng), cho bất kỳ loại nút nào, tạo ra đầu ra chính xác và đệ quy vào nút tiếp theo hoặc trẻ em theo cách thích hợp. Ví dụ, trong giả:

if node is of form (repeat n): # non-variable repeat 
    for i in 1 to n 
     recurse into child 
    recurse into threaded successor 

if node is of form (concat ...): 
    recurse into first element # last element will recurse into successor 

if node is of form (literal x): 
    emit x 
    recurse into successor 
    remove x 

if node is of form (charset ...): 
    for each element in charset: 
     emit element 
     recurse into successor 
     remove element 

if node is terminator: 
    add string created thus far to final output list 

vv Như bạn có thể quan sát, con của một nút repeat phải không recurse vào sự kế thừa của nút repeat, vì vậy mà cần phải được tính đến khi luồng cây. Sự chăm sóc tương tự cần được thực hiện là "tiến độ hiện tại" không bị mất khi đến cuối các nút con của nút repeat; Ngoài ra, sự kế thừa của các nút con có thể trỏ tới chính nút lặp lại (tức là một đóng cửa thực sự trên biểu đồ các nút), nhưng điều đó sẽ yêu cầu lưu trữ một bộ đếm ở đâu đó.

Tất cả trong tất cả, việc hoàn thành việc này có thể mất vài ngày, tùy thuộc vào mức độ linh hoạt và hiệu suất cần thiết. Cũng lưu ý rằng một số cấu trúc nhất định, chẳng hạn như sao Kleene hoặc đóng (* hoặc + trong regex mở rộng) sẽ dẫn đến danh sách vô hạn. Ngôn ngữ hỗ trợ trình tạo (ví dụ: cú pháp lặp của C#) hoặc coroutines/continuations (ví dụ: Gọi/cc) hoặc đánh giá lười (ví dụ: Haskell) có thể cho phép lặp qua vài phần tử đầu tiên của danh sách mà không phải đánh giá toàn bộ danh sách. Ngoài ra, việc chọn đầu ra tiềm năng ngẫu nhiên thay vì lặp lại toàn diện có thể thích hợp hơn để cung cấp các ví dụ tương ứng với cụm từ thông dụng.

Answer 2

Cho rằng bạn có thể tìm ra độ dài của các chuỗi có độ dài phù hợp, bạn có thể brute buộc nó bằng cách tạo tất cả các chuỗi có thể với độ dài chính xác và sau đó chỉ cố gắng khớp.

Answer 3

Sử dụng thrax !! Thrax cung cấp các công cụ dòng lệnh để tương tác với bộ công cụ OpenFST hạng nặng. Bạn có thể tìm thấy nó trên các trình quản lý gói như apt hoặc macports.

Dưới đây là ví dụ về cách sử dụng thrax để lấy mẫu regex. Hôm nay tôi muốn tìm ra tên cho một thư viện mà tôi đang viết. Tôi muốn tên là từ viết tắt của complete embedded? mrf? (optimization|inference) toolkit. Sau khi cố gắng đưa ra một tên bằng tay, tôi đã từ bỏ và viết regex sau đây cho các từ viết tắt có thể: co?m?e?m?[io]to?.

Vì vậy, hiện tại, sự cố giảm xuống để lấy mẫu một số chuỗi đáp ứng từ viết tắt này. Đây là nơi mà thrax đi vào. Đầu tiên chúng ta có thể viết regex trong một tập tin grm như thế này.

[Save following in file named tmp.grm] 
sigma=("c"|"o"|"m"|"e"|"i"|"o"|"t"); 
export a= Optimize[ ("c":"c") (("o":"")|("o":"o")) (("m":"")|("m":"m")) (("e":"")|("e":"e")) (("m":"")|("m":"m")) (("o":"o")|("i":"i")) ("t":"t") (("o":"")|("o":"o")) ]; 

Bạn có thể đoán được điều gì đang xảy ra. Đối với mỗi x? tôi đã chỉ định rằng x sẽ là đầu ra hoặc '' sẽ là đầu ra. Bây giờ chúng tôi có thể biên dịch tập tin grm và chuỗi mẫu này từ ngôn ngữ.

thraxcompiler --save_symbols --input_grammar=tmp.grm --output_far=tmp.far 
thraxrandom-generator --far=tmp.far --rule=a --noutput=100 

Đầu ra chứa các chuỗi có thể có mà regex có thể khớp. Tôi nghĩ rằng cũng có các tiện ích để tạo ra tất cả các kết quả đầu ra có thể bằng cách sử dụng thrax nhưng nếu bạn chỉ lấy mẫu một số lượng lớn các chuỗi và uniq chúng phải là một số tốt 90% solution.

**************************************** 
comemoto 
cmemot 
**************************************** 
comemoto 
comoto 
**************************************** 
comemoto 
comot 
**************************************** 
comemito 
coemito 
**************************************** 
comemoto 
coeot 
**************************************** 
comemoto 
cmeot 
**************************************** 
comemito 
coit 
**************************************** 
comemoto 
cemot 
**************************************** 
comemoto 
ceoto