Análise Léxica: O Primeiro Passo da Compilação
Bem-vindos à Aula 2 do nosso curso de Compiladores. Exploraremos como um compilador transforma texto em tokens através da análise léxica, etapa fundamental para o processamento de linguagens de programação.
Revisão: A Estrutura de um Compilador
Análise Léxica
Transforma caracteres em tokens
Análise Sintática
Organiza tokens em estrutura hierárquica
Análise Semântica
Verifica significado e consistência
Geração de Código
Produz código objeto final
Antes de avançarmos para a análise léxica, é importante recordar as etapas de compilação. Um compilador transforma código-fonte em código executável através dessas quatro etapas principais, com cada uma tendo papel específico na tradução.
Onde Estamos: Foco na Análise Léxica
Hoje focamos exclusivamente na primeira etapa do processo de compilação: a análise léxica. Esta fase é responsável por ler o fluxo de caracteres do código-fonte e agrupá-los em unidades significativas chamadas tokens.
O analisador léxico (scanner) funciona como um filtro entre o código-fonte e o analisador sintático, simplificando o trabalho das etapas posteriores e realizando as primeiras verificações de validade do código.
Exemplo Motivador: Decompondo em Tokens
Considere esta linha de código simples:
int soma = a + b;
O analisador léxico decompõe esta linha em uma sequência de tokens:
  1. Palavra-chave: int
  1. Identificador: soma
  1. Operador: =
  1. Identificador: a
  1. Operador: +
  1. Identificador: b
  1. Símbolo: ;
Tokens, Lexemas e Padrões: Definições Básicas
Token
Categoria ou classe sintática de elementos léxicos. Exemplos: IDENTIFICADOR, NÚMERO, OPERADOR, PALAVRA-CHAVE.
Lexema
Sequência de caracteres que forma uma unidade léxica concreta. Exemplos: "soma", "123", "+", "if".
Padrão
Descrição das regras que determinam quais lexemas pertencem a qual token. Geralmente expresso como expressão regular.
Entender estas distinções é fundamental para compreender o processo de análise léxica e implementar um analisador eficiente.
Exemplo Prático de Tokens em Código
while (count < 10) { sum = sum + value; count = count + 1; }
Tokens identificados:
  • WHILE - palavra-chave "while"
  • ABRE_PAREN - símbolo "("
  • ID - identificador "count"
  • MENOR - operador "<"
  • NUM - número "10"
  • FECHA_PAREN - símbolo ")"
  • ABRE_CHAVE - símbolo "{"
  • ...
Cada elemento significativo do código é classificado em um tipo de token específico, facilitando o processamento nas etapas seguintes da compilação.
Classificação de Tokens
Palavras-chave
Termos reservados da linguagem como "if", "while", "int", "return".
Identificadores
Nomes definidos pelo programador para variáveis, funções, classes.
Operadores
Símbolos para operações como +, -, *, /, =, ==, !=.
Literais
Valores constantes como números, strings, caracteres, booleanos.
Delimitadores
Símbolos que estruturam o código: ( ) { } [ ] , ; .
Erros Léxicos: Identificação e Tratamento
O que são erros léxicos?
Ocorrem quando o analisador léxico encontra sequências de caracteres que não correspondem a nenhum padrão válido de token na linguagem.
Exemplos comuns:
  • Caracteres inválidos: @#¢ em linguagens que não os suportam
  • Strings não fechadas: "texto sem aspas de fechamento
  • Números mal formados: 12.34.56
Estratégias de tratamento:
  1. Reportar erro com linha e coluna
  1. Tentar recuperação (pular caractere, inserir fechamento)
  1. Continuar análise para encontrar mais erros
Função do Analisador Léxico no Compilador
1
Tokenização
Transformar o fluxo de caracteres em tokens significativos, eliminando elementos irrelevantes como espaços em branco e comentários.
2
Remoção de Ruído
Filtrar comentários, espaços, tabulações e quebras de linha, simplificando o trabalho do analisador sintático.
3
Detecção de Erros
Identificar e reportar erros léxicos, como caracteres inválidos ou literais mal formados.
4
Interface com o Analisador Sintático
Fornecer tokens sob demanda para o analisador sintático, frequentemente através de uma função getNextToken().
Expressões Regulares: Definição e Motivação
O que são Expressões Regulares?
Expressões Regulares (ERs) são notações concisas e poderosas para descrever padrões de texto. Na análise léxica, são usadas para definir precisamente os padrões que cada tipo de token deve seguir.
Por que usar ERs?
  • Notação formal e precisa para especificar tokens
  • Facilmente convertíveis para implementações de autômatos
  • Linguagem padrão para reconhecimento de padrões
  • Suportadas diretamente por muitas linguagens e ferramentas
Notação de Expressões Regulares
Operadores Básicos
  • | - alternativa (a|b = a ou b)
  • * - repetição (0 ou mais vezes)
  • + - repetição (1 ou mais vezes)
  • ? - opcional (0 ou 1 vez)
Conjuntos e Ranges
  • [abc] - qualquer um dos caracteres a, b ou c
  • [a-z] - qualquer letra minúscula
  • [^0-9] - qualquer caractere exceto dígitos
Agrupamento e Escapes
  • (ab) - agrupamento (ab tratado como unidade)
  • \d - dígito (equivalente a [0-9])
  • \w - caractere alfanumérico
Esta notação permite descrever de forma precisa os padrões para reconhecimento de tokens em um analisador léxico.
ERs Comuns para Identificadores e Números
Identificadores
letra(letra|dígito|_)*
Ou em notação mais formal:
[a-zA-Z][a-zA-Z0-9_]*
Exemplos válidos: x, contador, valor_1, soma2
Exemplos inválidos: 1x, _var (em algumas linguagens)
Números
Inteiros:
dígito+
Ou:
[0-9]+
Ponto flutuante:
dígito+\.dígito+
Ou:
[0-9]+\.[0-9]+
Exemplos: 123, 0, 3.14, 0.001
ERs como Forma de Descrever Padrões de Tokens
As ERs são a forma mais comum e precisa de especificar os padrões que determinam quais sequências de caracteres pertencem a quais tipos de tokens, formando a base para a implementação do analisador léxico.
Limitações das Expressões Regulares
O que ERs não conseguem fazer:
  • Reconhecer linguagens dependentes de contexto
  • Verificar se parênteses estão balanceados
  • Contar e comparar ocorrências (ex: verificar se há igual número de 'a's e 'b's)
  • Reconhecer aninhamentos arbitrários
Implicações para compiladores:
Por isso, o analisador léxico é apenas a primeira etapa. A análise sintática (próxima fase) utiliza gramáticas livres de contexto para lidar com estruturas mais complexas que as ERs não conseguem capturar.
Introdução aos Autômatos Finitos Determinísticos (AFD)
Um Autômato Finito Determinístico (AFD) é um modelo matemático composto por:
  • Estados: representados por círculos
  • Transições: setas rotuladas com símbolos de entrada
  • Estado inicial: indicado por uma seta de entrada
  • Estados finais: representados por círculos duplos
O AFD processa uma sequência de entrada símbolo por símbolo, movendo-se de um estado para outro conforme as transições definidas. Se terminar em um estado final após processar toda a entrada, a sequência é aceita.
Diagrama de um Autômato Simples
Exemplo: Autômato para reconhecer a palavra-chave "if"
Este autômato possui:
  • Estado inicial q0
  • Estado q1 após reconhecer 'i'
  • Estado final q2 após reconhecer 'f'
O autômato aceita apenas a sequência exata "if". Qualquer outra sequência levará a um estado não final ou a um erro (transição indefinida).
AFD vs AFND: Diferenças Conceituais
Autômato Finito Determinístico (AFD)
  • Para cada estado e símbolo, existe no máximo uma transição
  • Não permite transições vazias (ε-transições)
  • Comportamento previsível e determinístico
  • Mais eficiente para implementação
Autômato Finito Não-Determinístico (AFND)
  • Pode haver múltiplas transições para o mesmo símbolo
  • Permite transições vazias (ε-transições)
  • Conceitualmente mais simples de construir
  • Pode ser convertido para AFD equivalente
Na prática, AFNDs são mais fáceis de projetar a partir de expressões regulares, mas AFDs são mais eficientes para implementação. Todo AFND pode ser convertido em um AFD equivalente.
Construção de Autômato para um Identificador
Um autômato para reconhecer identificadores como nome, x1, contador_total:
  1. Comece no estado inicial q0
  1. Se encontrar uma letra, vá para o estado q1 (aceitação)
  1. Em q1, se encontrar letra, dígito ou underscore (_), permaneça em q1
  1. Qualquer outro caractere não é aceito neste padrão
Este autômato implementa a expressão regular: [a-zA-Z][a-zA-Z0-9_]*
Transição de ER para Autômato
Processo de Conversão
  1. Converter ER para AFND (algoritmo de Thompson)
  1. Converter AFND para AFD (construção de subconjuntos)
  1. Minimizar o AFD resultante (opcional)
O processo completo pode ser complexo, mas existem algoritmos bem estabelecidos para automatizá-lo.
Na prática, ferramentas de geração de analisadores léxicos como Flex e bibliotecas como PLY fazem essa conversão automaticamente, permitindo que você defina tokens usando expressões regulares.
Ferramentas Tradicionais: Lex/Flex
O que são Lex e Flex?
Ferramentas clássicas para geração de analisadores léxicos a partir de especificações de expressões regulares.
  • Lex: original do Unix, gera código C
  • Flex: versão mais rápida e flexível, também gera código C
Estrutura de um arquivo Lex/Flex:
  1. Definições: macros e configurações
  1. Regras: padrões (ERs) e ações (código C)
  1. Código auxiliar: funções C adicionais
%{ /* Código C de configuração */ %} /* Definições */ DIGITO [0-9] ID [a-zA-Z][a-zA-Z0-9_]* %% /* Regras */ {DIGITO}+ { return NUM; } {ID} { return ID; } "+" { return MAIS; } %% /* Código auxiliar */ int main() { yylex(); return 0; }
Alternativa Prática: Uso de Python com PLY
PLY (Python Lex-Yacc)
Biblioteca Python que implementa os princípios do Lex e Yacc, permitindo criar analisadores léxicos e sintáticos em Python puro.
Vantagens do PLY:
  • Sintaxe mais simples e moderna
  • Integração fácil com código Python existente
  • Depuração mais simples
  • Sem necessidade de ferramentas externas
  • Ideal para fins didáticos e protótipos
Exemplo Básico com PLY - Definindo Tokens com Regex
import ply.lex as lex # Lista de nomes de tokens tokens = ( 'NUMBER', 'PLUS', 'MINUS', 'TIMES', 'DIVIDE', 'ID', ) # Expressões regulares para tokens simples t_PLUS = r'\+' t_MINUS = r'-' t_TIMES = r'\*' t_DIVIDE = r'/' # Expressão regular com ação para números def t_NUMBER(t): r'\d+' t.value = int(t.value) return t # Expressão regular para identificadores def t_ID(t): r'[a-zA-Z][a-zA-Z0-9_]*' return t # Caracteres ignorados (espaços e tabs) t_ignore = ' \t' # Construir o lexer lexer = lex.lex()
Este código define um analisador léxico simples usando PLY, com tokens para números, operadores e identificadores.
Função t_tokenname em PLY
Estrutura de uma função de token:
def t_NOME_DO_TOKEN(t): r'expressão_regular' # código Python opcional return t
Componentes principais:
  • Nome da função: deve começar com t_ seguido do nome do token
  • Docstring: contém a expressão regular (prefixo r para raw string)
  • Parâmetro t: objeto token com atributos como value, type, lineno, lexpos
  • Código: manipulação opcional do token
  • return t: retorna o token processado
# Exemplo de função para reconhecer números def t_NUMBER(t): r'\d+' # Converte string para inteiro t.value = int(t.value) return t # Exemplo para palavras-chave def t_ID(t): r'[a-zA-Z][a-zA-Z0-9_]*' # Verifica se é palavra-chave if t.value in keywords: t.type = t.value.upper() return t
Tratamento de Espaços e Erros com PLY
Ignorando espaços e quebras de linha
# Espaços e tabulações t_ignore = ' \t' # Quebras de linha def t_newline(t): r'\n+' t.lexer.lineno += len(t.value)
O atributo t_ignore faz o lexer pular caracteres específicos, enquanto a função t_newline conta linhas para rastreamento de erros.
Tratamento de erros léxicos
def t_error(t): print(f"Caractere ilegal '{t.value[0]}'") print(f"na linha {t.lexer.lineno}") t.lexer.skip(1)
A função t_error é chamada quando o lexer encontra um caractere que não corresponde a nenhum padrão. Geralmente reporta o erro e avança um caractere com skip(1).
Execução e Teste de um Analisador Léxico Simples
Código para teste do analisador
# Construir o lexer lexer = lex.lex() # Texto de entrada para teste data = ''' x = 10 + y * 5 if (contador > 20) { resultado = 30; } ''' # Fornecer a entrada ao lexer lexer.input(data) # Tokenizar for tok in lexer: print(tok)
Saída do teste
LexToken(ID,'x',2,1) LexToken(EQUALS,'=',2,3) LexToken(NUMBER,10,2,5) LexToken(PLUS,'+',2,8) LexToken(ID,'y',2,10) LexToken(TIMES,'*',2,12) LexToken(NUMBER,5,2,14) LexToken(IF,'if',3,16) LexToken(LPAREN,'(',3,19) LexToken(ID,'contador',3,20) ...
Cada token mostra seu tipo, valor, linha e posição.
Exercício 1: Reconhecer Números Inteiros e Identificadores
Objetivo
Implementar um analisador léxico em PLY que reconheça números inteiros e identificadores conforme as regras padrão de linguagens de programação.
Especificações
  • Número inteiro: sequência de um ou mais dígitos
  • Identificador: letra seguida de letras, dígitos ou underscore
import ply.lex as lex # Lista de tokens tokens = ('NUMBER', 'ID') # Regras def t_NUMBER(t): r'\d+' t.value = int(t.value) return t def t_ID(t): r'[a-zA-Z][a-zA-Z0-9_]*' return t # Ignorar espaços t_ignore = ' \t\n' # Tratamento de erros def t_error(t): print(f"Caractere ilegal: {t.value[0]}") t.lexer.skip(1) # Construir lexer lexer = lex.lex()
Exercício 2: Reconhecer Operadores Aritméticos
Objetivo
Ampliar o analisador léxico para reconhecer os operadores aritméticos básicos: +, -, *, /.
Especificações
  • Definir tokens para cada operador
  • Usar expressões regulares simples
  • Testar com expressões aritméticas básicas
# Adicionar à lista de tokens tokens = ('NUMBER', 'ID', 'PLUS', 'MINUS', 'TIMES', 'DIVIDE') # Regras para operadores t_PLUS = r'\+' t_MINUS = r'-' t_TIMES = r'\*' t_DIVIDE = r'/' # Testar com data = "x = 10 + y * 5 - z / 2" lexer.input(data) for tok in lexer: print(tok)
Desafio Prático: Analisador para Expressões Aritméticas
Implemente um analisador léxico completo para expressões aritméticas que reconheça:
  • Números inteiros e de ponto flutuante
  • Identificadores
  • Operadores: +, -, *, /, = (atribuição)
  • Parênteses: (, )
  • Ponto e vírgula: ;
O analisador deve ignorar espaços em branco e comentários (// para comentários de linha). Adicionalmente, implemente tratamento de erros que indique a linha e a posição do erro léxico.
Demonstração: Passo a Passo da Execução no Terminal
Código de teste:
# Entrada para teste data = ''' a = 10.5; b = 20; resultado = (a + b) * 2; // Este é um comentário c = 3.14159; @erro // caractere inválido ''' # Executar o lexer lexer.input(data) for tok in lexer: print(tok)
Saída esperada no terminal:
LexToken(ID,'a',2,1) LexToken(EQUALS,'=',2,3) LexToken(FLOAT,10.5,2,5) LexToken(SEMICOLON,';',2,9) LexToken(ID,'b',3,1) ... Caractere ilegal: @ na linha 7, posição 1 LexToken(ID,'erro',7,2)
Observe como o analisador léxico processa cada token, incluindo o tratamento do erro no caractere inválido @.
Resumo da Aula: Análise Léxica
Conceitos Fundamentais
Tokens, lexemas e padrões são os elementos básicos da análise léxica. O analisador léxico é responsável por transformar o código-fonte em uma sequência de tokens para o analisador sintático.
Expressões Regulares
Ferramenta poderosa para descrever padrões de tokens usando uma notação formal. Operadores como *, +, ?, | permitem definir padrões complexos de forma concisa.
Autômatos Finitos
Modelos matemáticos que implementam expressões regulares. AFDs são mais eficientes para implementação, enquanto AFNDs são mais fáceis de construir a partir de ERs.
Implementação com PLY
A biblioteca PLY oferece uma forma simples e poderosa de implementar analisadores léxicos em Python, usando expressões regulares para definir tokens.
Tarefa para a Próxima Aula
Atividade Prática
  1. Criar um analisador léxico que reconheça as palavras-chave if, else e while
  1. Implementar reconhecimento de operadores relacionais: ==, !=, >, <, >=, <=
  1. Adicionar suporte para comentários de linha // e de bloco /* ... */
  1. Explorar erros léxicos intencionalmente e observar o comportamento do analisador
Preparação para a Próxima Aula
Na próxima aula, abordaremos a Análise Sintática, que utiliza os tokens produzidos pelo analisador léxico para construir uma árvore sintática que representa a estrutura do programa.
Leitura recomendada:
  • Capítulo sobre gramáticas livres de contexto
  • Introdução a parsers descendentes e ascendentes
Tokens e Seu Papel na Compilação
Por que tokens são importantes?
Os tokens representam a menor unidade sintática significativa em uma linguagem de programação. Eles são o resultado da análise léxica e servem como entrada para a análise sintática.
Benefícios da tokenização:
  1. Simplificação: reduz a complexidade do analisador sintático
  1. Abstração: remove detalhes irrelevantes como espaços e comentários
  1. Eficiência: permite processar unidades lógicas em vez de caracteres individuais
  1. Detecção precoce de erros: identifica problemas léxicos antes da análise sintática
Representação Interna de Tokens
Estrutura Típica de um Token
class Token: def __init__(self, type, value, line, position): self.type = type # Categoria (ID, NUM, etc.) self.value = value # Lexema (texto real) self.line = line # Linha no código self.position = position # Posição na linha
Atributos Importantes
  • Tipo: classificação do token (categoria)
  • Valor: o texto real encontrado (lexema)
  • Posição: linha e coluna para mensagens de erro
  • Atributos específicos: valor numérico para números, etc.
No PLY
# O objeto token no PLY print(tok.type) # Tipo do token print(tok.value) # Valor/lexema print(tok.lineno) # Linha print(tok.lexpos) # Posição no texto
Implementação de uma Tabela de Símbolos Simples
O que é uma Tabela de Símbolos?
A tabela de símbolos é uma estrutura de dados que armazena informações sobre identificadores no programa. Durante a análise léxica, ela pode ser usada para:
  • Diferenciar identificadores de palavras-chave
  • Armazenar informações sobre símbolos encontrados
  • Servir como base para fases posteriores da compilação
# Implementação simples em Python class SymbolTable: def __init__(self): self.symbols = {} def insert(self, name, type=None): if name not in self.symbols: self.symbols[name] = { 'type': type, 'line': [], 'used': False } def lookup(self, name): return name in self.symbols def get_info(self, name): if self.lookup(name): return self.symbols[name] return None
Uso da Tabela de Símbolos no Analisador Léxico
import ply.lex as lex # Palavras-chave da linguagem keywords = {'if', 'else', 'while', 'int', 'float'} # Tabela de símbolos symbol_table = {} tokens = ['ID', 'NUMBER'] + [k.upper() for k in keywords] def t_ID(t): r'[a-zA-Z][a-zA-Z0-9_]*' # Verifica se é uma palavra-chave if t.value in keywords: t.type = t.value.upper() else: # Registra na tabela de símbolos if t.value not in symbol_table: symbol_table[t.value] = { 'type': None, 'lines': [t.lineno], 'declared': False } else: symbol_table[t.value]['lines'].append(t.lineno) return t
Este código mostra como integrar uma tabela de símbolos simples ao analisador léxico para rastrear identificadores e suas ocorrências.
Reconhecimento de Comentários em PLY
Tipos de Comentários
  1. Comentários de linha: começam com // e terminam no final da linha
  1. Comentários de bloco: delimitados por /* e */, podem se estender por múltiplas linhas
O tratamento de comentários é um desafio interessante na análise léxica, pois eles podem conter qualquer caractere (inclusive aqueles que normalmente seriam parte de tokens) e precisam ser completamente ignorados.
# Comentários de linha def t_COMMENT_LINE(t): r'//.*' # Ignora o comentário (não retorna token) pass # Comentários de bloco (multi-linha) def t_COMMENT_BLOCK(t): r'/\*(.|\n)*?\*/' # Conta novas linhas no comentário t.lexer.lineno += t.value.count('\n') # Ignora o comentário pass
Estas funções capturam os comentários mas não retornam tokens, efetivamente removendo-os do fluxo de tokens.
Reconhecimento de Strings e Caracteres
Desafios com Strings
  • Delimitação por aspas (simples ou duplas)
  • Sequências de escape (\n, \t, \", etc.)
  • Strings que se estendem por múltiplas linhas
  • Tratamento de erro para strings não fechadas
# String com aspas duplas def t_STRING(t): r'"([^"\\]|\\.)*"' # Remove as aspas t.value = t.value[1:-1] # Processa sequências de escape t.value = t.value.replace('\\n', '\n') t.value = t.value.replace('\\t', '\t') t.value = t.value.replace('\\"', '"') return t # Erro para string não fechada def t_error_string(t): r'"([^"\\]|\\.)*\n' print(f"String não fechada na linha {t.lexer.lineno}") t.lexer.skip(len(t.value))
Analisador Léxico para Operadores Compostos
Operadores compostos como ==, !=, <=, >= apresentam um desafio: precisamos garantir que sejam reconhecidos como um único token e não como dois tokens separados.
# Operadores de comparação compostos t_EQUALS = r'==' t_NOTEQUALS = r'!=' t_LESSEQUAL = r'<=' t_GREATEREQUAL = r'>=' # Operadores simples (devem vir depois dos compostos!) t_ASSIGN = r'=' t_LESS = r'<' t_GREATER = r'>'
A ordem das regras é importante: operadores compostos devem ser definidos antes dos simples para evitar que "==" seja interpretado como dois tokens "=" separados.
Tratamento de Números em Diferentes Bases
Formatos Comuns
  • Decimal: 123, 42
  • Hexadecimal: 0x1A, 0xFF
  • Octal: 0o777, 0o123
  • Binário: 0b1010, 0b11001
Um analisador léxico robusto deve reconhecer números em diferentes bases e convertê-los para o valor numérico correto.
def t_NUMBER(t): r'0x[0-9a-fA-F]+|0b[01]+|0o[0-7]+|\d+(\.\d+)?' # Hexadecimal if t.value.startswith('0x'): t.value = int(t.value[2:], 16) # Binário elif t.value.startswith('0b'): t.value = int(t.value[2:], 2) # Octal elif t.value.startswith('0o'): t.value = int(t.value[2:], 8) # Ponto flutuante elif '.' in t.value: t.value = float(t.value) # Decimal else: t.value = int(t.value) return t
Estados no Analisador Léxico
O Que São Estados no Lexer?
Estados permitem que o analisador léxico mude seu comportamento dependendo do contexto. São úteis para:
  • Processar diferentes seções do código
  • Lidar com construções complexas como strings multi-linha
  • Analisar blocos de código com regras diferentes
No PLY:
Podemos usar "estados léxicos" definindo tokens específicos para cada estado e mudando entre eles.
# Definição de estados states = ( ('string', 'exclusive'), ('comment', 'exclusive'), ) def t_begin_string(t): r'"' t.lexer.string_start = t.lexer.lexpos t.lexer.begin('string') # Muda para estado string def t_string_end(t): r'"' t.lexer.begin('INITIAL') # Volta ao estado normal # Obtém o conteúdo da string t.value = t.lexer.lexdata[t.lexer.string_start:t.lexer.lexpos] t.type = 'STRING' return t
Reconhecimento de Identificadores em Diferentes Linguagens
O reconhecimento de identificadores varia conforme a linguagem, e um analisador léxico deve se adaptar às regras específicas da linguagem que está sendo analisada.
Eficiência do Analisador Léxico
Impacto no Desempenho
O analisador léxico é executado sobre cada caractere do código-fonte, por isso sua eficiência impacta diretamente o desempenho do compilador como um todo.
Otimizações Comuns
  • Uso de autômatos finitos determinísticos (AFDs)
  • Tabelas de transição pré-computadas
  • Reconhecimento em um único passo (sem backtracking)
  • Minimização do número de estados do autômato
Buffering
Implementação de buffers para leitura eficiente do arquivo de entrada, reduzindo operações de I/O e permitindo lookhead quando necessário.
Ordem das Regras
Definir as regras em ordem de frequência ou complexidade pode melhorar o desempenho, com padrões mais comuns ou simples verificados primeiro.
História da Análise Léxica
1
Década de 1950
Primeiros compiladores usavam análise léxica ad-hoc, com código específico para cada linguagem.
2
1968
Publicação dos trabalhos sobre expressões regulares e autômatos finitos aplicados à análise léxica.
3
1975
Criação do Lex por Mike Lesk e Eric Schmidt na Bell Labs, primeiro gerador de analisadores léxicos amplamente utilizado.
4
1987
Desenvolvimento do Flex (Fast Lexical Analyzer Generator) como alternativa de código aberto ao Lex.
5
Anos 2000
Surgimento de bibliotecas como PLY, ANTLR e ferramentas integradas em linguagens modernas.
Análise Léxica em Linguagens Reais
A análise léxica varia significativamente entre linguagens de programação. Algumas diferenças notáveis incluem:
Uso da Classe StringIO para Testes
Facilitando Testes do Analisador Léxico
A classe StringIO do módulo io do Python permite criar objetos semelhantes a arquivos baseados em strings, o que é útil para testar analisadores léxicos sem precisar criar arquivos físicos.
Vantagens:
  • Simples de usar nos testes unitários
  • Permite múltiplos testes com diferentes entradas
  • Não requer operações de I/O com disco
  • Integra-se bem com frameworks de teste
import io import ply.lex as lex import unittest class TestLexer(unittest.TestCase): def setUp(self): self.lexer = lex.lex() def test_simple_tokens(self): data = io.StringIO("x = 10 + 20;") self.lexer.input(data.read()) # Verificar os tokens um a um tok = self.lexer.token() self.assertEqual(tok.type, 'ID') self.assertEqual(tok.value, 'x') tok = self.lexer.token() self.assertEqual(tok.type, 'EQUALS') self.assertEqual(tok.value, '=') # E assim por diante...
Palavras-chave e Identificadores: Estratégias de Diferenciação
Abordagens Comuns
  1. Tabela de palavras reservadas: verificar se um identificador está na lista de palavras-chave
  1. Regras específicas: definir uma regra separada para cada palavra-chave
  1. Combinação: usar uma regra geral para identificadores e depois verificar
# Abordagem 1: Tabela de palavras reservadas keywords = { 'if': 'IF', 'else': 'ELSE', 'while': 'WHILE', 'for': 'FOR', 'return': 'RETURN' } # Na função do token def t_ID(t): r'[a-zA-Z_][a-zA-Z0-9_]*' t.type = keywords.get(t.value, 'ID') return t
Esta abordagem é flexível e permite adicionar facilmente novas palavras-chave.
Análise Léxica em Linguagens com Indentação Significativa
O Desafio da Indentação
Em linguagens como Python, a indentação define blocos de código em vez de chaves ou palavras-chave. Isso apresenta desafios únicos para o analisador léxico:
  • Rastreamento do nível de indentação
  • Geração de tokens INDENT e DEDENT
  • Tratamento consistente de tabs vs. espaços
# Controle de indentação no PLY def t_newline(t): r'\n+' t.lexer.lineno += len(t.value) # Calcular indentação da próxima linha t.lexer.begin('INDENT') def t_INDENT_spaces(t): r'[ \t]+' # Contar espaços indent = 0 for c in t.value: if c == ' ': indent += 1 elif c == '\t': indent += 8 - (indent % 8) # Comparar com nível anterior if indent > t.lexer.indent_stack[-1]: t.lexer.indent_stack.append(indent) t.type = 'INDENT' return t # ...
Análise Léxica em Tempo de Execução
Casos de Uso:
  • Interpretadores interativos (REPLs)
  • Avaliação de expressões em tempo de execução
  • Templates e engines de script incorporados
  • DSLs (Domain Specific Languages) dinâmicas
Em alguns sistemas, a análise léxica não é apenas uma fase de compilação, mas um processo contínuo durante a execução do programa.
# Exemplo simples de avaliador de expressões def evaluate_expression(expr_str): # Inicializar o lexer lexer = lex.lex() lexer.input(expr_str) # Obter tokens tokens = [] for tok in lexer: tokens.append(tok) # Analisar e avaliar... result = parse_and_evaluate(tokens) return result # Uso em um programa maior user_input = input("Digite uma expressão: ") try: result = evaluate_expression(user_input) print(f"Resultado: {result}") except Exception as e: print(f"Erro na expressão: {e}")
Análise Léxica e Internacionalização
Com a globalização do desenvolvimento de software, os analisadores léxicos modernos precisam lidar com caracteres internacionais:
  • Unicode: suporte a caracteres de todos os idiomas e sistemas de escrita
  • Identificadores não-ASCII: permitir letras não-latinas em nomes de variáveis
  • Ordenação: considerar regras de ordenação específicas de cada idioma
  • Caracteres bidirecionais: lidar com idiomas que se escrevem da direita para a esquerda
Em Python 3, por exemplo, é possível usar letras acentuadas e caracteres Unicode em identificadores, o que exige um analisador léxico que compreenda adequadamente essas regras.
Próximos Passos: Preparação para Análise Sintática
Conexão com a Próxima Fase
Agora que compreendemos como transformar código-fonte em tokens, estamos prontos para avançar para a análise sintática, onde esses tokens serão organizados em estruturas hierárquicas.
O que vem pela frente:
  • Gramáticas livres de contexto
  • Árvores sintáticas
  • Métodos de parsing (top-down, bottom-up)
  • Implementação de parsers com PLY.yacc
Na próxima aula, veremos como os tokens produzidos pelo analisador léxico são combinados para formar estruturas mais complexas, seguindo as regras gramaticais da linguagem de programação.