📊 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:
Se X é terminal: \text{FIRST}(X) = \{X\}
Se X é não-terminal com produção X \rightarrow \varepsilon: adicione \varepsilon a \text{FIRST}(X)
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:
Coloque \$ em \text{FOLLOW}(S) onde S é o símbolo inicial
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)
Se há uma produção A \rightarrow \alpha B:
- Adicione \text{FOLLOW}(A) a \text{FOLLOW}(B)
Repita até que nenhum conjunto FOLLOW mude
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();
}#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!