Chuyển đổi cụm từ thông dụng sang CFG

Question

Làm cách nào để chuyển đổi một số ngôn ngữ thông thường sang Ngữ pháp tự do ngữ cảnh tương đương? Có cần thiết phải xây dựng DFA tương ứng với cụm từ thông dụng đó hoặc có một số quy tắc cho một chuyển đổi như vậy không?

Ví dụ, hãy xem xét các biểu thức chính quy sau

01 + 10 (11) ^*

Làm thế nào tôi có thể mô tả ngữ pháp tương ứng với RE trên?

Answer 1

• Change A + B để ngữ pháp

  G -> A 
  G -> B 
  

• Change A * để

  G -> (empty) 
  G -> A G 
  

• Thay đổi AB để

  G -> AB 
  

và tiến hành đệ quy trên A và B. Trường hợp cơ sở là ngôn ngữ trống (không có sản phẩm) và một biểu tượng duy nhất.

Trong trường hợp của bạn

A -> 01 
A -> 10B 
B -> (empty) 
B -> 11B 

Nếu ngôn ngữ được mô tả bằng automaton hữu hạn:

• bang sử dụng như là biểu tượng không thuộc đầu cuối
• ngôn ngữ sử dụng như thiết lập các biểu tượng terminal
• thêm một sự chuyển tiếp p -> aq cho bất kỳ chuyển tiếp p -> q nào trên chữ cái a trong ô tô gốc
• sử dụng trạng thái ban đầu làm ký hiệu ban đầu trong ngữ pháp

Answer 2

Tôi đoán bạn có nghĩa là chuyển đổi nó thành một ngữ pháp chính thức với các quy tắc của biểu mẫu V-> w, trong đó V là một nonterminal và w là một chuỗi các thiết bị đầu cuối/nonterminals. Để bắt đầu, bạn có thể chỉ cần nói (trộn CFG và cú pháp regex):

Trường hợp S là biểu tượng bắt đầu. Bây giờ chúng ta hãy phá vỡ nó lên một chút (và thêm khoảng trắng cho rõ ràng):

S -> 0 A 1 0 B 
A -> 1+ 
B -> (11)* 

Điều quan trọng là để chuyển đổi * es và + es để đệ quy. Đầu tiên, chúng tôi sẽ chuyển đổi các sao Kleene tới một cộng bằng cách chèn một nguyên tắc trung gian mà chấp nhận chuỗi rỗng:

S -> 0 A 1 0 B 
A -> 1+ 
B -> (empty) 
B -> C 
C -> (11)+ 

Cuối cùng, chúng tôi sẽ chuyển đổi + ký hiệu để đệ quy:

S -> 0 A 1 0 B 
A -> 1 
A -> A 1 
B -> (empty) 
B -> C 
C -> 11 
C -> C 11 

Xử lý x?, chỉ cần chia nó thành quy tắc sản xuất sản phẩm nào và quy tắc sản xuất x.

Answer 3

Thực ra, các ngữ pháp CFG khác nhau có thể sản xuất cùng một ngôn ngữ. Vì vậy, đưa ra một biểu thức chính quy (ngôn ngữ thông thường), ánh xạ của nó trở lại một CFG không phải là duy nhất.

Chắc chắn, bạn có thể xây dựng một CFG dẫn đến cụm từ thông dụng nhất định. Các câu trả lời ở trên cho thấy một số cách để đạt được điều này.

Hy vọng điều này mang đến cho bạn ý tưởng cấp cao.