Từng bước loại bỏ đệ quy gián tiếp này

Question

Tôi đã xem this algorithm người ta có thể sử dụng để loại bỏ tất cả đệ quy trái. Tuy nhiên, tôi chạy vào vấn đề với ngữ pháp đặc biệt này:

A -> Cd 
B -> Ce 
C -> A | B | f 

Dù tôi cố gắng tôi kết thúc trong vòng lặp hoặc với một ngữ pháp đó vẫn là gián tiếp đệ quy trái.

Các bước để triển khai đúng this algorithm về ngữ pháp này là gì?

Answer 1

Quy tắc là trước tiên bạn thiết lập một loại lệnh nào đó cho các thiết bị không phải là thiết bị đầu cuối và sau đó tìm tất cả các đường dẫn nơi đệ quy gián tiếp xảy ra.

Trong trật tự trường hợp sẽ là A < B < C, và có thể đường dẫn cho đệ quy của phi cảng C sẽ

C=> A => Cd 

và

C=> B => Ce 

quy tắc nên mới cho C sẽ

C=> Cd | Ce | f 

bây giờ bạn có thể chỉ cần loại bỏ đệ quy trái trực tiếp:

C=> fC' 
C'=> dC' | eC' | eps 

và kết quả ngữ pháp không đệ quy sẽ là:

A => Cd 
B => Ce 
C => fC' 
C' => dC' | eC' | eps 

Answer 2

Đã tìm ra. Sự nhầm lẫn của tôi là theo thứ tự này, thuật toán dường như không làm gì cả, vì vậy tôi nghĩ rằng đó là sai, và bắt đầu thay thế A -> Cd trong lần lặp đầu tiên (bỏ qua j không thể vượt quá i) đi vào vòng vô hạn .

1) Bằng cách sắp xếp lại các quy tắc:

C -> A | B | f 
A -> Cd 
B -> Ce 

2) thay thế C trong A -> Cd

C -> A | B | f 
A -> Ad | Bd | fd 
B -> Ce 

3) B chưa có trong phạm vi của j, vì vậy hãy để đó và thay thế trực tiếp đệ quy trái của A

C -> A | B | f 
A -> BdA' | fdA' 
A'-> dA' | epsylon 
B -> Ce 

4) thay thế C trong B -> Ce

C -> A | B | f 
A -> BdA' | fdA' 
A'-> dA' | epsylon 
B -> Ae | Be | fe 

5) chưa hoàn tất! cũng cần phải thay thế các quy tắc B mới -> Ae (sản xuất của A nằm trong phạm vi của j)

C -> A | B | f 
A -> BdA' | fdA' 
A'-> dA' | epsylon 
B -> BdA'e | fdA'e | Be | fe 

6) thay đệ quy trực tiếp trái trong tác phẩm của B

C -> A | B | f 
A -> BdA' | fdA' 
A'-> dA' | epsylon 
B -> fdA'eB' | feB' 
B'-> dA'eB' | eB' | epsylon 

tuyệt vời! trái phép đệ quy ngữ pháp miễn phí!