🔄 Derivações e Árvores Sintáticas
O Processo de Derivação
Uma derivação é uma sequência de substituições que começa com o símbolo inicial e termina em uma string de terminais. Cada passo aplica uma produção, substituindo um não-terminal pela parte direita de uma de suas produções.
🌿 Tipos de Derivação
Derivação Mais à Esquerda: Em cada passo, sempre substituímos o não-terminal mais à esquerda. Esta abordagem corresponde naturalmente ao parsing descendente, onde o parser explora a árvore da raiz para as folhas, da esquerda para a direita.
Derivação Mais à Direita: Em cada passo, sempre substituímos o não-terminal mais à direita. Esta abordagem corresponde ao parsing ascendente, onde o parser constrói a árvore das folhas para a raiz, processando a entrada da esquerda para a direita mas fazendo reduções da direita para a esquerda.
Ambas as estratégias produzem a mesma árvore de derivação final, mas a ordem de construção difere. Esta equivalência é fundamental: significa que a estrutura sintática é independente da estratégia de parsing escolhida.
Árvores de Derivação
Uma árvore de derivação (ou árvore sintática) é uma representação gráfica de como uma sentença é derivada da gramática. A raiz é o símbolo inicial, folhas são terminais, e nós internos são não-terminais. Cada nó interno representa a aplicação de uma produção.
// Classe para representar nós da árvore de derivação
class NoArvore {
String simbolo;
List<NoArvore> filhos;
bool ehTerminal;
NoArvore(this.simbolo, {this.ehTerminal = false, List<NoArvore>? filhos})
: filhos = filhos ?? [];
// Adiciona um filho ao nó
void adicionarFilho(NoArvore filho) {
filhos.add(filho);
}
// Gera representação textual da árvore
String paraString({int nivel = 0}) {
String indent = ' ' * nivel;
String resultado = '$indent$simbolo\n';
for (var filho in filhos) {
resultado += filho.paraString(nivel: nivel + 1);
}
return resultado;
}
// Extrai a sentença derivada (concatenação das folhas)
String extrairSentenca() {
if (ehTerminal) {
return simbolo;
}
return filhos.map((filho) => filho.extrairSentenca()).join(' ');
}
}
// Construtor de árvores de derivação
class ConstrutorArvore {
// Constrói árvore para "id + id * id"
static NoArvore construirExemplo() {
// Raiz: E
var raiz = NoArvore('E');
// E → E + T
var e1 = NoArvore('E');
var mais = NoArvore('+', ehTerminal: true);
var t1 = NoArvore('T');
raiz.adicionarFilho(e1);
raiz.adicionarFilho(mais);
raiz.adicionarFilho(t1);
// E → T → F → id
var t2 = NoArvore('T');
e1.adicionarFilho(t2);
var f1 = NoArvore('F');
t2.adicionarFilho(f1);
var id1 = NoArvore('id', ehTerminal: true);
f1.adicionarFilho(id1);
// T → T * F
var t3 = NoArvore('T');
var vezes = NoArvore('*', ehTerminal: true);
var f2 = NoArvore('F');
t1.adicionarFilho(t3);
t1.adicionarFilho(vezes);
t1.adicionarFilho(f2);
// T → F → id
var f3 = NoArvore('F');
t3.adicionarFilho(f3);
var id2 = NoArvore('id', ehTerminal: true);
f3.adicionarFilho(id2);
// F → id
var id3 = NoArvore('id', ehTerminal: true);
f2.adicionarFilho(id3);
return raiz;
}
// Demonstra a construção passo a passo
static void demonstrarConstrucao() {
var arvore = construirExemplo();
print('Árvore de derivação para "id + id * id":');
print(arvore.paraString());
print('\nSentença derivada: ${arvore.extrairSentenca()}');
print('\nObservações importantes:');
print('1. A multiplicação está mais profunda na árvore que a adição');
print('2. Isso garante que * tem precedência sobre +');
print('3. A estrutura reflete a semântica desejada: id + (id * id)');
}
}#include <string>
#include <vector>
#include <memory>
#include <iostream>
// Classe para representar nós da árvore de derivação
class NoArvore {
private:
std::string simbolo;
std::vector<std::shared_ptr<NoArvore>> filhos;
bool ehTerminal;
public:
NoArvore(const std::string& sim, bool term = false)
: simbolo(sim), ehTerminal(term) {}
// Adiciona um filho ao nó
void adicionarFilho(std::shared_ptr<NoArvore> filho) {
filhos.push_back(filho);
}
// Gera representação textual da árvore
std::string paraString(int nivel = 0) const {
std::string indent(nivel * 2, ' ');
std::string resultado = indent + simbolo + "\n";
for (const auto& filho : filhos) {
resultado += filho->paraString(nivel + 1);
}
return resultado;
}
// Extrai a sentença derivada (concatenação das folhas)
std::string extrairSentenca() const {
if (ehTerminal) {
return simbolo;
}
std::string sentenca;
for (size_t i = 0; i < filhos.size(); i++) {
sentenca += filhos[i]->extrairSentenca();
if (i < filhos.size() - 1) sentenca += " ";
}
return sentenca;
}
};
// Construtor de árvores de derivação
class ConstrutorArvore {
public:
// Constrói árvore para "id + id * id"
static std::shared_ptr<NoArvore> construirExemplo() {
// Raiz: E
auto raiz = std::make_shared<NoArvore>("E");
// E → E + T
auto e1 = std::make_shared<NoArvore>("E");
auto mais = std::make_shared<NoArvore>("+", true);
auto t1 = std::make_shared<NoArvore>("T");
raiz->adicionarFilho(e1);
raiz->adicionarFilho(mais);
raiz->adicionarFilho(t1);
// E → T → F → id
auto t2 = std::make_shared<NoArvore>("T");
e1->adicionarFilho(t2);
auto f1 = std::make_shared<NoArvore>("F");
t2->adicionarFilho(f1);
auto id1 = std::make_shared<NoArvore>("id", true);
f1->adicionarFilho(id1);
// T → T * F
auto t3 = std::make_shared<NoArvore>("T");
auto vezes = std::make_shared<NoArvore>("*", true);
auto f2 = std::make_shared<NoArvore>("F");
t1->adicionarFilho(t3);
t1->adicionarFilho(vezes);
t1->adicionarFilho(f2);
// T → F → id
auto f3 = std::make_shared<NoArvore>("F");
t3->adicionarFilho(f3);
auto id2 = std::make_shared<NoArvore>("id", true);
f3->adicionarFilho(id2);
// F → id
auto id3 = std::make_shared<NoArvore>("id", true);
f2->adicionarFilho(id3);
return raiz;
}
// Demonstra a construção passo a passo
static void demonstrarConstrucao() {
auto arvore = construirExemplo();
std::cout << "Árvore de derivação para \"id + id * id\":\n";
std::cout << arvore->paraString();
std::cout << "\nSentença derivada: " << arvore->extrairSentenca() << "\n";
std::cout << "\nObservações importantes:\n";
std::cout << "1. A multiplicação está mais profunda na árvore que a adição\n";
std::cout << "2. Isso garante que * tem precedência sobre +\n";
std::cout << "3. A estrutura reflete a semântica desejada: id + (id * id)\n";
}
};As árvores de derivação são fundamentais porque capturam a estrutura sintática da sentença de forma independente da ordem específica de derivação. Duas derivações diferentes (mais à esquerda versus mais à direita) produzem a mesma árvore se representam a mesma estrutura sintática. Esta invariância é essencial para a análise semântica subsequente.