Eliminação de Recursividade á Esquerda
Last updated
Last updated
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)*
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
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 )*
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
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
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.
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
