🔍 Fatoração à Esquerda

A fatoração à esquerda é outra transformação essencial para tornar gramáticas adequadas para parsing eficiente, especialmente para parsers LL(1).

O Problema

A falta de fatoração à esquerda ocorre quando múltiplas produções para o mesmo não-terminal começam com os mesmos símbolos. Este problema aparece com frequência em linguagens de programação reais. Por exemplo, considere como declarações de variáveis funcionam em muitas linguagens onde você pode ou não inicializar a variável no momento da declaração:

\text{Declaracao} \rightarrow \text{int identificador} ; \mid \text{int identificador} = \text{expressao} ;

Estas duas produções compartilham um longo prefixo comum: “int identificador”. Um parser descendente que lê da esquerda para a direita processa primeiro a palavra-chave “int”, depois lê o identificador da variável, mas neste ponto ainda não sabe qual das duas produções deve aplicar. Ele precisa olhar além, verificando se o próximo símbolo é um ponto-e-vírgula (indicando declaração simples sem inicialização) ou um sinal de igual (indicando declaração com inicialização). Este “olhar além” força o parser a fazer backtracking, experimentando uma produção e voltando atrás se não funcionar, para então tentar a outra alternativa. No pior caso, este comportamento torna o parsing exponencialmente mais lento conforme a gramática e os programas crescem.

O Algoritmo de Fatoração

Para eliminar este problema, aplicamos fatoração à esquerda seguindo um procedimento sistemático. Primeiro, identificamos o prefixo comum mais longo entre as produções alternativas. Depois, extraímos este prefixo em uma produção separada, criando uma nova variável auxiliar para capturar apenas as diferenças entre as alternativas.

Vamos aplicar este algoritmo ao exemplo da declaração de variáveis. O prefixo comum entre as duas produções é claramente “int identificador”. As partes que diferem são o sufixo “;” na primeira produção e o sufixo “= expressao ;” na segunda. Seguindo o algoritmo, criamos uma nova variável auxiliar que chamaremos de InicializacaoOpcional, cujo nome descritivo revela seu papel: ela representa a parte opcional de inicialização que pode ou não aparecer após declarar o tipo e nome da variável.

A transformação produz as seguintes produções:

\text{Declaracao} \rightarrow \text{int identificador InicializacaoOpcional} \text{InicializacaoOpcional} \rightarrow = \text{expressao} ; \mid ;

Observe como a nova estrutura resolve o problema de decisão do parser. Agora há apenas uma produção para Declaracao, então não há escolha a fazer quando o parser vê “int” seguido de um identificador. O parser aplica essa única produção imediatamente, consome “int” e o identificador da entrada, e avança para expandir InicializacaoOpcional. Neste ponto, a decisão se torna trivial: se o próximo token é “=”, o parser aplica a primeira produção de InicializacaoOpcional (aquela com inicialização); se o próximo token é “;”, aplica a segunda produção (sem inicialização). Esta decisão é local e imediata, baseada apenas no próximo token, sem necessidade de exploração especulativa ou backtracking.

A variável auxiliar InicializacaoOpcional tem um papel conceitual claro: ela encapsula a escolha entre ter ou não ter inicialização, adiando esta decisão até o momento em que o parser tem informação suficiente (o token seguinte) para decidir corretamente. Este padrão de “adiar decisões até ter informação suficiente” é a essência da fatoração à esquerda.

Vamos considerar outro exemplo comum que aparece em muitas linguagens de programação: a distinção entre chamadas de função e acessos a arrays. Em uma linguagem hipotética, tanto funcao(argumentos) quanto array[indice] começam com um identificador, criando um problema de fatoração:

\text{Acesso} \rightarrow \text{identificador} ( \text{argumentos} ) \mid \text{identificador} [ \text{indice} ]

O prefixo comum aqui é apenas “identificador”, e as diferenças começam imediatamente após. Aplicando fatoração à esquerda, criamos uma variável auxiliar que chamaremos de TipoAcesso, que distingue entre acesso funcional (com parênteses) e acesso indexado (com colchetes):

\text{Acesso} \rightarrow \text{identificador TipoAcesso} \text{TipoAcesso} \rightarrow ( \text{argumentos} ) \mid [ \text{indice} ]

Novamente, a transformação permite que o parser tome decisões baseadas apenas no próximo token. Após consumir o identificador, o parser olha o próximo símbolo: se é “(” aplica a primeira produção de TipoAcesso, se é “[” aplica a segunda. Não há ambiguidade, não há necessidade de explorar múltiplos caminhos especulativamente.

Um detalhe importante sobre as variáveis auxiliares criadas durante fatoração: seus nomes devem refletir claramente seu papel semântico. Ao invés de usar nomes genéricos e sem significado como A’, B’, ou C’, preferimos nomes descritivos como InicializacaoOpcional, TipoAcesso, ou RestoDeclaracao. Esta prática não apenas torna a gramática mais legível para humanos, mas também facilita a geração de mensagens de erro significativas durante parsing e ajuda na manutenção futura da gramática. Quando você revisa sua gramática meses depois, nomes descritivos tornam muito mais fácil compreender a estrutura e fazer modificações necessárias.

A fatoração à esquerda, assim como a eliminação de recursão à esquerda, é uma transformação que preserva a linguagem gerada pela gramática. Todas as mesmas sentenças que eram aceitas antes continuam sendo aceitas depois, e nenhuma sentença nova é introduzida. A única coisa que muda é a estrutura interna da gramática, tornando-a mais adequada para parsing eficiente sem backtracking. Esta propriedade de preservação de linguagem é crucial porque significa que podemos aplicar estas transformações com confiança, sabendo que não estamos alterando inadvertidamente a linguagem que nossa gramática descreve.

Dart

class FatoradorEsquerda {
  // Identifica o prefixo comum mais longo entre duas produções
  static List<String> prefixoComum(
      List<String> producao1, 
      List<String> producao2) {
    List<String> prefixo = [];
    int minLen = producao1.length < producao2.length 
        ? producao1.length 
        : producao2.length;
    
    for (int i = 0; i < minLen; i++) {
      if (producao1[i] == producao2[i]) {
        prefixo.add(producao1[i]);
      } else {
        break;
      }
    }
    
    return prefixo;
  }
  
  // Exemplo clássico: comando if com else opcional
  // S → if E then S else S | if E then S
  static void demonstrarFatoracao() {
    print('Gramática Original (Problemática):');
    print('  S → if E then S else S');
    print('  S → if E then S');
    print('\nProblema: Prefixo comum "if E then S"');
    print('Parser não consegue decidir qual produção usar');
    print('até ver se há "else" depois do segundo S');
    
    print('\nGramática Fatorada:');
    print('  S → if E then S S\'');
    print('  S\' → else S');
    print('  S\' → ε');
    print('\nVantagem: Parser decide imediatamente aplicar S → if E then S S\'');
    print('Depois de processar "if E then S", decide se expande S\' baseado');
    print('em ver ou não "else" no próximo token');
  }
  
  // Fatoração mais complexa: declarações de tipos
  static void demonstrarFatoracaoTipos() {
    print('\n---\n');
    print('Exemplo 2: Declarações de Variáveis');
    print('\nGramática Original:');
    print('  Declaracao → int id = Exp');
    print('  Declaracao → int id');
    print('  Declaracao → bool id = Exp');
    print('  Declaracao → bool id');
    
    print('\nProblema Duplo:');
    print('1. "int" vs "bool" (prefixo comum no nível do tipo)');
    print('2. Com/sem inicialização (prefixo comum "tipo id")');
    
    print('\nGramática Fatorada (Solução em Etapas):');
    print('Etapa 1 - Fatorar inicialização:');
    print('  Declaracao → int id Inicializacao');
    print('  Declaracao → bool id Inicializacao');
    print('  Inicializacao → = Exp');
    print('  Inicializacao → ε');
    
    print('\nEtapa 2 - Fatorar tipo (opcional, melhora clareza):');
    print('  Declaracao → Tipo id Inicializacao');
    print('  Tipo → int | bool');
    print('  Inicializacao → = Exp | ε');
    
    print('\nResultado: Parser processa linearmente da esquerda para direita');
    print('Cada decisão baseada apenas no token corrente!');
  }
}

C++

#include <vector>
#include <string>
#include <iostream>
#include <algorithm>

class FatoradorEsquerda {
public:
    // Identifica o prefixo comum mais longo entre duas produções
    static std::vector<std::string> prefixoComum(
        const std::vector<std::string>& producao1,
        const std::vector<std::string>& producao2) {
        
        std::vector<std::string> prefixo;
        size_t minLen = std::min(producao1.size(), producao2.size());
        
        for (size_t i = 0; i < minLen; i++) {
            if (producao1[i] == producao2[i]) {
                prefixo.push_back(producao1[i]);
            } else {
                break;
            }
        }
        
        return prefixo;
    }
    
    // Exemplo clássico: comando if com else opcional
    static void demonstrarFatoracao() {
        std::cout << "Gramática Original (Problemática):\n";
        std::cout << "  S → if E then S else S\n";
        std::cout << "  S → if E then S\n";
        std::cout << "\nProblema: Prefixo comum \"if E then S\"\n";
        std::cout << "Parser não consegue decidir qual produção usar\n";
        std::cout << "até ver se há \"else\" depois do segundo S\n";
        
        std::cout << "\nGramática Fatorada:\n";
        std::cout << "  S → if E then S S'\n";
        std::cout << "  S' → else S\n";
        std::cout << "  S' → ε\n";
        std::cout << "\nVantagem: Parser decide imediatamente aplicar S → if E then S S'\n";
        std::cout << "Depois de processar \"if E then S\", decide se expande S' baseado\n";
        std::cout << "em ver ou não \"else\" no próximo token\n";
    }
    
    // Fatoração mais complexa: declarações de tipos
    static void demonstrarFatoracaoTipos() {
        std::cout << "\n---\n";
        std::cout << "Exemplo 2: Declarações de Variáveis\n";
        std::cout << "\nGramática Original:\n";
        std::cout << "  Declaracao → int id = Exp\n";
        std::cout << "  Declaracao → int id\n";
        std::cout << "  Declaracao → bool id = Exp\n";
        std::cout << "  Declaracao → bool id\n";
        
        std::cout << "\nProblema Duplo:\n";
        std::cout << "1. \"int\" vs \"bool\" (prefixo comum no nível do tipo)\n";
        std::cout << "2. Com/sem inicialização (prefixo comum \"tipo id\")\n";
        
        std::cout << "\nGramática Fatorada (Solução em Etapas):\n";
        std::cout << "Etapa 1 - Fatorar inicialização:\n";
        std::cout << "  Declaracao → int id Inicializacao\n";
        std::cout << "  Declaracao → bool id Inicializacao\n";
        std::cout << "  Inicializacao → = Exp\n";
        std::cout << "  Inicializacao → ε\n";
        
        std::cout << "\nEtapa 2 - Fatorar tipo (opcional, melhora clareza):\n";
        std::cout << "  Declaracao → Tipo id Inicializacao\n";
        std::cout << "  Tipo → int | bool\n";
        std::cout << "  Inicializacao → = Exp | ε\n";
        
        std::cout << "\nResultado: Parser processa linearmente da esquerda para direita\n";
        std::cout << "Cada decisão baseada apenas no token corrente!\n";
    }
};

Exemplo Importante: O Problema do Dangling Else

Um exemplo clássico onde fatoração é essencial é o problema do “dangling else” em linguagens como C e Java:

if (condicao1)
    if (condicao2)
        comando1;
    else
        comando2;

A questão é: o else pertence ao primeiro ou ao segundo if? Uma gramática mal fatorada permite ambas as interpretações, criando ambiguidade séria.

Solução com fatoração:

\text{Comando} \rightarrow \text{if (Exp) Comando ElseOpc} \text{ElseOpc} \rightarrow \text{else Comando} \mid \varepsilon

Com a convenção adicional de que else sempre se associa com o if mais próximo (implementada processando a gramática da esquerda para a direita), eliminamos a ambiguidade mantendo a fatoração.