🏗️ Estudo de Caso Completo: Refinando uma Gramática Problemática

Vamos aplicar tudo que aprendemos a um exemplo realista e completo. Consideremos uma pequena linguagem de programação com declarações, atribuições e expressões.

Gramática Original (Problemática)

S → programa
programa → declaracao programa | comando programa | ε
declaracao → tipo lista_ids ;
tipo → int | bool
lista_ids → IDENTIFICADOR , lista_ids | IDENTIFICADOR
comando → atribuicao | condicional | bloco
atribuicao → IDENTIFICADOR = expressao ;
condicional → if ( expressao ) comando else comando
bloco → { programa }
expressao → expressao + expressao | expressao * expressao | ( expressao ) | IDENTIFICADOR | NUMERO

Problemas identificados:

1. Ambiguidade em expressões: expressao + expressao e expressao * expressao não especificam precedência
2. Recursão à esquerda: em expressao
3. Produção vazia: programa → ε pode causar problemas
4. Falta estrutura clara: mistura declarações e comandos sem organização

Passo 1: Corrigir Estrutura do Programa

Primeiro, eliminamos a produção vazia e organizamos melhor a estrutura:

S → programa
programa → item programa | item
item → declaracao | comando
declaracao → tipo lista_ids ;
tipo → int | bool
lista_ids → IDENTIFICADOR lista_ids' 
lista_ids' → , IDENTIFICADOR lista_ids' | ε
comando → atribuicao | condicional | bloco
atribuicao → IDENTIFICADOR = expressao ;
condicional → if ( expressao ) comando else comando
bloco → { programa }

Passo 2: Eliminar Ambiguidade e Recursão em Expressões

Criamos hierarquia para precedência (multiplicação > adição) e eliminamos recursão à esquerda:

expressao → termo expressao'
expressao' → + termo expressao' | ε
termo → fator termo'
termo' → * fator termo' | ε
fator → ( expressao ) | IDENTIFICADOR | NUMERO

Gramática Final Refinada

Dart

class GramaticaRefinada {
  // Gramática original problemática
  static const Map<String, List<List<String>>> gramaticaOriginal = {
    'S': [['programa']],
    'programa': [['declaracao', 'programa'], ['comando', 'programa'], []],
    'expressao': [
      ['expressao', '+', 'expressao'],
      ['expressao', '*', 'expressao'],
      ['(', 'expressao', ')'],
      ['IDENTIFICADOR'],
      ['NUMERO']
    ]
  };
  
  // Gramática corrigida sem ambiguidade
  static const Map<String, List<List<String>>> gramaticaCorrigida = {
    'S': [['programa']],
    'programa': [['item', 'programa'], ['item']],
    'item': [['declaracao'], ['comando']],
    'declaracao': [['tipo', 'lista_ids', ';']],
    'tipo': [['int'], ['bool']],
    'lista_ids': [['IDENTIFICADOR', 'lista_ids\'']],
    'lista_ids\'': [[',', 'IDENTIFICADOR', 'lista_ids\''], ['ε']],
    'comando': [['atribuicao'], ['condicional'], ['bloco']],
    'atribuicao': [['IDENTIFICADOR', '=', 'expressao', ';']],
    'condicional': [['if', '(', 'expressao', ')', 'comando', 'else', 'comando']],
    'bloco': [['{', 'programa', '}']],
    
    // Hierarquia de precedência para expressões
    'expressao': [['termo', 'expressao\'']],
    'expressao\'': [['+', 'termo', 'expressao\''], ['ε']],
    'termo': [['fator', 'termo\'']],
    'termo\'': [['*', 'fator', 'termo\''], ['ε']],
    'fator': [['(', 'expressao', ')'], ['IDENTIFICADOR'], ['NUMERO']]
  };
  
  // Análise das melhorias implementadas
  static Map<String, String> analiseMelhorias() {
    return {
      'eliminacao_ambiguidade': 'Hierarquia expressao->termo->fator resolve precedência',
      'eliminacao_epsilon': 'Substituição de programa→ε por estrutura recursiva clara',
      'recursao_controlada': 'Recursão à esquerda consistente para associatividade',
      'estrutura_clara': 'Separação clara entre declarações e comandos'
    };
  }
  
  // Método para verificar se a nova gramática gera as mesmas strings válidas
  static bool verificaEquivalencia(List<String> exemploPrograma) {
    // Implementação simplificada que verifica se um programa é válido
    // na gramática corrigida
    return true; // Placeholder para implementação completa
  }
}

C++

#include <map>
#include <vector>
#include <string>

class GramaticaRefinada {
public:
    // Gramática original problemática
    static const std::map<std::string, std::vector<std::vector<std::string>>> 
    gramaticaOriginal;
    
    // Gramática corrigida sem ambiguidade
    static const std::map<std::string, std::vector<std::vector<std::string>>> 
    gramaticaCorrigida;
    
    // Análise das melhorias implementadas
    static std::map<std::string, std::string> analiseMelhorias();
    
    // Verifica equivalência entre gramáticas
    static bool verificaEquivalencia(const std::vector<std::string>& exemploPrograma);
};

const std::map<std::string, std::vector<std::vector<std::string>>> 
GramaticaRefinada::gramaticaOriginal = {
    {"S", {{"programa"}}},
    {"programa", {{"declaracao", "programa"}, {"comando", "programa"}, {}}},
    {"expressao", {
        {"expressao", "+", "expressao"},
        {"expressao", "*", "expressao"},
        {"(", "expressao", ")"},
        {"IDENTIFICADOR"},
        {"NUMERO"}
    }}
};

const std::map<std::string, std::vector<std::vector<std::string>>> 
GramaticaRefinada::gramaticaCorrigida = {
    {"S", {{"programa"}}},
    {"programa", {{"item", "programa"}, {"item"}}},
    {"item", {{"declaracao"}, {"comando"}}},
    {"declaracao", {{"tipo", "lista_ids", ";"}}},
    {"tipo", {{"int"}, {"bool"}}},
    {"lista_ids", {{"IDENTIFICADOR", "lista_ids'"}}},
    {"lista_ids'", {{",", "IDENTIFICADOR", "lista_ids'"}, {"ε"}}},
    {"comando", {{"atribuicao"}, {"condicional"}, {"bloco"}}},
    {"atribuicao", {{"IDENTIFICADOR", "=", "expressao", ";"}}},
    {"condicional", {{"if", "(", "expressao", ")", "comando", "else", "comando"}}},
    {"bloco", {{"{", "programa", "}"}}},
    
    // Hierarquia de precedência para expressões
    {"expressao", {{"termo", "expressao'"}}},
    {"expressao'", {{"+", "termo", "expressao'"}, {"ε"}}},
    {"termo", {{"termo'", "fator"}}},
    {"termo'", {{"*", "fator", "termo'"}, {"ε"}}},
    {"fator", {{"(", "expressao", ")"}, {"IDENTIFICADOR"}, {"NUMERO"}}}
};

std::map<std::string, std::string> GramaticaRefinada::analiseMelhorias() {
    return {
        {"eliminacao_ambiguidade", "Hierarquia expressao->termo->fator resolve precedência"},
        {"eliminacao_epsilon", "Substituição de programa→ε por estrutura recursiva clara"},
        {"recursao_controlada", "Recursão à esquerda consistente para associatividade"},
        {"estrutura_clara", "Separação clara entre declarações e comandos"}
    };
}

Validação da Solução

Vamos verificar se nossa gramática corrigida realmente resolve os problemas:

Teste de Precedência: A expressão a + b * c agora só pode ser derivada como a + (b * c) devido à hierarquia expressao → termo → fator. A multiplicação fica mais “profunda” na árvore, garantindo precedência maior.

Teste de Associatividade: A expressão a + b + c deriva como ((a + b) + c) devido à recursão à esquerda em expressao → termo expressao', que foi transformada mas mantém a associatividade à esquerda desejada.

Eliminação de Ambiguidade: Cada expressão válida possui exatamente uma árvore de derivação na gramática corrigida.

Processabilidade: A gramática agora não tem recursão à esquerda e pode ser processada por parsers descendentes.