Aula 04: Análise Léxica: Conceitos e Autômatos

Objetivos

Ao final desta aula, você será capaz de:

• Distinguir com precisão padrão, lexema e token e explicar o papel de cada um no pipeline.
• Descrever o funcionamento de um scanner em termos de autômatos finitos (AFD/AFN).
• Identificar desafios de implementação: lookahead, bufferização, sentinelas e tratamento de erros léxicos.
• Relacionar a análise léxica com a fase seguinte (parser) e com o projeto Mini-Pascal.

Motivação e papel no pipeline

A análise léxica é a primeira interface entre o compilador e o código fonte. Ela precisa ser:

• Eficiente: toca cada caractere ao menos uma vez; ineficiência aqui se propaga.
• Robusta: um scanner mal projetado pode gerar tokens incorretos e mascarar erros reais.
• Flexível: deve acompanhar a evolução da linguagem (novos operadores, palavras-chave) sem virar um emaranhado de condicionais.

Fluxo de dados do scanner

O diagrama abaixo resume a posição do scanner no pipeline e o que ele consome/produz.

flowchart LR
  Fonte[Arquivo fonte] --> Buf[Buffer]
  Buf --> Scan[Scanner]
  Scan --> Tokens[Sequência de tokens]
  Tokens --> Parser[Parser]
  Scan --> Erro[Erros léxicos]

O scanner lê caracteres (geralmente de um buffer), agrupa sequências em lexemas, classifica cada lexema segundo um padrão e devolve tokens ao parser. Erros léxicos (símbolo inválido, string não fechada, etc.) devem ser reportados com localização (linha/coluna).

Conteúdo

1. Padrão, lexema e token

É essencial distinguir três conceitos:

Conceito	Descrição	Exemplo
Padrão	Regra abstrata que define uma categoria de lexemas; em geral expressa por ER ou autômato.	“Um ou mais dígitos”; “letra seguida de letras/dígitos”.
Lexema	Sequência concreta de caracteres no código que casa com um padrão.	42, 1024, 0; x, count, i.
Token	Estrutura de dados devolvida ao parser: (tipo, atributo). O tipo identifica a categoria; o atributo pode ser o lexema, um valor numérico ou um ponteiro para a tabela de símbolos.	<NUMBER, 42>, <ID, "count">, <IF, ->.

Observação: Tokens “fixos” (palavras-chave como if, operadores como +) em geral não precisam de atributo (o tipo já identifica). Tokens “variáveis” (identificadores, literais numéricos, strings) carregam o lexema ou uma representação interna (número, entrada na tabela de símbolos).

2. Autômatos finitos e o scanner

O reconhecimento de cada padrão de token pode ser modelado por um autômato finito. Na prática, todos os padrões são combinados em um único autômato (por exemplo, AFD) cujos estados finais estão associados a ações (qual token retornar e qual atributo preencher).

flowchart LR
  subgraph modelo [Modelo do scanner]
    ER[Padrões ER] --> AFN[AFN]
    AFN --> AFD[AFD]
    AFD --> Sim[Simulação]
    Sim --> Token[Token]
  end

• AFN (Autômato Finito Não-Determinístico): pode ter várias transições para o mesmo símbolo e transições \(\epsilon\); reconhece a mesma classe de linguagens que AFD, mas a simulação direta é mais cara.
• AFD (Autômato Finito Determinístico): para cada estado e cada símbolo há no máximo uma transição; a simulação é um loop que, a cada caractere, faz uma única transição. É a base de implementações eficientes (tabela de transição ou código gerado).

A construção de um AFD a partir das ERs dos tokens (via Thompson e construção de subconjuntos) é o tema da Aula 05; aqui o foco é o papel do scanner e os conceitos de padrão, lexema e token.

3. Lookahead

Muitas vezes o scanner precisa “espiar” o próximo caractere para decidir qual token reconhecer.

Exemplo: Ao ler <, o scanner não sabe, só com esse caractere, se será:

• < (menor que),
• <= (menor ou igual),
• <> (diferente, em algumas linguagens),
• ou início de <= (outro operador).

Estratégias comuns:

• Lookahead de um caractere: manter um caractere “à frente”; após consumir um token, o próximo caractere já está disponível.
• Buffer com ponteiro: avançar o ponteiro apenas quando um token for concluído; o “próximo” caractere é o que está na posição atual após o reconhecimento.

A ordem das regras e a regra do maximal munch (maior lexema possível) também resolvem ambiguidades: por exemplo, <= deve ser reconhecido como um único token quando houver uma regra que o defina.

4. Bufferização

Ler o arquivo caractere a caractere com chamadas de sistema seria muito lento. Na prática:

• Um buffer (por exemplo, 4 KB ou 8 KB) é preenchido com um bloco de caracteres.
• O scanner consome caracteres do buffer; quando o buffer se esgota, um novo bloco é lido.
• Buffer duplo: dois buffers alternados permitem que o scanner “olhe à frente” além do fim de um buffer sem perder caracteres (técnica clássica em geradores como Lex/Flex).

Objetivo: reduzir chamadas ao sistema operacional e manter o código simples (ponteiro de leitura, verificação de fim de buffer).

5. Sentinelas

Para evitar verificar “estou no fim do buffer?” a cada avanço de caractere, usa-se uma sentinela: um caractere especial (por exemplo, EOF ou um valor que não aparece no alfabeto normal) colocado após o último caractere válido do buffer. Quando o scanner encontra esse valor, sabe que deve recarregar o buffer ou encerrar a leitura. Isso torna o loop interno do scanner mais rápido.

6. Tratamento de erros léxicos

Erros léxicos típicos:

• Símbolo inválido: caractere que não pertence a nenhum padrão (ex.: @ em uma linguagem que não o define).
• String não fechada: aspas de abertura sem aspas de fechamento até o fim da linha ou arquivo.
• Número mal formado: ex.: 12.34.56 se a linguagem não permite dois pontos decimais.

O scanner deve:

• Reportar o erro com localização (linha, coluna).
• Decidir se aborta ou recupera (por exemplo, ignora o caractere inválido e tenta continuar) para permitir encontrar mais erros no mesmo arquivo. A recuperação não deve gerar tokens que confundam o parser de forma grave.

Exemplo: trecho de código e tokens

Para uma linha como:

if (x <= 10) result = 42;

uma sequência típica de tokens poderia ser:

IF LPAR ID("x") LE NUMBER(10) RPAR ID("result") ASSIGN NUMBER(42) SEMICOLON

O parser não vê mais os caracteres nem os espaços; só essa sequência de tokens. Por isso a definição precisa dos padrões e a ordem das regras (por exemplo, palavras-chave antes de identificador) são importantes.

Conexões com o projeto Mini-Pascal

• Na Etapa 2 você implementa um scanner manual para Mini-Pascal: definição dos tipos de token, padrões (por ER ou autômato), lookahead quando necessário, e entrega de tokens ao parser.
• Na Etapa 4, ao usar ANTLR, as regras léxicas substituem o scanner manual; os conceitos de padrão, lexema e token continuam os mesmos.
• Decisões de design: como tratar comentários (ignorar e não gerar token), delimitadores, palavras-chave vs identificadores (ordem das regras ou tabela de palavras reservadas).

Resumo

• Padrão = regra que define uma categoria; lexema = sequência que casa; token = (tipo, atributo) para o parser.
• O scanner pode ser visto como a simulação de um AFD sobre a entrada; AFD é obtido a partir das ERs dos tokens.
• Lookahead, bufferização e sentinelas são técnicas para eficiência e correção.
• Erros léxicos devem ser reportados com localização; recuperação deve ser controlada para não gerar tokens incoerentes.

Perguntas de reflexão

• Por que não é uma boa ideia deixar o parser “ver” caracteres individuais em vez de tokens?
• Como você implementaria lookahead de um caractere em um scanner que usa um único buffer e um ponteiro?
• Dê um exemplo de linguagem real em que o mesmo lexema pode corresponder a tokens diferentes conforme o contexto (dica: palavras-chave vs identificadores).

Referências

• Aho et al. (2006). Compilers: Principles, Techniques, and Tools. Cap. 3.
• Cooper & Torczon (2011). Engineering a Compiler.

Materiais da aula

• Capítulo em PDF
• Slides
• Questionário

Última atualização: 08/03/2026