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

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

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

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


left-recursion context-free-grammar
person Mercfh    schedule 30.09.2010    source источник

Ответы (2)


arrow_upward
0
arrow_downward

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

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

person Alexander Rafferty    schedule 30.09.2010

arrow_upward
0
arrow_downward

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

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


A --> { S } [ A ]
person Scott Wisniewski    schedule 30.09.2010