我的語法中的間接左遞歸？

Question

我的語法似乎有一個間接左遞歸的情況，看了一些其他類似的問題，不能很好地使他們和我的語法之間的心理聯繫，我不知道如何解決它。

A ::= A' a 
    | A 
    | b 

A' ::= c 
    | A 

A'從A調用，但A'是c或A，這是造成左遞歸，怎麼會這樣被重新排列爲等效的語法，同時消除了左遞歸？

Answer 1

您有以下作品：

1: A -> A' a 
2: A -> A 
3: A -> b 
4: A' -> c 
5: A' -> A 

首先要注意生產＃2使得這個語法含糊的，其實是有種毫無意義。讓我們刪除它。

1: A -> A' a 
3: A -> b 
4: A' -> c 
5: A' -> A 

在維基百科上的「左遞歸」製品含有（無法查證）algorithm to eliminate all left recursion，包括間接左遞歸。讓我們忽略這個特定的算法，而是將注意力集中在這個想法上：首先將間接遞歸轉化爲通過替換直接遞歸，然後通過添加尾部非終端來解決直接遞歸。

例如，我們可以通過與

6: A -> c a (see #1 and #4) 
7: A -> A a (see #1 and #5) 

替換它替代生產＃1 A'語法變成如下：

4: A' -> c 
5: A' -> A 
6: A -> c a 
7: A -> A a 

，我們已經打開所有間接遞歸直接進入遞歸。所有這一切仍然是消除A直接遞歸：

4: A' -> c 
5: A' -> A 
6: A -> c a T 
8: T -> epsilon 
9: T -> a T