graph TD
A[📝 Código Fonte] --> B[🔬 Análise Léxica]
B --> C[🌳 Análise Sintática]
C --> D[🧠 Análise Semântica]
D --> E[⚡ Geração de Código Intermediário]
E --> F[🔧 Otimização]
F --> G[🎯 Geração de Código Final]
G --> H[💻 Código Executável]
I[📋 Tabela de Símbolos] -.-> C
I -.-> D
I -.-> E
I -.-> F
J[❌ Tratamento de Erros] -.-> B
J -.-> C
J -.-> D
style B fill:#e8f5e8
style I fill:#fff3e0
style J fill:#ffebee
Análise Léxica em Compiladores 🔬
🚀 Da Teoria à Prática: Construindo Analisadores Reais
Chegou o momento mais emocionante da nossa jornada! Depois de mergulharmos nas profundezas matemáticas dos autômatos finitos e linguagens regulares, agora você verá como toda essa teoria elegante se materializa na primeira fase de qualquer compilador real: a análise léxica. Esta não é apenas mais uma aplicação - é onde matemática pura se transforma em software que funciona no mundo real.
Prepare-se para uma experiência transformadora onde conceitos abstratos ganharão vida através de código que você mesmo criará. Ao final desta semana, você terá nas mãos um analisador léxico funcional capaz de processar linguagens de programação reais!
🎯 O Que Você Descobrirá Nesta Jornada
Esta semana representa um marco fundamental na sua formação como cientista da computação. Você não apenas aprenderá sobre análise léxica - você dominará a arte de transformar especificações matemáticas em implementações eficientes e robustas.
🔍 Visão Geral da Transformação Conceitual
Dos Autômatos Finitos aos Analisadores Léxicos: Você descobrirá como os AFDs e AFNs que estudou se tornam as máquinas de estado que reconhecem tokens em código fonte real. Esta conexão direta entre teoria e prática será uma das experiências mais satisfatórias do curso.
De Linguagens Regulares para Tokens: As expressões regulares que você dominou agora definirão precisamente cada categoria de token na sua linguagem - identificadores, números, operadores, palavras-chave. Você verá como padrões abstratos se tornam reconhecedores concretos.
Da Matemática para Engenharia: Aprenderá a equilibrar correção teórica com eficiência prática, descobrindo como implementações reais otimizam algoritmos sem sacrificar correção matemática.
Ao longo desta semana, você construirá uma ponte sólida entre o mundo acadêmico dos fundamentos teóricos e o mundo profissional da engenharia de compiladores. Esta habilidade de navegar fluentemente entre teoria e prática é o que distingue cientistas da computação de meros programadores.
🏗️ A Arquitetura de um Compilador Moderno
Para compreender completamente o papel da análise léxica, precisamos primeiro entender onde ela se encaixa na arquitetura geral de um compilador. Um compilador moderno é uma obra de engenharia sofisticada, composta por múltiplas fases coordenadas que transformam código fonte em código executável.
🏢 As Fases de um Compilador
Observe como a análise léxica ocupa uma posição privilegiada - é o primeiro contato do compilador com o mundo exterior, a interface entre texto sem estrutura e estruturas de dados organizadas que as fases subsequentes podem processar eficientemente.
A análise léxica serve como o alicerce de todo o processo de compilação. Qualquer erro ou ineficiência nesta fase se amplifica ao longo de todo o pipeline. Por isso, compreender profundamente esta fase é absolutamente essencial para qualquer desenvolvedor de compiladores.
A transformação fundamental que ocorre aqui é a conversão de uma sequência linear de caracteres em uma sequência estruturada de tokens. Esta aparente simplicidade esconde complexidades fascinantes que você dominará ao longo desta semana.
🗂️ Implementação Prática do Analisador Léxico Baseado em AFD
Agora que o AFD foi completamente especificado matematicamente, inicio a fase de implementação concreta. Esta é a materialização final de todo o trabalho teórico, onde estruturas de dados e algoritmos transformam o modelo matemático em software funcional.
Representação de Estados-Conjunto
Uma decisão importante de implementação é como representar estados-conjunto de forma eficiente. Uma abordagem comum e prática é usar strings ordenadas para representar conjuntos de estados. Por exemplo, o conjunto {q0, q2, q1} seria representado pela string “{q0,q1,q2}” (note a ordem alfabética). Esta representação tem várias vantagens: é facilmente serializada para debugging e logging, a ordenação garante que o mesmo conjunto sempre tem a mesma representação (facilitando comparações de igualdade), e pode ser usada diretamente como chave em tabelas hash.
#include <string>
#include <set>
#include <algorithm>
// Usa set para ordenação automática, string com reserve para eficiência
inline std::string conjunto_para_string(const std::set<std::string>& conjunto) {
if (conjunto.empty()) return "{}";
std::string resultado;
resultado.reserve(conjunto.size() * 8); // Estimativa de tamanho
resultado.push_back('{');
auto it = conjunto.begin();
resultado.append(*it);
for (++it; it != conjunto.end(); ++it) {
resultado.push_back(',');
resultado.append(*it);
}
resultado.push_back('}');
return resultado;
}
// Versão alternativa com unordered_set (mais eficiente para criação)
inline std::string conjunto_para_string_fast(std::unordered_set<std::string> conjunto) {
if (conjunto.empty()) return "{}";
std::vector<std::string> vec(conjunto.begin(), conjunto.end());
std::sort(vec.begin(), vec.end()); // Ordena apenas quando necessário
std::string resultado;
resultado.reserve(vec.size() * 8);
resultado.push_back('{');
resultado.append(vec[0]);
for (size_t i = 1; i < vec.size(); ++i) {
resultado.push_back(',');
resultado.append(vec[i]);
}
resultado.push_back('}');
return resultado;
}#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_STRING_SIZE 512
// Função de comparação para qsort
static int comparar_strings(const void* a, const void* b) {
return strcmp(*(const char**)a, *(const char**)b);
}
// Converte conjunto para string canônica (usa buffer estático por eficiência)
char* conjunto_para_string(const conjunto_estados_t* conjunto) {
static char buffer[MAX_STRING_SIZE];
if (conjunto->count == 0) {
strcpy(buffer, "{}");
return buffer;
}
// Cria array de ponteiros para ordenação
char* ptrs[MAX_ESTADOS];
for (int i = 0; i < conjunto->count; i++) {
ptrs[i] = (char*)conjunto->estados[i];
}
// Ordena os ponteiros
qsort(ptrs, conjunto->count, sizeof(char*), comparar_strings);
// Constrói a string resultante
char* pos = buffer;
*pos++ = '{';
strcpy(pos, ptrs[0]);
pos += strlen(ptrs[0]);
for (int i = 1; i < conjunto->count; i++) {
*pos++ = ',';
strcpy(pos, ptrs[i]);
pos += strlen(ptrs[i]);
}
*pos++ = '}';
*pos = '\0';
return buffer;
}
// Versão com alocação dinâmica (mais segura para strings longas)
char* conjunto_para_string_alloc(const conjunto_estados_t* conjunto) {
if (conjunto->count == 0) {
char* resultado = malloc(3);
strcpy(resultado, "{}");
return resultado;
}
char* ptrs[MAX_ESTADOS];
for (int i = 0; i < conjunto->count; i++) {
ptrs[i] = (char*)conjunto->estados[i];
}
qsort(ptrs, conjunto->count, sizeof(char*), comparar_strings);
size_t tamanho = 3; // "{" + "}" + '\0'
for (int i = 0; i < conjunto->count; i++) {
tamanho += strlen(ptrs[i]) + (i > 0 ? 1 : 0);
}
char* resultado = malloc(tamanho);
char* pos = resultado;
*pos++ = '{';
strcpy(pos, ptrs[0]);
pos += strlen(ptrs[0]);
for (int i = 1; i < conjunto->count; i++) {
*pos++ = ',';
strcpy(pos, ptrs[i]);
pos += strlen(ptrs[i]);
}
*pos++ = '}';
*pos = '\0';
return resultado;
}Estruturas de Dados Fundamentais
A escolha das estruturas de dados determina não apenas a eficiência, mas também a clareza e manutenibilidade da implementação. Para o AFD resultante, desenvolvi uma hierarquia cuidadosamente planejada:
Representação de Estados:
Cada estado do AFD é representado por uma classe que encapsula:
- Identificador único (derivado do conjunto de estados do AFN que representa)
- Flag indicando se é estado final
- Tipo de token reconhecido (se for estado final)
- Metadados adicionais para debugging e rastreamento
Tabela de Transições:
A função de transição \delta_{AFD} é implementada através de um mapa bidimensional otimizado:
- Primeira dimensão: estado atual
- Segunda dimensão: símbolo de entrada
- Valor: próximo estado (ou null se transição indefinida)
Otimização crítica: Em vez de alocar uma matriz completa |Q_{AFD}| \times |\Sigma_{AFD}| (que seria extremamente esparsa), use uma estrutura de mapa hash aninhado que armazena apenas transições definidas explicitamente.
/// Classe que representa um Autômato Finito Determinístico (AFD).
///
/// Esta implementação mantém todos os componentes de um AFD:
/// - Conjunto de estados
/// - Alfabeto
/// - Função de transição
/// - Estado inicial
/// - Conjunto de estados finais
class AFD {
// Conjunto de todos os estados do AFD
final Set<String> estados = {};
// Alfabeto (conjunto de símbolos) do AFD
final Set<String> alfabeto = {};
// Função de transição: mapeia (estado, símbolo) -> estado destino
final Map<String, String> transicoes = {};
// Estado inicial do AFD
String? estadoInicial;
// Conjunto de estados finais (de aceitação)
final Set<String> estadosFinais = {};
/// Adiciona um estado ao conjunto de estados do AFD
void adicionarEstado(String estado) {
estados.add(estado);
}
/// Adiciona uma transição ao AFD
///
/// [origem] - Estado de origem
/// [simbolo] - Símbolo que causa a transição
/// [destino] - Estado de destino
void adicionarTransicao(String origem, String simbolo, String destino) {
final chave = '$origem,$simbolo';
transicoes[chave] = destino;
}
/// Verifica se um estado é final (de aceitação)
bool ehFinal(String estado) {
return estadosFinais.contains(estado);
}
/// Processa uma string e determina se ela é aceita pelo AFD
///
/// [entrada] - String a ser processada
///
/// Retorna true se a string é aceita, false caso contrário
bool processarString(String entrada) {
// Verifica se há estado inicial definido
if (estadoInicial == null) {
return false;
}
String estadoAtual = estadoInicial!;
// Processa cada símbolo da entrada
for (int i = 0; i < entrada.length; i++) {
final simbolo = entrada[i];
final chave = '$estadoAtual,$simbolo';
// Verifica se há transição definida
if (!transicoes.containsKey(chave)) {
return false; // Transição não definida, rejeita
}
// Faz a transição
estadoAtual = transicoes[chave]!;
}
// Aceita se o estado final é de aceitação
return ehFinal(estadoAtual);
}
}#include <unordered_set>
#include <unordered_map>
#include <string>
#include <string_view>
class AFD {
private:
std::unordered_set<std::string> estados;
std::unordered_set<char> alfabeto;
std::unordered_map<std::string, std::string> transicoes;
std::string estado_inicial;
std::unordered_set<std::string> estados_finais;
// Cache de strings de transição para evitar alocações
mutable std::string chave_cache;
public:
AFD() {
chave_cache.reserve(64);
estados.reserve(128);
transicoes.reserve(512);
}
// Move semantics para eficiência
inline void adicionar_estado(std::string&& estado) {
estados.insert(std::move(estado));
}
inline void adicionar_estado(const std::string& estado) {
estados.insert(estado);
}
// Inline para eliminar overhead de função
inline void adicionar_transicao(
const std::string& origem,
char simbolo,
const std::string& destino
) {
std::string chave = origem;
chave.push_back(',');
chave.push_back(simbolo);
transicoes[std::move(chave)] = destino;
}
inline bool eh_final(const std::string& estado) const {
return estados_finais.find(estado) != estados_finais.end();
}
inline void set_estado_inicial(std::string&& estado) {
estado_inicial = std::move(estado);
}
inline void adicionar_estado_final(std::string&& estado) {
estados_finais.insert(std::move(estado));
}
// Processa string com otimizações máximas
bool processar_string(std::string_view entrada) const {
if (estado_inicial.empty()) return false;
std::string estado_atual = estado_inicial;
chave_cache.clear();
for (char simbolo : entrada) {
chave_cache = estado_atual;
chave_cache.push_back(',');
chave_cache.push_back(simbolo);
auto it = transicoes.find(chave_cache);
if (it == transicoes.end()) return false;
estado_atual = it->second;
chave_cache.clear();
}
return eh_final(estado_atual);
}
// Versão ainda mais otimizada usando referência
bool processar_string_fast(const char* entrada, size_t len) const {
if (estado_inicial.empty()) return false;
std::string estado_atual = estado_inicial;
for (size_t i = 0; i < len; ++i) {
chave_cache = estado_atual;
chave_cache.push_back(',');
chave_cache.push_back(entrada[i]);
auto it = transicoes.find(chave_cache);
if (it == transicoes.end()) return false;
estado_atual = it->second;
chave_cache.clear();
}
return estados_finais.find(estado_atual) != estados_finais.end();
}
};#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#define MAX_AFD_ESTADOS 256
#define MAX_AFD_TRANSICOES 2048
#define MAX_ALFABETO 128
typedef struct {
char origem[32];
char simbolo;
char destino[32];
} transicao_afd_t;
typedef struct {
char estados[MAX_AFD_ESTADOS][32];
int num_estados;
char alfabeto[MAX_ALFABETO];
int tamanho_alfabeto;
transicao_afd_t transicoes[MAX_AFD_TRANSICOES];
int num_transicoes;
char estado_inicial[32];
char estados_finais[MAX_AFD_ESTADOS][32];
int num_estados_finais;
} afd_t;
// Inicializa AFD
static inline void afd_init(afd_t* afd) {
memset(afd, 0, sizeof(afd_t));
}
// Adiciona estado (verifica duplicatas)
static inline void afd_adicionar_estado(afd_t* afd, const char* estado) {
for (int i = 0; i < afd->num_estados; i++) {
if (strcmp(afd->estados[i], estado) == 0) return;
}
if (afd->num_estados < MAX_AFD_ESTADOS) {
strcpy(afd->estados[afd->num_estados++], estado);
}
}
// Adiciona transição (otimizado para busca rápida)
static inline void afd_adicionar_transicao(
afd_t* afd,
const char* origem,
char simbolo,
const char* destino
) {
if (afd->num_transicoes < MAX_AFD_TRANSICOES) {
transicao_afd_t* t = &afd->transicoes[afd->num_transicoes++];
strcpy(t->origem, origem);
t->simbolo = simbolo;
strcpy(t->destino, destino);
}
}
// Busca transição (busca linear otimizada com likely/unlikely)
static inline const char* afd_buscar_transicao(
const afd_t* afd,
const char* origem,
char simbolo
) {
// Busca reversa é mais rápida para transições recentes
for (int i = afd->num_transicoes - 1; i >= 0; i--) {
const transicao_afd_t* t = &afd->transicoes[i];
if (t->simbolo == simbolo && strcmp(t->origem, origem) == 0) {
return t->destino;
}
}
return NULL;
}
// Verifica se estado é final
static inline bool afd_eh_final(const afd_t* afd, const char* estado) {
for (int i = 0; i < afd->num_estados_finais; i++) {
if (strcmp(afd->estados_finais[i], estado) == 0) return true;
}
return false;
}
// Adiciona estado final
static inline void afd_adicionar_estado_final(afd_t* afd, const char* estado) {
if (afd->num_estados_finais < MAX_AFD_ESTADOS) {
strcpy(afd->estados_finais[afd->num_estados_finais++], estado);
}
}
// Processa string (máxima performance)
bool afd_processar_string(const afd_t* afd, const char* entrada, size_t len) {
if (afd->estado_inicial[0] == '\0') return false;
char estado_atual[32];
strcpy(estado_atual, afd->estado_inicial);
for (size_t i = 0; i < len; i++) {
const char* proximo = afd_buscar_transicao(afd, estado_atual, entrada[i]);
if (proximo == NULL) return false;
strcpy(estado_atual, proximo);
}
return afd_eh_final(afd, estado_atual);
}
// Versão com hash table para O(1) lookup (mais memória, mais velocidade)
typedef struct {
char chave[64]; // "origem,simbolo"
char destino[32];
} entrada_hash_t;
typedef struct {
entrada_hash_t tabela[MAX_AFD_TRANSICOES * 2]; // Load factor ~0.5
int capacidade;
} hash_transicoes_t;
static inline unsigned int hash_string(const char* str) {
unsigned int hash = 5381;
int c;
while ((c = *str++)) {
hash = ((hash << 5) + hash) + c;
}
return hash;
}
// Versão ultra-otimizada com hash table
bool afd_processar_string_hash(
const hash_transicoes_t* hash,
const char* estado_inicial,
const char* entrada,
size_t len,
const afd_t* afd
) {
char estado_atual[32];
strcpy(estado_atual, estado_inicial);
char chave[64];
for (size_t i = 0; i < len; i++) {
sprintf(chave, "%s,%c", estado_atual, entrada[i]);
unsigned int idx = hash_string(chave) % hash->capacidade;
// Linear probing
while (hash->tabela[idx].chave[0] != '\0') {
if (strcmp(hash->tabela[idx].chave, chave) == 0) {
strcpy(estado_atual, hash->tabela[idx].destino);
goto proximo_simbolo;
}
idx = (idx + 1) % hash->capacidade;
}
return false; // Não encontrou transição
proximo_simbolo:;
}
return afd_eh_final(afd, estado_atual);
}⚠️ A Importância Prática do Epsilon-Closure
Por que o epsilon-closure é tão fundamental? A razão está na semântica das epsilon-transições. Quando um AFN está em um estado q e não há nenhum símbolo sendo lido naquele momento, ele pode “saltar” instantaneamente e gratuitamente para qualquer estado alcançável via epsilon-transições. Isso significa que estar no estado q é essencialmente equivalente a estar simultaneamente em todos os estados no ε-CLOSURE(q).
Durante a conversão para AFD, precisamos capturar explicitamente estas configurações implícitas. Quando criamos o estado inicial do AFD, não podemos simplesmente usar o estado inicial do AFN. Precisamos usar o epsilon-closure desse estado inicial, porque mesmo antes de ler qualquer símbolo, o AFN pode já estar em múltiplos estados através de epsilon-transições. Similarmente, após cada transição que consome um símbolo, precisamos calcular o epsilon-closure dos estados destino, porque após a transição o AFN pode imediatamente fazer mais epsilon-transições.
Calculando Epsilon-Closure: O Algoritmo
O cálculo do epsilon-closure é essencialmente um problema de busca em grafos. Podemos visualizar as epsilon-transições do AFN como arestas direcionadas em um grafo onde os vértices são os estados. O epsilon-closure de um estado q é então o conjunto de todos os vértices alcançáveis a partir de q seguindo apenas estas arestas epsilon.
Existem duas abordagens clássicas para este problema: busca em profundidade (DFS) e busca em largura (BFS). Ambas funcionam corretamente, mas a busca em profundidade tende a ser ligeiramente mais eficiente na prática devido à localidade de acesso à memória. O algoritmo que apresentaremos usa uma abordagem iterativa baseada em DFS, que evita os problemas de estouro de pilha que poderiam ocorrer com implementações recursivas em grafos com muitas epsilon-transições encadeadas.
A estrutura do algoritmo é elegante e direta. Começamos com um conjunto resultado inicializado com os estados de entrada. Também mantemos uma pilha de trabalho contendo estes mesmos estados. Enquanto a pilha não está vazia, removemos um estado, examinamos todas as suas epsilon-transições, e para cada destino que ainda não foi visitado, adicionamos esse destino tanto ao resultado quanto à pilha de trabalho. A pilha garante que processaremos todos os estados alcançáveis, e o conjunto de visitados garante que cada estado é processado exatamente uma vez, evitando loops infinitos em ciclos de epsilon-transições.
/// Calcula o epsilon-closure de um conjunto de estados.
///
/// Este algoritmo usa busca em profundidade (DFS) para encontrar
/// todos os estados alcançáveis via epsilon-transições.
///
/// [conjuntoEstados] - Conjunto inicial de estados
/// [transicoesEpsilon] - Mapa de estado para lista de destinos via epsilon
///
/// Retorna um Set contendo todos os estados alcançáveis
Set<String> epsilonClosure(
Set<String> conjuntoEstados,
Map<String, List<String>> transicoesEpsilon,
) {
// Inicializa o resultado com os estados de entrada
final resultado = Set<String>.from(conjuntoEstados);
// Pilha para processar estados (DFS)
final pilha = List<String>.from(conjuntoEstados);
// Conjunto para rastrear estados já visitados
final visitados = Set<String>.from(conjuntoEstados);
// Processa enquanto houver estados na pilha
while (pilha.isNotEmpty) {
final estadoAtual = pilha.removeLast();
// Verifica se há epsilon-transições deste estado
if (transicoesEpsilon.containsKey(estadoAtual)) {
// Para cada destino alcançável via epsilon
for (final estadoDestino in transicoesEpsilon[estadoAtual]!) {
// Se ainda não foi visitado, adiciona ao resultado
if (!visitados.contains(estadoDestino)) {
visitados.add(estadoDestino);
resultado.add(estadoDestino);
pilha.add(estadoDestino);
}
}
}
}
return resultado;
}#include <unordered_set>
#include <unordered_map>
#include <vector>
#include <string>
// Usa hash set para O(1) lookup, vector para pilha eficiente
inline std::unordered_set<std::string> epsilon_closure(
const std::unordered_set<std::string>& conjunto_estados,
const std::unordered_map<std::string, std::vector<std::string>>& transicoes_epsilon
) {
std::unordered_set<std::string> resultado(conjunto_estados);
std::vector<std::string> pilha(conjunto_estados.begin(), conjunto_estados.end());
std::unordered_set<std::string> visitados(conjunto_estados);
pilha.reserve(conjunto_estados.size() * 2); // Pre-aloca memória
while (!pilha.empty()) {
std::string estado_atual = std::move(pilha.back());
pilha.pop_back();
auto it = transicoes_epsilon.find(estado_atual);
if (it != transicoes_epsilon.end()) {
const auto& destinos = it->second;
for (const auto& destino : destinos) {
if (visitados.insert(destino).second) { // Insert + check em uma operação
resultado.insert(destino);
pilha.push_back(destino);
}
}
}
}
return resultado;
}#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#define MAX_ESTADOS 256
#define MAX_TRANSICOES 64
typedef struct {
char estados[MAX_ESTADOS][32];
int count;
} conjunto_estados_t;
typedef struct {
char origem[32];
char destinos[MAX_TRANSICOES][32];
int num_destinos;
} transicao_epsilon_t;
// Busca estado no conjunto (busca linear otimizada)
static inline bool contem_estado(const conjunto_estados_t* conjunto, const char* estado) {
for (int i = 0; i < conjunto->count; i++) {
if (strcmp(conjunto->estados[i], estado) == 0) return true;
}
return false;
}
// Adiciona estado ao conjunto se não existir
static inline void adicionar_estado(conjunto_estados_t* conjunto, const char* estado) {
if (!contem_estado(conjunto, estado) && conjunto->count < MAX_ESTADOS) {
strcpy(conjunto->estados[conjunto->count++], estado);
}
}
// Calcula epsilon-closure (otimizado para performance máxima)
conjunto_estados_t epsilon_closure(
const conjunto_estados_t* inicial,
const transicao_epsilon_t* transicoes,
int num_transicoes
) {
conjunto_estados_t resultado = {0};
conjunto_estados_t visitados = {0};
char pilha[MAX_ESTADOS][32];
int topo = 0;
// Inicializa com estados iniciais
memcpy(&resultado, inicial, sizeof(conjunto_estados_t));
memcpy(&visitados, inicial, sizeof(conjunto_estados_t));
for (int i = 0; i < inicial->count; i++) {
strcpy(pilha[topo++], inicial->estados[i]);
}
// DFS iterativo
while (topo > 0) {
char* estado_atual = pilha[--topo];
// Busca transições epsilon deste estado
for (int i = 0; i < num_transicoes; i++) {
if (strcmp(transicoes[i].origem, estado_atual) == 0) {
for (int j = 0; j < transicoes[i].num_destinos; j++) {
const char* destino = transicoes[i].destinos[j];
if (!contem_estado(&visitados, destino)) {
adicionar_estado(&visitados, destino);
adicionar_estado(&resultado, destino);
strcpy(pilha[topo++], destino);
}
}
break;
}
}
}
return resultado;
}Exemplo Passo a Passo de Epsilon-Closure
Para solidificar a compreensão, vamos trabalhar um exemplo concreto e detalhado. Considere um AFN com cinco estados {q0, q1, q2, q3, q4} e as seguintes epsilon-transições: q0 tem epsilon-transições para q1 e q3, e q1 tem uma epsilon-transição para q2. Vamos calcular ε-CLOSURE(q0) executando manualmente o algoritmo passo a passo.
Inicialmente, resultado contém apenas {q0}, a pilha contém [q0], e o conjunto de visitados também contém {q0}. Processamos q0, que está no topo da pilha. Consultamos as epsilon-transições e descobrimos que q0 tem transições para q1 e q3. Como q1 não foi visitado, adicionamos ele ao resultado, ao conjunto de visitados, e à pilha. Resultado agora é {q0, q1}, visitados é {q0, q1}, e a pilha é [q1, q3].
Processamos q1, que agora está no topo da pilha. Descobrimos que q1 tem uma epsilon-transição para q2. Como q2 não foi visitado, adicionamos ele ao resultado, ao conjunto de visitados, e à pilha. Resultado agora é {q0, q1, q2}, visitados é {q0, q1, q2}, e a pilha é [q3, q2]. Processamos q3 da pilha. Não há epsilon-transições saindo de q3, então simplesmente continuamos. Processamos q2. Não há epsilon-transições saindo de q2 também. A pilha agora está vazia, então o algoritmo termina.
O resultado final é ε-CLOSURE(q0) = {q0, q1, q2}. Este conjunto nos diz que se o AFN está no estado q0 e não está lendo nenhum símbolo naquele momento, ele pode efetivamente estar em qualquer um dos estados q0, q1 ou q2 através de epsilon-transições gratuitas.
Algoritmo de Reconhecimento no AFD
O coração do analisador léxico é o algoritmo que usa o AFD para reconhecer tokens. Implemento uma versão otimizada que incorpora as melhores práticas de engenharia de compiladores:
Pseudocódigo de alto nível:
FUNÇÃO reconhecer_token(entrada, posição_inicial):
estado_atual = estado_inicial_AFD
posição = posição_inicial
último_estado_final = null
posição_último_final = -1
buffer = ""
ENQUANTO posição < comprimento(entrada) FAÇA:
caractere = entrada[posição]
# Tenta transição para próximo estado
próximo_estado = δ_AFD(estado_atual, caractere)
SE próximo_estado ≠ null ENTÃO:
# Transição válida encontrada
estado_atual = próximo_estado
buffer += caractere
posição++
# Registra se alcançamos estado final
SE estado_atual ∈ F_AFD ENTÃO:
último_estado_final = estado_atual
posição_último_final = posição
FIM SE
SENÃO:
# Não há transição válida - finalizar reconhecimento
SAIR DO LOOP
FIM SE
FIM ENQUANTO
# Processar resultado
SE último_estado_final ≠ null ENTÃO:
# Retroceder para última posição final
lexema = buffer[0 : posição_último_final - posição_inicial]
tipo_token = obter_tipo(último_estado_final)
# Aplicar classificação hash se necessário
SE tipo_token = REQUER_CLASSIFICACAO_HASH ENTÃO:
tipo_token = consultar_tabela_hash(lexema)
FIM SE
RETORNAR Token(tipo_token, lexema, posição_inicial)
SENÃO:
# Nenhum token válido reconhecido
RETORNAR ErroLéxico(posição_inicial)
FIM SE
FIM FUNÇÃOCaracterísticas desta implementação:
- Princípio do match mais longo: Armazena o último estado final alcançado e retrocede se necessário
- Buffering eficiente: Constrói o lexema incrementalmente durante o processamento
- Rastreamento de posição: Mantém informação precisa sobre localização para mensagens de erro
- Integração com tabela hash: Classificação final de identificadores vs palavras-chave
/// Classe que representa um Autômato Finito Determinístico (AFD).
///
/// Esta implementação mantém todos os componentes de um AFD:
/// - Conjunto de estados
/// - Alfabeto
/// - Função de transição
/// - Estado inicial
/// - Conjunto de estados finais
class AFD {
// Conjunto de todos os estados do AFD
final Set<String> estados = {};
// Alfabeto (conjunto de símbolos) do AFD
final Set<String> alfabeto = {};
// Função de transição: mapeia (estado, símbolo) -> estado destino
final Map<String, String> transicoes = {};
// Estado inicial do AFD
String? estadoInicial;
// Conjunto de estados finais (de aceitação)
final Set<String> estadosFinais = {};
/// Adiciona um estado ao conjunto de estados do AFD
void adicionarEstado(String estado) {
estados.add(estado);
}
/// Adiciona uma transição ao AFD
///
/// [origem] - Estado de origem
/// [simbolo] - Símbolo que causa a transição
/// [destino] - Estado de destino
void adicionarTransicao(String origem, String simbolo, String destino) {
final chave = '$origem,$simbolo';
transicoes[chave] = destino;
}
/// Verifica se um estado é final (de aceitação)
bool ehFinal(String estado) {
return estadosFinais.contains(estado);
}
/// Processa uma string e determina se ela é aceita pelo AFD
///
/// [entrada] - String a ser processada
///
/// Retorna true se a string é aceita, false caso contrário
bool processarString(String entrada) {
// Verifica se há estado inicial definido
if (estadoInicial == null) {
return false;
}
String estadoAtual = estadoInicial!;
// Processa cada símbolo da entrada
for (int i = 0; i < entrada.length; i++) {
final simbolo = entrada[i];
final chave = '$estadoAtual,$simbolo';
// Verifica se há transição definida
if (!transicoes.containsKey(chave)) {
return false; // Transição não definida, rejeita
}
// Faz a transição
estadoAtual = transicoes[chave]!;
}
// Aceita se o estado final é de aceitação
return ehFinal(estadoAtual);
}
}#include <unordered_set>
#include <unordered_map>
#include <string>
#include <string_view>
class AFD {
private:
std::unordered_set<std::string> estados;
std::unordered_set<char> alfabeto;
std::unordered_map<std::string, std::string> transicoes;
std::string estado_inicial;
std::unordered_set<std::string> estados_finais;
// Cache de strings de transição para evitar alocações
mutable std::string chave_cache;
public:
AFD() {
chave_cache.reserve(64);
estados.reserve(128);
transicoes.reserve(512);
}
// Move semantics para eficiência
inline void adicionar_estado(std::string&& estado) {
estados.insert(std::move(estado));
}
inline void adicionar_estado(const std::string& estado) {
estados.insert(estado);
}
// Inline para eliminar overhead de função
inline void adicionar_transicao(
const std::string& origem,
char simbolo,
const std::string& destino
) {
std::string chave = origem;
chave.push_back(',');
chave.push_back(simbolo);
transicoes[std::move(chave)] = destino;
}
inline bool eh_final(const std::string& estado) const {
return estados_finais.find(estado) != estados_finais.end();
}
inline void set_estado_inicial(std::string&& estado) {
estado_inicial = std::move(estado);
}
inline void adicionar_estado_final(std::string&& estado) {
estados_finais.insert(std::move(estado));
}
// Processa string com otimizações máximas
bool processar_string(std::string_view entrada) const {
if (estado_inicial.empty()) return false;
std::string estado_atual = estado_inicial;
chave_cache.clear();
for (char simbolo : entrada) {
chave_cache = estado_atual;
chave_cache.push_back(',');
chave_cache.push_back(simbolo);
auto it = transicoes.find(chave_cache);
if (it == transicoes.end()) return false;
estado_atual = it->second;
chave_cache.clear();
}
return eh_final(estado_atual);
}
// Versão ainda mais otimizada usando referência
bool processar_string_fast(const char* entrada, size_t len) const {
if (estado_inicial.empty()) return false;
std::string estado_atual = estado_inicial;
for (size_t i = 0; i < len; ++i) {
chave_cache = estado_atual;
chave_cache.push_back(',');
chave_cache.push_back(entrada[i]);
auto it = transicoes.find(chave_cache);
if (it == transicoes.end()) return false;
estado_atual = it->second;
chave_cache.clear();
}
return estados_finais.find(estado_atual) != estados_finais.end();
}
};#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#define MAX_AFD_ESTADOS 256
#define MAX_AFD_TRANSICOES 2048
#define MAX_ALFABETO 128
typedef struct {
char origem[32];
char simbolo;
char destino[32];
} transicao_afd_t;
typedef struct {
char estados[MAX_AFD_ESTADOS][32];
int num_estados;
char alfabeto[MAX_ALFABETO];
int tamanho_alfabeto;
transicao_afd_t transicoes[MAX_AFD_TRANSICOES];
int num_transicoes;
char estado_inicial[32];
char estados_finais[MAX_AFD_ESTADOS][32];
int num_estados_finais;
} afd_t;
// Inicializa AFD
static inline void afd_init(afd_t* afd) {
memset(afd, 0, sizeof(afd_t));
}
// Adiciona estado (verifica duplicatas)
static inline void afd_adicionar_estado(afd_t* afd, const char* estado) {
for (int i = 0; i < afd->num_estados; i++) {
if (strcmp(afd->estados[i], estado) == 0) return;
}
if (afd->num_estados < MAX_AFD_ESTADOS) {
strcpy(afd->estados[afd->num_estados++], estado);
}
}
// Adiciona transição (otimizado para busca rápida)
static inline void afd_adicionar_transicao(
afd_t* afd,
const char* origem,
char simbolo,
const char* destino
) {
if (afd->num_transicoes < MAX_AFD_TRANSICOES) {
transicao_afd_t* t = &afd->transicoes[afd->num_transicoes++];
strcpy(t->origem, origem);
t->simbolo = simbolo;
strcpy(t->destino, destino);
}
}
// Busca transição (busca linear otimizada com likely/unlikely)
static inline const char* afd_buscar_transicao(
const afd_t* afd,
const char* origem,
char simbolo
) {
// Busca reversa é mais rápida para transições recentes
for (int i = afd->num_transicoes - 1; i >= 0; i--) {
const transicao_afd_t* t = &afd->transicoes[i];
if (t->simbolo == simbolo && strcmp(t->origem, origem) == 0) {
return t->destino;
}
}
return NULL;
}
// Verifica se estado é final
static inline bool afd_eh_final(const afd_t* afd, const char* estado) {
for (int i = 0; i < afd->num_estados_finais; i++) {
if (strcmp(afd->estados_finais[i], estado) == 0) return true;
}
return false;
}
// Adiciona estado final
static inline void afd_adicionar_estado_final(afd_t* afd, const char* estado) {
if (afd->num_estados_finais < MAX_AFD_ESTADOS) {
strcpy(afd->estados_finais[afd->num_estados_finais++], estado);
}
}
// Processa string (máxima performance)
bool afd_processar_string(const afd_t* afd, const char* entrada, size_t len) {
if (afd->estado_inicial[0] == '\0') return false;
char estado_atual[32];
strcpy(estado_atual, afd->estado_inicial);
for (size_t i = 0; i < len; i++) {
const char* proximo = afd_buscar_transicao(afd, estado_atual, entrada[i]);
if (proximo == NULL) return false;
strcpy(estado_atual, proximo);
}
return afd_eh_final(afd, estado_atual);
}
// Versão com hash table para O(1) lookup (mais memória, mais velocidade)
typedef struct {
char chave[64]; // "origem,simbolo"
char destino[32];
} entrada_hash_t;
typedef struct {
entrada_hash_t tabela[MAX_AFD_TRANSICOES * 2]; // Load factor ~0.5
int capacidade;
} hash_transicoes_t;
static inline unsigned int hash_string(const char* str) {
unsigned int hash = 5381;
int c;
while ((c = *str++)) {
hash = ((hash << 5) + hash) + c;
}
return hash;
}
// Versão ultra-otimizada com hash table
bool afd_processar_string_hash(
const hash_transicoes_t* hash,
const char* estado_inicial,
const char* entrada,
size_t len,
const afd_t* afd
) {
char estado_atual[32];
strcpy(estado_atual, estado_inicial);
char chave[64];
for (size_t i = 0; i < len; i++) {
sprintf(chave, "%s,%c", estado_atual, entrada[i]);
unsigned int idx = hash_string(chave) % hash->capacidade;
// Linear probing
while (hash->tabela[idx].chave[0] != '\0') {
if (strcmp(hash->tabela[idx].chave, chave) == 0) {
strcpy(estado_atual, hash->tabela[idx].destino);
goto proximo_simbolo;
}
idx = (idx + 1) % hash->capacidade;
}
return false; // Não encontrou transição
proximo_simbolo:;
}
return afd_eh_final(afd, estado_atual);
}🧩 Tokens: Os Átomos das Linguagens de Programação
O conceito de token é simultaneamente simples e profundo. Tokens são as unidades léxicas mínimas de uma linguagem de programação - os “átomos” que, quando combinados, formam as moléculas sintáticas que estudaremos nas próximas semanas.
🎭 Anatomia de um Token
graph LR
A[🔤 Lexema<br/>Sequência de caracteres<br/>exata no código fonte] --> B[🏷️ Token<br/>Categoria léxica<br/>com atributos]
C[Exemplo: 'contador'] --> D[TOKEN_IDENTIFICADOR<br/>valor: 'contador'<br/>posição: linha 5, coluna 10]
E[Exemplo: '123.45'] --> F[TOKEN_NUMERO_REAL<br/>valor: 123.45<br/>posição: linha 8, coluna 20]
G[Exemplo: 'if'] --> H[TOKEN_PALAVRA_CHAVE<br/>tipo: IF<br/>posição: linha 12, coluna 5]
style B fill:#e8f5e8
style D fill:#e8f5e8
style F fill:#e8f5e8
style H fill:#e8f5e8
Lexemas versus Tokens: Esta distinção é fundamental. O lexema é a sequência literal de caracteres no código fonte, enquanto o token é a representação abstrata que carrega informações estruturadas sobre esse lexema. Pense no lexema como a “palavra escrita” e no token como o “conceito que ela representa”.
Atributos de Tokens: Cada token carrega informações que serão vitais para fases posteriores. A posição no arquivo fonte permite mensagens de erro precisas. O valor numérico ou string permite análise semântica. O tipo específico orienta decisões sintáticas.
Categorias Fundamentais: A maioria das linguagens de programação organiza tokens em categorias similares:
- Identificadores: Nomes criados pelo programador (variáveis, funções, classes)
- Literais: Valores constantes (números, strings, booleanos)
- Palavras-chave: Termos reservados da linguagem (if, while, class)
- Operadores: Símbolos de operações (=, +, -, &&, ||)
- Delimitadores: Símbolos estruturais (;, {, }, (, ))
- Comentários: Texto ignorado pelo compilador mas preservado para documentação
Esta categorização não é arbitrária - reflete décadas de evolução no design de linguagens e otimização de compiladores.
⚙️ O Processo de Tokenização: Algoritmos e Estruturas
A tokenização é o processo algorítmico que transforma uma sequência de caracteres em uma sequência de tokens. Este processo pode parecer direto, mas esconde sutilezas fascinantes que distinguem implementações amadoras de soluções profissionais.
🔄 Fluxo Algorítmico da Tokenização
graph TB
A[📖 Buffer de Entrada] --> B{Próximo Caractere}
B --> C[🔍 Reconhecimento de Padrão]
C --> D{Padrão Completo?}
D -->|Não| E[📝 Adicionar ao Buffer Atual]
E --> B
D -->|Sim| F[🏷️ Criar Token]
F --> G[📤 Emitir Token]
G --> H{Fim do Arquivo?}
H -->|Não| I[🧹 Limpar Buffer]
I --> B
H -->|Sim| J[✅ Finalizar]
K[❌ Erro Léxico] --> L[📢 Reportar Erro]
C --> K
L --> M[🔄 Estratégia de Recuperação]
M --> B
style F fill:#e8f5e8
style K fill:#ffebee
style L fill:#ffebee
O Princípio da Correspondência Máxima: Um analisador léxico deve sempre tentar formar o token mais longo possível. Se a entrada for “<=”, o analisador deve reconhecer um único token MENOR_IGUAL ao invés de dois tokens separados: MENOR e IGUAL. Esta regra resolve ambiguidades naturalmente.
Lookahead e Backtracking: Frequentemente, o analisador precisa ler caracteres além do token atual para tomar decisões corretas. Por exemplo, ao ver “123”, ele precisa continuar lendo para determinar se é um inteiro “123” ou o início de um real “123.45”.
Gerenciamento de Estados: O processo de tokenização é inerentemente baseado em estados. O analisador mantém informações sobre onde está no processo de reconhecimento de cada padrão, utilizando exatamente os conceitos de AFDs que você dominou.
Tratamento de Ambiguidades Léxicas
Uma das questões mais sutis na implementação de analisadores léxicos é o tratamento de situações onde múltiplos padrões podem corresponder à mesma sequência de caracteres.
💡 Exemplo Clássico de Ambiguidade
Considere a sequência “if” em um código fonte. Ela deveria ser reconhecida como:
- A palavra-chave IF?
- Um identificador com nome “if”?
A resposta depende do contexto e das regras de precedência da linguagem.
Estratégias de Resolução:
- Precedência por Ordem: Palavras-chave têm precedência sobre identificadores
- Correspondência Mais Longa: Sempre escolher o token mais longo possível
- Contexto Léxico: Usar informações sobre o estado atual do parser
Implementação Prática: Na prática, muitos analisadores primeiro reconhecem identificadores e depois consultam uma tabela hash para determinar se são palavras-chave. Esta abordagem combina eficiência com simplicidade.
🎨 Especificação de Tokens com Expressões Regulares
As expressões regulares que você dominou nas semanas anteriores agora se tornam a ferramenta fundamental para especificar precisamente cada categoria de token. Esta aplicação direta da teoria é uma das conexões mais elegantes entre matemática e engenharia prática.
📝 Especificações Regulares para Tokens Comuns
%% ---
%% title: Especificações Regulares para Tokens Comuns
%% displayMode: compact
%% config:
%% theme: forest
%% layout: elk
%% elk:
%% mergeEdges: true
%% nodePlacementStrategy: LINEAR_SEGMENTS
%% ---
graph LR
subgraph "Identificadores"
A["[a-zA-Z_][a-zA-Z0-9_]*"] --> B[contador_total<br/>_variavel<br/>MinhaClasse]
end
subgraph "Números Inteiros"
C["[0-9]+"] --> D[123<br/>0<br/>999]
end
subgraph "Números Reais"
E["[0-9]+\.[0-9]+"] --> F[123.45<br/>0.0<br/>3.14159]
end
subgraph "Strings"
G["#quot;[^#quot;]*#quot;"] --> H["#quot;Hello World#quot;<br/>#quot;texto#quot;<br/>#quot;#quot;"]
end
style B fill:#e8f5e8
style D fill:#e8f5e8
style F fill:#e8f5e8
style H fill:#e8f5e8
Identificadores: A expressão regular [a-zA-Z_][a-zA-Z0-9_]* captura uma regra universal: identificadores começam com letra ou underscore, seguidos por qualquer número de letras, dígitos ou underscores. Esta convenção, adotada por dezenas de linguagens, reflete décadas de experiência em design de linguagens.
Números: Especificar números corretamente é mais sutil do que parece. Considere todas as variações que uma linguagem moderna deve suportar:
- Inteiros: 123, -456, 0x1A2B (hexadecimal), 0b1010 (binário) - Reais: 123.45, .5, 3., 1.23e-4 (notação científica) - Especiais: infinity, NaN
Strings: O tratamento de strings literais introduz complexidades interessantes:
- Caracteres de escape: \", \n, \t, \\ - Unicode: Como lidar com caracteres não-ASCII? - Strings multi-linha: Algumas linguagens permitem strings que se estendem por várias linhas
Comentários: Mesmo comentários, que são “ignorados” pelo compilador, requerem especificação cuidadosa:
- Comentários de linha: // até o fim da linha - Comentários de bloco: /* podem se estender por múltiplas linhas */ - Comentários aninhados: Alguns linguagens permitem /* comentários /* aninhados */ */
Expressões Regulares Avançadas para Análise Léxica
Linguagens de programação modernas frequentemente incluem construtos que requerem expressões regulares mais sofisticadas do que os exemplos básicos.
from dataclasses import dataclass
from enum import Enum
from typing import List, Tuple, Dict, Any
# 1. Definição dos Tipos de Token (Enum)
class TokenType(Enum):
"""Tipos possíveis de tokens."""
WHITESPACE = 'WHITESPACE'
COMMENT = 'COMMENT'
BLOCK_COMMENT = 'BLOCK_COMMENT'
NUMBER = 'NUMBER'
STRING = 'STRING'
IDENTIFIER = 'IDENTIFIER'
LESS_EQUAL = 'LESS_EQUAL'
GREATER_EQUAL = 'GREATER_EQUAL'
EQUALS = 'EQUALS'
NOT_EQUALS = 'NOT_EQUALS'
LOGICAL_AND = 'LOGICAL_AND'
LOGICAL_OR = 'LOGICAL_OR'
OPERATOR = 'OPERATOR'
DELIMITER = 'DELIMITER'
# ... outros tipos de token
# 2. Especificação do Token (Dataclass)
@dataclass(frozen=True) # frozen=True simula a imutabilidade do `const` do Dart
class TokenSpecification:
"""Define a especificação de um token."""
pattern: str # Padrão de expressão regular
type: TokenType # Tipo de token
ignore: bool = False # Se o token deve ser ignorado pelo lexer
# 3. Definição das Especificações do Lexer
class LexerSpecifications:
"""Contém a lista de todas as especificações de tokens para o lexer."""
# Usando uma lista de TokenSpecification, que é a estrutura mais clara e imutável (graças ao dataclass `frozen=True`)
SPECIFICATIONS: List[TokenSpecification] = [
# Espaços em branco (ignorados)
TokenSpecification(r'\s+', TokenType.WHITESPACE, ignore=True),
# Comentários
TokenSpecification(r'//.*$', TokenType.COMMENT, ignore=True),
TokenSpecification(r'/\*[\s\S]*?\*/', TokenType.BLOCK_COMMENT, ignore=True),
# Números com suporte a notação científica
TokenSpecification(r'\d+\.?\d*([eE][+-]?\d+)?', TokenType.NUMBER),
# Strings com escape
# Nota: O padrão do Dart 'r"([^"\\]|\\.)*"' usa aspas duplas dentro.
# Em Python, é mais comum o r'\"([^"\\]|\\.)*\"' para expressões regex que
# usam aspas duplas como delimitadores. A versão original é tecnicamente correta,
# mas a seguir é mais legível como string raw do Python:
TokenSpecification(r'\"([^"\\]|\\.)*\"', TokenType.STRING),
# Identificadores (incluindo Unicode, \w já cobre muitas letras Unicode)
TokenSpecification(r'[a-zA-Z_]\w*', TokenType.IDENTIFIER),
# Operadores compostos (ordem importa!)
TokenSpecification(r'<=', TokenType.LESS_EQUAL),
TokenSpecification(r'>=', TokenType.GREATER_EQUAL),
TokenSpecification(r'==', TokenType.EQUALS),
TokenSpecification(r'!=', TokenType.NOT_EQUALS),
TokenSpecification(r'&&', TokenType.LOGICAL_AND),
TokenSpecification(r'\|\|', TokenType.LOGICAL_OR),
# Operadores simples
# Adicionamos \. para escapar os metacaracteres no conjunto
TokenSpecification(r'[+\-*/=<>!]', TokenType.OPERATOR),
# Delimitadores
TokenSpecification(r'[{}();,.]', TokenType.DELIMITER),
]
# Opcional: Para máxima otimização de tempo de execução (Lexer)
# A otimização máxima para um lexer geralmente envolve compilar todas
# as especificações em um único padrão RegEx e usar o método `re.match`
# de forma eficiente. O formato preferido para isso seria:
class OptimizedLexerSpecs:
"""Representação otimizada das especificações para uso direto em um Lexer baseado em re."""
# Cria uma lista de tuplas (pattern, type) que é mais simples para iteração do lexer
RAW_SPECIFICATIONS: List[Tuple[str, TokenType, bool]] = [
# (pattern, type, ignore)
(r'\s+', TokenType.WHITESPACE, True),
(r'//.*$', TokenType.COMMENT, True),
(r'/\*[\s\S]*?\*/', TokenType.BLOCK_COMMENT, True),
(r'\d+\.?\d*([eE][+-]?\d+)?', TokenType.NUMBER, False),
(r'\"([^"\\]|\\.)*\"', TokenType.STRING, False),
(r'[a-zA-Z_]\w*', TokenType.IDENTIFIER, False),
(r'<=', TokenType.LESS_EQUAL, False),
(r'>=', TokenType.GREATER_EQUAL, False),
(r'==', TokenType.EQUALS, False),
(r'!=', TokenType.NOT_EQUALS, False),
(r'&&', TokenType.LOGICAL_AND, False),
(r'\|\|', TokenType.LOGICAL_OR, False),
(r'[+\-*/=<>!]', TokenType.OPERATOR, False),
(r'[{}();,.]', TokenType.DELIMITER, False),
]
# Para máxima performance, você pode querer apenas a lista de padrões
# e tipos não ignorados para compilação em um único RegEx com grupos nomeados.
# Exemplo (conceitual):
# FULL_REGEX = '|'.join(f'(?P<{spec[1].name}>{spec[0]})'
# for spec in RAW_SPECIFICATIONS if not spec[2])
# # Importar `re` e usar `re.compile(FULL_REGEX)`class TokenSpecification {
final String pattern;
final TokenType type;
final bool ignore;
const TokenSpecification(this.pattern, this.type, {this.ignore = false});
}
class LexerSpecifications {
static const List<TokenSpecification> specifications = [
// Espaços em branco (ignorados)
TokenSpecification(r'\s+', TokenType.WHITESPACE, ignore: true),
// Comentários
TokenSpecification(r'//.*$', TokenType.COMMENT, ignore: true),
TokenSpecification(r'/\*[\s\S]*?\*/', TokenType.BLOCK_COMMENT, ignore: true),
// Números com suporte a notação científica
TokenSpecification(r'\d+\.?\d*([eE][+-]?\d+)?', TokenType.NUMBER),
// Strings com escape
TokenSpecification(r'"([^"\\]|\\.)*"', TokenType.STRING),
// Identificadores (incluindo Unicode)
TokenSpecification(r'[a-zA-Z_]\w*', TokenType.IDENTIFIER),
// Operadores compostos (ordem importa!)
TokenSpecification(r'<=', TokenType.LESS_EQUAL),
TokenSpecification(r'>=', TokenType.GREATER_EQUAL),
TokenSpecification(r'==', TokenType.EQUALS),
TokenSpecification(r'!=', TokenType.NOT_EQUALS),
TokenSpecification(r'&&', TokenType.LOGICAL_AND),
TokenSpecification(r'\|\|', TokenType.LOGICAL_OR),
// Operadores simples
TokenSpecification(r'[+\-*/=<>!]', TokenType.OPERATOR),
// Delimitadores
TokenSpecification(r'[{}();,.]', TokenType.DELIMITER),
];
}#include <regex>
#include <vector>
#include <string>
enum class TokenType {
WHITESPACE, COMMENT, BLOCK_COMMENT,
NUMBER, STRING, IDENTIFIER,
LESS_EQUAL, GREATER_EQUAL, EQUALS, NOT_EQUALS,
LOGICAL_AND, LOGICAL_OR,
OPERATOR, DELIMITER
};
struct TokenSpecification {
std::regex pattern;
TokenType type;
bool ignore;
TokenSpecification(const std::string& pat, TokenType t, bool ign = false)
: pattern(pat), type(t), ignore(ign) {}
};
class LexerSpecifications {
public:
static const std::vector<TokenSpecification> specifications;
};
const std::vector<TokenSpecification> LexerSpecifications::specifications = {
// Ordem é essencial para resolver ambiguidades
{R"(\s+)", TokenType::WHITESPACE, true},
{R"(//.*$)", TokenType::COMMENT, true},
{R"(/\*[\s\S]*?\*/)", TokenType::BLOCK_COMMENT, true},
// Números com precisão científica
{R"(\d+\.?\d*([eE][+-]?\d+)?)", TokenType::NUMBER},
// Strings com caracteres de escape
{R"("([^"\\]|\\.)*")", TokenType::STRING},
// Identificadores Unicode-aware
{R"([a-zA-Z_]\w*)", TokenType::IDENTIFIER},
// Operadores compostos primeiro (precedência!)
{R"(<=)", TokenType::LESS_EQUAL},
{R"(>=)", TokenType::GREATER_EQUAL},
{R"(==)", TokenType::EQUALS},
{R"(!=)", TokenType::NOT_EQUALS},
{R"(&&)", TokenType::LOGICAL_AND},
{R"(\|\|)", TokenType::LOGICAL_OR},
// Operadores simples
{R"([+\-*/=<>!])", TokenType::OPERATOR},
// Delimitadores estruturais
{R"([{}();,.])", TokenType::DELIMITER}
};lexer_spec.h
#ifndef LEXER_SPEC_H
#define LEXER_SPEC_H
#include <stdbool.h>
// --- 1. Enumeração dos Tipos de Token ---
typedef enum {
// Tipos de tokens a ignorar
TOKEN_WHITESPACE, TOKEN_COMMENT, TOKEN_BLOCK_COMMENT,
// Tipos de tokens válidos
TOKEN_NUMBER, TOKEN_STRING, TOKEN_IDENTIFIER,
// Operadores Compostos (Devem ser verificados primeiro!)
TOKEN_LESS_EQUAL, TOKEN_GREATER_EQUAL, TOKEN_EQUALS, TOKEN_NOT_EQUALS,
TOKEN_LOGICAL_AND, TOKEN_LOGICAL_OR,
// Operadores Simples e Delimitadores
TOKEN_OPERATOR, TOKEN_DELIMITER,
// Fim de Arquivo e Erro
TOKEN_EOF, TOKEN_ERROR
} TokenType;
// --- 2. Estrutura de Token ---
typedef struct {
TokenType type;
char *lexema; // Ponteiro para o início do lexema na entrada (ou pool de strings)
int length;
int start_pos;
} Token;
// --- 3. Estrutura Principal do Analisador Léxico (para manter o estado) ---
typedef struct {
const char *input;
int current_pos;
int input_len;
} Lexer;
// Funções públicas
void lexer_init(Lexer *l, const char *input);
Token lexer_next_token(Lexer *l);
// Constantes para otimização de classificação de caracteres
#define CHAR_LETTER 1
#define CHAR_DIGIT 2
#define CHAR_UNDERSCORE 3
#define CHAR_OTHER 0
#endif // LEXER_SPEC_Hlexer_spec.c
#include "lexer_spec.h"
#include <string.h>
#include <stdlib.h>
#include <ctype.h>
// --- Tabela de Classificação Otimizada (Somente para ASCII) ---
static int char_classification[256];
static void init_char_classification() {
// Inicialização O(1)
for (int i = 0; i < 256; i++) {
char_classification[i] = CHAR_OTHER;
}
for (int i = 'a'; i <= 'z'; i++) {
char_classification[i] = CHAR_LETTER;
}
for (int i = 'A'; i <= 'Z'; i++) {
char_classification[i] = CHAR_LETTER;
}
for (int i = '0'; i <= '9'; i++) {
char_classification[i] = CHAR_DIGIT;
}
char_classification['_'] = CHAR_UNDERSCORE;
}
static inline int classify_char(int c) {
if (c >= 0 && c < 256) {
return char_classification[c];
}
return CHAR_OTHER; // Assume caracteres Unicode são 'OUTRO'
}
// --- Funções Auxiliares (Lookahead) ---
static inline int lexer_peek(Lexer *l, int offset) {
int pos = l->current_pos + offset;
if (pos >= l->input_len) {
return 0; // 0 ou EOF
}
return l->input[pos];
}
static inline void lexer_advance(Lexer *l, int count) {
l->current_pos += count;
}
// --- Inicialização do Lexer ---
void lexer_init(Lexer *l, const char *input) {
// Garante que a classificação seja inicializada
static bool initialized = false;
if (!initialized) {
init_char_classification();
initialized = true;
}
l->input = input;
l->current_pos = 0;
l->input_len = strlen(input);
}
// --- Implementação do Reconhecimento (Maximal Munch / AFD Manual) ---
static Token lexer_scan_token(Lexer *l) {
int start_pos = l->current_pos;
int current_char = lexer_peek(l, 0);
Token token = {TOKEN_ERROR, (char*)l->input + start_pos, 0, start_pos};
// Fim da entrada
if (current_char == 0) {
token.type = TOKEN_EOF;
return token;
}
// --- 1. Whitespace e Comentários (Ignorar) ---
// A ordem de verificação é essencial (similar à ordem da especificação C++)
// Espaços em branco (R"(\s+)")
if (isspace(current_char)) {
int count = 0;
while (isspace(lexer_peek(l, count))) {
count++;
}
lexer_advance(l, count);
token.type = TOKEN_WHITESPACE;
token.length = count;
return token;
}
// Comentário de Bloco (R"(/\*[\s\S]*?\*/)")
if (current_char == '/' && lexer_peek(l, 1) == '*') {
lexer_advance(l, 2); // Consome /*
int count = 2;
while (l->current_pos < l->input_len) {
count++;
if (lexer_peek(l, 0) == '*' && lexer_peek(l, 1) == '/') {
lexer_advance(l, 2); // Consome */
count += 2;
token.type = TOKEN_BLOCK_COMMENT;
token.length = count;
return token;
}
lexer_advance(l, 1);
}
// Erro: Comentário não terminado
return token;
}
// Comentário de Linha (R"(//.*$)")
if (current_char == '/' && lexer_peek(l, 1) == '/') {
int count = 2;
while (l->current_pos < l->input_len && lexer_peek(l, 0) != '\n' && lexer_peek(l, 0) != '\r') {
lexer_advance(l, 1);
count++;
}
token.type = TOKEN_COMMENT;
token.length = count;
return token;
}
// --- 2. Operadores Compostos e Simples ---
// A ordem de verificação garante que `<=`, `==`, etc. sejam casados antes de `<` ou `=`.
switch (current_char) {
case '<':
if (lexer_peek(l, 1) == '=') { lexer_advance(l, 2); token.type = TOKEN_LESS_EQUAL; token.length = 2; return token; }
lexer_advance(l, 1); token.type = TOKEN_OPERATOR; token.length = 1; return token;
case '>':
if (lexer_peek(l, 1) == '=') { lexer_advance(l, 2); token.type = TOKEN_GREATER_EQUAL; token.length = 2; return token; }
lexer_advance(l, 1); token.type = TOKEN_OPERATOR; token.length = 1; return token;
case '=':
if (lexer_peek(l, 1) == '=') { lexer_advance(l, 2); token.type = TOKEN_EQUALS; token.length = 2; return token; }
lexer_advance(l, 1); token.type = TOKEN_OPERATOR; token.length = 1; return token;
case '!':
if (lexer_peek(l, 1) == '=') { lexer_advance(l, 2); token.type = TOKEN_NOT_EQUALS; token.length = 2; return token; }
// O `!` sozinho também pode ser um operador
lexer_advance(l, 1); token.type = TOKEN_OPERATOR; token.length = 1; return token;
case '&':
if (lexer_peek(l, 1) == '&') { lexer_advance(l, 2); token.type = TOKEN_LOGICAL_AND; token.length = 2; return token; }
lexer_advance(l, 1); token.type = TOKEN_OPERATOR; token.length = 1; return token;
case '|':
if (lexer_peek(l, 1) == '|') { lexer_advance(l, 2); token.type = TOKEN_LOGICAL_OR; token.length = 2; return token; }
lexer_advance(l, 1); token.type = TOKEN_OPERATOR; token.length = 1; return token;
case '+':
case '-':
case '*':
case '/':
// Já tratamos /**/ e //, o restante é operador simples
lexer_advance(l, 1); token.type = TOKEN_OPERATOR; token.length = 1; return token;
}
// --- 3. Delimitadores Estruturais ---
switch (current_char) {
case '{':
case '}':
case '(':
case ')':
case ';':
case ',':
case '.':
lexer_advance(l, 1); token.type = TOKEN_DELIMITER; token.length = 1; return token;
}
// --- 4. Strings (R"("([^"\\]|\\.)*")") ---
if (current_char == '"') {
lexer_advance(l, 1); // Consome aspa inicial
int count = 1;
while (l->current_pos < l->input_len) {
current_char = lexer_peek(l, 0);
if (current_char == '"') {
lexer_advance(l, 1); // Consome aspa final
count++;
token.type = TOKEN_STRING;
token.length = count;
return token;
}
if (current_char == '\\') {
lexer_advance(l, 2); // Consome \ e o próximo caractere de escape
count += 2;
} else {
lexer_advance(l, 1);
count++;
}
}
// Erro: String não terminada
return token;
}
// --- 5. Números (R"(\d+\.?\d*([eE][+-]?\d+)?)") ---
int pos_temp = l->current_pos;
bool is_number = false;
if (classify_char(current_char) == CHAR_DIGIT) {
is_number = true;
while (classify_char(lexer_peek(l, 0)) == CHAR_DIGIT) {
lexer_advance(l, 1);
}
// Ponto decimal
if (lexer_peek(l, 0) == '.') {
lexer_advance(l, 1);
while (classify_char(lexer_peek(l, 0)) == CHAR_DIGIT) {
lexer_advance(l, 1);
}
}
// Notação Científica
if (lexer_peek(l, 0) == 'e' || lexer_peek(l, 0) == 'E') {
lexer_advance(l, 1);
if (lexer_peek(l, 0) == '+' || lexer_peek(l, 0) == '-') {
lexer_advance(l, 1);
}
if (classify_char(lexer_peek(l, 0)) == CHAR_DIGIT) {
while (classify_char(lexer_peek(l, 0)) == CHAR_DIGIT) {
lexer_advance(l, 1);
}
} else {
// Erro: 'e' sem expoente
l->current_pos = pos_temp; // Reverter
token.type = TOKEN_ERROR;
return token;
}
}
}
if (is_number) {
token.type = TOKEN_NUMBER;
token.length = l->current_pos - start_pos;
return token;
}
l->current_pos = pos_temp; // Reverter
// --- 6. Identificadores (R"([a-zA-Z_]\w*)") ---
int class = classify_char(current_char);
if (class == CHAR_LETTER || class == CHAR_UNDERSCORE) {
lexer_advance(l, 1);
int count = 1;
while (1) {
class = classify_char(lexer_peek(l, 0));
if (class == CHAR_LETTER || class == CHAR_DIGIT || class == CHAR_UNDERSCORE) {
lexer_advance(l, 1);
count++;
} else {
break;
}
}
token.type = TOKEN_IDENTIFIER;
token.length = count;
// NOTA: A verificação de palavras-chave DEVE vir aqui.
// O C++ não tinha isso na especificação, mas o lexer C precisa implementar
// a verificação (ex: com uma trie ou tabela de hash estática) após reconhecer o ID.
return token;
}
// Se nenhum padrão casar, é um erro
lexer_advance(l, 1);
token.type = TOKEN_ERROR;
token.length = 1;
return token;
}
// O Lexer deve ignorar tokens de formatação (WHITESPACE, COMMENT, BLOCK_COMMENT)
Token lexer_next_token(Lexer *l) {
Token token;
do {
token = lexer_scan_token(l);
if (token.type != TOKEN_WHITESPACE &&
token.type != TOKEN_COMMENT &&
token.type != TOKEN_BLOCK_COMMENT) {
return token;
}
} while (token.type != TOKEN_EOF && token.type != TOKEN_ERROR);
return token;
}
// --- Exemplo de Uso (main.c) ---
/*
#include <stdio.h>
#include <string.h>
int main() {
// A string de entrada que será analisada
const char *source = "var x = 123.45e+2; // comentario\n if (x <= 5) { /* block */ }";
Lexer lexer;
lexer_init(&lexer, source);
Token token;
printf("Lexing: '%s'\n", source);
do {
token = lexer_next_token(&lexer);
char lexeme_buffer[20];
strncpy(lexeme_buffer, token.lexema, token.length > 19 ? 19 : token.length);
lexeme_buffer[token.length > 19 ? 19 : token.length] = '\0';
printf("Tipo: %d, Lexema: '%.*s'\n", token.type, token.length, token.lexema);
} while (token.type != TOKEN_EOF && token.type != TOKEN_ERROR);
return 0;
}
*/A Importância da Ordem: Observe como as especificações estão ordenadas cuidadosamente. Operadores compostos como “==” devem vir antes do operador simples “=” para evitar que o analisador pare prematuramente na primeira correspondência.
Tratamento de Unicode: Linguagens modernas devem suportar identificadores em múltiplos idiomas. A especificação [a-zA-Z_]\w* funciona para idiomas baseados no alfabeto latino, mas linguagens verdadeiramente internacionais precisam de suporte Unicode completo.
🤖 Implementação com Autômatos Finitos
Agora chegamos ao momento onde toda a teoria de autômatos finitos que você estudou se materializa em código funcional. Cada expressão regular que especifica um token pode ser convertida em um AFN, que por sua vez pode ser convertido em um AFD otimizado.
🔧 Do AFD ao Código: Implementação Direta
---
displayMode: compact
config:
theme: forest
layout: elk
elk:
mergeEdges: true
nodePlacementStrategy: LINEAR_SEGMENTS
---
stateDiagram-v2
[*] --> q0
q0 --> q1 : letra|_
q1 --> q1 : letra|dígito|_
q1 --> [*] : outros
q0 --> q2 : dígito
q2 --> q2 : dígito
q2 --> q3 : .
q3 --> q4 : dígito
q4 --> q4 : dígito
q2 --> [*] : outros
q4 --> [*] : outros
q0 --> q5 : "
q5 --> q5 : qualquer exceto "
q5 --> q6 : "
q6 --> [*] : outros
note right of q1 : Estado final\nTOKEN_IDENTIFICADOR
note right of q2 : Estado final\nTOKEN_INTEIRO
note right of q4 : Estado final\nTOKEN_REAL
note right of q6 : Estado final\nTOKEN_STRING
Este diagrama mostra como um único AFD pode reconhecer múltiplos tipos de tokens, com estados finais diferentes correspondendo a diferentes categorias de tokens.
Implementação Baseada em Tabela de Transições
A abordagem mais eficiente para implementar AFDs em analisadores léxicos é usar uma tabela de transições bidimensional onde cada célula [estado][símbolo] contém o próximo estado.
import re
from typing import List, Set, Dict, Optional
from dataclasses import dataclass
from enum import Enum # Assumimos que TokenType está definida
# --- Dependências (Replicando o necessário do exemplo anterior) ---
# Se for usar, defina TokenType:
class TokenType(Enum):
IDENTIFIER = 'IDENTIFIER'
NUMBER = 'NUMBER'
# ... outros tipos de token
# --- Fim das Dependências ---
@dataclass(frozen=True)
class Token:
"""
Representa um token léxico encontrado.
O `frozen=True` simula a imutabilidade do `final` do Dart.
"""
tipo: TokenType
lexema: str
posicao: int
class AFDLexer:
"""
Implementa um Lexer baseado em AFD usando a técnica "maximal munch".
Atributos:
- tabela_transicoes: Matriz (Lista de Listas de Int/None) do AFD.
- estados_finais: Conjunto de estados que são finais.
- tipos_por_estado: Mapeamento de estado final para TokenType.
"""
# Compila os regex para otimização de desempenho
# Padrão: re.Pattern[str] (disponível no Python 3.9+)
_REGEX_LETRA = re.compile(r'[a-zA-Z_]')
_REGEX_DIGITO = re.compile(r'[0-9]')
def __init__(self, tabela_transicoes: List[List[Optional[int]]],
estados_finais: Set[int],
tipos_por_estado: Dict[int, TokenType]):
"""Construtor que recebe a estrutura do AFD."""
self.tabela_transicoes = tabela_transicoes
self.estados_finais = estados_finais
self.tipos_por_estado = tipos_por_estado
def _mapear_caractere(self, c: str) -> int:
"""
Mapeia um caractere de entrada para o índice da coluna na tabela de transições.
Indices de Coluna:
0: Letra ou _
1: Dígito
2: Ponto (.)
3: Aspas (")
4: Outros
"""
# A performance é otimizada usando os objetos RegEx compilados
if self._REGEX_LETRA.match(c):
return 0 # Letra
if self._REGEX_DIGITO.match(c):
return 1 # Dígito
if c == '.':
return 2 # Ponto
if c == '"':
return 3 # Aspas
return 4 # Outros
def proximo_token(self, entrada: str, posicao: int) -> Optional[Token]:
"""
Encontra o próximo token válido a partir da 'posicao' na 'entrada'.
Retorna um Token se encontrado, ou None (representando erro léxico/EOF).
"""
estado_atual: int = 0
inicio_token: int = posicao
ultimo_estado_final: int = -1
ultima_posicao_valida: int = -1
entrada_len: int = len(entrada) # Cache do tamanho para performance
while posicao < entrada_len:
caractere: str = entrada[posicao]
simbolo: int = self._mapear_caractere(caractere)
# Tabela de transição (usa .get() ou tenta acesso)
# O Dart usa `int?` (nullable int), o Python usa `Optional[int]` ou None
try:
proximo_estado: Optional[int] = self.tabela_transicoes[estado_atual][simbolo]
except IndexError:
# Ocorre se o estado_atual ou o simbolo (índice da coluna) for inválido.
proximo_estado = None
if proximo_estado is None:
break # Não há transição válida (similar ao `proximoEstado == null` do Dart)
estado_atual = proximo_estado
posicao += 1
# Verifica se o novo estado é um estado final
if estado_atual in self.estados_finais:
ultimo_estado_final = estado_atual
ultima_posicao_valida = posicao
# --- Processamento Final (Maximal Munch) ---
if ultimo_estado_final != -1:
# Encontrou o token mais longo válido (maximal munch)
lexema: str = entrada[inicio_token:ultima_posicao_valida]
# O `!` do Dart (non-null assertion) é substituído pela certeza
# de que a chave existe, ou uma checagem (preferível)
tipo: Optional[TokenType] = self.tipos_por_estado.get(ultimo_estado_final)
if tipo is None:
# Isto deve ser um erro de design do AFD, mas é uma segurança
raise ValueError(f"Estado final {ultimo_estado_final} não mapeado para um TokenType.")
return Token(tipo, lexema, inicio_token)
return None # Indica que nenhum token válido foi encontradoclass AFDLexer {
final List<List<int?>> tabelaTransicoes;
final Set<int> estadosFinais;
final Map<int, TokenType> tiposPorEstado;
AFDLexer(this.tabelaTransicoes, this.estadosFinais, this.tiposPorEstado);
Token? proximoToken(String entrada, int posicao) {
int estadoAtual = 0; // Estado inicial
int inicioToken = posicao;
int ultimoEstadoFinal = -1;
int ultimaPosicaoValida = -1;
while (posicao < entrada.length) {
String caractere = entrada[posicao];
int simbolo = _mapearCaractere(caractere);
int? proximoEstado = tabelaTransicoes[estadoAtual][simbolo];
if (proximoEstado == null) {
break; // Não há transição válida
}
estadoAtual = proximoEstado;
posicao++;
if (estadosFinais.contains(estadoAtual)) {
ultimoEstadoFinal = estadoAtual;
ultimaPosicaoValida = posicao;
}
}
if (ultimoEstadoFinal != -1) {
String lexema = entrada.substring(inicioToken, ultimaPosicaoValida);
TokenType tipo = tiposPorEstado[ultimoEstadoFinal]!;
return Token(tipo, lexema, inicioToken);
}
return null; // Erro léxico
}
int _mapearCaractere(String c) {
if (RegExp(r'[a-zA-Z_]').hasMatch(c)) return 0; // Letra
if (RegExp(r'[0-9]').hasMatch(c)) return 1; // Dígito
if (c == '.') return 2; // Ponto
if (c == '"') return 3; // Aspas
return 4; // Outros
}
}
class Token {
final TokenType tipo;
final String lexema;
final int posicao;
Token(this.tipo, this.lexema, this.posicao);
}#include <vector>
#include <unordered_set>
#include <unordered_map>
#include <string>
#include <optional>
enum class TokenType {
IDENTIFICADOR, INTEIRO, REAL, STRING
};
struct Token {
TokenType tipo;
std::string lexema;
size_t posicao;
Token(TokenType t, const std::string& l, size_t p)
: tipo(t), lexema(l), posicao(p) {}
};
class AFDLexer {
private:
std::vector<std::vector<int>> tabelaTransicoes;
std::unordered_set<int> estadosFinais;
std::unordered_map<int, TokenType> tiposPorEstado;
int mapearCaractere(char c) {
if (std::isalpha(c) || c == '_') return 0; // Letra
if (std::isdigit(c)) return 1; // Dígito
if (c == '.') return 2; // Ponto
if (c == '"') return 3; // Aspas
return 4; // Outros
}
public:
AFDLexer(const std::vector<std::vector<int>>& tabela,
const std::unordered_set<int>& finais,
const std::unordered_map<int, TokenType>& tipos)
: tabelaTransicoes(tabela), estadosFinais(finais), tiposPorEstado(tipos) {}
std::optional<Token> proximoToken(const std::string& entrada, size_t& posicao) {
int estadoAtual = 0; // Estado inicial
size_t inicioToken = posicao;
int ultimoEstadoFinal = -1;
size_t ultimaPosicaoValida = 0;
while (posicao < entrada.length()) {
char caractere = entrada[posicao];
int simbolo = mapearCaractere(caractere);
if (simbolo >= tabelaTransicoes[estadoAtual].size() ||
tabelaTransicoes[estadoAtual][simbolo] == -1) {
break; // Não há transição válida
}
estadoAtual = tabelaTransicoes[estadoAtual][simbolo];
posicao++;
if (estadosFinais.count(estadoAtual)) {
ultimoEstadoFinal = estadoAtual;
ultimaPosicaoValida = posicao;
}
}
if (ultimoEstadoFinal != -1) {
std::string lexema = entrada.substr(inicioToken,
ultimaPosicaoValida - inicioToken);
TokenType tipo = tiposPorEstado.at(ultimoEstadoFinal);
return Token(tipo, lexema, inicioToken);
}
return std::nullopt; // Erro léxico
}
};afd_lexer.h
#ifndef AFD_LEXER_H
#define AFD_LEXER_H
#include <stdbool.h>
#include <stddef.h> // Para size_t
// --- 1. Enumeração e Constantes ---
typedef enum {
TOKEN_IDENTIFICADOR,
TOKEN_INTEIRO,
TOKEN_REAL,
TOKEN_STRING,
TOKEN_ERROR,
TOKEN_EOF
} TokenType;
// Colunas da tabela de transições (símbolos de entrada)
enum {
SYM_LETRA_UNDERSCORE, // 0: isalpha() || '_'
SYM_DIGITO, // 1: isdigit()
SYM_PONTO, // 2: '.'
SYM_ASPAS, // 3: '"'
SYM_OUTRO, // 4: Outros caracteres
NUM_SYMBOLS // Número total de colunas na tabela (5)
};
// --- 2. Estrutura de Token ---
typedef struct {
TokenType type;
const char *lexema_start; // Ponteiro para o início na entrada
size_t length;
size_t posicao; // Posição inicial (offset)
} Token;
// --- 3. Estrutura do Lexer (AFD) ---
typedef struct {
const char *input;
size_t input_len;
size_t current_pos;
} AFDLexer;
// Funções públicas
void afd_lexer_init(AFDLexer *l, const char *input);
// Retorna um Token ou um Token com type=TOKEN_ERROR ou TOKEN_EOF
Token afd_lexer_next_token(AFDLexer *l);
#endif // AFD_LEXER_Hafd_lexer.c
#include "afd_lexer.h"
#include <string.h>
#include <ctype.h>
#include <stdlib.h>
// --- 4. Tabela Estática de Transições (Substitui std::vector<std::vector<int>>) ---
// Tabela de Transições: [Estado Atual][Símbolo de Entrada] -> Próximo Estado
// Esta é uma TABELA EXEMPLO para Identificador, Inteiro e Real (simplificado)
// Estado 0: Inicial
// Estado 1: Identificador (encontrada Letra/_ )
// Estado 2: Número Inteiro (encontrado Dígito)
// Estado 3: Número Real (encontrado Ponto)
// Estado 4: Número Real (encontrado Dígito após Ponto)
// Estado 5: String (encontrada aspa inicial)
// Estado 6: Dentro da String
// -1: Estado de Erro/Inexistente
#define NUM_STATES 8 // Número de estados na tabela
static const int TRANSITION_TABLE[NUM_STATES][NUM_SYMBOLS] = {
// ESTADO: Letra/_ (0) | Dígito (1) | Ponto (2) | Aspas (3) | Outro (4)
/* Estado 0 (Init) */ { 1, 2, -1, 5, -1 },
/* Estado 1 (ID) */ { 1, 1, -1, -1, -1 }, // ID ou Continuação
/* Estado 2 (Int) */ { -1, 2, 3, -1, -1 }, // Inteiro ou Real
/* Estado 3 (Ponto) */{ -1, 4, -1, -1, -1 }, // Ponto esperando Dígito
/* Estado 4 (Real) */ { -1, 4, -1, -1, -1 }, // Continuação de Real
/* Estado 5 (Str") */ { 6, 6, 6, 7, 6 }, // Aspa inicial
/* Estado 6 (Str) */ { 6, 6, 6, 7, 6 }, // Dentro da String
/* Estado 7 (Str") */ { -1, -1, -1, -1, -1 } // String Final
};
// --- 5. Mapeamento de Estado Final e Tipo (Substitui unordered_set/map) ---
// Estados que representam tokens válidos.
static const int FINAL_STATES[] = { 1, 2, 4, 7 };
static const size_t NUM_FINAL_STATES = sizeof(FINAL_STATES) / sizeof(FINAL_STATES[0]);
// Mapa direto de Estado Final -> Tipo de Token (INDEXADO PELO ESTADO)
// Use TOKEN_ERROR para estados não-finais ou que não mapeiam para um tipo único.
static const TokenType TYPE_MAP[NUM_STATES] = {
/* 0 */ TOKEN_ERROR,
/* 1 */ TOKEN_IDENTIFICADOR,
/* 2 */ TOKEN_INTEIRO,
/* 3 */ TOKEN_ERROR, // Não é final, precisa de dígito após o ponto
/* 4 */ TOKEN_REAL,
/* 5 */ TOKEN_ERROR, // Não é final, está esperando o conteúdo
/* 6 */ TOKEN_ERROR, // Não é final, está esperando a aspa final
/* 7 */ TOKEN_STRING // String terminada
};
// --- 6. Tabela de Classificação de Caracteres Otimizada (O(1)) ---
static int char_symbol_map[256];
static void init_char_symbol_map() {
int i;
for (i = 0; i < 256; i++) {
char_symbol_map[i] = SYM_OUTRO;
}
// Letra ou Underscore
for (i = 'a'; i <= 'z'; i++) char_symbol_map[i] = SYM_LETRA_UNDERSCORE;
for (i = 'A'; i <= 'Z'; i++) char_symbol_map[i] = SYM_LETRA_UNDERSCORE;
char_symbol_map['_'] = SYM_LETRA_UNDERSCORE;
// Dígitos
for (i = '0'; i <= '9'; i++) char_symbol_map[i] = SYM_DIGITO;
// Especiais
char_symbol_map['.'] = SYM_PONTO;
char_symbol_map['"'] = SYM_ASPAS;
}
static inline int map_char_to_symbol(char c) {
if ((unsigned char)c < 256) {
return char_symbol_map[(unsigned char)c];
}
return SYM_OUTRO; // Caracteres Unicode ou não-mapeados
}
// --- 7. Implementação do Lexer ---
void afd_lexer_init(AFDLexer *l, const char *input) {
// Inicializa o mapeamento de caracteres uma única vez
static bool initialized = false;
if (!initialized) {
init_char_symbol_map();
initialized = true;
}
l->input = input;
l->current_pos = 0;
l->input_len = (input != NULL) ? strlen(input) : 0;
}
/**
* Implementa o algoritmo Maximal Munch baseado na Tabela de Transições.
* Nota: Strings (Estado 5 e 6) precisam de lógica expandida para escapes,
* mas aqui seguimos a transição simples do AFD da tabela.
*/
Token afd_lexer_next_token(AFDLexer *l) {
int estado_atual = 0;
size_t inicio_token = l->current_pos;
int ultimo_estado_final = -1;
size_t ultima_posicao_valida = 0;
// Token de retorno padrão (em caso de erro)
Token erro_token = {TOKEN_ERROR, l->input + inicio_token, 1, inicio_token};
// --- Tratamento de EOF ---
if (l->current_pos >= l->input_len) {
return (Token){TOKEN_EOF, NULL, 0, l->current_pos};
}
// --- Loop Principal do AFD (Maximal Munch) ---
while (l->current_pos < l->input_len) {
char caractere = l->input[l->current_pos];
int simbolo = map_char_to_symbol(caractere);
int proximo_estado;
// Verifica transição na tabela estática
if (estado_atual < NUM_STATES && simbolo < NUM_SYMBOLS) {
proximo_estado = TRANSITION_TABLE[estado_atual][simbolo];
} else {
proximo_estado = -1;
}
if (proximo_estado == -1) {
break; // Não há transição válida a partir do estado atual
}
estado_atual = proximo_estado;
l->current_pos++;
// --- Maximal Munch (Mantém o estado final mais longo) ---
// Verifica se o novo estado é um estado final válido
// Usamos o mapeamento direto TYPE_MAP em vez de um loop por FINAL_STATES
if (TYPE_MAP[estado_atual] != TOKEN_ERROR) {
ultimo_estado_final = estado_atual;
ultima_posicao_valida = l->current_pos;
}
}
// --- Construção do Token Final ---
if (ultimo_estado_final != -1) {
// Recua a posição do lexer para o final do lexema válido
l->current_pos = ultima_posicao_valida;
// Cria o token
size_t token_length = ultima_posicao_valida - inicio_token;
Token final_token = {
TYPE_MAP[ultimo_estado_final],
l->input + inicio_token, // Ponteiro para o lexema
token_length,
inicio_token
};
return final_token;
}
// --- Erro Léxico ---
// Se não casou nada, mas avançou, o AFD retornou para um estado não-final.
// Neste AFD de exemplo, o erro mais simples é consumir 1 caractere e retornar ERRO.
if (l->current_pos == inicio_token) {
// Nenhuma transição foi feita, trata como caractere de erro
l->current_pos++;
erro_token.length = 1;
} else {
// Algum avanço ocorreu, mas terminou em um estado não-final (erro de malformação)
// Recua para o início do token e consome 1 caractere de erro.
l->current_pos = inicio_token + 1;
erro_token.length = 1;
}
return erro_token;
}Princípio da Correspondência Mais Longa: Observe como o algoritmo implementa o princípio da correspondência mais longa mantendo rastro do último estado final alcançado e sua posição correspondente. Isso garante que “123.45” seja reconhecido como um único token REAL ao invés de um INTEIRO seguido por PONTO e outro INTEIRO.
Tratamento de Erros: Quando não há transição válida, o algoritmo retorna o token mais longo válido encontrado até aquele ponto. Se nenhum estado final foi alcançado, indica um erro léxico que deve ser tratado apropriadamente.
📊 Gerenciamento de Estado e Contexto
Analisadores léxicos sofisticados frequentemente precisam manter informações de contexto que vão além do estado atual do AFD. Isso é especialmente importante para tratamento de strings multi-linha, comentários aninhados, e outros construtos complexos.
🔄 Estados de Contexto Léxico
---
displayMode: compact
config:
theme: forest
layout: elk
elk:
mergeEdges: true
nodePlacementStrategy: LINEAR_SEGMENTS
---
stateDiagram-v2
[*] --> NORMAL : início
NORMAL --> STRING : "
STRING --> STRING : qualquer\nexceto " e \
STRING --> ESCAPE : \
ESCAPE --> STRING : qualquer
STRING --> NORMAL : "
NORMAL --> COMMENT : //
COMMENT --> COMMENT : qualquer\nexceto \n
COMMENT --> NORMAL : \n
NORMAL --> BLOCK_COMMENT : /*
BLOCK_COMMENT --> BLOCK_COMMENT : qualquer\nexceto *
BLOCK_COMMENT --> MAYBE_END : *
MAYBE_END --> BLOCK_COMMENT : qualquer\nexceto /
MAYBE_END --> NORMAL : /
note right of STRING : Processamento\nespecial de escapes
note right of COMMENT : Ignora até\nfim da linha
note right of BLOCK_COMMENT : Ignora até\n*/
Implementação de Contexto Avançado
Para construtos que requerem processamento contextual mais sofisticado, podemos estender nosso analisador básico com uma pilha de contextos.
from enum import Enum
from typing import List, Optional, Any, TYPE_CHECKING
from dataclasses import dataclass
# --- Dependências (Presumidas para compilar o código) ---
# Em um ambiente de produção, estas classes seriam importadas.
class TokenType(Enum):
# Tipos mínimos para o exemplo
WHITESPACE = 'WHITESPACE'
NEWLINE = 'NEWLINE'
# ... outros
@dataclass(frozen=True)
class Token:
tipo: TokenType
lexema: str
posicao: int
deve_ignorar: bool = False # Propriedade fundamental para o LexerAvancado
# ... outros atributos
# --- Enum para Contexto Léxico ---
class ContextoLexico(Enum):
"""Estados que o Lexer pode estar, controlados por pilha."""
NORMAL = 'NORMAL'
DENTRO_STRING = 'DENTRO_STRING'
ESCAPE_STRING = 'ESCAPE_STRING'
COMENTARIO_LINHA = 'COMENTARIO_LINHA'
COMENTARIO_BLOCO = 'COMENTARIO_BLOCO'
MAYBE_FIM_COMENTARIO = 'MAYBE_FIM_COMENTARIO'
# --- Classe Principal: Lexer Avançado ---
class LexerAvancado:
"""
Um Lexer baseado em pilha de contexto, ideal para tratar
comentários aninhados, strings com escape e outros estados.
"""
# Atributos inicializados no construtor
pilha_contexto: List[ContextoLexico]
numero_linha: int
numero_coluna: int
def __init__(self):
"""Inicializa o lexer com o estado NORMAL."""
# Usa List[ContextoLexico] para simular a pilha (o mais idiomático em Python)
self.pilha_contexto = [ContextoLexico.NORMAL]
self.numero_linha = 1
self.numero_coluna = 1
@property
def contexto_atual(self) -> ContextoLexico:
"""Getter: Retorna o contexto no topo da pilha."""
# Acesso direto ao último elemento da lista
return self.pilha_contexto[-1]
def push_contexto(self, novo_contexto: ContextoLexico):
"""Adiciona um novo contexto ao topo da pilha (push)."""
self.pilha_contexto.append(novo_contexto)
def pop_contexto(self):
"""Remove o contexto do topo da pilha (pop), exceto o contexto NORMAL."""
if len(self.pilha_contexto) > 1:
self.pilha_contexto.pop()
def atualizar_posicao(self, caractere: str):
"""Atualiza a linha e coluna com base no caractere consumido."""
if caractere == '\n':
self.numero_linha += 1
self.numero_coluna = 1
# Opcional: Aqui poderíamos criar um token de NEWLINE para rastreamento
else:
self.numero_coluna += 1
def tokenizar(self, entrada: str) -> List[Token]:
"""
Percorre toda a entrada e gera uma lista de tokens válidos.
"""
tokens: List[Token] = []
posicao: int = 0
entrada_len: int = len(entrada)
while posicao < entrada_len:
# Note: Este design de lexer baseado em caractere a caractere (e não em casamento de RegEx)
# é inerentemente mais lento, mas necessário para lógica de estados complexos (pilha).
# Chama a lógica principal de processamento de estado
token: Optional[Token] = self._processar_caractere_em_contexto(entrada, posicao)
if token is not None and not token.deve_ignorar:
tokens.append(token)
# Avança a posição e atualiza a contagem de linha/coluna
self.atualizar_posicao(entrada[posicao])
posicao += 1
return tokens
def _processar_caractere_em_contexto(self, entrada: str, posicao: int) -> Optional[Token]:
"""
Função principal de dispatch (despacho) baseada no estado atual.
O `switch` do Dart é substituído por um `match/case` (Python 3.10+) ou um dicionário/if-elif-else.
Usaremos o `if-elif-else` por ser universal no Python.
"""
# Captura o caractere a ser processado (necessário para as sub-funções)
caractere: str = entrada[posicao]
# Dispatch baseado no contexto atual (simulando o switch/case)
if self.contexto_atual == ContextoLexico.NORMAL:
# Estes métodos precisam ser implementados na classe
return self._processar_contexto_normal(caractere, posicao)
elif self.contexto_atual == ContextoLexico.DENTRO_STRING:
return self._processar_dentro_string(caractere, posicao)
elif self.contexto_atual == ContextoLexico.COMENTARIO_LINHA:
return self._processar_comentario_linha(caractere, posicao)
elif self.contexto_atual == ContextoLexico.COMENTARIO_BLOCO:
return self._processar_comentario_bloco(caractere, posicao)
else:
# Tratar ESCAPE_STRING e MAYBE_FIM_COMENTARIO, que geralmente
# não produzem tokens diretamente, mas mudam o estado.
# Se o caso for o MAYBE_FIM_COMENTARIO ou ESCAPE_STRING,
# a lógica de estado deve estar DENTRO do processador de seu pai.
return None
# --- Métodos de Processamento de Estado (Stubs/Exemplos) ---
# Estes métodos são apenas esboços (stubs), pois a lógica interna
# não estava definida no código Dart original.
def _processar_contexto_normal(self, c: str, pos: int) -> Optional[Token]:
# Exemplo de transição de estado: Iniciar um comentário de bloco
if c == '/' and pos + 1 < len(self.pilha_contexto) and self.pilha_contexto[pos + 1] == '*':
self.push_contexto(ContextoLexico.COMENTARIO_BLOCO)
# Retornar um token "Token de Início de Comentário" ou None/Ignorar
return Token(TokenType.WHITESPACE, c, pos, deve_ignorar=True)
# Lógica para IDENTIFICADORES, NÚMEROS, OPERADORES...
return None # Caso não haja token ou transição de estado
def _processar_dentro_string(self, c: str, pos: int) -> Optional[Token]:
# Exemplo: Encontrar o fim da string
if c == '"':
self.pop_contexto() # Sai do estado DENTRO_STRING
# Retorna o token STRING completo (o lexema seria construído)
# Exemplo: Encontrar um escape
elif c == '\\':
self.push_contexto(ContextoLexico.ESCAPE_STRING)
return None
def _processar_comentario_linha(self, c: str, pos: int) -> Optional[Token]:
if c == '\n':
self.pop_contexto() # Sai do estado COMENTARIO_LINHA
return None # O '\n' será processado pelo loop principal e `atualizar_posicao`
return None # Ignora o caractere do comentário
def _processar_comentario_bloco(self, c: str, pos: int) -> Optional[Token]:
# Exemplo de transição de estado: Possível fim do bloco
if c == '*':
self.push_contexto(ContextoLexico.MAYBE_FIM_COMENTARIO)
return Noneenum ContextoLexico {
NORMAL,
DENTRO_STRING,
ESCAPE_STRING,
COMENTARIO_LINHA,
COMENTARIO_BLOCO,
MAYBE_FIM_COMENTARIO
}
class LexerAvancado {
final List<ContextoLexico> pilhaContexto = [ContextoLexico.NORMAL];
int numeroLinha = 1;
int numeroColuna = 1;
ContextoLexico get contextoAtual => pilhaContexto.last;
void pushContexto(ContextoLexico novoContexto) {
pilhaContexto.add(novoContexto);
}
void popContexto() {
if (pilhaContexto.length > 1) {
pilhaContexto.removeLast();
}
}
List<Token> tokenizar(String entrada) {
List<Token> tokens = [];
int posicao = 0;
while (posicao < entrada.length) {
Token? token = processarCaractereEmContexto(entrada, posicao);
if (token != null && !token.deveIgnorar) {
tokens.add(token);
}
posicao++;
atualizarPosicao(entrada[posicao - 1]);
}
return tokens;
}
Token? processarCaractereEmContexto(String entrada, int posicao) {
switch (contextoAtual) {
case ContextoLexico.NORMAL:
return processarContextoNormal(entrada, posicao);
case ContextoLexico.DENTRO_STRING:
return processarDentroString(entrada, posicao);
case ContextoLexico.COMENTARIO_LINHA:
return processarComentarioLinha(entrada, posicao);
case ContextoLexico.COMENTARIO_BLOCO:
return processarComentarioBloco(entrada, posicao);
default:
return null;
}
}
void atualizarPosicao(String caractere) {
if (caractere == '\n') {
numeroLinha++;
numeroColuna = 1;
} else {
numeroColuna++;
}
}
}#include <stack>
#include <string>
#include <vector>
enum class ContextoLexico {
NORMAL,
DENTRO_STRING,
ESCAPE_STRING,
COMENTARIO_LINHA,
COMENTARIO_BLOCO,
MAYBE_FIM_COMENTARIO
};
class LexerAvancado {
private:
std::stack<ContextoLexico> pilhaContexto;
size_t numeroLinha = 1;
size_t numeroColuna = 1;
ContextoLexico contextoAtual() const {
return pilhaContexto.top();
}
void pushContexto(ContextoLexico novoContexto) {
pilhaContexto.push(novoContexto);
}
void popContexto() {
if (pilhaContexto.size() > 1) {
pilhaContexto.pop();
}
}
void atualizarPosicao(char caractere) {
if (caractere == '\n') {
numeroLinha++;
numeroColuna = 1;
} else {
numeroColuna++;
}
}
public:
LexerAvancado() {
pilhaContexto.push(ContextoLexico::NORMAL);
}
std::vector<Token> tokenizar(const std::string& entrada) {
std::vector<Token> tokens;
size_t posicao = 0;
while (posicao < entrada.length()) {
auto token = processarCaractereEmContexto(entrada, posicao);
if (token.has_value() && !token->deveIgnorar()) {
tokens.push_back(token.value());
}
atualizarPosicao(entrada[posicao]);
posicao++;
}
return tokens;
}
std::optional<Token> processarCaractereEmContexto(
const std::string& entrada, size_t posicao) {
switch (contextoAtual()) {
case ContextoLexico::NORMAL:
return processarContextoNormal(entrada, posicao);
case ContextoLexico::DENTRO_STRING:
return processarDentroString(entrada, posicao);
case ContextoLexico::COMENTARIO_LINHA:
return processarComentarioLinha(entrada, posicao);
case ContextoLexico::COMENTARIO_BLOCO:
return processarComentarioBloco(entrada, posicao);
default:
return std::nullopt;
}
}
};lexer_advanced.h
#ifndef LEXER_ADVANCED_H
#define LEXER_ADVANCED_H
#include <stddef.h>
#include <stdbool.h>
// --- 1. Tipos de Contexto (Estado) ---
typedef enum {
CONTEXT_NORMAL,
CONTEXT_DENTRO_STRING,
CONTEXT_ESCAPE_STRING,
CONTEXT_COMENTARIO_LINHA,
CONTEXT_COMENTARIO_BLOCO,
CONTEXT_MAYBE_FIM_COMENTARIO
} ContextoLexico;
// --- 2. Estrutura de Token (Assumindo um Lexer completo, como nos exemplos anteriores) ---
// Note que esta struct depende do seu Lexer real
typedef enum {
TOKEN_WHITESPACE, TOKEN_COMMENT, TOKEN_BLOCK_COMMENT,
TOKEN_STRING, TOKEN_IDENTIFIER, TOKEN_DELIMITER,
TOKEN_EOF, TOKEN_ERROR
} TokenType;
typedef struct {
TokenType type;
const char *lexema_start;
size_t length;
size_t posicao;
size_t linha;
size_t coluna;
bool ignore; // Substitui o `token->deveIgnorar()` do C++
} Token;
// --- 3. Estrutura do Lexer (Gerenciamento de Estado) ---
typedef struct {
ContextoLexico current_context; // Substitui a pilha para a maioria dos casos
// A pilha de contexto real só é necessária para aninhamento (não demonstrado aqui)
size_t numero_linha;
size_t numero_coluna;
} LexerAvancado;
// Funções públicas
void lexer_avancado_init(LexerAvancado *l);
// Retorna um array de Tokens (Aloca memória no heap!) - Mantenho a assinatura para compatibilidade
// Em C puro, é comum que esta função apenas preencha um buffer.
Token* lexer_avancado_tokenizar(const char *entrada, size_t *out_count);
#endif // LEXER_ADVANCED_Hlexer_advanced.c
#include "lexer_advanced.h"
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
// --- 4. Implementação das Funções Auxiliares (Otimizadas) ---
void lexer_avancado_init(LexerAvancado *l) {
// Inicializa o estado base
l->current_context = CONTEXT_NORMAL;
l->numero_linha = 1;
l->numero_coluna = 1;
}
static inline void atualizar_posicao(LexerAvancado *l, char caractere) {
if (caractere == '\n') {
l->numero_linha++;
l->numero_coluna = 1;
} else {
l->numero_coluna++;
}
}
// --- 5. Funções de Processamento de Contexto (Stubs) ---
// Retorna o próximo token encontrado, avançando a 'posicao'.
// Retorna 'true' se um token válido (não-ignorado) foi encontrado e preenchido.
static bool processar_contexto_normal(LexerAvancado *l, const char *entrada, size_t entrada_len, size_t *posicao, Token *out_token) {
char c = entrada[*posicao];
size_t start_pos = *posicao;
// Simplificando a lógica do AFD para mudar o estado baseado em 1 ou 2 caracteres
// Tentativa de Comentário de Linha
if (c == '/' && *posicao + 1 < entrada_len && entrada[*posicao + 1] == '/') {
l->current_context = CONTEXT_COMENTARIO_LINHA;
// O token será emitido quando o loop consumir o restante da linha.
// Neste ponto, apenas muda o estado.
}
// Tentativa de Comentário de Bloco
else if (c == '/' && *posicao + 1 < entrada_len && entrada[*posicao + 1] == '*') {
l->current_context = CONTEXT_COMENTARIO_BLOCO;
}
// Início de String
else if (c == '"') {
l->current_context = CONTEXT_DENTRO_STRING;
}
// Exemplo: Casamento de Delimitador Simples
else if (c == ';') {
out_token->type = TOKEN_DELIMITER;
out_token->lexema_start = entrada + start_pos;
out_token->length = 1;
out_token->ignore = false;
*posicao = start_pos; // O loop principal avançará
return true;
}
// Exemplo: Whitespace (para ser ignorado)
else if (c == ' ' || c == '\t' || c == '\n' || c == '\r') {
out_token->ignore = true;
}
// Nenhuma transição de contexto ou token imediato encontrado.
return false;
}
static bool processar_dentro_string(LexerAvancado *l, const char *entrada, size_t entrada_len, size_t *posicao, Token *out_token) {
// Implementação simplificada:
if (entrada[*posicao] == '"') {
l->current_context = CONTEXT_NORMAL;
// O token de string completo é emitido quando o contexto é encerrado.
// A lógica de extração real da string (que começou em 'inicio') é omitida aqui.
} else if (entrada[*posicao] == '\\') {
l->current_context = CONTEXT_ESCAPE_STRING;
}
return false; // Continua consumindo caracteres
}
static bool processar_comentario_linha(LexerAvancado *l, const char *entrada, size_t entrada_len, size_t *posicao, Token *out_token) {
if (entrada[*posicao] == '\n') {
l->current_context = CONTEXT_NORMAL;
out_token->ignore = true;
}
return false; // Continua consumindo caracteres
}
static bool processar_comentario_bloco(LexerAvancado *l, const char *entrada, size_t entrada_len, size_t *posicao, Token *out_token) {
if (entrada[*posicao] == '*') {
l->current_context = CONTEXT_MAYBE_FIM_COMENTARIO;
}
return false;
}
static bool processar_maybe_fim_comentario(LexerAvancado *l, const char *entrada, size_t entrada_len, size_t *posicao, Token *out_token) {
if (entrada[*posicao] == '/') {
l->current_context = CONTEXT_NORMAL;
out_token->ignore = true; // Comentário de bloco completo
} else if (entrada[*posicao] != '*') {
// Não era o fim, volta para o estado DENTRO_COMENTARIO_BLOCO
l->current_context = CONTEXT_COMENTARIO_BLOCO;
}
// Se for '*', permanece no estado MAYBE_FIM_COMENTARIO
return false;
}
// --- 6. Função de Roteamento (Main Dispatcher) ---
static bool processar_caractere_em_contexto(LexerAvancado *l, const char *entrada, size_t entrada_len, size_t *posicao, Token *out_token) {
// Armazena a posição inicial antes do avanço no contexto
out_token->posicao = *posicao;
out_token->linha = l->numero_linha;
out_token->coluna = l->numero_coluna;
bool token_found = false;
// Roteamento baseado no estado atual
switch (l->current_context) {
case CONTEXT_NORMAL:
token_found = processar_contexto_normal(l, entrada, entrada_len, posicao, out_token);
break;
case CONTEXT_DENTRO_STRING:
token_found = processar_dentro_string(l, entrada, entrada_len, posicao, out_token);
break;
case CONTEXT_COMENTARIO_LINHA:
token_found = processar_comentario_linha(l, entrada, entrada_len, posicao, out_token);
break;
case CONTEXT_COMENTARIO_BLOCO:
token_found = processar_comentario_bloco(l, entrada, entrada_len, posicao, out_token);
break;
case CONTEXT_MAYBE_FIM_COMENTARIO:
token_found = processar_maybe_fim_comentario(l, entrada, entrada_len, posicao, out_token);
break;
case CONTEXT_ESCAPE_STRING:
// Consome o caractere de escape, volta para DENTRO_STRING
l->current_context = CONTEXT_DENTRO_STRING;
break;
}
// Se o token foi encontrado e o contexto é NORMAL, ele é válido
return token_found && l->current_context == CONTEXT_NORMAL && !out_token->ignore;
}
// --- 7. Função Principal de Tokenização (Alocação Dinâmica) ---
Token* lexer_avancado_tokenizar(const char *entrada, size_t *out_count) {
LexerAvancado l;
lexer_avancado_init(&l);
size_t entrada_len = strlen(entrada);
size_t posicao = 0;
// Usa um vetor dinâmico (alocação) para armazenar os tokens
size_t max_tokens = entrada_len / 2; // Estimativa razoável
Token *tokens = (Token *)malloc(max_tokens * sizeof(Token));
size_t token_count = 0;
while (posicao < entrada_len) {
Token temp_token;
temp_token.ignore = false;
bool token_found = processar_caractere_em_contexto(&l, entrada, entrada_len, &posicao, &temp_token);
if (token_found) {
// Redimensiona o array se necessário (melhora de performance em C)
if (token_count >= max_tokens) {
max_tokens *= 2;
tokens = (Token *)realloc(tokens, max_tokens * sizeof(Token));
}
tokens[token_count++] = temp_token;
}
// Avance a posição (loop principal)
atualizar_posicao(&l, entrada[posicao]);
posicao++;
}
// Finaliza o token
if (token_count >= max_tokens) {
max_tokens++; // +1 para EOF
tokens = (Token *)realloc(tokens, max_tokens * sizeof(Token));
}
tokens[token_count++] = (Token){TOKEN_EOF, NULL, 0, l.numero_linha, l.numero_coluna, 0, false};
*out_count = token_count;
return tokens;
}Pilha de Contextos: A pilha permite aninhamento de contextos, o que é essencial para linguagens que suportam construtos como strings dentro de comentários ou comentários aninhados. Cada contexto na pilha representa um nível de processamento especializado.
Rastreamento de Posição: Manter informações precisas sobre linha e coluna é fundamental para mensagens de erro úteis. Usuários de compiladores dependem dessas informações para localizar rapidamente problemas em seu código.
🚨 Tratamento de Erros e Recuperação
O tratamento de erros em análise léxica é uma arte que equilibra precisão técnica com usabilidade prática. Um bom analisador léxico não apenas detecta erros - ele fornece diagnósticos úteis e tenta se recuperar graciosamente para continuar processando o resto do arquivo.
⚠️ Estratégias de Recuperação de Erros
---
displayMode: compact
config:
theme: forest
layout: elk
elk:
mergeEdges: true
nodePlacementStrategy: LINEAR_SEGMENTS
---
graph TD
A[❌ Erro Léxico Detectado] --> B{Tipo de Erro}
B -->|Caractere Inválido| C[🔍 Identificar Contexto]
C --> D[📝 Sugerir Correção]
D --> E[⏭️ Pular Caractere]
B -->|String Não Terminada| F[🔚 Assumir Fim da String]
F --> G[📢 Avisar sobre Aspas Faltantes]
B -->|Número Malformado| H[✂️ Truncar na Parte Válida]
H --> I[⚠️ Avisar sobre Formato]
E --> J[🔄 Continuar Análise]
G --> J
I --> J
J --> K{Mais Entrada?}
K -->|Sim| L[⚡ Processar Próximo Token]
K -->|Não| M[✅ Finalizar com Erros Reportados]
style A fill:#ffebee
style D fill:#e8f5e8
style G fill:#e8f5e8
style I fill:#e8f5e8
Implementação de Diagnósticos Inteligentes
Um analisador léxico profissional vai além de simplesmente reportar “caractere inválido”. Ele analisa o contexto e oferece sugestões construtivas.
from enum import Enum
from typing import List, Optional, Dict
from dataclasses import dataclass
# --- 1. Definição dos Tipos de Erro (Enum) ---
class TipoErro(Enum):
"""Tipos de erros léxicos que podem ser reportados."""
CARACTERE_INVALIDO = 'CARACTERE_INVALIDO'
STRING_NAO_TERMINADA = 'STRING_NAO_TERMINADA'
NUMERO_MALFORMADO = 'NUMERO_MALFORMADO'
COMENTARIO_NAO_TERMINADO = 'COMENTARIO_NAO_TERMINADO'
# --- 2. Classe de Diagnóstico (Dataclass) ---
@dataclass(frozen=True) # frozen=True simula a imutabilidade do `final` do Dart
class DiagnosticoLexico:
"""Registra um erro léxico, sua localização e uma possível sugestão."""
tipo: TipoErro
mensagem: str
linha: int
coluna: int
sugestao: Optional[str] = None # Simula o parâmetro opcional ([this.sugestao])
# --- 3. Classe Lexer com Capacidade de Diagnóstico ---
class LexerComDiagnosticos:
"""
Classe que gerencia e reporta erros léxicos usando a estrutura DiagnosticoLexico.
"""
# Usa uma lista para armazenar os diagnósticos (erros)
diagnosticos: List[DiagnosticoLexico]
# Mapeamento de caracteres para sugestão (compilado apenas uma vez)
_MAPA_SUBSTITUICOES: Dict[str, str] = {
'–': '-', # en-dash para hífen
'—': '-', # em-dash para hífen
'“': '"', # aspas curvas de abertura
'”': '"', # aspas curvas de fechamento
'‘': "'", # apóstrofes curvos de abertura
'’': "'", # apóstrofes curvos de fechamento
}
def __init__(self):
"""Inicializa a lista de diagnósticos."""
self.diagnosticos = []
def reportar_erro(self, tipo: TipoErro, contexto: str, linha: int, coluna: int):
"""
Gera a mensagem e a sugestão, e adiciona o diagnóstico à lista.
"""
mensagem: str = self._gerar_mensagem(tipo, contexto)
sugestao: Optional[str] = self._gerar_sugestao(tipo, contexto)
diagnostico = DiagnosticoLexico(tipo, mensagem, linha, coluna, sugestao)
self.diagnosticos.append(diagnostico)
def _gerar_mensagem(self, tipo: TipoErro, contexto: str) -> str:
"""
Cria a mensagem de erro detalhada.
Usaremos a estrutura if/elif/else (universal no Python) para o dispatch.
"""
if tipo == TipoErro.CARACTERE_INVALIDO:
return f"Caractere inválido '{contexto}' encontrado"
elif tipo == TipoErro.STRING_NAO_TERMINADA:
return "String iniciada mas não terminada"
elif tipo == TipoErro.NUMERO_MALFORMADO:
return f"Formato de número inválido: '{contexto}'"
elif tipo == TipoErro.COMENTARIO_NAO_TERMINADO:
return "Comentário de bloco não terminado"
else:
return f"Erro léxico desconhecido ({tipo.value}) no contexto '{contexto}'"
def _gerar_sugestao(self, tipo: TipoErro, contexto: str) -> Optional[str]:
"""
Gera uma sugestão de correção para o erro.
"""
if tipo == TipoErro.CARACTERE_INVALIDO:
return self._analisar_caractere_invalido(contexto)
elif tipo == TipoErro.STRING_NAO_TERMINADA:
return "Adicione aspas de fechamento (\") no final da string"
elif tipo == TipoErro.NUMERO_MALFORMADO:
return self._analisar_numero_malformado(contexto)
elif tipo == TipoErro.COMENTARIO_NAO_TERMINADO:
return "Adicione */ para fechar o comentário"
return None
def _analisar_caractere_invalido(self, caractere: str) -> Optional[str]:
"""
Sugere a substituição de caracteres unicode comuns por equivalentes ASCII.
"""
# Acesso ao mapeamento de substituições pré-compilado
substituicao: Optional[str] = self._MAPA_SUBSTITUICOES.get(caractere)
if substituicao is not None:
return f"Talvez você queira usar '{substituicao}'?"
return None
def _analisar_numero_malformado(self, numero: str) -> Optional[str]:
"""
Análise heurística básica para números malformados.
"""
if '..' in numero:
return "Números não podem ter múltiplos pontos decimais"
if numero.startswith('.'):
return f"Considere adicionar um zero antes do ponto: 0{numero}"
if numero.endswith('.'):
return f"Considere adicionar um zero depois do ponto: {numero}0"
return Noneclass DiagnosticoLexico {
final TipoErro tipo;
final String mensagem;
final int linha;
final int coluna;
final String? sugestao;
DiagnosticoLexico(this.tipo, this.mensagem, this.linha, this.coluna,
[this.sugestao]);
}
enum TipoErro {
CARACTERE_INVALIDO,
STRING_NAO_TERMINADA,
NUMERO_MALFORMADO,
COMENTARIO_NAO_TERMINADO
}
class LexerComDiagnosticos {
final List<DiagnosticoLexico> diagnosticos = [];
void reportarErro(TipoErro tipo, String contexto, int linha, int coluna) {
String mensagem = gerarMensagem(tipo, contexto);
String? sugestao = gerarSugestao(tipo, contexto);
diagnosticos.add(DiagnosticoLexico(tipo, mensagem, linha, coluna, sugestao));
}
String gerarMensagem(TipoErro tipo, String contexto) {
switch (tipo) {
case TipoErro.CARACTERE_INVALIDO:
return "Caractere inválido '${contexto}' encontrado";
case TipoErro.STRING_NAO_TERMINADA:
return "String iniciada mas não terminada";
case TipoErro.NUMERO_MALFORMADO:
return "Formato de número inválido: '${contexto}'";
case TipoErro.COMENTARIO_NAO_TERMINADO:
return "Comentário de bloco não terminado";
}
}
String? gerarSugestao(TipoErro tipo, String contexto) {
switch (tipo) {
case TipoErro.CARACTERE_INVALIDO:
return analisarCaractereInvalido(contexto);
case TipoErro.STRING_NAO_TERMINADA:
return "Adicione aspas de fechamento (\") no final da string";
case TipoErro.NUMERO_MALFORMADO:
return analisarNumeroMalformado(contexto);
case TipoErro.COMENTARIO_NAO_TERMINADO:
return "Adicione */ para fechar o comentário";
}
}
String? analisarCaractereInvalido(String caractere) {
// Análise inteligente de caracteres similares
Map<String, String> substituicoes = {
'–': '-', // en-dash para hífen
'—': '-', // em-dash para hífen
'"': '"', // aspas curvas para aspas retas
'"': '"',
''': "'", // apóstrofes curvos para retos
''': "'",
};
if (substituicoes.containsKey(caractere)) {
return "Talvez você queira usar '${substituicoes[caractere]}'?";
}
return null;
}
String? analisarNumeroMalformado(String numero) {
if (numero.contains('..')) {
return "Números não podem ter múltiplos pontos decimais";
}
if (numero.startsWith('.')) {
return "Considere adicionar um zero antes do ponto: 0${numero}";
}
if (numero.endsWith('.')) {
return "Considere adicionar um zero depois do ponto: ${numero}0";
}
return null;
}
}#include <string>
#include <vector>
#include <unordered_map>
#include <optional>
enum class TipoErro {
CARACTERE_INVALIDO,
STRING_NAO_TERMINADA,
NUMERO_MALFORMADO,
COMENTARIO_NAO_TERMINADO
};
struct DiagnosticoLexico {
TipoErro tipo;
std::string mensagem;
size_t linha;
size_t coluna;
std::optional<std::string> sugestao;
DiagnosticoLexico(TipoErro t, const std::string& m, size_t l, size_t c,
const std::optional<std::string>& s = std::nullopt)
: tipo(t), mensagem(m), linha(l), coluna(c), sugestao(s) {}
};
class LexerComDiagnosticos {
private:
std::vector<DiagnosticoLexico> diagnosticos;
std::string gerarMensagem(TipoErro tipo, const std::string& contexto) {
switch (tipo) {
case TipoErro::CARACTERE_INVALIDO:
return "Caractere inválido '" + contexto + "' encontrado";
case TipoErro::STRING_NAO_TERMINADA:
return "String iniciada mas não terminada";
case TipoErro::NUMERO_MALFORMADO:
return "Formato de número inválido: '" + contexto + "'";
case TipoErro::COMENTARIO_NAO_TERMINADO:
return "Comentário de bloco não terminado";
}
return "";
}
std::optional<std::string> gerarSugestao(TipoErro tipo,
const std::string& contexto) {
switch (tipo) {
case TipoErro::CARACTERE_INVALIDO:
return analisarCaractereInvalido(contexto);
case TipoErro::STRING_NAO_TERMINADA:
return "Adicione aspas de fechamento (\") no final da string";
case TipoErro::NUMERO_MALFORMADO:
return analisarNumeroMalformado(contexto);
case TipoErro::COMENTARIO_NAO_TERMINADO:
return "Adicione */ para fechar o comentário";
}
return std::nullopt;
}
std::optional<std::string> analisarCaractereInvalido(
const std::string& caractere) {
std::unordered_map<std::string, std::string> substituicoes = {
{"–", "-"}, // en-dash para hífen
{"—", "-"}, // em-dash para hífen
{""", "\""}, // aspas curvas para aspas retas
{""", "\""},
{"'", "'"}, // apóstrofes curvos para retos
{"'", "'"}
};
auto it = substituicoes.find(caractere);
if (it != substituicoes.end()) {
return "Talvez você queira usar '" + it->second + "'?";
}
return std::nullopt;
}
std::optional<std::string> analisarNumeroMalformado(
const std::string& numero) {
if (numero.find("..") != std::string::npos) {
return "Números não podem ter múltiplos pontos decimais";
}
if (numero.front() == '.') {
return "Considere adicionar um zero antes do ponto: 0" + numero;
}
if (numero.back() == '.') {
return "Considere adicionar um zero depois do ponto: " + numero + "0";
}
return std::nullopt;
}
public:
void reportarErro(TipoErro tipo, const std::string& contexto,
size_t linha, size_t coluna) {
std::string mensagem = gerarMensagem(tipo, contexto);
auto sugestao = gerarSugestao(tipo, contexto);
diagnosticos.emplace_back(tipo, mensagem, linha, coluna, sugestao);
}
const std::vector<DiagnosticoLexico>& obterDiagnosticos() const {
return diagnosticos;
}
};diagnostics.h
#ifndef DIAGNOSTICS_H
#define DIAGNOSTICS_H
#include <stddef.h>
#include <stdbool.h>
// Tamanho máximo do lexema de contexto para mensagens de erro (ex: "caractere inválido 'X'")
#define MAX_CONTEXT_LEN 32
// Tamanho máximo da string de mensagem ou sugestão de erro
#define MAX_MESSAGE_LEN 128
// Número máximo de diagnósticos que o lexer pode armazenar antes de parar
#define MAX_DIAGNOSTICS 64
// --- 1. Enumeração de Tipos de Erro ---
typedef enum {
ERRO_CARACTERE_INVALIDO,
ERRO_STRING_NAO_TERMINADA,
ERRO_NUMERO_MALFORMADO,
ERRO_COMENTARIO_NAO_TERMINADO
} TipoErro;
// --- 2. Estrutura de Diagnóstico (Sem alocação de heap por diagnóstico) ---
typedef struct {
TipoErro tipo;
char mensagem[MAX_MESSAGE_LEN];
size_t linha;
size_t coluna;
bool tem_sugestao;
char sugestao[MAX_MESSAGE_LEN]; // Sugestão armazenada em buffer fixo
} DiagnosticoLexico;
// --- 3. Estrutura do Lexer com Diagnósticos ---
typedef struct {
DiagnosticoLexico diagnosticos[MAX_DIAGNOSTICS]; // Array de tamanho fixo
size_t count;
} LexerComDiagnosticos;
// Funções públicas
void lexer_diag_init(LexerComDiagnosticos *l);
// Reporta um erro, gerando a mensagem e sugestão internamente
void lexer_diag_reportar_erro(LexerComDiagnosticos *l, TipoErro tipo,
const char *contexto, size_t linha, size_t coluna);
// Retorna o array estático de diagnósticos
DiagnosticoLexico* lexer_diag_obter_diagnosticos(LexerComDiagnosticos *l, size_t *out_count);
#endif // DIAGNOSTICS_Hdiagnistics.c
#include "diagnostics.h"
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
// --- 4. Tabela Estática de Substituições Comuns (Otimização) ---
typedef struct {
const char *invalido;
const char *sugerido;
} SugestaoCaractere;
// Substitui o std::unordered_map
static const SugestaoCaractere SUBSTITUICOES_COMUNS[] = {
{"–", "-"}, // en-dash para hífen
{"—", "-"}, // em-dash para hífen
{"“", "\""}, // aspas curvas esquerdas para aspas retas
{"”", "\""}, // aspas curvas direitas para aspas retas
{"‘", "'"}, // apóstrofo curvo esquerdo
{"’", "'"} // apóstrofo curvo direito
};
static const size_t NUM_SUBSTITUICOES = sizeof(SUBSTITUICOES_COMUNS) / sizeof(SUBSTITUICOES_COMUNS[0]);
// --- 5. Lógica de Geração de Mensagens e Sugestões (Otimizada) ---
// Gera a mensagem de erro formatada no buffer `out_msg`
static void gerar_mensagem(TipoErro tipo, const char *contexto, char *out_msg) {
switch (tipo) {
case ERRO_CARACTERE_INVALIDO:
snprintf(out_msg, MAX_MESSAGE_LEN, "Caractere inválido '%s' encontrado", contexto);
break;
case ERRO_STRING_NAO_TERMINADA:
snprintf(out_msg, MAX_MESSAGE_LEN, "String iniciada mas não terminada");
break;
case ERRO_NUMERO_MALFORMADO:
snprintf(out_msg, MAX_MESSAGE_LEN, "Formato de número inválido: '%s'", contexto);
break;
case ERRO_COMENTARIO_NAO_TERMINADO:
snprintf(out_msg, MAX_MESSAGE_LEN, "Comentário de bloco não terminado");
break;
default:
snprintf(out_msg, MAX_MESSAGE_LEN, "Erro léxico desconhecido");
}
}
static bool analisar_caractere_invalido(const char *contexto, char *out_sugestao) {
// Lookup de sugestão por iteração (rápido em C para arrays pequenos)
for (size_t i = 0; i < NUM_SUBSTITUICOES; i++) {
if (strcmp(contexto, SUBSTITUICOES_COMUNS[i].invalido) == 0) {
snprintf(out_sugestao, MAX_MESSAGE_LEN,
"Talvez você queira usar '%s'?", SUBSTITUICOES_COMUNS[i].sugerido);
return true;
}
}
return false;
}
static bool analisar_numero_malformado(const char *numero, char *out_sugestao) {
// Substitui a busca por std::string::npos e front()/back() por strstr e ponteiros
// Múltiplos pontos
if (strstr(numero, "..") != NULL) {
snprintf(out_sugestao, MAX_MESSAGE_LEN, "Números não podem ter múltiplos pontos decimais");
return true;
}
// Começa com ponto (ex: ".5")
if (numero[0] == '.') {
snprintf(out_sugestao, MAX_MESSAGE_LEN, "Considere adicionar um zero antes do ponto: 0%s", numero);
return true;
}
// Termina com ponto (ex: "5.")
size_t len = strlen(numero);
if (len > 0 && numero[len - 1] == '.') {
snprintf(out_sugestao, MAX_MESSAGE_LEN, "Considere adicionar um zero depois do ponto: %s0", numero);
return true;
}
return false;
}
static bool gerar_sugestao(TipoErro tipo, const char *contexto, char *out_sugestao) {
switch (tipo) {
case ERRO_CARACTERE_INVALIDO:
return analisar_caractere_invalido(contexto, out_sugestao);
case ERRO_STRING_NAO_TERMINADA:
snprintf(out_sugestao, MAX_MESSAGE_LEN, "Adicione aspas de fechamento (\") no final da string");
return true;
case ERRO_COMENTARIO_NAO_TERMINADO:
snprintf(out_sugestao, MAX_MESSAGE_LEN, "Adicione */ para fechar o comentário");
return true;
case ERRO_NUMERO_MALFORMADO:
return analisar_numero_malformado(contexto, out_sugestao);
}
return false;
}
// --- 6. Funções de Interface ---
void lexer_diag_init(LexerComDiagnosticos *l) {
l->count = 0;
}
void lexer_diag_reportar_erro(LexerComDiagnosticos *l, TipoErro tipo,
const char *contexto, size_t linha, size_t coluna) {
if (l->count >= MAX_DIAGNOSTICS) {
// Log de erro: buffer de diagnósticos cheio
return;
}
DiagnosticoLexico *diag = &l->diagnosticos[l->count];
// 1. Preenche dados básicos
diag->tipo = tipo;
diag->linha = linha;
diag->coluna = coluna;
// 2. Gera Mensagem (snprintf)
gerar_mensagem(tipo, contexto, diag->mensagem);
// 3. Gera Sugestão (snprintf e bool)
diag->tem_sugestao = gerar_sugestao(tipo, contexto, diag->sugestao);
l->count++;
}
DiagnosticoLexico* lexer_diag_obter_diagnosticos(LexerComDiagnosticos *l, size_t *out_count) {
*out_count = l->count;
return l->diagnosticos; // Retorna o ponteiro para o array estático
}Análise Contextual de Erros: O analisador examina não apenas o caractere problemático, mas o contexto ao redor para fornecer sugestões mais precisas. Por exemplo, detectar que o usuário pode ter usado aspas curvas ao invés de aspas retas.
Recuperação Inteligente: Ao invés de parar no primeiro erro, o analisador tenta continuar processando, aplicando heurísticas para “adivinhar” a intenção do programador e continuar a análise.
🔧 Ferramentas de Geração Automática
A construção manual de analisadores léxicos, embora educativa, é trabalhosa e propensa a erros para linguagens complexas. Felizmente, existem ferramentas poderosas que automatizam este processo, gerando código eficiente a partir de especificações de alto nível.
🛠️ LEX/Flex: O Padrão da Indústria
LEX e sua implementação moderna Flex são geradores de analisadores léxicos que transformam especificações baseadas em expressões regulares em código C eficiente. Aqui está um exemplo de especificação Flex para uma linguagem simples:
%{
#include <stdio.h>
#include <stdlib.h>
#include "tokens.h"
%}
DIGIT [0-9]
LETTER [a-zA-Z]
ID {LETTER}({LETTER}|{DIGIT})*
INTEGER {DIGIT}+
REAL {DIGIT}+\.{DIGIT}+
STRING \"[^\"]*\"
%%
{INTEGER} { yylval.num = atoi(yytext); return TOKEN_INTEGER; }
{REAL} { yylval.real = atof(yytext); return TOKEN_REAL; }
{STRING} { yylval.str = strdup(yytext); return TOKEN_STRING; }
{ID} { return lookup_keyword(yytext); }
"if" { return TOKEN_IF; }
"while" { return TOKEN_WHILE; }
"else" { return TOKEN_ELSE; }
"+" { return TOKEN_PLUS; }
"-" { return TOKEN_MINUS; }
"*" { return TOKEN_MULT; }
"/" { return TOKEN_DIV; }
"(" { return TOKEN_LPAREN; }
")" { return TOKEN_RPAREN; }
"{" { return TOKEN_LBRACE; }
"}" { return TOKEN_RBRACE; }
[ \t\n]+ { /* ignore whitespace */ }
. { printf("Unexpected character: %c\n", yytext[0]); }
%%
int yywrap() {
return 1;
}Esta especificação é compilada pelo Flex em um arquivo C contendo um analisador léxico completo e otimizado.
Vantagens e Limitações das Ferramentas Automáticas
Vantagens das Ferramentas Automáticas:
- Eficiência de Desenvolvimento: Reduzem drasticamente o tempo necessário para implementar analisadores léxicos
- Otimização Automática: Geram código altamente otimizado com técnicas avançadas de otimização
- Correção Garantida: Eliminam bugs comuns em implementações manuais
- Manutenibilidade: Mudanças na especificação são facilmente incorporadas
Limitações e Considerações:
- Controle Limitado: Menos flexibilidade para otimizações específicas ou comportamentos personalizados
- Dependência Externa: Adiciona uma ferramenta ao pipeline de build
- Curva de Aprendizado: Requer conhecimento da sintaxe específica da ferramenta
- Debugging: Pode ser mais difícil debuggar código gerado automaticamente
📈 Otimização e Performance
A performance da análise léxica tem impacto direto na velocidade de compilação. Para compiladores que processam grandes bases de código, otimizações na análise léxica podem resultar em melhorias significativas no tempo total de compilação.
⚡ Técnicas de Otimização Avançadas
---
displayMode: compact
config:
theme: forest
layout: elk
elk:
mergeEdges: true
nodePlacementStrategy: LINEAR_SEGMENTS
---
graph LR
A[📖 Arquivo Fonte] --> B[🔄 Buffer Circular]
B --> C[🎯 Look-ahead Buffer]
C --> D[🏎️ DFA Otimizado]
D --> E[🗂️ Tabela Hash<br/>Palavras-chave]
E --> F[📤 Stream de Tokens]
G[💾 Cache de Caracteres] -.-> B
H[🔍 Predição de Branch] -.-> D
I[⚡ SIMD Processing] -.-> D
style B fill:#e8f5e8
style D fill:#e8f5e8
style E fill:#e8f5e8
Implementação de Buffers Eficientes
O gerenciamento eficiente de entrada é fundamental para performance. Técnicas como buffering duplo e look-ahead otimizado podem melhorar significativamente a velocidade de processamento.
import asyncio
import aiofiles
from math import min as math_min
class BufferConstants:
TAMANHO_BUFFER = 8192
TAMANHO_LOOKAHEAD = 256
class BufferOtimizadoAsync:
"""
Implementa um buffer duplo assíncrono usando asyncio e aiofiles.
Lê o arquivo em blocos (streaming), mantendo suporte a lookahead limitado.
"""
TAMANHO_BUFFER = BufferConstants.TAMANHO_BUFFER
TAMANHO_LOOKAHEAD = BufferConstants.TAMANHO_LOOKAHEAD
def __init__(self, arquivo_path: str):
self.arquivo_path = arquivo_path
self.buffer1 = bytearray(self.TAMANHO_BUFFER + self.TAMANHO_LOOKAHEAD)
self.buffer2 = bytearray(self.TAMANHO_BUFFER + self.TAMANHO_LOOKAHEAD)
self.buffer_ativo = self.buffer1
self.buffer_secundario = self.buffer2
self.posicao_buffer = 0
self.tamanho_valido = 0
self.fim_arquivo = False
self._arquivo = None
async def __aenter__(self):
self._arquivo = await aiofiles.open(self.arquivo_path, mode='rb')
await self._carregar_proximo_buffer()
return self
async def __aexit__(self, exc_type, exc, tb):
await self._arquivo.close()
async def proximo_caractere(self) -> int:
"""Retorna o próximo byte (0–255) ou -1 se EOF."""
if self.posicao_buffer >= self.tamanho_valido:
if self.fim_arquivo:
return -1
await self._trocar_buffers()
await self._carregar_proximo_buffer()
if self.tamanho_valido == 0:
self.fim_arquivo = True
return -1
byte_lido = self.buffer_ativo[self.posicao_buffer]
self.posicao_buffer += 1
return byte_lido
def espiar_caractere(self, offset: int) -> int:
"""Olha bytes à frente sem consumir."""
pos_futura = self.posicao_buffer + offset
if 0 <= pos_futura < self.tamanho_valido:
return self.buffer_ativo[pos_futura]
return -1
async def _trocar_buffers(self):
bytes_lookahead = math_min(
self.TAMANHO_LOOKAHEAD,
self.tamanho_valido - self.posicao_buffer,
)
self.buffer_secundario[:bytes_lookahead] = \
self.buffer_ativo[self.posicao_buffer:self.posicao_buffer + bytes_lookahead]
self.buffer_ativo, self.buffer_secundario = \
self.buffer_secundario, self.buffer_ativo
self.posicao_buffer = bytes_lookahead
self.tamanho_valido = bytes_lookahead
async def _carregar_proximo_buffer(self):
"""Lê o próximo bloco de bytes de forma assíncrona."""
try:
novos_bytes = await self._arquivo.read(self.TAMANHO_BUFFER)
if not novos_bytes:
self.fim_arquivo = True
return
self.buffer_ativo[self.tamanho_valido:self.tamanho_valido + len(novos_bytes)] = novos_bytes
self.tamanho_valido += len(novos_bytes)
except Exception as e:
print(f"Erro de I/O: {e}")
self.fim_arquivo = True
# --- Exemplo de uso ---
async def main():
nome_arquivo = "teste_stream.txt"
with open(nome_arquivo, 'w', encoding='utf-8') as f:
f.write("ABCDEFGHIJKLMNOPQRSTUVWXYZ")
async with BufferOtimizadoAsync(nome_arquivo) as buffer:
print("Lendo 5 caracteres:")
for _ in range(5):
c = await buffer.proximo_caractere()
if c != -1:
print(chr(c), end='')
print()
print("Espiando caracteres seguintes:")
print(chr(buffer.espiar_caractere(0)))
print(chr(buffer.espiar_caractere(1)))
import os
os.remove(nome_arquivo)
if __name__ == '__main__':
asyncio.run(main())import 'dart:async';
import 'dart:io';
import 'dart:typed_data';
import 'dart:math';
class BufferOtimizadoStream {
static const int TAMANHO_BUFFER = 8192;
static const int TAMANHO_LOOKAHEAD = 256;
final Stream<List<int>> stream;
late StreamSubscription<List<int>> _assinatura;
final List<int> _filaBytes = [];
late Uint8List buffer1;
late Uint8List buffer2;
late Uint8List bufferAtivo;
late Uint8List bufferSecundario;
int posicaoBuffer = 0;
int tamanhoValido = 0;
bool fimArquivo = false;
bool _carregando = false;
BufferOtimizadoStream(File arquivo)
: stream = arquivo.openRead() {
buffer1 = Uint8List(TAMANHO_BUFFER + TAMANHO_LOOKAHEAD);
buffer2 = Uint8List(TAMANHO_BUFFER + TAMANHO_LOOKAHEAD);
bufferAtivo = buffer1;
bufferSecundario = buffer2;
_assinatura = stream.listen(
(dados) => _filaBytes.addAll(dados),
onDone: () => fimArquivo = true,
onError: (_) => fimArquivo = true,
cancelOnError: true,
);
}
Future<int> proximoCaractere() async {
if (posicaoBuffer >= tamanhoValido) {
if (fimArquivo && _filaBytes.isEmpty) return -1;
await _carregarProximoBuffer();
if (tamanhoValido == 0) {
fimArquivo = true;
return -1;
}
}
return bufferAtivo[posicaoBuffer++];
}
int espiarCaractere(int offset) {
int posicaoFutura = posicaoBuffer + offset;
if (posicaoFutura < tamanhoValido) {
return bufferAtivo[posicaoFutura];
}
return -1; // Implementar lookahead mais complexo se quiser
}
Future<void> _carregarProximoBuffer() async {
if (_carregando) return;
_carregando = true;
// Move os bytes de lookahead
int bytesLookahead = min(TAMANHO_LOOKAHEAD, tamanhoValido - posicaoBuffer);
bufferSecundario.setRange(0, bytesLookahead, bufferAtivo, posicaoBuffer);
// Troca buffers
var temp = bufferAtivo;
bufferAtivo = bufferSecundario;
bufferSecundario = temp;
posicaoBuffer = 0;
tamanhoValido = bytesLookahead;
// Preenche o resto com dados da fila
while (_filaBytes.isEmpty && !fimArquivo) {
await Future.delayed(const Duration(milliseconds: 1));
}
int bytesParaLer = min(TAMANHO_BUFFER, _filaBytes.length);
if (bytesParaLer > 0) {
bufferAtivo.setRange(tamanhoValido, tamanhoValido + bytesParaLer, _filaBytes);
_filaBytes.removeRange(0, bytesParaLer);
tamanhoValido += bytesParaLer;
}
_carregando = false;
}
Future<void> fechar() async {
await _assinatura.cancel();
}
}#include <vector>
#include <fstream>
#include <algorithm>
class BufferOtimizado {
private:
static constexpr size_t TAMANHO_BUFFER = 8192;
static constexpr size_t TAMANHO_LOOKAHEAD = 256;
std::ifstream& arquivo;
std::vector<char> buffer1;
std::vector<char> buffer2;
std::vector<char>* bufferAtivo;
std::vector<char>* bufferSecundario;
size_t posicaoBuffer = 0;
size_t tamanhoValido = 0;
bool fimArquivo = false;
void trocarBuffers() {
// Copia look-ahead do buffer atual para o início do próximo
size_t bytesLookahead = std::min(TAMANHO_LOOKAHEAD,
tamanhoValido - posicaoBuffer);
std::copy(bufferAtivo->begin() + posicaoBuffer,
bufferAtivo->begin() + posicaoBuffer + bytesLookahead,
bufferSecundario->begin());
// Troca os buffers
std::swap(bufferAtivo, bufferSecundario);
posicaoBuffer = 0;
tamanhoValido = bytesLookahead;
}
void carregarProximoBuffer() {
arquivo.read(bufferAtivo->data() + tamanhoValido, TAMANHO_BUFFER);
size_t bytesLidos = arquivo.gcount();
tamanhoValido += bytesLidos;
if (bytesLidos < TAMANHO_BUFFER) {
fimArquivo = true;
}
}
public:
BufferOtimizado(std::ifstream& arq) : arquivo(arq) {
buffer1.resize(TAMANHO_BUFFER + TAMANHO_LOOKAHEAD);
buffer2.resize(TAMANHO_BUFFER + TAMANHO_LOOKAHEAD);
bufferAtivo = &buffer1;
bufferSecundario = &buffer2;
carregarProximoBuffer();
}
int proximoCaractere() {
if (posicaoBuffer >= tamanhoValido) {
if (fimArquivo) return -1; // EOF
trocarBuffers();
carregarProximoBuffer();
if (tamanhoValido == 0) {
fimArquivo = true;
return -1;
}
}
return static_cast<unsigned char>((*bufferAtivo)[posicaoBuffer++]);
}
int espiarCaractere(size_t offset) {
size_t posicaoFutura = posicaoBuffer + offset;
if (posicaoFutura < tamanhoValido) {
return static_cast<unsigned char>((*bufferAtivo)[posicaoFutura]);
}
// Implementar lógica de look-ahead mais complexa
return -1;
}
};double_buffer.h
#ifndef DOUBLE_BUFFER_H
#define DOUBLE_BUFFER_H
#include <stdio.h>
#include <stddef.h>
#include <stdbool.h>
// --- 1. Constantes de Bufferização ---
#define TAMANHO_BUFFER 8192 // Tamanho do bloco principal de leitura
#define TAMANHO_LOOKAHEAD 256 // Tamanho do lookahead copiado entre buffers
#define BUFFER_TOTAL_SIZE (TAMANHO_BUFFER + TAMANHO_LOOKAHEAD)
// --- 2. Estrutura do Buffer (Substitui a classe C++) ---
typedef struct {
FILE *arquivo; // Substitui std::ifstream&
char *buffer1;
char *buffer2;
char *buffer_ativo; // Ponteiro para o buffer que está sendo lido
char *buffer_secundario; // Ponteiro para o outro buffer
size_t posicao_buffer; // Posição atual de leitura no buffer_ativo
size_t tamanho_valido; // Quantidade de dados válidos em buffer_ativo
bool fim_arquivo;
} BufferOtimizado;
// Funções públicas
bool buffer_init(BufferOtimizado *b, const char *nome_arquivo);
int buffer_proximo_caractere(BufferOtimizado *b);
int buffer_espiar_caractere(BufferOtimizado *b, size_t offset);
void buffer_destroy(BufferOtimizado *b);
#endif // DOUBLE_BUFFER_Hdouble_buffer.c
#include "double_buffer.h"
#include <stdlib.h>
#include <string.h>
#include <unistd.h> // Para posix_memalign ou malloc
#include <errno.h>
// --- 3. Funções de Gerenciamento de Buffer (Privadas) ---
// Carrega o próximo bloco de dados para o buffer ativo, a partir de tamanho_valido
static void carregar_proximo_bloco(BufferOtimizado *b) {
// Tenta ler o restante do TAMANHO_BUFFER no espaço disponível
size_t bytes_to_read = TAMANHO_BUFFER;
// fread é mais comum em C padrão, mas funções POSIX como read() podem ser mais rápidas
size_t bytes_lidos = fread(b->buffer_ativo + b->tamanho_valido, 1, bytes_to_read, b->arquivo);
b->tamanho_valido += bytes_lidos;
// Se menos bytes foram lidos do que o tamanho do bloco, é o fim do arquivo
if (bytes_lidos < bytes_to_read) {
b->fim_arquivo = true;
// Preenche o restante com um caractere EOF virtual (se necessário)
// memset(b->buffer_ativo + b->tamanho_valido, 0, BUFFER_TOTAL_SIZE - b->tamanho_valido);
}
}
// Troca os buffers e copia o lookahead (Core do Double Buffering)
static void trocar_buffers(BufferOtimizado *b) {
// 1. Calcula o look-ahead
// O Look-ahead é a parte não consumida do buffer ativo (do início da posição até o final)
size_t bytes_disponiveis = b->tamanho_valido - b->posicao_buffer;
size_t bytes_lookahead = (bytes_disponiveis < TAMANHO_LOOKAHEAD) ? bytes_disponiveis : TAMANHO_LOOKAHEAD;
// 2. Copia look-ahead (std::copy -> memmove/memcpy em C)
// Copia do buffer ativo (b->posicao_buffer) para o início do secundário
memmove(b->buffer_secundario,
b->buffer_ativo + b->posicao_buffer,
bytes_lookahead);
// 3. Troca os ponteiros
char *temp = b->buffer_ativo;
b->buffer_ativo = b->buffer_secundario;
b->buffer_secundario = temp;
// 4. Reinicia o estado
b->posicao_buffer = 0;
b->tamanho_valido = bytes_lookahead; // O tamanho válido inicial é o lookahead copiado
}
// --- 4. Funções de Interface (Públicas) ---
bool buffer_init(BufferOtimizado *b, const char *nome_arquivo) {
// 1. Abre o arquivo
b->arquivo = fopen(nome_arquivo, "rb"); // Leitura binária para eficiência
if (!b->arquivo) {
perror("Erro ao abrir arquivo");
return false;
}
// 2. Aloca buffers (Substitui std::vector<char>)
// Usamos malloc para alocar na heap
b->buffer1 = (char*)malloc(BUFFER_TOTAL_SIZE * sizeof(char));
b->buffer2 = (char*)malloc(BUFFER_TOTAL_SIZE * sizeof(char));
if (!b->buffer1 || !b->buffer2) {
fclose(b->arquivo);
return false;
}
// 3. Inicializa o estado
b->buffer_ativo = b->buffer1;
b->buffer_secundario = b->buffer2;
b->posicao_buffer = 0;
b->tamanho_valido = 0;
b->fim_arquivo = false;
// 4. Carrega o primeiro buffer
carregar_proximo_bloco(b);
// Carrega o segundo buffer em paralelo (otimização de I/O)
// Para simplificar, o código C padrão carrega serialmente,
// mas na primeira troca (trocar_buffers), o carregar_proximo_bloco carregará o segundo buffer.
return true;
}
void buffer_destroy(BufferOtimizado *b) {
if (b->arquivo) fclose(b->arquivo);
if (b->buffer1) free(b->buffer1);
if (b->buffer2) free(b->buffer2);
// Limpar ponteiros para evitar dangling pointers
b->buffer1 = b->buffer2 = NULL;
b->buffer_ativo = b->buffer_secundario = NULL;
}
int buffer_proximo_caractere(BufferOtimizado *b) {
// Se a posição no buffer ativo chegou ao fim dos dados válidos:
if (b->posicao_buffer >= b->tamanho_valido) {
if (b->fim_arquivo && b->tamanho_valido == 0) {
return -1; // EOF final
}
// 1. Troca de buffers: move lookahead do ativo para o secundário e troca os ponteiros
trocar_buffers(b);
// 2. Carrega o novo bloco no buffer secundário (que agora é o buffer ativo antigo)
carregar_proximo_bloco(b);
// 3. Verifica se a carga resultou em dados
if (b->tamanho_valido == 0) {
b->fim_arquivo = true;
return -1;
}
}
// Retorna o caractere e avança a posição
// Retorna o char como int (unsigned char) para garantir que -1 seja único para EOF
return (unsigned char)b->buffer_ativo[b->posicao_buffer++];
}
int buffer_espiar_caractere(BufferOtimizado *b, size_t offset) {
size_t posicao_futura = b->posicao_buffer + offset;
// Se o lookahead está dentro dos dados válidos do buffer ativo
if (posicao_futura < b->tamanho_valido) {
return (unsigned char)b->buffer_ativo[posicao_futura];
}
// Implementação C++ original falhava aqui.
// Otimização C: Se a posição for pequena o suficiente para o lookahead,
// o caractere estaria no início do buffer_secundario após a troca.
// Se o offset é pequeno (dentro do lookahead copiado no próximo buffer),
// o caractere já deveria estar lá se a lógica do proximoCaractere fosse chamada.
// Para simplificar, assumimos que lookahead está sempre dentro do buffer_ativo.
return -1;
}Buffer Duplo: A técnica de buffer duplo permite leitura contínua sem pausas para I/O. Enquanto um buffer está sendo processado, o outro está sendo carregado em background.
Look-ahead Eficiente: Manter um buffer de look-ahead permite que o analisador examine caracteres futuros sem comprometer a performance, essencial para implementar corretamente o princípio da correspondência mais longa.
🌐 Considerações Modernas: Unicode e Internacionalização
Compiladores modernos devem suportar Unicode completo, permitindo identificadores em múltiplos idiomas e processamento correto de strings internationalizadas. Isso adiciona complexidades interessantes à análise léxica.
🌍 Suporte a Unicode e Múltiplos Idiomas
Unicode introduz várias complexidades que analisadores léxicos tradicionais baseados em ASCII não precisavam considerar:
Codificação de Caracteres: UTF-8, UTF-16, UTF-32 cada uma com suas peculiaridades de decodificação Caracteres Multi-byte: Um único “caractere” pode ocupar 1-4 bytes em UTF-8 Normalização: O mesmo caractere pode ter múltiplas representações Unicode Categorias de Caracteres: Unicode define categorias como Letter, Number, Symbol que devem ser respeitadas Direção de Texto: Alguns idiomas são escritos da direita para esquerda
---
displayMode: compact
config:
theme: forest
layout: elk
elk:
mergeEdges: true
nodePlacementStrategy: LINEAR_SEGMENTS
---
graph TD
A[📄 Arquivo Fonte UTF-8] --> B[🔍 Detector de BOM]
B --> C[📖 Decodificador UTF-8]
C --> D[🔤 Normalizador Unicode]
D --> E[📊 Categorizador de Caracteres]
E --> F[🏷️ Gerador de Tokens]
G[🌐 Tabelas Unicode] -.-> E
H[📚 Regras de Normalização] -.-> D
style C fill:#e8f5e8
style D fill:#fff3e0
style E fill:#e3f2fd
Implementação de Suporte Unicode
import codecs
import re
import unicodedata
from typing import List, Optional, Dict
from dataclasses import dataclass
from enum import Enum
# --- Dependências (Assumidas) ---
class TokenType(Enum):
IDENTIFICADOR = 'IDENTIFICADOR'
IF = 'IF'
ELSE = 'ELSE'
WHILE = 'WHILE'
FUNCTION = 'FUNCTION'
# ... outros
@dataclass(frozen=True)
class Token:
tipo: TokenType
lexema: str
posicao: int
# --- Fim das Dependências ---
class UnicodeTokenizer:
"""
Lida com a inicialização de arquivos, detecção de BOM e tokenização
de identificadores com suporte a Unicode e Normalização (NFC).
"""
# Constante para BOM UTF-8 (Python lida com isso na decodificação)
BOM_UTF8: int = 0xEFBBBF
# Em Python, o StringBuffer é frequentemente substituído por uma lista de strings e join.
buffer_atual: List[str]
entrada: str = "" # A string decodificada
posicao: int = 0
def __init__(self):
"""Inicializa o tokenizer."""
self.buffer_atual = []
def inicializar(self, bytes_arquivo: bytes) -> bool:
"""
Decodifica os bytes do arquivo para string, tratando o BOM.
Em Python, o módulo `codecs` ou `bytes.decode()` lida
automaticamente com o BOM UTF-8 (se iniciado com 'utf-8-sig').
"""
# Em Python, bytes.decode() com 'utf-8-sig' lida com o BOM UTF-8 automaticamente.
# Isso otimiza o código, removendo a detecção manual do BOM em Dart.
try:
self.entrada = bytes_arquivo.decode('utf-8-sig', errors='strict')
return True
except UnicodeDecodeError as e:
# O parâmetro `allowMalformed: false` do Dart é o padrão 'strict' do Python
print(f'Erro de codificação UTF-8: {e}')
return False
# --- Funções de Validação de Identificador (Otimizadas para `re.UNICODE`) ---
# No Python padrão (`re`), a sintaxe \p{L}, \p{Nl}, etc. não é suportada.
# Otimizamos usando `\w` com a flag re.UNICODE, que cobre a maioria dos casos.
# Para suporte completo a categorias específicas, seria necessário o módulo 'regex'.
# Otimização: A decodificação de `codePoint` para `str` é cara.
# Usamos o `re.match` para checagem rápida em Python.
def eh_inicio_identificador(self, caractere: str) -> bool:
"""
Verifica se o caractere é válido para o início de um identificador
(letra ou sublinhado). Usamos re.UNICODE.
"""
# [a-zA-Z_] (letras ASCII) ou \w (letras Unicode, dígitos, sublinhado)
# A flag re.UNICODE permite que \w inclua letras Unicode.
# Esta é a simplificação necessária.
return bool(re.match(r'[a-zA-Z_]', caractere, re.UNICODE) or
re.match(r'\w', caractere, re.UNICODE) and not caractere.isdigit())
def eh_continuacao_identificador(self, caractere: str) -> bool:
"""
Verifica se o caractere é válido para continuação de identificador
(letras, dígitos, conectores/sublinhado).
"""
return bool(re.match(r'\w', caractere, re.UNICODE))
# --- Processamento ---
def processar_identificador_unicode(self) -> Optional[Token]:
"""
Processa o identificador mais longo possível a partir da posição atual.
"""
inicio: int = self.posicao
entrada_len: int = len(self.entrada)
if self.posicao >= entrada_len:
return None
primeiro_caractere: str = self.entrada[self.posicao]
if not self.eh_inicio_identificador(primeiro_caractere):
return None
self.buffer_atual.clear()
self.buffer_atual.append(primeiro_caractere)
self.posicao += 1
while self.posicao < entrada_len:
caractere_atual: str = self.entrada[self.posicao]
if not self.eh_continuacao_identificador(caractere_atual):
break
self.buffer_atual.append(caractere_atual)
self.posicao += 1
# Otimização: Junta a lista de strings (buffer) para formar o lexema
lexema: str = "".join(self.buffer_atual)
# Normalização Unicode NFC (Forma C - Canonical Decomposition, then Composition)
# O equivalente ao `lexema.normalize()` do Dart.
lexema_normalizado: str = unicodedata.normalize('NFC', lexema)
tipo_token: TokenType = self.verificar_palavra_chave(lexema_normalizado)
return Token(
tipo=tipo_token or TokenType.IDENTIFICADOR,
lexema=lexema_normalizado,
posicao=inicio
)
def verificar_palavra_chave(self, lexema: str) -> Optional[TokenType]:
"""
Verifica se o lexema normalizado é uma palavra-chave reservada.
"""
# Palavras-chave em minúsculas (a normalização do Dart implica case-insensitivity)
palavras_chave: Dict[str, TokenType] = {
# Português
'se': TokenType.IF,
'senao': TokenType.ELSE,
'enquanto': TokenType.WHILE,
'funcao': TokenType.FUNCTION,
# Inglês
'if': TokenType.IF,
'else': TokenType.ELSE,
'while': TokenType.WHILE,
'function': TokenType.FUNCTION,
}
# O `.get()` retorna `None` se a chave não existir
return palavras_chave.get(lexema.lower())import 'dart:async';
import 'dart:convert';
import 'dart:typed_data';
/// Tipos de tokens suportados.
enum TokenType { IF, ELSE, WHILE, FUNCTION, IDENTIFICADOR }
/// Estrutura básica de um token.
class Token {
final TokenType tipo;
final String lexema;
final int posicao;
Token({required this.tipo, required this.lexema, required this.posicao});
@override
String toString() => 'Token($tipo, "$lexema", pos=$posicao)';
}
/// Tokenizador Unicode otimizado para leitura de streams.
/// - Lê bytes em UTF-8 de forma incremental.
/// - Remove o BOM.
/// - Emite tokens conforme os dados chegam.
/// - Usa async*, Stream e buffers otimizados.
class UnicodeTokenizerStream {
static const int BOM_UTF8_1 = 0xEF;
static const int BOM_UTF8_2 = 0xBB;
static const int BOM_UTF8_3 = 0xBF;
final Stream<List<int>> origem;
final StringBuffer _bufferAtual = StringBuffer();
final StringBuffer _textoDecodificado = StringBuffer();
int _posicaoGlobal = 0;
bool _bomRemovido = false;
UnicodeTokenizerStream(this.origem);
/// Processa o stream e emite tokens conforme encontrados.
Stream<Token> tokenizar() async* {
final decoder = Utf8Decoder(allowMalformed: false);
await for (final chunk in origem) {
// Remover BOM apenas no primeiro bloco
final bytes = _bomRemovido ? chunk : _removerBOM(chunk);
_bomRemovido = true;
// Decodificar chunk UTF-8 incrementalmente
final trecho = decoder.convert(bytes);
_textoDecodificado.write(trecho);
// Processar tokens desse trecho
Token? token;
while ((token = _processarIdentificadorUnicode()) != null) {
yield token!;
}
}
// Processar o que restou no buffer final
Token? token;
while ((token = _processarIdentificadorUnicode()) != null) {
yield token!;
}
}
/// Remove o BOM (Byte Order Mark) do início, se presente.
List<int> _removerBOM(List<int> bytes) {
if (bytes.length >= 3 &&
bytes[0] == BOM_UTF8_1 &&
bytes[1] == BOM_UTF8_2 &&
bytes[2] == BOM_UTF8_3) {
return bytes.sublist(3);
}
return bytes;
}
/// Retorna `true` se o caractere puder iniciar um identificador Unicode.
bool _ehInicioIdentificador(int codePoint) {
final caractere = String.fromCharCode(codePoint);
return caractere.contains(RegExp(r'\p{L}|\p{Nl}|_', unicode: true));
}
/// Retorna `true` se o caractere puder continuar um identificador.
bool _ehContinuacaoIdentificador(int codePoint) {
final caractere = String.fromCharCode(codePoint);
return caractere.contains(RegExp(
r'\p{L}|\p{Nl}|\p{Nd}|\p{Mn}|\p{Mc}|\p{Pc}|_',
unicode: true,
));
}
/// Extrai um identificador Unicode a partir da posição atual do buffer.
Token? _processarIdentificadorUnicode() {
final entrada = _textoDecodificado.toString();
if (_posicaoGlobal >= entrada.length) return null;
final primeiroChar = entrada.codeUnitAt(_posicaoGlobal);
if (!_ehInicioIdentificador(primeiroChar)) {
_posicaoGlobal++;
return null;
}
_bufferAtual.clear();
final inicio = _posicaoGlobal;
_bufferAtual.writeCharCode(primeiroChar);
_posicaoGlobal++;
while (_posicaoGlobal < entrada.length) {
final charAtual = entrada.codeUnitAt(_posicaoGlobal);
if (!_ehContinuacaoIdentificador(charAtual)) break;
_bufferAtual.writeCharCode(charAtual);
_posicaoGlobal++;
}
final lexema = _bufferAtual.toString();
final lexemaNormalizado = lexema; // Dart já armazena Unicode normalizado (NFC)
return Token(
tipo: _verificarPalavraChave(lexemaNormalizado) ?? TokenType.IDENTIFICADOR,
lexema: lexemaNormalizado,
posicao: inicio,
);
}
/// Palavras-chave reconhecidas (em múltiplos idiomas).
TokenType? _verificarPalavraChave(String lexema) {
const palavrasChave = {
// Português
'se': TokenType.IF,
'senao': TokenType.ELSE,
'enquanto': TokenType.WHILE,
'funcao': TokenType.FUNCTION,
// Inglês
'if': TokenType.IF,
'else': TokenType.ELSE,
'while': TokenType.WHILE,
'function': TokenType.FUNCTION,
};
return palavrasChave[lexema.toLowerCase()];
}
}keywords.h
#ifndef KEYWORDS_H
#define KEYWORDS_H
#include <string>
// Enum C++-style (strongly typed)
enum class TokenType {
IDENTIFIER, // ID padrão (se não for palavra-chave)
IF, ELSE, WHILE, FOR,
FUNCTION, RETURN, VAR, CONST,
ERROR // Para casos não encontrados
};
// Função pública: Usa std::string_view para evitar cópias desnecessárias
// do lexema no ponto de chamada, se possível (C++17+)
TokenType lookup_keyword(std::string_view lexeme);
#endif // KEYWORDS_Hkeywords.c
#include "keywords.h"
#include <unordered_map>
#include <string_view>
using namespace std::string_literals;
// Estrutura para o mapeamento: Chave (string) -> Valor (TokenType)
// A unordered_map é inicializada apenas uma vez na primeira chamada
// de lookup_keyword, garantindo eficiência e segurança de threads
// (se implementada corretamente ou se não for acessada simultaneamente).
// No entanto, é mais comum declará-la globalmente ou estaticamente
// dentro da função.
const std::unordered_map<std::string, TokenType> KEYWORDS_MAP = {
{"if"s, TokenType::IF},
{"else"s, TokenType::ELSE},
{"while"s, TokenType::WHILE},
{"for"s, TokenType::FOR},
{"function"s, TokenType::FUNCTION},
{"return"s, TokenType::RETURN},
{"var"s, TokenType::VAR},
{"const"s, TokenType::CONST}
// Adicione mais palavras-chave aqui
};
// Implementação da função de lookup
TokenType lookup_keyword(std::string_view lexeme) {
// Busca a palavra-chave no mapa
// O .find() em unordered_map é O(1) em média.
auto it = KEYWORDS_MAP.find(std::string(lexeme));
// Se o iterador for diferente do .end(), a palavra-chave foi encontrada
if (it != KEYWORDS_MAP.end()) {
return it->second;
}
// Caso contrário, é um identificador
return TokenType::IDENTIFIER;
}Desafios do Unicode: O suporte completo a Unicode requer bibliotecas especializadas como ICU (International Components for Unicode) para implementar corretamente todas as nuances de normalização, categorização de caracteres, e regras de formação de identificadores.
Performance vs Correção: Implementações completas de Unicode podem ser computacionalmente caras. Compiladores práticos frequentemente usam implementações otimizadas que cobrem os casos mais comuns enquanto delegam casos edge para bibliotecas especializadas.
🔗 Integração com Análise Sintática
A análise léxica não opera em isolamento - ela deve fornecer uma interface limpa e eficiente para a análise sintática. O design desta interface afeta profundamente a arquitetura de todo o compilador.
🤝 Interface Léxico-Sintática
---
displayMode: compact
config:
theme: forest
layout: elk
elk:
mergeEdges: true
nodePlacementStrategy: LINEAR_SEGMENTS
---
sequenceDiagram
participant P as Parser Sintático
participant L as Analisador Léxico
participant B as Buffer de Entrada
participant T as Tabela de Símbolos
P->>L: próximoToken()
L->>B: lerCaracteres()
B-->>L: sequência de chars
L->>L: reconhecer padrão
alt Token Identificador
L->>T: verificar/inserir símbolo
T-->>L: informações do símbolo
end
L-->>P: Token com atributos
P->>P: processar token sintáticamente
alt Erro sintático
P->>L: sincronizar()
L->>L: descartar tokens até ;
end
Design de Interface Eficiente
from abc import ABC, abstractmethod
from typing import List, Optional, Set, Any
from dataclasses import dataclass
from enum import Enum
# --- Dependências (Assumidas/Stubs) ---
# A LexicalAnalyzer deve ser uma classe concreta que implementa o método nextToken().
class TokenType(Enum):
# Tipos mínimos para o exemplo
IF = 'IF'
ELSE = 'ELSE'
# ... outros
pass
@dataclass(frozen=True)
class Token:
tipo: TokenType
lexema: str
posicao: int # Posição inicial (offset)
# ... outros atributos (como deve_ignorar)
@dataclass(frozen=True)
class Position:
"""Representa a posição exata no código-fonte."""
linha: int
coluna: int
offset: int
arquivo: str
def __str__(self):
return f"{self.arquivo}:{self.linha}:{self.coluna}"
# Tipo genérico para o Lexer, garantindo a interface mínima
class LexicalAnalyzer(ABC):
@abstractmethod
def nextToken(self) -> Optional[Token]:
pass
@property
@abstractmethod
def currentPosition(self) -> Position:
pass
# --- Fim das Dependências ---
# --- Interface Abstrata (Simulando o `abstract class` do Dart) ---
class TokenStream(ABC):
"""Interface para um fluxo de tokens."""
@abstractmethod
def peek(self, offset: int = 0) -> Optional[Token]:
pass
@abstractmethod
def next(self) -> Optional[Token]:
pass
@abstractmethod
def putBack(self, token: Token) -> None:
pass
@property
@abstractmethod
def atEnd(self) -> bool:
pass
@property
@abstractmethod
def position(self) -> Position:
pass
# --- Implementação Otimizada (BufferedTokenStream) ---
class BufferedTokenStream(TokenStream):
"""
Fluxo de tokens com buffer interno para look-ahead e backtracking.
"""
lexer: LexicalAnalyzer
buffer: List[Token]
posicao_buffer: int
_at_end: bool
def __init__(self, lexer: LexicalAnalyzer):
self.lexer = lexer
self.buffer = []
self.posicao_buffer = 0
self._at_end = False # Marca se o Lexer atingiu o fim da entrada
def _ensure_tokens_available(self, quantidade: int):
"""
Garante que 'quantidade' de tokens estejam disponíveis no buffer.
Chama o lexer se necessário.
"""
# Só tenta carregar se a condição for verdadeira e o Lexer não tiver terminado
while len(self.buffer) - self.posicao_buffer < quantidade and not self._at_end:
novo_token: Optional[Token] = self.lexer.nextToken()
if novo_token is None:
self._at_end = True # O Lexer não tem mais tokens
break
# Otimização: A responsabilidade de ignorar tokens (como WHITESPACE)
# deve ser do Lexer ou da função `nextToken()` do Lexer, não do Stream.
self.buffer.append(novo_token)
# --- Métodos de Interface (TokenStream) ---
def peek(self, offset: int = 0) -> Optional[Token]:
"""Espia o token na posição (posicao_buffer + offset) sem consumi-lo."""
self._ensure_tokens_available(offset + 1)
indice: int = self.posicao_buffer + offset
# Otimização: Usamos List[Token].get() não existe. Checamos o índice.
if indice >= len(self.buffer):
return None
return self.buffer[indice]
def next(self) -> Optional[Token]:
"""Consome e retorna o próximo token no fluxo."""
self._ensure_tokens_available(1)
if self.posicao_buffer >= len(self.buffer):
self._at_end = True
return None
token = self.buffer[self.posicao_buffer]
self.posicao_buffer += 1
return token
def putBack(self, token: Token) -> None:
"""
Coloca um token de volta no fluxo.
Otimizado para o caso mais comum: o último token lido.
"""
# Prioriza o backtracking (o Dart faz isso com posicaoBuffer--)
if self.posicao_buffer > 0 and self.buffer[self.posicao_buffer - 1] is token:
self.posicao_buffer -= 1
self._at_end = False # Se colocamos algo de volta, não estamos no fim
elif self.posicao_buffer > 0 and self.buffer[self.posicao_buffer - 1] is not token:
# Caso raro: se o token não for o último, substituímos o último lido
self.posicao_buffer -= 1
self.buffer[self.posicao_buffer] = token
self._at_end = False
else:
# Caso extremo: o buffer está vazio ou no início. Simplesmente inserimos no início.
self.buffer.insert(0, token)
self._at_end = False
@property
def atEnd(self) -> bool:
"""Verifica se o fluxo chegou ao fim (EOF)."""
# Chegamos ao final se o lexer não tem mais tokens E o buffer está consumido
return self._at_end and self.posicao_buffer >= len(self.buffer)
@property
def position(self) -> Position:
"""Retorna a posição léxica atual (geralmente a do Lexer)."""
# Otimização: Se houver tokens no buffer, a posição ideal seria a do último token
# ou a do token atual, mas mantemos o comportamento do Dart que usa a do lexer.
return self.lexer.currentPosition
# --- Backtracking e Recuperação de Erros ---
def criar_checkpoint(self) -> int:
"""Cria um ponto de restauração no buffer."""
return self.posicao_buffer
def restaurar_checkpoint(self, checkpoint: int):
"""Volta ao ponto de restauração, habilitando a leitura novamente."""
if 0 <= checkpoint <= len(self.buffer):
self.posicao_buffer = checkpoint
self._at_end = False # Garante que o fluxo possa continuar lendo
else:
# Tratamento de erro para checkpoint inválido
raise ValueError("Checkpoint inválido para o buffer.")
def sincronizar_ate(self, tipos_sync: Set[TokenType]):
"""
Descarta tokens até que um token com um dos 'tipos_sync' seja encontrado.
Comum em recuperação de erros de parsing.
"""
while not self.atEnd:
token: Optional[Token] = self.peek()
if token is None:
break
if token.tipo in tipos_sync:
break # Encontrado token de sincronização
self.next() # Descartar o tokenabstract class TokenStream {
Token? peek([int offset = 0]);
Token? next();
void putBack(Token token);
bool get atEnd;
Position get position;
}
class BufferedTokenStream implements TokenStream {
final LexicalAnalyzer lexer;
final List<Token> buffer = [];
int posicaoBuffer = 0;
bool _atEnd = false;
BufferedTokenStream(this.lexer);
@override
Token? peek([int offset = 0]) {
_ensureTokensAvailable(offset + 1);
int indice = posicaoBuffer + offset;
if (indice >= buffer.length) return null;
return buffer[indice];
}
@override
Token? next() {
_ensureTokensAvailable(1);
if (posicaoBuffer >= buffer.length) {
_atEnd = true;
return null;
}
return buffer[posicaoBuffer++];
}
@override
void putBack(Token token) {
if (posicaoBuffer > 0) {
posicaoBuffer--;
buffer[posicaoBuffer] = token;
} else {
buffer.insert(0, token);
}
}
@override
bool get atEnd => _atEnd && posicaoBuffer >= buffer.length;
@override
Position get position => lexer.currentPosition;
void _ensureTokensAvailable(int quantidade) {
while (buffer.length - posicaoBuffer < quantidade && !_atEnd) {
Token? novoToken = lexer.nextToken();
if (novoToken == null) {
_atEnd = true;
break;
}
buffer.add(novoToken);
}
}
// Método especializado para recuperação de erros
void sincronizarAte(Set<TokenType> tiposSync) {
while (!atEnd) {
Token? token = peek();
if (token == null) break;
if (tiposSync.contains(token.tipo)) break;
next(); // Descartar token
}
}
// Checkpoint para backtracking
int criarCheckpoint() => posicaoBuffer;
void restaurarCheckpoint(int checkpoint) {
posicaoBuffer = checkpoint;
_atEnd = false;
}
}
class Position {
final int linha;
final int coluna;
final int offset;
final String arquivo;
const Position(this.linha, this.coluna, this.offset, this.arquivo);
@override
String toString() => '$arquivo:$linha:$coluna';
}#include <vector>
#include <memory>
#include <unordered_set>
struct Position {
size_t linha;
size_t coluna;
size_t offset;
std::string arquivo;
Position(size_t l, size_t c, size_t o, const std::string& a)
: linha(l), coluna(c), offset(o), arquivo(a) {}
std::string toString() const {
return arquivo + ":" + std::to_string(linha) + ":" + std::to_string(coluna);
}
};
class TokenStream {
public:
virtual ~TokenStream() = default;
virtual std::optional<Token> peek(size_t offset = 0) = 0;
virtual std::optional<Token> next() = 0;
virtual void putBack(const Token& token) = 0;
virtual bool atEnd() const = 0;
virtual Position getPosition() const = 0;
};
class BufferedTokenStream : public TokenStream {
private:
std::unique_ptr<LexicalAnalyzer> lexer;
std::vector<Token> buffer;
size_t posicaoBuffer = 0;
bool _atEnd = false;
void ensureTokensAvailable(size_t quantidade) {
while (buffer.size() - posicaoBuffer < quantidade && !_atEnd) {
auto novoToken = lexer->nextToken();
if (!novoToken.has_value()) {
_atEnd = true;
break;
}
buffer.push_back(novoToken.value());
}
}
public:
BufferedTokenStream(std::unique_ptr<LexicalAnalyzer> lex)
: lexer(std::move(lex)) {}
std::optional<Token> peek(size_t offset = 0) override {
ensureTokensAvailable(offset + 1);
size_t indice = posicaoBuffer + offset;
if (indice >= buffer.size()) return std::nullopt;
return buffer[indice];
}
std::optional<Token> next() override {
ensureTokensAvailable(1);
if (posicaoBuffer >= buffer.size()) {
_atEnd = true;
return std::nullopt;
}
return buffer[posicaoBuffer++];
}
void putBack(const Token& token) override {
if (posicaoBuffer > 0) {
posicaoBuffer--;
buffer[posicaoBuffer] = token;
} else {
buffer.insert(buffer.begin(), token);
}
}
bool atEnd() const override {
return _atEnd && posicaoBuffer >= buffer.size();
}
Position getPosition() const override {
return lexer->getCurrentPosition();
}
// Métodos especializados para parsing
void sincronizarAte(const std::unordered_set<TokenType>& tiposSync) {
while (!atEnd()) {
auto token = peek();
if (!token.has_value()) break;
if (tiposSync.count(token->tipo)) break;
next(); // Descartar token
}
}
// Sistema de checkpoint para backtracking
size_t criarCheckpoint() const { return posicaoBuffer; }
void restaurarCheckpoint(size_t checkpoint) {
posicaoBuffer = checkpoint;
_atEnd = false;
}
// Look-ahead múltiplo para parsing LL(k)
std::vector<Token> peek_multiple(size_t quantidade) {
ensureTokensAvailable(quantidade);
std::vector<Token> resultado;
for (size_t i = 0; i < quantidade && posicaoBuffer + i < buffer.size(); ++i) {
resultado.push_back(buffer[posicaoBuffer + i]);
}
return resultado;
}
};Buffer de Tokens: O uso de um buffer permite que o parser sintático faça look-ahead eficiente, essencial para muitos algoritmos de parsing. O buffer também facilita operações de backtracking quando necessário.
Recuperação de Erros: A interface fornece métodos especializados para sincronização após erros, permitindo que o parser continue a análise mesmo quando encontra construtos inválidos.
📊 Validação e Testes
A validação do analisador léxico é um processo sistemático que vai além de simplesmente verificar se o código compila. Vocês devem implementar uma suite de testes abrangente que cubra todos os aspectos da funcionalidade.
🧪 Estratégias de Teste Sistemático
---
displayMode: compact
config:
theme: forest
layout: elk
elk:
mergeEdges: true
nodePlacementStrategy: LINEAR_SEGMENTS
---
graph TD
A[📋 Suite de Testes] --> B[✅ Testes Unitários]
A --> C[🔄 Testes de Integração]
A --> D[🚨 Testes de Erro]
A --> E[⚡ Testes de Performance]
B --> B1[Tokens Individuais]
B --> B2[Casos Limítrofes]
B --> B3[Expressões Regulares]
C --> C1[Sequências de Tokens]
C --> C2[Interface Sintática]
C --> C3[Recuperação de Erros]
D --> D1[Caracteres Inválidos]
D --> D2[Strings Malformadas]
D --> D3[Números Incorretos]
E --> E1[Arquivos Grandes]
E --> E2[Casos Extremos]
E --> E3[Uso de Memória]
style B fill:#e8f5e8
style C fill:#e3f2fd
style D fill:#ffebee
style E fill:#fff3e0
Implementação de Testes Automatizados
import pytest
import time
import os # Para simular a limpeza do ProcessInfo (não há equivalente direto simples)
from typing import List, Any
from unittest.mock import MagicMock # Usado para simular ProcessInfo
# --- Stubs de Classes Necessárias para Teste (Ajuste conforme suas classes reais) ---
# Em um ambiente real, você importaria estas classes.
class TokenType:
IDENTIFICADOR = 'IDENTIFICADOR'
INTEIRO = 'INTEIRO'
REAL = 'REAL'
SE = 'SE'
MENOR_IGUAL = 'MENOR_IGUAL'
MENOR = 'MENOR'
IGUAL = 'IGUAL'
STRING = 'STRING'
PAREN_ESQ = 'PAREN_ESQ'
class Token:
def __init__(self, tipo: TokenType, lexema: str, valor: Any = None):
self.tipo = tipo
self.lexema = lexema
self.valor = valor
class ErroLexico(Exception):
"""Exceção para erros léxicos."""
pass
# Mock do AnalisadorLexico (A ser substituído pela sua implementação real)
class AnalisadorLexico:
def tokenizar(self, entrada: str) -> List[Token]:
# Esta é uma simulação da lógica de tokenização para que os testes passem
if entrada == 'contador_total':
return [Token(TokenType.IDENTIFICADOR, 'contador_total')]
if entrada == '12345':
return [Token(TokenType.INTEIRO, '12345', 12345)]
if entrada == '123.45':
return [Token(TokenType.REAL, '123.45', 123.45)]
if entrada == 'se identificador':
return [
Token(TokenType.SE, 'se'),
Token(TokenType.IDENTIFICADOR, 'identificador')
]
if entrada == '<= < =':
return [
Token(TokenType.MENOR_IGUAL, '<='),
Token(TokenType.MENOR, '<'),
Token(TokenType.IGUAL, '=')
]
if entrada == '999999999999999999':
return [Token(TokenType.INTEIRO, '999999999999999999', int(entrada))]
if entrada == '"Olá\\nMundo\\t\\"teste\\""':
return [Token(TokenType.STRING, '"Olá\nMundo\t\\"teste\\""', 'Olá\nMundo\t"teste"')]
# Simulação de erros
if '@' in entrada or '123.45.67' in entrada or 'string sem fim' in entrada:
raise ErroLexico("Erro encontrado durante a tokenização.")
# Simulação para o teste de performance
if entrada.startswith('var x = 1;\n'):
# 5 tokens por linha: var, x, =, 1, ;
num_linhas = entrada.count('\n')
return [Token(TokenType.IDENTIFICADOR, 'simulado')] * (5 * num_linhas)
# Simulação para o teste de integração
if entrada.startswith('se (x > 0) entao y = 1; fim'):
return [
Token(TokenType.SE, 'se'),
Token(TokenType.PAREN_ESQ, '('),
# ... outros tokens ...
]
return []
# Simulação da classe TokenStream
class TokenStream:
def __init__(self, analisador: AnalisadorLexico):
self.analisador = analisador
self.tokens = self.analisador.tokenizar('se (x > 0) entao y = 1; fim')
self.posicao = 0
def inicializar(self, entrada: str):
# Simulação de inicialização
pass
def peek(self, offset: int = 0) -> Optional[Token]:
idx = self.posicao + offset
return self.tokens[idx] if 0 <= idx < len(self.tokens) else None
def next(self) -> Optional[Token]:
if self.posicao < len(self.tokens):
token = self.tokens[self.posicao]
self.posicao += 1
return token
return None
def putBack(self, token: Token):
self.posicao -= 1
# --- Suite de Testes Pytest ---
# O nome da classe deve começar com 'Test' para ser descoberto pelo pytest
class TesteSuiteAnalisadorLexico:
"""
Simulação da TesteSuiteAnalisadorLexico do Dart usando pytest.
"""
# O método 'setup' do Dart é traduzido para o método pytest 'setup_method'
# ou, mais comum, para o fixture 'autouse=True' ou 'session'
@pytest.fixture(autouse=True)
def setup_analisador(self):
"""Método de setup executado antes de cada teste."""
self.analisador = AnalisadorLexico()
# --- Testes de Tokens Básicos ---
# O 'group' do Dart é simulado por classes ou funções agrupadoras no pytest
# O pytest usa a convenção `test_` para métodos de teste
def test_reconhecimento_identificadores(self):
tokens = self.analisador.tokenizar('contador_total')
assert len(tokens) == 1
assert tokens[0].tipo == TokenType.IDENTIFICADOR
assert tokens[0].lexema == 'contador_total'
def test_reconhecimento_numeros_inteiros(self):
tokens = self.analisador.tokenizar('12345')
assert len(tokens) == 1
assert tokens[0].tipo == TokenType.INTEIRO
# A comparação de valor direto é preferível no Python
assert tokens[0].valor == 12345
def test_reconhecimento_numeros_reais(self):
tokens = self.analisador.tokenizar('123.45')
assert len(tokens) == 1
assert tokens[0].tipo == TokenType.REAL
# pytest usa `pytest.approx` para comparação de ponto flutuante (closeTo)
assert tokens[0].valor == pytest.approx(123.45, abs=0.001)
def test_distincao_identificadores_e_palavras_chave(self):
tokens = self.analisador.tokenizar('se identificador')
assert len(tokens) == 2
assert tokens[0].tipo == TokenType.SE
assert tokens[1].tipo == TokenType.IDENTIFICADOR
# --- Testes de Casos Limítrofes ---
def test_numeros_no_limite_de_precisao(self):
# Python lida com inteiros de tamanho arbitrário (sem limite de precisão fixo)
tokens = self.analisador.tokenizar('999999999999999999')
assert len(tokens) == 1
assert tokens[0].tipo == TokenType.INTEIRO
assert tokens[0].valor == 999999999999999999
def test_strings_com_caracteres_de_escape(self):
tokens = self.analisador.tokenizar('"Olá\\nMundo\\t\\"teste\\""')
assert len(tokens) == 1
assert tokens[0].tipo == TokenType.STRING
# A string de valor esperada após o processamento léxico
assert tokens[0].valor == 'Olá\nMundo\t"teste"'
def test_operadores_compostos_vs_simples(self):
tokens = self.analisador.tokenizar('<= < =')
assert len(tokens) == 3
assert tokens[0].tipo == TokenType.MENOR_IGUAL
assert tokens[1].tipo == TokenType.MENOR
assert tokens[2].tipo == TokenType.IGUAL
# --- Testes de Tratamento de Erros ---
def test_caracteres_invalidos(self):
# pytest usa 'with pytest.raises' para verificar se uma exceção é lançada
with pytest.raises(ErroLexico):
self.analisador.tokenizar('var @ = 5;')
def test_string_nao_terminada(self):
with pytest.raises(ErroLexico):
self.analisador.tokenizar('"string sem fim')
def test_numero_malformado(self):
with pytest.raises(ErroLexico):
self.analisador.tokenizar('123.45.67')
# --- Testes de Performance e Integração ---
# Nota: Testes de memória (ProcessInfo.currentRss) são complexos e dependem de
# bibliotecas externas (como `psutil`) ou ferramentas de profiling em Python.
# O teste de memória abaixo é substituído por um mock ou removido.
def test_processamento_de_arquivo_grande(self):
# Simulação do Stopwatch
codigo_grande = 'var x = 1;\n' * 10000
start_time = time.time()
tokens = self.analisador.tokenizar(codigo_grande)
elapsed_time = (time.time() - start_time) * 1000 # em milissegundos
# 5 tokens por linha: var, x, =, 1, ; (o lexer precisa ignorar espaços e \n)
assert len(tokens) == 50000
# Asserção de tempo (menos de 1 segundo)
assert elapsed_time < 1000
# O teste de memória é removido ou exige mocks/bibliotecas específicas de SO
# O teste abaixo é apenas um placeholder:
@pytest.mark.skip(reason="O teste de uso de memória exige dependências externas (ex: psutil).")
def test_uso_de_memoria_controlado(self):
# Substituído por um mock para evitar erro de execução.
pass
def test_interface_com_parser_sintatico(self):
stream = TokenStream(self.analisador)
stream.inicializar('se (x > 0) entao y = 1; fim')
# Teste de peek
assert stream.peek().tipo == TokenType.SE
# Teste de next
assert stream.next().tipo == TokenType.SE
assert stream.peek().tipo == TokenType.PAREN_ESQ
# Teste de putBack
token_paren = stream.next()
stream.putBack(token_paren)
assert stream.next().tipo == TokenType.PAREN_ESQimport 'package:test/test.dart';
class TesteSuiteAnalisadorLexico {
late AnalisadorLexico analisador;
void setUp() {
analisador = AnalisadorLexico();
}
void executarTodosTestes() {
group('Testes de Tokens Básicos', () {
test('Reconhecimento de identificadores', () {
var tokens = analisador.tokenizar('contador_total');
expect(tokens.length, equals(1));
expect(tokens[0].tipo, equals(TokenType.IDENTIFICADOR));
expect(tokens[0].lexema, equals('contador_total'));
});
test('Reconhecimento de números inteiros', () {
var tokens = analisador.tokenizar('12345');
expect(tokens.length, equals(1));
expect(tokens[0].tipo, equals(TokenType.INTEIRO));
expect(tokens[0].valor, equals(12345));
});
test('Reconhecimento de números reais', () {
var tokens = analisador.tokenizar('123.45');
expect(tokens.length, equals(1));
expect(tokens[0].tipo, equals(TokenType.REAL));
expect(tokens[0].valor, closeTo(123.45, 0.001));
});
test('Distinção entre identificadores e palavras-chave', () {
var tokens = analisador.tokenizar('se identificador');
expect(tokens.length, equals(2));
expect(tokens[0].tipo, equals(TokenType.SE));
expect(tokens[1].tipo, equals(TokenType.IDENTIFICADOR));
});
});
group('Testes de Casos Limítrofes', () {
test('Números no limite de precisão', () {
var tokens = analisador.tokenizar('999999999999999999');
expect(tokens.length, equals(1));
expect(tokens[0].tipo, equals(TokenType.INTEIRO));
});
test('Strings com caracteres de escape', () {
var tokens = analisador.tokenizar('"Olá\\nMundo\\t\\"teste\\""');
expect(tokens.length, equals(1));
expect(tokens[0].tipo, equals(TokenType.STRING));
expect(tokens[0].valor, equals('Olá\nMundo\t"teste"'));
});
test('Operadores compostos vs simples', () {
var tokens = analisador.tokenizar('<= < =');
expect(tokens.length, equals(3));
expect(tokens[0].tipo, equals(TokenType.MENOR_IGUAL));
expect(tokens[1].tipo, equals(TokenType.MENOR));
expect(tokens[2].tipo, equals(TokenType.IGUAL));
});
});
group('Testes de Tratamento de Erros', () {
test('Caracteres inválidos', () {
expect(() => analisador.tokenizar('var @ = 5;'),
throwsA(isA<ErroLexico>()));
});
test('String não terminada', () {
expect(() => analisador.tokenizar('"string sem fim'),
throwsA(isA<ErroLexico>()));
});
test('Número malformado', () {
expect(() => analisador.tokenizar('123.45.67'),
throwsA(isA<ErroLexico>()));
});
});
group('Testes de Performance', () {
test('Processamento de arquivo grande', () {
String codigoGrande = 'var x = 1;\n' * 10000;
Stopwatch cronometro = Stopwatch()..start();
var tokens = analisador.tokenizar(codigoGrande);
cronometro.stop();
expect(tokens.length, equals(50000)); // 5 tokens por linha * 10000 linhas
expect(cronometro.elapsedMilliseconds, lessThan(1000)); // Menos de 1 segundo
});
test('Uso de memória controlado', () {
String codigoGrande = 'identificador_muito_longo_' * 1000;
int memoriaAntes = ProcessInfo.currentRss;
var tokens = analisador.tokenizar(codigoGrande);
int memoriaDepois = ProcessInfo.currentRss;
int crescimentoMemoria = memoriaDepois - memoriaAntes;
expect(crescimentoMemoria, lessThan(10 * 1024 * 1024)); // Menos de 10MB
});
});
group('Testes de Integração', () {
test('Interface com parser sintático', () {
var stream = TokenStream(analisador);
stream.inicializar('se (x > 0) entao y = 1; fim');
expect(stream.peek()?.tipo, equals(TokenType.SE));
expect(stream.next()?.tipo, equals(TokenType.SE));
expect(stream.peek()?.tipo, equals(TokenType.PAREN_ESQ));
// Teste de putBack
var token = stream.next()!;
stream.putBack(token);
expect(stream.next()?.tipo, equals(TokenType.PAREN_ESQ));
});
});
}
}#include <gtest/gtest.h>
#include <chrono>
#include <fstream>
class TestAnalisadorLexico : public ::testing::Test {
protected:
void SetUp() override {
analisador = std::make_unique<AnalisadorLexico>();
}
std::unique_ptr<AnalisadorLexico> analisador;
};
// Testes de Tokens Básicos
TEST_F(TestAnalisadorLexico, ReconhecimentoIdentificadores) {
auto tokens = analisador->tokenizar("contador_total");
ASSERT_EQ(tokens.size(), 1);
EXPECT_EQ(tokens[0].tipo, TokenType::IDENTIFICADOR);
EXPECT_EQ(tokens[0].lexema, "contador_total");
}
TEST_F(TestAnalisadorLexico, ReconhecimentoNumerosInteiros) {
auto tokens = analisador->tokenizar("12345");
ASSERT_EQ(tokens.size(), 1);
EXPECT_EQ(tokens[0].tipo, TokenType::INTEIRO);
EXPECT_EQ(std::get<int>(tokens[0].valor), 12345);
}
TEST_F(TestAnalisadorLexico, ReconhecimentoNumerosReais) {
auto tokens = analisador->tokenizar("123.45");
ASSERT_EQ(tokens.size(), 1);
EXPECT_EQ(tokens[0].tipo, TokenType::REAL);
EXPECT_NEAR(std::get<double>(tokens[0].valor), 123.45, 0.001);
}
TEST_F(TestAnalisadorLexico, DistincaoIdentificadoresPalavrasChave) {
auto tokens = analisador->tokenizar("se identificador");
ASSERT_EQ(tokens.size(), 2);
EXPECT_EQ(tokens[0].tipo, TokenType::SE);
EXPECT_EQ(tokens[1].tipo, TokenType::IDENTIFICADOR);
}
// Testes de Casos Limítrofes
TEST_F(TestAnalisadorLexico, NumerosLimitePrecisao) {
auto tokens = analisador->tokenizar("999999999999999999");
ASSERT_EQ(tokens.size(), 1);
EXPECT_EQ(tokens[0].tipo, TokenType::INTEIRO);
}
TEST_F(TestAnalisadorLexico, StringsComCaracteresEscape) {
auto tokens = analisador->tokenizar("\"Olá\\nMundo\\t\\\"teste\\\"\"");
ASSERT_EQ(tokens.size(), 1);
EXPECT_EQ(tokens[0].tipo, TokenType::STRING);
EXPECT_EQ(std::get<std::string>(tokens[0].valor), "Olá\nMundo\t\"teste\"");
}
TEST_F(TestAnalisadorLexico, OperadoresCompostosVsSimples) {
auto tokens = analisador->tokenizar("<= < =");
ASSERT_EQ(tokens.size(), 3);
EXPECT_EQ(tokens[0].tipo, TokenType::MENOR_IGUAL);
EXPECT_EQ(tokens[1].tipo, TokenType::MENOR);
EXPECT_EQ(tokens[2].tipo, TokenType::IGUAL);
}
// Testes de Tratamento de Erros
TEST_F(TestAnalisadorLexico, CaracteresInvalidos) {
EXPECT_THROW(analisador->tokenizar("var @ = 5;"), ErroLexico);
}
TEST_F(TestAnalisadorLexico, StringNaoTerminada) {
EXPECT_THROW(analisador->tokenizar("\"string sem fim"), ErroLexico);
}
TEST_F(TestAnalisadorLexico, NumeroMalformado) {
EXPECT_THROW(analisador->tokenizar("123.45.67"), ErroLexico);
}
// Testes de Performance
TEST_F(TestAnalisadorLexico, ProcessamentoArquivoGrande) {
std::string codigoGrande;
for (int i = 0; i < 10000; ++i) {
codigoGrande += "var x = 1;\n";
}
auto inicio = std::chrono::high_resolution_clock::now();
auto tokens = analisador->tokenizar(codigoGrande);
auto fim = std::chrono::high_resolution_clock::now();
auto duracao = std::chrono::duration_cast<std::chrono::milliseconds>(fim - inicio);
EXPECT_EQ(tokens.size(), 50000); // 5 tokens por linha * 10000 linhas
EXPECT_LT(duracao.count(), 1000); // Menos de 1 segundo
}
// Testes de Integração
TEST_F(TestAnalisadorLexico, InterfaceComParserSintatico) {
auto stream = std::make_unique<TokenStream>(std::move(analisador));
stream->inicializar("se (x > 0) entao y = 1; fim");
EXPECT_EQ(stream->peek()->tipo, TokenType::SE);
EXPECT_EQ(stream->next()->tipo, TokenType::SE);
EXPECT_EQ(stream->peek()->tipo, TokenType::PAREN_ESQ);
// Teste de putBack
auto token = stream->next();
stream->putBack(*token);
EXPECT_EQ(stream->next()->tipo, TokenType::PAREN_ESQ);
}Cobertura Abrangente: Os testes devem cobrir não apenas casos normais, mas também situações límitrofes, casos de erro, e cenários de performance. Esta abordagem sistemática garante que o analisador seja robusto em situações reais.
Automação e Integração Contínua: Implementem os testes de forma que possam ser executados automaticamente a cada modificação do código. Isso permite detecção precoce de regressões e mantém a qualidade do código.
🔍 Análise de Performance e Otimização
Um analisador léxico eficiente pode significar a diferença entre um compilador utilizável e um que seja frustrantemente lento. Compreender onde o tempo é gasto e como otimizar operações críticas é essencial para implementações profissionais.
📊 Profiling e Identificação de Gargalos
---
displayMode: compact
config:
theme: forest
layout: elk
elk:
mergeEdges: true
nodePlacementStrategy: LINEAR_SEGMENTS
---
pie
"I/O de Arquivo" : 15
"Reconhecimento de Padrões" : 35
"Alocação de Strings" : 25
"Consulta Tabela Hash" : 10
"Tratamento de Unicode" : 10
"Outros" : 5
Os dados mostram que a maior parte do tempo é gasta em reconhecimento de padrões e manipulação de strings. Otimizações nestas áreas têm o maior impacto na performance geral.
Técnicas de Otimização Avançadas
from typing import List, Dict, Optional, Any
import string
# --- Constantes para Classificação de Caracteres ---
# Definidas como constantes de módulo em Python (maiúsculas)
CHAR_LETRA = 1
CHAR_DIGITO = 2
CHAR_UNDERSCORE = 3
CHAR_PONTO = 4
CHAR_ASPAS = 5
CHAR_ESPACO = 6
CHAR_NEWLINE = 7
CHAR_OUTRO = 0
# Função utilitária para obter o código ASCII (o Python nativo já faz isso com ord())
def ord_(char: str) -> int:
return ord(char)
# --- Stubs de Dependências (Ajuste conforme seu projeto) ---
class TokenType:
IDENTIFICADOR = 'IDENTIFICADOR'
SE = 'SE'
SENAO = 'SENAO'
ENQUANTO = 'ENQUANTO'
PARA = 'PARA'
FUNCAO = 'FUNCAO'
RETORNA = 'RETORNA'
VAR = 'VAR'
CONST = 'CONST'
REAL = 'REAL'
INTEIRO = 'INTEIRO'
# ... outros
class Token:
def __init__(self, tipo: TokenType, lexema: str, posicao: int, valor: Any = None):
self.tipo = tipo
self.lexema = lexema
self.posicao = posicao
self.valor = valor
# --- Analisador Léxico Otimizado ---
class AnalisadorLexicoOtimizado:
"""
Analisador léxico altamente otimizado usando pré-cálculo de classificação
de caracteres e string interning.
"""
# Pool de strings para interning (reutilização de objetos imutáveis)
pool_strings: Dict[str, str]
# Cache de classificação de caracteres (List[int] de 256 posições)
classificacao_caracteres: List[int]
# Tabela de palavras-chave otimizada: {comprimento: {palavra: tipo}}
tabela_palavras_chave: Dict[int, Dict[str, TokenType]]
def __init__(self):
"""Inicializa caches e tabelas de lookup."""
self.pool_strings = {}
# Chamada dos métodos de inicialização
self._inicializar_classificacao_caracteres()
self._inicializar_tabela_palavras_chave()
def _inicializar_classificacao_caracteres(self):
"""
Pré-calcula o tipo de cada um dos 256 primeiros caracteres ASCII.
Isto substitui a classificação em runtime constante (O(1)).
"""
# Inicializa a lista com 256 posições
self.classificacao_caracteres = [CHAR_OUTRO] * 256
# Otimização: Usa as constantes string.ascii_letters, string.digits
# para inicialização limpa e rápida.
# Letras ASCII
for char in string.ascii_letters:
self.classificacao_caracteres[ord(char)] = CHAR_LETRA
# Dígitos
for char in string.digits:
self.classificacao_caracteres[ord(char)] = CHAR_DIGITO
# Caracteres especiais
self.classificacao_caracteres[ord('_')] = CHAR_UNDERSCORE
self.classificacao_caracteres[ord('.')] = CHAR_PONTO
self.classificacao_caracteres[ord('"')] = CHAR_ASPAS
# Espaços em branco e novas linhas
# O Python lida com \t, \n, \r de forma nativa
self.classificacao_caracteres[ord(' ')] = CHAR_ESPACO
self.classificacao_caracteres[ord('\t')] = CHAR_ESPACO
self.classificacao_caracteres[ord('\n')] = CHAR_NEWLINE
self.classificacao_caracteres[ord('\r')] = CHAR_NEWLINE
def _inicializar_tabela_palavras_chave(self):
"""
Organiza palavras-chave em uma tabela indexada pelo comprimento.
"""
self.tabela_palavras_chave = {}
palavras_chave = {
'se': TokenType.SE,
'senao': TokenType.SENAO,
'enquanto': TokenType.ENQUANTO,
'para': TokenType.PARA,
'funcao': TokenType.FUNCAO,
'retorna': TokenType.RETORNA,
'var': TokenType.VAR,
'const': TokenType.CONST,
}
# Otimização: Agrupamento por comprimento
for lexema, tipo in palavras_chave.items():
comprimento = len(lexema)
# Python usa .setdefault() que é o equivalente idiomático do putIfAbsent
tabela_por_comprimento = self.tabela_palavras_chave.setdefault(comprimento, {})
tabela_por_comprimento[lexema] = tipo
def _intern_string(self, text: str) -> str:
"""
Realiza String Interning: retorna uma referência à string no pool
se ela já existir.
"""
# putIfAbsent do Dart é substituído pelo setdefault do Python (mais limpo)
return self.pool_strings.setdefault(text, text)
def _buscar_palavra_chave(self, lexema: str) -> Optional[TokenType]:
"""
Busca o tipo de token na tabela otimizada.
"""
# 1. Look up pelo comprimento
tabela = self.tabela_palavras_chave.get(len(lexema))
if tabela is None:
return None
# 2. Look up pela string
return tabela.get(lexema)
def _reconhecer_identificador_rapido(self, entrada: str, posicao: int) -> Optional[Token]:
"""
Reconhecimento de identificadores usando a tabela de classificação,
evitando chamadas de função e alocações excessivas.
"""
inicio: int = posicao
entrada_len: int = len(entrada)
if posicao >= entrada_len:
return None
# Otimização: Obtém o código do caractere (code point)
char_code: int = ord(entrada[posicao])
# 1. Verificar primeiro caractere (ASCII < 256)
# O código Dart verifica `char >= 256`. Identificadores Unicode (> 256)
# não serão tratados por este caminho otimizado, apenas por um caminho de fallback.
if char_code >= 256:
return None # Deve ser tratado por um método Unicode separado
tipo_char: int = self.classificacao_caracteres[char_code]
if tipo_char != CHAR_LETRA and tipo_char != CHAR_UNDERSCORE:
return None
posicao += 1
# 2. Loop para continuação do identificador
while posicao < entrada_len:
char_code = ord(entrada[posicao])
if char_code >= 256:
break
tipo_char = self.classificacao_caracteres[char_code]
# Condição AND otimizada
if tipo_char == CHAR_LETRA or tipo_char == CHAR_DIGITO or tipo_char == CHAR_UNDERSCORE:
posicao += 1
else:
break
# Extrai, interna e busca a palavra-chave
lexema: str = entrada[inicio:posicao]
lexema_internado: str = self._intern_string(lexema)
tipo_palavra_chave: Optional[TokenType] = self._buscar_palavra_chave(lexema_internado)
return Token(
tipo=tipo_palavra_chave if tipo_palavra_chave is not None else TokenType.IDENTIFICADOR,
lexema=lexema_internado,
posicao=inicio
)
def _reconhecer_numero_rapido(self, entrada: str, posicao: int) -> Optional[Token]:
"""
Reconhecimento de números (inteiros e reais) sem regex, usando a tabela
de classificação.
"""
inicio: int = posicao
entrada_len: int = len(entrada)
tem_ponto: bool = False
# 1. Parte inteira
num_digits_int = 0
while posicao < entrada_len:
char_code: int = ord(entrada[posicao])
if char_code >= 256 or self.classificacao_caracteres[char_code] != CHAR_DIGITO:
break
posicao += 1
num_digits_int += 1
if num_digits_int == 0: # Não começou com um dígito
return None
# 2. Verificar parte decimal
if posicao < entrada_len and ord(entrada[posicao]) == ord('.'):
proximo_pos: int = posicao + 1
if proximo_pos < entrada_len:
proximo_char_code: int = ord(entrada[proximo_pos])
# Otimização: Somente avança se houver um dígito após o ponto
if proximo_char_code < 256 and self.classificacao_caracteres[proximo_char_code] == CHAR_DIGITO:
tem_ponto = True
posicao += 1 # Consome o ponto
# Dígitos da parte decimal
while posicao < entrada_len:
char_code = ord(entrada[posicao])
if char_code >= 256 or self.classificacao_caracteres[char_code] != CHAR_DIGITO:
break
posicao += 1
# 3. Construir Token
lexema: str = entrada[inicio:posicao]
if tem_ponto:
# Tenta converter para float (double no Dart)
try:
valor: float = float(lexema)
tipo: TokenType = TokenType.REAL
except ValueError:
# Se a conversão falhar (ex: ponto sem dígitos após, mas o código acima já prevê),
# seria um erro léxico na prática.
return None
else:
# Tenta converter para int
try:
valor: int = int(lexema)
tipo: TokenType = TokenType.INTEIRO
except ValueError:
return None
return Token(
tipo=tipo,
lexema=lexema,
valor=valor,
posicao=inicio
)class AnalisadorLexicoOtimizado {
// Pool de strings para reduzir alocações
final Map<String, String> poolStrings = {};
// Cache de classificação de caracteres
late final List<int> classificacaoCaracteres;
// Tabela de palavras-chave otimizada
late final Map<int, Map<String, TokenType>> tabelaPalavrasChave;
AnalisadorLexicoOtimizado() {
_inicializarClassificacaoCaracteres();
_inicializarTabelaPalavrasChave();
}
void _inicializarClassificacaoCaracteres() {
classificacaoCaracteres = List.filled(256, CHAR_OUTRO);
// ASCII letters
for (int i = ord('a'); i <= ord('z'); i++) {
classificacaoCaracteres[i] = CHAR_LETRA;
}
for (int i = ord('A'); i <= ord('Z'); i++) {
classificacaoCaracteres[i] = CHAR_LETRA;
}
// Digits
for (int i = ord('0'); i <= ord('9'); i++) {
classificacaoCaracteres[i] = CHAR_DIGITO;
}
// Special characters
classificacaoCaracteres[ord('_')] = CHAR_UNDERSCORE;
classificacaoCaracteres[ord('.')] = CHAR_PONTO;
classificacaoCaracteres[ord('"')] = CHAR_ASPAS;
// Whitespace
classificacaoCaracteres[ord(' ')] = CHAR_ESPACO;
classificacaoCaracteres[ord('\t')] = CHAR_ESPACO;
classificacaoCaracteres[ord('\n')] = CHAR_NEWLINE;
classificacaoCaracteres[ord('\r')] = CHAR_NEWLINE;
}
void _inicializarTabelaPalavrasChave() {
tabelaPalavrasChave = {};
const palavrasChave = {
'se': TokenType.SE,
'senao': TokenType.SENAO,
'enquanto': TokenType.ENQUANTO,
'para': TokenType.PARA,
'funcao': TokenType.FUNCAO,
'retorna': TokenType.RETORNA,
'var': TokenType.VAR,
'const': TokenType.CONST,
};
// Organizar por comprimento para lookup mais eficiente
for (var entrada in palavrasChave.entries) {
int comprimento = entrada.key.length;
tabelaPalavrasChave.putIfAbsent(comprimento, () => {});
tabelaPalavrasChave[comprimento]![entrada.key] = entrada.value;
}
}
String _internString(String str) {
// String interning para reduzir uso de memória
return poolStrings.putIfAbsent(str, () => str);
}
Token? _reconhecerIdentificadorRapido(String entrada, int posicao) {
int inicio = posicao;
// Primeiro caractere deve ser letra ou underscore
if (posicao >= entrada.length) return null;
int char = entrada.codeUnitAt(posicao);
if (char >= 256 || classificacaoCaracteres[char] != CHAR_LETRA &&
classificacaoCaracteres[char] != CHAR_UNDERSCORE) {
return null;
}
posicao++;
// Continuar com letras, dígitos ou underscores
while (posicao < entrada.length) {
char = entrada.codeUnitAt(posicao);
if (char >= 256) break;
int tipo = classificacaoCaracteres[char];
if (tipo != CHAR_LETRA && tipo != CHAR_DIGITO && tipo != CHAR_UNDERSCORE) {
break;
}
posicao++;
}
String lexema = entrada.substring(inicio, posicao);
String lexemaInternado = _internString(lexema);
// Lookup eficiente de palavra-chave
TokenType? tipoPalavraChave = _buscarPalavraChave(lexemaInternado);
return Token(
tipo: tipoPalavraChave ?? TokenType.IDENTIFICADOR,
lexema: lexemaInternado,
posicao: inicio
);
}
TokenType? _buscarPalavraChave(String lexema) {
var tabela = tabelaPalavrasChave[lexema.length];
return tabela?[lexema];
}
Token? _reconhecerNumeroRapido(String entrada, int posicao) {
int inicio = posicao;
bool temPonto = false;
// Parte inteira
while (posicao < entrada.length) {
int char = entrada.codeUnitAt(posicao);
if (char >= 256 || classificacaoCaracteres[char] != CHAR_DIGITO) {
break;
}
posicao++;
}
// Verificar parte decimal
if (posicao < entrada.length && entrada.codeUnitAt(posicao) == ord('.')) {
int proximoPos = posicao + 1;
if (proximoPos < entrada.length) {
int proximoChar = entrada.codeUnitAt(proximoPos);
if (proximoChar < 256 && classificacaoCaracteres[proximoChar] == CHAR_DIGITO) {
temPonto = true;
posicao++; // Pular o ponto
// Dígitos da parte decimal
while (posicao < entrada.length) {
int char = entrada.codeUnitAt(posicao);
if (char >= 256 || classificacaoCaracteres[char] != CHAR_DIGITO) {
break;
}
posicao++;
}
}
}
}
String lexema = entrada.substring(inicio, posicao);
if (temPonto) {
double valor = double.parse(lexema);
return Token(
tipo: TokenType.REAL,
lexema: lexema,
valor: valor,
posicao: inicio
);
} else {
int valor = int.parse(lexema);
return Token(
tipo: TokenType.INTEIRO,
lexema: lexema,
valor: valor,
posicao: inicio
);
}
}
}
// Constantes para classificação de caracteres
const int CHAR_LETRA = 1;
const int CHAR_DIGITO = 2;
const int CHAR_UNDERSCORE = 3;
const int CHAR_PONTO = 4;
const int CHAR_ASPAS = 5;
const int CHAR_ESPACO = 6;
const int CHAR_NEWLINE = 7;
const int CHAR_OUTRO = 0;
int ord(String char) => char.codeUnitAt(0);#include <unordered_map>
#include <array>
#include <string_view>
class AnalisadorLexicoOtimizado {
private:
// Pool de strings para string interning
std::unordered_map<std::string, std::string> poolStrings;
// Cache de classificação de caracteres (ASCII apenas)
std::array<char, 256> classificacaoCaracteres;
// Tabela de palavras-chave por comprimento
std::unordered_map<size_t, std::unordered_map<std::string, TokenType>>
tabelaPalavrasChave;
// Constantes para tipos de caractere
static constexpr char CHAR_LETRA = 1;
static constexpr char CHAR_DIGITO = 2;
static constexpr char CHAR_UNDERSCORE = 3;
static constexpr char CHAR_PONTO = 4;
static constexpr char CHAR_ASPAS = 5;
static constexpr char CHAR_ESPACO = 6;
static constexpr char CHAR_NEWLINE = 7;
static constexpr char CHAR_OUTRO = 0;
void inicializarClassificacaoCaracteres() {
std::fill(classificacaoCaracteres.begin(),
classificacaoCaracteres.end(), CHAR_OUTRO);
// ASCII letters
for (char c = 'a'; c <= 'z'; ++c) {
classificacaoCaracteres[static_cast<unsigned char>(c)] = CHAR_LETRA;
}
for (char c = 'A'; c <= 'Z'; ++c) {
classificacaoCaracteres[static_cast<unsigned char>(c)] = CHAR_LETRA;
}
// Digits
for (char c = '0'; c <= '9'; ++c) {
classificacaoCaracteres[static_cast<unsigned char>(c)] = CHAR_DIGITO;
}
// Special characters
classificacaoCaracteres['_'] = CHAR_UNDERSCORE;
classificacaoCaracteres['.'] = CHAR_PONTO;
classificacaoCaracteres['"'] = CHAR_ASPAS;
// Whitespace
classificacaoCaracteres[' '] = CHAR_ESPACO;
classificacaoCaracteres['\t'] = CHAR_ESPACO;
classificacaoCaracteres['\n'] = CHAR_NEWLINE;
classificacaoCaracteres['\r'] = CHAR_NEWLINE;
}
void inicializarTabelaPalavrasChave() {
std::unordered_map<std::string, TokenType> palavrasChave = {
{"se", TokenType::SE},
{"senao", TokenType::SENAO},
{"enquanto", TokenType::ENQUANTO},
{"para", TokenType::PARA},
{"funcao", TokenType::FUNCAO},
{"retorna", TokenType::RETORNA},
{"var", TokenType::VAR},
{"const", TokenType::CONST}
};
// Organizar por comprimento
for (const auto& [palavra, tipo] : palavrasChave) {
tabelaPalavrasChave[palavra.length()][palavra] = tipo;
}
}
const std::string& internString(const std::string& str) {
auto it = poolStrings.find(str);
if (it != poolStrings.end()) {
return it->second;
}
return poolStrings.emplace(str, str).first->second;
}
std::optional<TokenType> buscarPalavraChave(const std::string& lexema) {
auto it = tabelaPalavrasChave.find(lexema.length());
if (it != tabelaPalavrasChave.end()) {
auto& tabela = it->second;
auto palavra_it = tabela.find(lexema);
if (palavra_it != tabela.end()) {
return palavra_it->second;
}
}
return std::nullopt;
}
public:
AnalisadorLexicoOtimizado() {
inicializarClassificacaoCaracteres();
inicializarTabelaPalavrasChave();
}
std::optional<Token> reconhecerIdentificadorRapido(
std::string_view entrada, size_t& posicao) {
size_t inicio = posicao;
// Primeiro caractere
if (posicao >= entrada.length()) return std::nullopt;
unsigned char primeiroChar = entrada[posicao];
char tipoChar = classificacaoCaracteres[primeiroChar];
if (tipoChar != CHAR_LETRA && tipoChar != CHAR_UNDERSCORE) {
return std::nullopt;
}
++posicao;
// Caracteres subsequentes
while (posicao < entrada.length()) {
unsigned char c = entrada[posicao];
char tipo = classificacaoCaracteres[c];
if (tipo != CHAR_LETRA && tipo != CHAR_DIGITO &&
tipo != CHAR_UNDERSCORE) {
break;
}
++posicao;
}
std::string lexema(entrada.substr(inicio, posicao - inicio));
const std::string& lexemaInternado = internString(lexema);
auto tipoPalavraChave = buscarPalavraChave(lexemaInternado);
TokenType tipo = tipoPalavraChave.value_or(TokenType::IDENTIFICADOR);
return Token{tipo, lexemaInternado, std::nullopt, inicio};
}
std::optional<Token> reconhecerNumeroRapido(
std::string_view entrada, size_t& posicao) {
size_t inicio = posicao;
bool temPonto = false;
// Parte inteira
while (posicao < entrada.length()) {
unsigned char c = entrada[posicao];
if (classificacaoCaracteres[c] != CHAR_DIGITO) break;
++posicao;
}
// Verificar parte decimal
if (posicao < entrada.length() && entrada[posicao] == '.') {
if (posicao + 1 < entrada.length()) {
unsigned char proximoChar = entrada[posicao + 1];
if (classificacaoCaracteres[proximoChar] == CHAR_DIGITO) {
temPonto = true;
++posicao; // Pular o ponto
// Dígitos da parte decimal
while (posicao < entrada.length()) {
unsigned char c = entrada[posicao];
if (classificacaoCaracteres[c] != CHAR_DIGITO) break;
++posicao;
}
}
}
}
std::string lexema(entrada.substr(inicio, posicao - inicio));
if (temPonto) {
double valor = std::stod(lexema);
return Token{TokenType::REAL, lexema, valor, inicio};
} else {
long long valor = std::stoll(lexema);
return Token{TokenType::INTEIRO, lexema, valor, inicio};
}
}
};String Interning: Reutilizar strings idênticas reduz significativamente o uso de memória, especialmente para identificadores que aparecem múltiplas vezes.
Cache de Classificação: Pré-computar a classificação de todos os caracteres ASCII elimina verificações repetitivas durante o processamento.
Lookup Otimizado: Organizar palavras-chave por comprimento permite filtragem rápida antes da comparação de strings.
🎭 Casos Especiais e Peculiaridades
Toda linguagem de programação tem suas peculiaridades léxicas que requerem tratamento especial. Compreender e implementar corretamente estes casos especiais é o que distingue analisadores amadores de implementações profissionais.
🎪 Desafios Léxicos Complexos
Operadores Ambíguos: Como distinguir entre “- -” (dois operadores de subtração) e “–” (operador de decremento)? A solução requer lookahead cuidadoso e regras de precedência claras.
Templates e Generics: Em linguagens como C++, a sequência “>>” pode ser o operador shift right ou o fechamento de dois templates aninhados: vector<vector<int>>. O contexto sintático deve informar a decisão léxica.
Strings Raw: Linguagens modernas frequentemente suportam strings “raw” onde caracteres de escape são ignorados. Python usa r"string", C# usa @"string". Cada sintaxe requer tratamento especializado.
Interpolação de Strings: JavaScript template literals ${expression} e similar constructs misturam código com string literals, requerindo transição dinâmica entre modos de tokenização.
Números em Bases Múltiplas: Hexadecimal (0x1A2B), octal (0o755), binário (0b1010), e até bases arbitrárias requerem validação cuidadosa para evitar interpretações incorretas.
---
displayMode: compact
config:
theme: forest
layout: elk
elk:
mergeEdges: true
nodePlacementStrategy: LINEAR_SEGMENTS
---
graph TD
A[String Interpolada] --> B{Encontrou ${}?}
B -->|Não| C[Continuar String Normal]
B -->|Sim| D[Entrar Modo Expressão]
D --> E[Tokenizar Expressão]
E --> F{Encontrou }?}
F -->|Não| E
F -->|Sim| G[Voltar Modo String]
G --> A
🌟 Reflexões Finais: A Elegância da Análise Léxica
Chegamos ao final de nossa jornada através da análise léxica, e espero que você tenha desenvolvido uma apreciação profunda pela elegância e complexidade desta fase aparentemente simples da compilação.
🎓 Lições Fundamentais Aprendidas
A Beleza da Matemática Aplicada: Você viu como conceitos matemáticos abstratos - autômatos finitos, linguagens regulares, expressões regulares - se materializam em software robusto e eficiente. Esta conexão entre teoria e prática é uma das experiências mais satisfatórias em ciência da computação.
A Importância dos Detalhes: A análise léxica ensina que detalhes aparentemente pequenos - como a ordem de especificação de tokens, estratégias de recuperação de erros, e otimizações de performance - têm impacto desproporcional na qualidade final do sistema.
O Equilíbrio entre Simplicidade e Funcionalidade: Você aprendeu a navegar entre implementações simples que são fáceis de entender e manter, e implementações sofisticadas que oferecem funcionalidades avançadas e performance superior.
A Arte do Design de Interface: A criação de uma interface limpa entre análise léxica e sintática demonstra princípios fundamentais de design de software que se aplicam muito além de compiladores.
Quando você implementa seu analisador léxico, você está participando de uma tradição que remonta aos primórdios da computação. Cada decisão que você toma - desde a especificação de tokens até estratégias de otimização - reflete décadas de evolução na engenharia de compiladores.
A experiência de ver código fonte sendo transformado sistematicamente em uma sequência estruturada de tokens é genuinamente transformadora. Você está testemunhando o primeiro passo no processo quase mágico pelo qual texto sem estrutura se torna programas executáveis.
As habilidades que você desenvolveu transcendem análise léxica. O pensamento sistemático sobre padrões, a capacidade de especificar formalmente comportamentos complexos, e a disciplina de implementar algoritmos robustos servirão você ao longo de toda sua carreira em tecnologia.
🚀 Preparando-se para o Próximo Desafio
A análise léxica produz uma sequência de tokens, mas tokens isolados não constituem programas. Na próxima semana, você descobrirá como gramáticas livres de contexto capturam a estrutura hierárquica das linguagens de programação, permitindo que compiladores compreendam não apenas palavras individuais, mas como essas palavras se combinam para formar expressões, comandos, e programas completos.
🔮 Antecipando Gramáticas Livres de Contexto
A Limitação das Linguagens Regulares: Por mais poderosas que sejam, linguagens regulares não podem capturar estruturas aninhadas como parênteses balanceados ou blocos de código hierárquicos. Esta limitação fundamental motiva a necessidade de ferramentas mais expressivas.
A Ascensão na Hierarquia de Chomsky: Você fará a transição das linguagens regulares (Tipo 3) para linguagens livres de contexto (Tipo 2), descobrindo um universo muito mais rico de padrões estruturais.
Gramáticas como Especificações: Assim como expressões regulares especificam tokens, gramáticas livres de contexto especificarão a sintaxe completa da linguagem Didágica. Você verá como regras gramaticais se traduzem diretamente em algoritmos de parsing.
Da Análise para Síntese: Compreender estruturas sintáticas é o primeiro passo para manipulá-las. As árvores sintáticas que você construirá formarão a base para todas as fases subsequentes do compilador.
Seu analisador léxico funcionará perfeitamente integrado com o parser sintático que você desenvolverá. A interface que você projetou esta semana será testada e refinada, demonstrando como decisões de arquitetura se propagam através de sistemas complexos.
O conhecimento profundo que você adquiriu sobre reconhecimento de padrões e processamento sistemático de entrada será inestimável quando você enfrentar os desafios mais sofisticados da análise sintática. Você está construindo não apenas um compilador, mas uma compreensão fundamental de como linguagens formais funcionam.
Continue com confiança para a próxima etapa da jornada. Você dominou os fundamentos e está preparado para os desafios mais emocionantes que estão por vir. A transformação de tokens em árvores sintáticas será ainda mais satisfatória que a transformação de caracteres em tokens que você acabou de dominar!