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

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 ]