Удаление левой рекурсии в контекстно-свободной грамматике

Question

Попытка выяснить, как удалить левую рекурсию в контекстно-свободных грамматиках.Я привык к определенным формам, но эта заставляет меня немного запутаться.

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

Я также должен разработать приличный парсер, который я могу сделать.Однако выяснение этой левой рекурсии (особенно первой) привело меня в замешательство.

Answer 1

Попробуйте это:

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


A --> { S } [ A ]

Answer 2

Есть интересная статья в Википедии о левой рекурсии. Также имеется раздел об удалении левой рекурсии для неконтекстных грамматик.

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