🔄 Eliminação de Recursão à Esquerda
A recursão à esquerda é um problema fundamental para parsers descendentes, mas felizmente existe um algoritmo sistemático para eliminá-la. Vamos entender primeiro por que recursão à esquerda é problemática, depois aprender como transformá-la.
🚫 Por Que Recursão à Esquerda É Problemática
Um parser descendente começa com o símbolo inicial e tenta expandir não-terminais até produzir a sequência de terminais que corresponde à entrada. Quando encontra uma produção recursiva à esquerda como A \rightarrow A\alpha, o parser tenta expandir A aplicando a mesma produção, criando um loop infinito que nunca consome nenhum símbolo de entrada.
Para entender isto concretamente, imagine um parser tentando reconhecer id + id. Ele começa com E e vê que pode aplicar E \rightarrow E + T. Agora precisa reconhecer um E antes de ler qualquer símbolo! Então tenta aplicar E \rightarrow E + T novamente, e novamente, infinitamente. O parser fica preso em recursão infinita sem fazer progresso real.
Recursão Imediata à Esquerda
A forma mais simples de recursão à esquerda é a recursão imediata, onde um não-terminal aparece imediatamente após si mesmo no lado direito de uma produção. Considere o conjunto de produções:
A \rightarrow A\alpha_1 \mid A\alpha_2 \mid \ldots \mid A\alpha_m \mid \beta_1 \mid \beta_2 \mid \ldots \mid \beta_n
Aqui, \alpha_i são strings que não começam com A, e \beta_j são strings que não começam com A. As produções com A\alpha_i são recursivas à esquerda, enquanto as produções com \beta_j não são.
O algoritmo de eliminação de recursão imediata à esquerda funciona assim:
- Substitua todas as produções de A por:
- A \rightarrow \beta_1 A' \mid \beta_2 A' \mid \ldots \mid \beta_n A'
- Introduza uma nova variável A' com produções:
- A' \rightarrow \alpha_1 A' \mid \alpha_2 A' \mid \ldots \mid \alpha_m A' \mid \varepsilon
Esta transformação preserva a linguagem gerada mas elimina a recursão à esquerda, substituindo-a por recursão à direita que parsers descendentes podem processar sem problemas.
Vamos trabalhar com um exemplo concreto que você certamente já encontrou: a gramática de expressões aritméticas com adição. Esta é uma situação muito comum onde recursão à esquerda aparece naturalmente quando tentamos expressar que a adição é associativa à esquerda (ou seja, que a + b + c deve ser interpretado como (a + b) + c).
Considere a seguinte gramática original que modela expressões aritméticas simples:
E \rightarrow E + T \mid E - T \mid T
Esta gramática tem três produções para o não-terminal E. As duas primeiras produções (E \rightarrow E + T e E \rightarrow E - T) são recursivas à esquerda porque começam com o próprio E. A terceira produção (E \rightarrow T) não é recursiva. Esta estrutura captura perfeitamente a ideia de que uma expressão pode ser uma soma ou subtração de termos, mas cria o problema de loop infinito para parsers descendentes.
Vamos aplicar o algoritmo passo a passo. Primeiro, identificamos os componentes da nossa gramática usando a notação do algoritmo. Temos A = E, as partes recursivas são \alpha_1 = + T e \alpha_2 = - T (removemos o E inicial de cada produção recursiva), e a parte não-recursiva é \beta_1 = T.
Agora aplicamos a transformação. O primeiro passo diz para substituir todas as produções de E por versões que começam com as partes não-recursivas seguidas de uma nova variável. Como temos apenas uma produção não-recursiva (\beta_1 = T), criamos:
E \rightarrow T E'
Esta nova produção diz que toda expressão começa com um termo T, seguido por algo que será definido pela nova variável E'. Observe que eliminamos completamente a recursão à esquerda de E - agora E sempre começa expandindo T, nunca E novamente.
O segundo passo introduz a nova variável E' que captura a recursão, mas agora à direita. Como tínhamos duas partes recursivas (\alpha_1 = + T e \alpha_2 = - T), criamos as produções:
E' \rightarrow + T E' E' \rightarrow - T E' E' \rightarrow \varepsilon
A intuição aqui é que E' representa “zero ou mais ocorrências de operador seguido de termo”. A primeira produção diz “pode haver uma adição de termo seguida de mais operações”. A segunda diz “pode haver uma subtração de termo seguida de mais operações”. A terceira produção vazia diz “ou pode não haver mais nada”.
A gramática completa transformada é:
E \rightarrow T E' E' \rightarrow + T E' \mid - T E' \mid \varepsilon
Vamos verificar que esta gramática gera a mesma linguagem através de um exemplo. Considere a expressão a + b - c. Na gramática original, derivaríamos algo como:
E \Rightarrow E - T \Rightarrow E + T - T \Rightarrow T + T - T \Rightarrow a + b - c
Na gramática transformada, a derivação é:
E \Rightarrow T E' \Rightarrow a E' \Rightarrow a + T E' \Rightarrow a + b E' \Rightarrow a + b - T E' \Rightarrow a + b - c E' \Rightarrow a + b - c
Observe que chegamos à mesma string final! A diferença crucial é que na gramática transformada, nunca precisamos expandir E em algo que começa com E novamente. Sempre começamos expandindo T, que eventualmente chega a um identificador ou número que consome um token de entrada. Isto permite que o parser descendente faça progresso imediato, evitando o loop infinito.
A transformação é sutil mas poderosa. Essencialmente, mudamos de dizer “uma expressão é uma expressão seguida de operador e termo” (recursão à esquerda) para dizer “uma expressão é um termo seguido de zero ou mais pares de operador-e-termo” (recursão à direita). Ambas as formulações descrevem a mesma linguagem, mas a segunda pode ser processada eficientemente por parsers descendentes.
Um detalhe importante: embora esta transformação elimine o problema de loop infinito, ela muda sutilmente a estrutura da árvore sintática gerada. A gramática original produzia árvores que naturalmente refletiam associatividade à esquerda, enquanto a gramática transformada produz árvores com estrutura diferente. Na prática, compensamos isto na análise semântica subsequente, interpretando a árvore transformada de maneira que preserve a semântica de associatividade à esquerda desejada. Esta é uma troca aceitável porque parsing eficiente é mais importante que ter exatamente a estrutura de árvore que gostaríamos idealmente.
🧪 Exemplo prático
E → E + T | T
Vamos montar a expressão a + b + c com a nova gramática:
- E → T E’
- T → a
- E’ → + T E’
- T → b
- E’ → + T E’
- T → c
- E’ → ε
Resultado: a + b + c
class EliminadorRecursaoEsquerda {
// Representa uma produção gramatical
static class Producao {
String ladoEsquerdo;
List<String> ladoDireito;
Producao(this.ladoEsquerdo, this.ladoDireito);
@override
String toString() => '$ladoEsquerdo → ${ladoDireito.join(" ")}';
}
// Exemplo: E → E + T | T
static List<Producao> gramaticaOriginal = [
Producao('E', ['E', '+', 'T']), // Recursiva à esquerda
Producao('E', ['T']) // Não recursiva
];
// Resultado após eliminação: E → T E' e E' → + T E' | ε
static List<Producao> gramaticaTransformada = [
Producao('E', ['T', "E'"]),
Producao("E'", ['+', 'T', "E'"]),
Producao("E'", ['ε'])
];
// Elimina recursão imediata à esquerda
static List<Producao> eliminarRecursaoImediata(
String naoTerminal,
List<Producao> producoes) {
// Separa produções recursivas das não-recursivas
List<List<String>> recursivas = [];
List<List<String>> naoRecursivas = [];
for (var prod in producoes) {
if (prod.ladoEsquerdo == naoTerminal) {
if (prod.ladoDireito.isNotEmpty &&
prod.ladoDireito[0] == naoTerminal) {
// Recursiva: A → A α (remove o A inicial)
recursivas.add(prod.ladoDireito.sublist(1));
} else {
// Não recursiva: A → β
naoRecursivas.add(prod.ladoDireito);
}
}
}
// Se não há recursão, retorna produções originais
if (recursivas.isEmpty) {
return producoes;
}
// Cria nova variável A'
String novaVariavel = "$naoTerminal'";
List<Producao> resultado = [];
// A → β A' para cada β não-recursivo
for (var beta in naoRecursivas) {
resultado.add(Producao(naoTerminal, [...beta, novaVariavel]));
}
// A' → α A' para cada α recursivo
for (var alpha in recursivas) {
resultado.add(Producao(novaVariavel, [...alpha, novaVariavel]));
}
// A' → ε
resultado.add(Producao(novaVariavel, ['ε']));
return resultado;
}
// Demonstra a transformação
static void demonstrar() {
print('Gramática Original:');
for (var prod in gramaticaOriginal) {
print(' $prod');
}
print('\nProblema: E → E + T causa loop infinito em parser descendente');
print('Ao tentar expandir E, aplica E → E + T recursivamente');
var transformada = eliminarRecursaoImediata('E', gramaticaOriginal);
print('\nGramática Transformada:');
for (var prod in transformada) {
print(' $prod');
}
print('\nVantagem: Agora o parser pode processar da esquerda para direita');
print('E sempre começa com T, que não é recursivo');
print("E' captura a recursão (zero ou mais ocorrências de '+ T')");
}
}#include <string>
#include <vector>
#include <iostream>
class EliminadorRecursaoEsquerda {
public:
// Representa uma produção gramatical
struct Producao {
std::string ladoEsquerdo;
std::vector<std::string> ladoDireito;
Producao(const std::string& esq, const std::vector<std::string>& dir)
: ladoEsquerdo(esq), ladoDireito(dir) {}
std::string toString() const {
std::string result = ladoEsquerdo + " → ";
for (size_t i = 0; i < ladoDireito.size(); i++) {
result += ladoDireito[i];
if (i < ladoDireito.size() - 1) result += " ";
}
return result;
}
};
// Exemplo: E → E + T | T
static std::vector<Producao> gramaticaOriginal() {
return {
Producao("E", {"E", "+", "T"}), // Recursiva à esquerda
Producao("E", {"T"}) // Não recursiva
};
}
// Elimina recursão imediata à esquerda
static std::vector<Producao> eliminarRecursaoImediata(
const std::string& naoTerminal,
const std::vector<Producao>& producoes) {
// Separa produções recursivas das não-recursivas
std::vector<std::vector<std::string>> recursivas;
std::vector<std::vector<std::string>> naoRecursivas;
for (const auto& prod : producoes) {
if (prod.ladoEsquerdo == naoTerminal) {
if (!prod.ladoDireito.empty() &&
prod.ladoDireito[0] == naoTerminal) {
// Recursiva: A → A α (remove o A inicial)
std::vector<std::string> alpha(
prod.ladoDireito.begin() + 1,
prod.ladoDireito.end()
);
recursivas.push_back(alpha);
} else {
// Não recursiva: A → β
naoRecursivas.push_back(prod.ladoDireito);
}
}
}
// Se não há recursão, retorna produções originais
if (recursivas.empty()) {
return producoes;
}
// Cria nova variável A'
std::string novaVariavel = naoTerminal + "'";
std::vector<Producao> resultado;
// A → β A' para cada β não-recursivo
for (const auto& beta : naoRecursivas) {
std::vector<std::string> novaProd = beta;
novaProd.push_back(novaVariavel);
resultado.push_back(Producao(naoTerminal, novaProd));
}
// A' → α A' para cada α recursivo
for (const auto& alpha : recursivas) {
std::vector<std::string> novaProd = alpha;
novaProd.push_back(novaVariavel);
resultado.push_back(Producao(novaVariavel, novaProd));
}
// A' → ε
resultado.push_back(Producao(novaVariavel, {"ε"}));
return resultado;
}
// Demonstra a transformação
static void demonstrar() {
auto original = gramaticaOriginal();
std::cout << "Gramática Original:\n";
for (const auto& prod : original) {
std::cout << " " << prod.toString() << "\n";
}
std::cout << "\nProblema: E → E + T causa loop infinito em parser descendente\n";
std::cout << "Ao tentar expandir E, aplica E → E + T recursivamente\n";
auto transformada = eliminarRecursaoImediata("E", original);
std::cout << "\nGramática Transformada:\n";
for (const auto& prod : transformada) {
std::cout << " " << prod.toString() << "\n";
}
std::cout << "\nVantagem: Agora o parser pode processar da esquerda para direita\n";
std::cout << "E sempre começa com T, que não é recursivo\n";
std::cout << "E' captura a recursão (zero ou mais ocorrências de '+ T')\n";
}
};Exemplo Completo de Eliminação
Vamos aplicar o algoritmo completo a uma gramática para expressões aritméticas, usando nomes mais descritivos que revelam o papel de cada componente. Ao invés de usar símbolos abstratos como E, T e F, vamos usar nomes que expressam claramente o conceito sintático que cada não-terminal representa.
Gramática original (com recursão à esquerda):
\text{Expressao} \rightarrow \text{Expressao} + \text{Termo} \mid \text{Expressao} - \text{Termo} \mid \text{Termo} \text{Termo} \rightarrow \text{Termo} * \text{Fator} \mid \text{Termo} / \text{Fator} \mid \text{Fator} \text{Fator} \rightarrow ( \text{Expressao} ) \mid \text{numero} \mid \text{variavel}
Esta gramática captura expressões aritméticas completas onde podemos ter somas e subtrações de termos, termos são produtos e divisões de fatores, e fatores são números, variáveis, ou expressões entre parênteses. O problema é que tanto Expressao quanto Termo têm recursão à esquerda, o que causa loops infinitos em parsers descendentes.
Vamos agora eliminar a recursão passo a passo, começando pela não-terminal Expressao.
Passo 1: Eliminar recursão de Expressao.
Observe que Expressao tem duas produções recursivas à esquerda (aquelas que começam com Expressao do lado direito) e uma produção não-recursiva (aquela que começa com Termo). Quando aplicamos o algoritmo, separamos estas produções. As partes recursivas são “+ \text{Termo}” e “- \text{Termo}” (removemos o Expressao inicial de cada produção recursiva para isolar apenas o que vem depois). A parte não-recursiva é simplesmente “Termo”.
Agora criamos uma nova variável chamada RestoExpressao (ao invés de E’) que capturará a ideia de “o que pode vir depois do termo inicial em uma expressão”. As novas produções ficam:
\text{Expressao} \rightarrow \text{Termo RestoExpressao} \text{RestoExpressao} \rightarrow + \text{Termo RestoExpressao} \mid - \text{Termo RestoExpressao} \mid \varepsilon
Leia estas produções assim: “Uma expressão sempre começa com um termo, seguido possivelmente de mais operações de adição ou subtração”. A variável RestoExpressao representa “zero ou mais ocorrências de operador-de-adição-ou-subtração seguido de termo”. A produção vazia (épsilon) permite que RestoExpressao desapareça quando não há mais operações.
Passo 2: Eliminar recursão de Termo.
Aplicamos exatamente o mesmo processo ao não-terminal Termo. Ele também tem duas produções recursivas à esquerda (multiplicação e divisão) e uma não-recursiva (que deriva Fator). As partes recursivas, após removermos o Termo inicial, são “* \text{Fator}” e “/ \text{Fator}”. A parte não-recursiva é “Fator”.
Criamos uma nova variável RestoTermo que representa “o que pode vir depois do fator inicial em um termo”. As novas produções ficam:
\text{Termo} \rightarrow \text{Fator RestoTermo} \text{RestoTermo} \rightarrow * \text{Fator RestoTermo} \mid / \text{Fator RestoTermo} \mid \varepsilon
Agora leia: “Um termo sempre começa com um fator, seguido possivelmente de mais operações de multiplicação ou divisão”. A variável RestoTermo representa “zero ou mais ocorrências de operador-de-multiplicação-ou-divisão seguido de fator”.
Gramática transformada (sem recursão à esquerda):
\text{Expressao} \rightarrow \text{Termo RestoExpressao} \text{RestoExpressao} \rightarrow + \text{Termo RestoExpressao} \mid - \text{Termo RestoExpressao} \mid \varepsilon \text{Termo} \rightarrow \text{Fator RestoTermo} \text{RestoTermo} \rightarrow * \text{Fator RestoTermo} \mid / \text{Fator RestoTermo} \mid \varepsilon \text{Fator} \rightarrow ( \text{Expressao} ) \mid \text{numero} \mid \text{variavel}
Vamos verificar que funciona com um exemplo concreto. Considere a expressão x + y * z. Na gramática transformada, a derivação procede assim:
Começamos com Expressao. Aplicamos a única produção disponível, que diz que devemos expandir Termo seguido de RestoExpressao. Expandindo Termo, obtemos Fator seguido de RestoTermo. O Fator se expande para a variável x. Como não há multiplicação ou divisão imediatamente após x, RestoTermo desaparece usando a produção vazia. Agora processamos RestoExpressao, que vê o operador + e portanto usa a produção que adiciona mais um termo. Este novo termo se expande em y multiplicado por z, onde a multiplicação é capturada por RestoTermo.
O ponto crucial é que em nenhum momento o parser tentou expandir Expressao em algo começando com Expressao, ou Termo em algo começando com Termo. Sempre começamos expandindo o não-recursivo (Termo para Expressao, Fator para Termo), garantindo progresso imediato ao consumir símbolos de entrada. As variáveis RestoExpressao e RestoTermo capturam a repetição através de recursão à direita, que parsers descendentes processam naturalmente através da pilha de chamadas recursivas.
Esta gramática transformada gera exatamente a mesma linguagem que a original (todas as mesmas expressões aritméticas válidas), mas agora pode ser processada por parsers descendentes sem loops infinitos!