左遞歸沒有下面的字符串

Question

我有兩個以下維基百科的defintions：

左遞歸

文法是左遞歸的當且僅當存在一個非終結 符號A可派生出一個句子形式與其自身作爲 最左邊的符號。象徵性地， A⇒Aα其中⇒表示進行一個或多個替換的操作，並且α是任何序列的終端和非終端符號。發生

和

直接左遞歸

直接左遞歸時，定義可以得到滿意的只有一個替代。它需要形式的⇒Aα其中α是非終結符和終端的序列的規則，

https://en.wikipedia.org/wiki/Left_recursion

和示例：

S → AB 
A → B | ab | abc 
B → A | d | cd 

這不是太多關於左遞歸本身但更多關於α。 α允許成爲空字（作爲終端）還是空字符串？在所有的例子我可以間接左遞歸，發現有總是喜歡

A→的α是巴布或 乙→抗體

但我不知道如何爭辯，如果A→B和B→A（所以沒有任何α跟隨）。按定義它是否仍然是一個左遞歸？

Answer 1

α可以是任何序列的終端和非終端，包括空序列。

但是，形式A → A的生產是毫無意義的。更糟糕的是，它會產生歧義，因爲它可以在推導中應用任意次數，所以不能確定性地解析Gramar。如果存在循環間接推導（符號中的A ⇒ A），則同樣如此。這就是爲什麼你很少在例子中找到這種情況。但它們當然是左遞歸的。 （它們也是右遞歸的）。

單位生產（A → B，其中A和B不同）很常見，應該不會有問題。顯然他們需要在分析語法時加以考慮。但我不認爲這是你的問題。