刪除上下文免費語法中的左遞歸

Question

試圖找出在上下文無關語法中刪除左遞歸。我習慣了某些形式，但這個讓我有點難以理解。

S --> S {S} S | (A) | a 
A --> {S} A | epsilon 

我也必須設計一個體面的解析器，我可以做。然而，搞清楚這個左遞歸（尤其是第一個）讓我感到困惑。

Answer 1

有一個有趣的維基百科關於左遞歸的文章。它還有一個關於刪除非上下文語法的左遞歸的章節。

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

Answer 2

試試這個：

S --> a [ { S } S ] 
    | ([ A ]) [ {S} S ] 


A --> { S } [ A ]