如何消除LL語法分析器的左遞歸

Question

如何消除以下類型的左遞歸？我似乎無法在這個特定的規則上應用一般規則。

A -> A | a | b 

通過使用刪除規則你：

A -> aA' | bA' 
A' -> A' | epsilon 

仍然有左遞歸。

這是說什麼關於語法是/不是LL（1）？

謝謝。

Answer 1

注意，規則

甲→甲

是，從某種意義上說，完全無用的。對於應用此規則的推導，它沒有做任何事情。因此，我們可以安全地從語法中刪除它，而不會改變語法產生的內容。這留下了

A → a | b

這是LL（1）。