📊 Conjuntos FIRST e FOLLOW

Para determinar se uma gramática pode ser processada eficientemente por um parser preditivo (LL(1)), precisamos calcular dois conjuntos fundamentais para cada não-terminal: FIRST e FOLLOW.

Conjunto FIRST

O conjunto FIRST(\alpha) contém todos os terminais que podem aparecer no início de strings derivadas de \alpha. Se \alpha pode derivar a string vazia, então \varepsilon \in \text{FIRST}(\alpha).

Algoritmo para calcular FIRST:

1. Se X é terminal: \text{FIRST}(X) = \{X\}

2. Se X é não-terminal com produção X \rightarrow \varepsilon: adicione \varepsilon a \text{FIRST}(X)

3. Se X é não-terminal com produção X \rightarrow Y_1 Y_2 \ldots Y_k:

   • Adicione todos os não-\varepsilon de \text{FIRST}(Y_1) a \text{FIRST}(X)
   • Se \varepsilon \in \text{FIRST}(Y_1), adicione todos os não-\varepsilon de \text{FIRST}(Y_2) a \text{FIRST}(X)
   • Continue para Y_3, Y_4, \ldots enquanto \varepsilon estiver em todos os FIRST anteriores
   • Se \varepsilon está em todos os \text{FIRST}(Y_i), adicione \varepsilon a \text{FIRST}(X)

Conjunto FOLLOW

O conjunto FOLLOW(A) contém todos os terminais que podem aparecer imediatamente após A em alguma derivação. Por convenção, \$ \in \text{FOLLOW}(S) onde \$ representa o fim da entrada e S é o símbolo inicial.

Algoritmo para calcular FOLLOW:

1. Coloque \$ em \text{FOLLOW}(S) onde S é o símbolo inicial

2. Se há uma produção A \rightarrow \alpha B \beta:

   • Adicione todos os não-\varepsilon de \text{FIRST}(\beta) a \text{FOLLOW}(B)
   • Se \varepsilon \in \text{FIRST}(\beta), adicione \text{FOLLOW}(A) a \text{FOLLOW}(B)

3. Se há uma produção A \rightarrow \alpha B:

   • Adicione \text{FOLLOW}(A) a \text{FOLLOW}(B)

4. Repita até que nenhum conjunto FOLLOW mude

Dart

class CalculadorFIRSTFOLLOW {
  Map<String, Set<String>> first = {};
  Map<String, Set<String>> follow = {};
  Map<String, List<List<String>>> gramatica;
  String simboloInicial;
  
  CalculadorFIRSTFOLLOW(this.gramatica, this.simboloInicial);
  
  // Verifica se um símbolo é terminal
  bool ehTerminal(String simbolo) {
    return !gramatica.containsKey(simbolo) && simbolo != 'ε';
  }
  
  // Calcula FIRST para todos os não-terminais
  void calcularFIRST() {
    // Inicializa conjuntos vazios
    for (var naoTerminal in gramatica.keys) {
      first[naoTerminal] = {};
    }
    
    bool mudou = true;
    while (mudou) {
      mudou = false;
      
      for (var naoTerminal in gramatica.keys) {
        for (var producao in gramatica[naoTerminal]!) {
          var antesSize = first[naoTerminal]!.length;
          
          if (producao.isEmpty || producao[0] == 'ε') {
            // Produção vazia
            first[naoTerminal]!.add('ε');
          } else {
            // Processa cada símbolo da produção
            bool todosDerivamEpsilon = true;
            
            for (var simbolo in producao) {
              if (ehTerminal(simbolo)) {
                // Terminal: adiciona e para
                first[naoTerminal]!.add(simbolo);
                todosDerivamEpsilon = false;
                break;
              } else {
                // Não-terminal: adiciona FIRST(simbolo) exceto ε
                var firstSimbolo = first[simbolo] ?? {};
                first[naoTerminal]!.addAll(
                    firstSimbolo.where((s) => s != 'ε'));
                
                // Se simbolo não deriva ε, para
                if (!firstSimbolo.contains('ε')) {
                  todosDerivamEpsilon = false;
                  break;
                }
              }
            }
            
            // Se todos derivam ε, adiciona ε ao resultado
            if (todosDerivamEpsilon) {
              first[naoTerminal]!.add('ε');
            }
          }
          
          if (first[naoTerminal]!.length > antesSize) {
            mudou = true;
          }
        }
      }
    }
  }
  
  // Calcula FOLLOW para todos os não-terminais
  void calcularFOLLOW() {
    // Inicializa conjuntos vazios
    for (var naoTerminal in gramatica.keys) {
      follow[naoTerminal] = {};
    }
    
    // Símbolo inicial tem $ no FOLLOW
    follow[simboloInicial]!.add('\$');
    
    bool mudou = true;
    while (mudou) {
      mudou = false;
      
      for (var naoTerminal in gramatica.keys) {
        for (var producao in gramatica[naoTerminal]!) {
          // Processa cada símbolo da produção
          for (int i = 0; i < producao.length; i++) {
            var simbolo = producao[i];
            
            if (!ehTerminal(simbolo) && simbolo != 'ε') {
              var antesSize = follow[simbolo]!.length;
              
              if (i == producao.length - 1) {
                // Último símbolo: adiciona FOLLOW(naoTerminal)
                follow[simbolo]!.addAll(follow[naoTerminal]!);
              } else {
                // Não é último: processa beta (resto da produção)
                var beta = producao.sublist(i + 1);
                var firstBeta = calcularFIRSTString(beta);
                
                // Adiciona FIRST(beta) exceto ε
                follow[simbolo]!.addAll(
                    firstBeta.where((s) => s != 'ε'));
                
                // Se β pode derivar ε, adiciona FOLLOW(naoTerminal)
                if (firstBeta.contains('ε')) {
                  follow[simbolo]!.addAll(follow[naoTerminal]!);
                }
              }
              
              if (follow[simbolo]!.length > antesSize) {
                mudou = true;
              }
            }
          }
        }
      }
    }
  }
  
  // Calcula FIRST de uma string de símbolos
  Set<String> calcularFIRSTString(List<String> simbolos) {
    Set<String> resultado = {};
    bool todosDerivamEpsilon = true;
    
    for (var simbolo in simbolos) {
      if (ehTerminal(simbolo)) {
        resultado.add(simbolo);
        todosDerivamEpsilon = false;
        break;
      } else {
        var firstSimbolo = first[simbolo] ?? {};
        resultado.addAll(firstSimbolo.where((s) => s != 'ε'));
        
        if (!firstSimbolo.contains('ε')) {
          todosDerivamEpsilon = false;
          break;
        }
      }
    }
    
    if (todosDerivamEpsilon) {
      resultado.add('ε');
    }
    
    return resultado;
  }
  
  // Demonstra o cálculo completo
  void demonstrar() {
    print('Calculando conjuntos FIRST...');
    calcularFIRST();
    
    print('\nConjuntos FIRST:');
    first.forEach((naoTerminal, conjunto) {
      print('  FIRST($naoTerminal) = {${conjunto.join(', ')}}');
    });
    
    print('\nCalculando conjuntos FOLLOW...');
    calcularFOLLOW();
    
    print('\nConjuntos FOLLOW:');
    follow.forEach((naoTerminal, conjunto) {
      print('  FOLLOW($naoTerminal) = {${conjunto.join(', ')}}');
    });
  }
}

// Exemplo de uso
void exemploCalculoFIRSTFOLLOW() {
  // Gramática de expressões aritméticas
  var gramatica = {
    'E': [
      ['T', "E'"]
    ],
    "E'": [
      ['+', 'T', "E'"],
      ['ε']
    ],
    'T': [
      ['F', "T'"]
    ],
    "T'": [
      ['*', 'F', "T'"],
      ['ε']
    ],
    'F': [
      ['(', 'E', ')'],
      ['id']
    ]
  };
  
  var calculador = CalculadorFIRSTFOLLOW(gramatica, 'E');
  calculador.demonstrar();
}

C++

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

class CalculadorFIRSTFOLLOW {
private:
    std::map<std::string, std::set<std::string>> first;
    std::map<std::string, std::set<std::string>> follow;
    std::map<std::string, std::vector<std::vector<std::string>>> gramatica;
    std::string simboloInicial;
    
public:
    CalculadorFIRSTFOLLOW(
        const std::map<std::string, std::vector<std::vector<std::string>>>& gram,
        const std::string& inicial)
        : gramatica(gram), simboloInicial(inicial) {}
    
    // Verifica se um símbolo é terminal
    bool ehTerminal(const std::string& simbolo) const {
        return gramatica.find(simbolo) == gramatica.end() && simbolo != "ε";
    }
    
    // Calcula FIRST para todos os não-terminais
    void calcularFIRST() {
        // Inicializa conjuntos vazios
        for (const auto& par : gramatica) {
            first[par.first] = std::set<std::string>();
        }
        
        bool mudou = true;
        while (mudou) {
            mudou = false;
            
            for (const auto& par : gramatica) {
                const auto& naoTerminal = par.first;
                
                for (const auto& producao : par.second) {
                    size_t antesSize = first[naoTerminal].size();
                    
                    if (producao.empty() || producao[0] == "ε") {
                        // Produção vazia
                        first[naoTerminal].insert("ε");
                    } else {
                        // Processa cada símbolo da produção
                        bool todosDerivamEpsilon = true;
                        
                        for (const auto& simbolo : producao) {
                            if (ehTerminal(simbolo)) {
                                // Terminal: adiciona e para
                                first[naoTerminal].insert(simbolo);
                                todosDerivamEpsilon = false;
                                break;
                            } else {
                                // Não-terminal: adiciona FIRST(simbolo) exceto ε
                                const auto& firstSimbolo = first[simbolo];
                                for (const auto& s : firstSimbolo) {
                                    if (s != "ε") {
                                        first[naoTerminal].insert(s);
                                    }
                                }
                                
                                // Se simbolo não deriva ε, para
                                if (firstSimbolo.find("ε") == firstSimbolo.end()) {
                                    todosDerivamEpsilon = false;
                                    break;
                                }
                            }
                        }
                        
                        // Se todos derivam ε, adiciona ε ao resultado
                        if (todosDerivamEpsilon) {
                            first[naoTerminal].insert("ε");
                        }
                    }
                    
                    if (first[naoTerminal].size() > antesSize) {
                        mudou = true;
                    }
                }
            }
        }
    }
    
    // Calcula FOLLOW para todos os não-terminais
    void calcularFOLLOW() {
        // Inicializa conjuntos vazios
        for (const auto& par : gramatica) {
            follow[par.first] = std::set<std::string>();
        }
        
        // Símbolo inicial tem $ no FOLLOW
        follow[simboloInicial].insert("$");
        
        bool mudou = true;
        while (mudou) {
            mudou = false;
            
            for (const auto& par : gramatica) {
                const auto& naoTerminal = par.first;
                
                for (const auto& producao : par.second) {
                    // Processa cada símbolo da produção
                    for (size_t i = 0; i < producao.size(); i++) {
                        const auto& simbolo = producao[i];
                        
                        if (!ehTerminal(simbolo) && simbolo != "ε") {
                            size_t antesSize = follow[simbolo].size();
                            
                            if (i == producao.size() - 1) {
                                // Último símbolo: adiciona FOLLOW(naoTerminal)
                                for (const auto& s : follow[naoTerminal]) {
                                    follow[simbolo].insert(s);
                                }
                            } else {
                                // Não é último: processa beta (resto da produção)
                                std::vector<std::string> beta(
                                    producao.begin() + i + 1,
                                    producao.end()
                                );
                                auto firstBeta = calcularFIRSTString(beta);
                                
                                // Adiciona FIRST(beta) exceto ε
                                for (const auto& s : firstBeta) {
                                    if (s != "ε") {
                                        follow[simbolo].insert(s);
                                    }
                                }
                                
                                // Se β pode derivar ε, adiciona FOLLOW(naoTerminal)
                                if (firstBeta.find("ε") != firstBeta.end()) {
                                    for (const auto& s : follow[naoTerminal]) {
                                        follow[simbolo].insert(s);
                                    }
                                }
                            }
                            
                            if (follow[simbolo].size() > antesSize) {
                                mudou = true;
                            }
                        }
                    }
                }
            }
        }
    }
    
    // Calcula FIRST de uma string de símbolos
    std::set<std::string> calcularFIRSTString(
        const std::vector<std::string>& simbolos) {
        
        std::set<std::string> resultado;
        bool todosDerivamEpsilon = true;
        
        for (const auto& simbolo : simbolos) {
            if (ehTerminal(simbolo)) {
                resultado.insert(simbolo);
                todosDerivamEpsilon = false;
                break;
            } else {
                const auto& firstSimbolo = first[simbolo];
                for (const auto& s : firstSimbolo) {
                    if (s != "ε") {
                        resultado.insert(s);
                    }
                }
                
                if (firstSimbolo.find("ε") == firstSimbolo.end()) {
                    todosDerivamEpsilon = false;
                    break;
                }
            }
        }
        
        if (todosDerivamEpsilon) {
            resultado.insert("ε");
        }
        
        return resultado;
    }
    
    // Demonstra o cálculo completo
    void demonstrar() {
        std::cout << "Calculando conjuntos FIRST...\n";
        calcularFIRST();
        
        std::cout << "\nConjuntos FIRST:\n";
        for (const auto& par : first) {
            std::cout << "  FIRST(" << par.first << ") = {";
            bool primeiro = true;
            for (const auto& elem : par.second) {
                if (!primeiro) std::cout << ", ";
                std::cout << elem;
                primeiro = false;
            }
            std::cout << "}\n";
        }
        
        std::cout << "\nCalculando conjuntos FOLLOW...\n";
        calcularFOLLOW();
        
        std::cout << "\nConjuntos FOLLOW:\n";
        for (const auto& par : follow) {
            std::cout << "  FOLLOW(" << par.first << ") = {";
            bool primeiro = true;
            for (const auto& elem : par.second) {
                if (!primeiro) std::cout << ", ";
                std::cout << elem;
                primeiro = false;
            }
            std::cout << "}\n";
        }
    }
};

Exemplo Completo de Cálculo

Vamos calcular FIRST e FOLLOW para a gramática de expressões que transformamos anteriormente:

E \rightarrow T E' E' \rightarrow + T E' \mid \varepsilon T \rightarrow F T' T' \rightarrow * F T' \mid \varepsilon F \rightarrow (E) \mid \text{id}

Conjuntos FIRST:

• \text{FIRST}(E) = \text{FIRST}(T) = \text{FIRST}(F) = \{(, \text{id}\}
• \text{FIRST}(E') = \{+, \varepsilon\}
• \text{FIRST}(T') = \{*, \varepsilon\}

Conjuntos FOLLOW:

• \text{FOLLOW}(E) = \{), \$\}
• \text{FOLLOW}(E') = \{), \$\}
• \text{FOLLOW}(T) = \{+, ), \$\}
• \text{FOLLOW}(T') = \{+, ), \$\}
• \text{FOLLOW}(F) = \{*, +, ), \$\}

Estes conjuntos são fundamentais para construir tabelas de parsing preditivo, como veremos em breve!

Calcular os conjuntos FIRST e FOLLOW para os não-terminais da gramática:

Statement → Designator = Expr ;
          | if ( Expr ) Statement
          | while ( Expr ) Statement
          | { StatementList }
StatementList → "{" {Statement} "}"
Designator → Ident { "." Ident | "[" Expr "]" } .

Expr → Term Expr'
Expr' → + Term Expr' | - Term Expr' | ε

Term → Factor Term'
Term' → * Factor Term' | / Factor Term' | ε

Factor → Designator | number | ( Expr )

---

🔍 Etapas para calcular FIRST

Regras básicas:

• Se a produção começa com um terminal, ele entra no FIRST.
• Se começa com um não-terminal, adicionamos o FIRST desse não-terminal (exceto ε).
• Se todas as alternativas podem derivar ε, então ε também entra no FIRST.

Cálculo:

FIRST(Factor)

Produções:

• Designator → começa com id
• number → terminal
• ( Expr ) → começa com (

Resultado:

FIRST(Factor) = { id, number, ( }

---

FIRST(Term)

Produção:

Term → Factor Term'  

→ Começa com Factor

Resultado:

FIRST(Term) = FIRST(Factor) = { id, number, ( }

---

FIRST(Expr)

Produção:

Expr → Term Expr'  

→ Começa com Term

Resultado:

FIRST(Expr) = FIRST(Term) = { id, number, ( }

---

FIRST(Expr’)

Produções:

+ Term Expr' → começa com +
- Term Expr' → começa com -
ε → vazio

Resultado:

FIRST(Expr') = { +, -, ε }

---

FIRST(Statement)

Produções:

Designator = Expr ; → começa com id
if ( Expr ) Statement → começa com if
while ( Expr ) Statement → começa com while
{ StatementList } → começa com {

Resultado:

FIRST(Statement) = { id, if, while, { }

---

Etapas para calcular FOLLOW

Regras básicas

• Coloque $ (fim de entrada) no FOLLOW do símbolo inicial.
• Se um não-terminal A aparece antes de B em uma produção, então tudo que está em FIRST(B) (exceto ε) vai para FOLLOW(A).
• Se B pode derivar ε, então FOLLOW(B) também vai para FOLLOW(A).

Cálculo:

FOLLOW(Expr)

Aparece em:
if ( Expr ) Statement → seguido por )
while ( Expr ) Statement → seguido por )
( Expr ) → seguido por )
Designator = Expr ; → seguido por ;

Resultado:

FOLLOW(Expr) = { ), ; }

---

FOLLOW(Expr’)

Aparece em:

Expr → Term Expr'  
→ herda FOLLOW(Expr)

Resultado:

FOLLOW(Expr') = FOLLOW(Expr) = { ), ; }

---

FOLLOW(Term)

Aparece em:

Expr → Term Expr'  
→ FIRST(Expr') = { +, -, ε }  
→ Adiciona { +, - }  
→ Como Expr' pode ser ε, adiciona FOLLOW(Expr) também

Resultado:

FOLLOW(Term) = { +, -, ), ; }

---

FOLLOW(Term’)

Aparece em:

Term → Factor Term'  
→ herda FOLLOW(Term)

Resultado:

FOLLOW(Term') = { +, -, ), ; }

---

FOLLOW(Factor)

Aparece em:

Term → Factor Term'  
→ FIRST(Term') = { *, /, ε }  
→ Adiciona { *, / }  
→ Como Term' pode ser ε, adiciona FOLLOW(Term)

Resultado:

FOLLOW(Factor) = { *, /, +, -, ), ; }

---

FOLLOW(Statement)

Aparece em:

StatementList → "{" Statement Statement ... Statement "}" | ε  
→ seguido por outro Statement ou fim de bloco }  
→ também pode ser último comando → adiciona $

Resultado:

FOLLOW(Statement) = { "}", $ }

---

✅ Resumo final

Não-Terminal	FIRST	FOLLOW
Statement	{ id, if, while, { }	{ }, $ }
Expr	{ id, number, ( }	{ ), ; }
Expr’	{ +, -, ε }	{ ), ; }
Term	{ id, number, ( }	{ +, -, ), ; }
Term’	{ *, /, ε }	{ +, -, ), ; }
Factor	{ id, number, ( }	{ *, /, +, -, ), ; }