📚 Definição Formal de Gramáticas Livres de Contexto

A Estrutura Fundamental

Uma gramática livre de contexto é um sistema de reescrita que especifica como construir palavras válidas de uma linguagem através de regras de produção hierárquicas.

📋 Definição Formal

Uma gramática livre de contexto é uma 4-tupla G = (V, \Sigma, P, S) onde:

• V é um conjunto finito de variáveis (símbolos não-terminais)
• \Sigma é um conjunto finito de símbolos terminais (alfabeto da linguagem)
• P é um conjunto finito de produções da forma A \rightarrow \alpha
• S \in V é a variável inicial (símbolo inicial)

Restrições importantes:

• V \cap \Sigma = \varnothing (terminais e não-terminais são disjuntos)
• Em cada produção A \rightarrow \alpha: A \in V e \alpha \in (V \cup \Sigma)^*
• A diferença das gramáticas regulares: o lado direito \alpha pode conter qualquer combinação de terminais e não-terminais

Esta definição pode parecer similar às gramáticas regulares que você estudou anteriormente, mas a diferença fundamental está na forma das produções. Enquanto gramáticas regulares restringem severamente a forma do lado direito das produções, gramáticas livres de contexto permitem flexibilidade total, possibilitando a expressão de estruturas recursivas complexas.

O que torna essas gramáticas “livres de contexto” é a forma restrita das produções. Cada produção tem exatamente um não-terminal do lado esquerdo, independentemente do contexto em que esse não-terminal aparece. Esta propriedade simplifica enormemente o processamento, mas ainda permite expressar estruturas recursivas complexas que são essenciais para linguagens de programação.

Componentes em Detalhes

Variáveis (Não-terminais): Representam categorias sintáticas ou conceitos que podem ser expandidos em estruturas mais complexas. Em gramáticas para linguagens de programação, variáveis típicas incluem \text{Expressao}, \text{Comando}, \text{Programa}, \text{Declaracao}. Cada variável representa uma classe de estruturas que compartilham propriedades sintáticas comuns.

Símbolos Terminais: São os elementos atômicos da linguagem - tokens que aparecem diretamente nas palavras finais. Para linguagens de programação, incluem palavras-chave como \text{if}, \text{while}, operadores como +, *, e símbolos especiais como parênteses e ponto-e-vírgula.

Produções: Especificam como variáveis podem ser expandidas ou “reescritas” em combinações de outras variáveis e terminais. A produção A \rightarrow \alpha significa “a variável A pode ser substituída pela string \alpha”. Esta substituição é o mecanismo fundamental através do qual derivações constroem palavras da linguagem.

Símbolo Inicial: A variável de onde todas as derivações começam. Tipicamente representa o conceito mais abrangente da linguagem - para linguagens de programação, frequentemente algo como \text{Programa} ou \text{UnidadeDeCompilacao}.

Exemplo Detalhado: Expressões Aritméticas

Para ilustrar estes conceitos, consideremos uma gramática para expressões aritméticas simples:

Dart

// Definição da gramática para expressões aritméticas
class GramaticaExpressoes {
  // V = {E, T, F} - Variáveis (não-terminais)
  static const Set<String> variaveis = {'E', 'T', 'F'};
  
  // Σ = {+, *, (, ), id} - Símbolos terminais
  static const Set<String> terminais = {'+', '*', '(', ')', 'id'};
  
  // S = E - Símbolo inicial
  static const String simboloInicial = 'E';
  
  // P - Conjunto de produções
  static const Map<String, List<List<String>>> producoes = {
    'E': [
      ['E', '+', 'T'],  // E → E + T
      ['T']             // E → T
    ],
    'T': [
      ['T', '*', 'F'],  // T → T * F
      ['F']             // T → F
    ],
    'F': [
      ['(', 'E', ')'],  // F → ( E )
      ['id']            // F → id
    ]
  };
  
  // Método para derivar uma expressão passo a passo
  static List<String> derivarExpressao(String expressao) {
    List<String> passos = [];
    passos.add('Início: E');
    
    // Exemplo de derivação para "id + id * id"
    if (expressao == 'id + id * id') {
      passos.add('E → E + T');
      passos.add('E + T → T + T');
      passos.add('T + T → F + T');
      passos.add('F + T → id + T');
      passos.add('id + T → id + T * F');
      passos.add('id + T * F → id + F * F');
      passos.add('id + F * F → id + id * F');
      passos.add('id + id * F → id + id * id');
    }
    
    return passos;
  }
  
  // Visualização da árvore de derivação
  static String gerarArvore(String expressao) {
    // Retorna representação textual da árvore
    return '''
        E
        ├── E
        │   └── T
        │       └── F
        │           └── id
        ├── +
        └── T
            ├── T
            │   └── F
            │       └── id
            ├── *
            └── F
                └── id
    ''';
  }
}

C++

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

class GramaticaExpressoes {
public:
    // V = {E, T, F} - Variáveis (não-terminais)
    static const std::set<std::string> variaveis;
    
    // Σ = {+, *, (, ), id} - Símbolos terminais
    static const std::set<std::string> terminais;
    
    // S = E - Símbolo inicial
    static const std::string simboloInicial;
    
    // P - Conjunto de produções
    static const std::map<std::string, std::vector<std::vector<std::string>>> producoes;
    
    // Deriva uma expressão passo a passo
    static std::vector<std::string> derivarExpressao(const std::string& expressao);
    
    // Gera representação textual da árvore
    static std::string gerarArvore(const std::string& expressao);
};

const std::set<std::string> GramaticaExpressoes::variaveis = {"E", "T", "F"};
const std::set<std::string> GramaticaExpressoes::terminais = {"+", "*", "(", ")", "id"};
const std::string GramaticaExpressoes::simboloInicial = "E";

const std::map<std::string, std::vector<std::vector<std::string>>> 
GramaticaExpressoes::producoes = {
    {"E", {{"E", "+", "T"}, {"T"}}},
    {"T", {{"T", "*", "F"}, {"F"}}},
    {"F", {{"(", "E", ")"}, {"id"}}}
};

std::vector<std::string> GramaticaExpressoes::derivarExpressao(
    const std::string& expressao) {
    std::vector<std::string> passos;
    passos.push_back("Início: E");
    
    // Exemplo de derivação para "id + id * id"
    if (expressao == "id + id * id") {
        passos.push_back("E → E + T");
        passos.push_back("E + T → T + T");
        passos.push_back("T + T → F + T");
        passos.push_back("F + T → id + T");
        passos.push_back("id + T → id + T * F");
        passos.push_back("id + T * F → id + F * F");
        passos.push_back("id + F * F → id + id * F");
        passos.push_back("id + id * F → id + id * id");
    }
    
    return passos;
}

Esta gramática ilustra elegantemente como a estrutura hierárquica codifica precedência de operadores. Observe que multiplicação aparece “mais profundamente” na hierarquia (em T e F) do que adição (que aparece no nível mais alto, em E). Esta profundidade estrutural força a multiplicação a ser avaliada antes da adição, implementando as regras matemáticas de precedência que aprendemos desde a escola.