Eliminação de Recursividade á Esquerda

A gramática seguinte, onde a e b representam sequências de símbolos terminais e/ou não terminais, com b não começando por A, representa genericamente a recursividade direta simples à esquerda.

• A -> A a | b

Aplicando a primeira produção n vezes e a seguir a segunda, obtem-se

• A => A a => A a a => A a ... a a => b a ... a a

Ou seja:

• 

Que corresponde ao b seguindo do fecho de a, podendo ser representada pela gramática

• A -> b X X -> end | a X

Em ANTLR seria possível fazer-se A -> b (a)*

Exemplo com recursividade direta simples

Para a gramática

• S -> S a b | c b a

obtenha-se uma gramática equivalente sem recursividade à esquerda

Aplicando a estratégia anterior, tem-se

• S => S a b => S a b ... a b => c b a a b ... a b

Ou seja

• S = (c b a) (a b)^n, n>=0

Que corresponde à gramática

• S -> c b a X X -> end | a b X

Recursividade Direta Múltipla

As gramáticas seguintes, onde ai e bj representam sequências de símbolos terminais e/ou não terminais, com os bj não começando por A, representa genericamente a recursividade direta múltipla à esquerda

• A -> A a1 | A a2 | ... | A an | b1 | b2 | ... | bm

Aplicando a estratégia anterior, tem-se

• A = ( b1 | b2 | ... | bm ) ( a1 | a2 | ... | an )^k com k >= 0

Que corresponde à gramática

• A -> b1 X | b2 X | ... | bm X X -> end | a1 X | a2 X | ... | an X

Em ANTLR seria possível fazer-se ( b1 | b2 | ... | bm )( a1 | a2 | ... | an )*

Exemplo

Obtenha-se uma gramática equivalente à seguinte sem recursividade à esquerda

• S -> S a b | S c | b b | c c

As palavras da linguagem são da forma

• S = (bb|cc)(ab|c)^k , k >=0

Obtendo-se a gramática

• S = ( b b X | c c X ) X -> end | a b X | c X

Ilustração de recursividade indireta

Aplique-se o procedimento anterior à gramática seguinte, assumindo que a recursividade à esquerda está no A

• S -> A a | b A -> A c | S d | end

O resultado seria

• S -> A a | b A -> S d X | X X -> end | c X

A recursividade não foi eliminada

• S => A a => S d X a => A a d X a

• Porque a recursividade existe de forma indireta

Como resolver a recursividade à esquerda (direta e indireta) ?

S pode transformar-se em algo começado por A que, por sua vez, se pode transformar em algo que começa por S

Recursividade indireta

Algoritmo

• Define-se uma ordem para os símbolos não terminais, por exemplo A1, A2, ..., An

• Para cada Ai:

  • fazem-se transformações de equivalência de modo a garantir que nenhuma produções com cabeça Ai, se expande em algo começado por Aj, com j < i.

  • elimina-se a recursividade à esquerda direta que as produções começadas por Ai possam ter.

Exemplo

Aplique-se este procedimento à gramatica seguinte, estabelecendo-se a ordem S, A

• S -> A a | b A -> A c | S d | end

As produções começadas por S satisfazem a condição, pelo que não é necessária qualquer transformação

A produção A -> S d viola a regra definida, pelo que, nela, S é substituído por ( A a | b ), obtendo-se

• S -> A a | b A -> A c | A a d | b d | end

Elimina-se a recursividade à esquerda direta das produções começadas por A, obtendo-se

• S -> A a | b A -> b d X | X X -> end | c X | a d X