Thuật toán để tạo ngữ cảnh tự do ngữ cảnh từ bất kỳ regex

Question

Bất kỳ ai có thể phác thảo cho tôi một thuật toán có thể chuyển đổi bất kỳ regex đã cho nào thành một bộ quy tắc CFG tương đương không?

tôi biết làm thế nào để giải quyết những thứ tiểu như (a | b) *:

S -> a A 
S -> a B 
S -> b A 
S -> b B 
A -> a A 
A -> a B 
A -> epsilon 
B -> b A 
B -> b B 
B -> epsilon 
S -> epsilon (end of string) 

Tuy nhiên, tôi đang gặp một số vấn đề chính thức hóa nó thành một thuật toán thích hợp đặc biệt với các biểu thức phức tạp hơn có thể có nhiều hoạt động lồng nhau.

Answer 1

Nếu bạn chỉ nói về biểu thức thông thường từ một quan điểm lý thuyết, có ba cấu trúc:

ab  # concatenation 
a|b  # alternation 
a*  # repetition or Kleene closure 

gì sau đó bạn có thể chỉ cần làm:

• tạo ra một quy tắc S -> (fullRegex)
• cho mỗi cụm từ lặp lại (x)* trong fullRegex tạo quy tắc X -> x X và X -> ε, sau đó thay thế (x)* bằng X.
• cho mỗi thay đổi luân phiên (a|b|c) tạo các quy tắc Y -> a, Y -> b và Y -> c, sau đó thay thế (a|b|c) với Y

Chỉ cần lặp lại này một cách đệ quy (lưu ý rằng tất cả x,a, b và c vẫn có thể được biểu thức thông thường phức tạp). Lưu ý rằng tất nhiên bạn phải sử dụng số nhận dạng duy nhất cho mỗi bước.

Điều này là đủ. Điều này chắc chắn sẽ không cung cấp cho ngữ pháp thanh lịch hoặc hiệu quả nhất, nhưng đó là những gì bình thường hóa (và nó nên được thực hiện trong một bước riêng biệt và có well-defined steps để làm điều này).

Một ví dụ: a(b|cd*(e|f)*)*

S -> a(b|cd*(e|f)*)* 

S -> a X1; X1 -> (b|cd*(e|f)*) X1; X1 -> ε 

S -> a X1; X1 -> Y1 X1; X1 -> ε; Y1 -> b; Y1 -> cd*(e|f)* 

S -> a X1; X1 -> Y1 X1; X1 -> ε; Y1 -> b; Y1 -> c X2 (e|f)*; X2 -> d X2; X2 -> ε 

... and a few more of those steps, until you end up with: 

S -> a X1 
X1 -> Y1 X1 
X1 -> ε 
Y1 -> b 
Y1 -> c X2 X3 
X2 -> d X2 
X2 -> ε 
X3 -> Y2 X3 
X3 -> ε 
Y2 -> e 
Y2 -> f