# 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_\
  &#x20;   \| _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:

* ![](https://2105802016-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FP0B5wWrJT1pz8LDXyP2I%2Fuploads%2FVZa25x8kU6bCyo51tXzN%2F2022-07-05_00-18.png?alt=media\&token=f473a344-3ffd-41ff-ab5e-d2c4ed9e54e3)

Que corresponde ao _b_ seguindo do fecho de _a_, podendo ser representada pela gramática

* _A -> b X_\
  _X -> end_\
  &#x20;   \| _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_\
  &#x20;   \| _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_\
  &#x20;   \| _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_\
  &#x20;   \| _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_\
  &#x20;   \| _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_ )\
  &#xNAN;_&#x58; -> end_\
  &#x20;   \| _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

![](https://2105802016-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FP0B5wWrJT1pz8LDXyP2I%2Fuploads%2FZSOkmDPMK5s8Bh8NhSuU%2F2022-07-05_00-18.png?alt=media\&token=229d2a6f-0344-4f43-8bcf-558cad5c0ef8)

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_

&#x20;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_
