Aula 17 - Análise Léxica e Autômatos Finitos 🔍

📑 1. Fundamentos Teóricos & Análise Técnica

Um Compilador é um pipeline complexo de transformação de programas que traduz código-fonte de alto nível para linguagem de máquina ou bytecode intermediário. A primeira fase desse pipeline é a Análise Léxica (Lexical Analysis / Scanning).

O papel do Lexer: 1. Lê o arquivo de código-fonte caractere por caractere a partir de um buffer de entrada. 2. Descarta elementos sintáticos irrelevantes para a semântica da execução (espaços em branco, quebras de linha redundantes e comentários). 3. Agrupa sequências de caracteres (Lexemas) e produz uma sequência estruturada de Tokens (<TIPO, VALOR, LINHA, COLUNA>).

A fundamentação teórica baseia-se na equivalência entre Expressões Regulares (Regex) e Autômatos Finitos Determinísticos (AFD) formalizada pelo algoritmo de Thompson e o algoritmo de subconjuntos de Powerset, permitindo ao lexer transitar entre estados discretos a cada caractere lido em tempo linear \(O(n)\).

📐 Arquitetura Conceitual & Diagrama de Fluxo

flowchart LR
    Source["Código Fonte: 'let x = 42;'"] --> Lexer["Analisador Léxico (Scanner / AFD)"]
    Lexer --> Tokens["Fluxo de Tokens Estruturados:<br>[TOKEN_LET, 'let']<br>[TOKEN_IDENT, 'x']<br>[TOKEN_ASSIGN, '=']<br>[TOKEN_INT, '42']<br>[TOKEN_SEMICOLON, ';']"]
    Tokens --> Parser["Próxima Fase: Analisador Sintático"]
    style Source fill:#e1f5fe,stroke:#01579b
    style Lexer fill:#fff3e0,stroke:#e65100
    style Tokens fill:#e8f5e9,stroke:#2e7d32

🔍 Pilares e Diretrizes Técnicas

Nesta unidade, aprofundamos os seguintes conceitos fundamentais: - Autômatos Finitos Determinísticos (AFD): Garantia de que cada caractere lido conduza a no máximo uma transição de estado sem retrocessos (backtracking). - Regra do Lexema Mais Longo (Maximal Munch): O lexer consome a maior sequência válida possível (ex: == é reconhecido como operador de igualdade, não duas atribuições =). - Tabela de Símbolos Preliminar: Registro de identificadores e palavras reservadas da linguagem. - Rastreamento de Coordenadas de Erro: Armazenamento da linha e coluna de cada token para mensagens de erro precisas.

🛠️ 2. Implementação Prática em Teoria de Compiladores e Análise Léxica

Abaixo está a implementação técnica de referência, estruturada com padrões de engenharia de software e foco em robustez:

// simple_lexer.c (Implementação Manual de Analisador Léxico em C)
#include <stdio.h>
#include <ctype.h>
#include <string.h>

typedef enum {
    TOKEN_EOF,
    TOKEN_KEYWORD,
    TOKEN_IDENT,
    TOKEN_NUMBER,
    TOKEN_ASSIGN,
    TOKEN_PLUS
} TokenType;

typedef struct {
    TokenType type;
    char text[64];
    int line;
} Token;

Token next_token(const char** src, int* line) {
    while (**src && isspace(**src)) {
        if (**src == '\n') (*line)++;
        (*src)++;
    }
    if (!**src) return (Token){TOKEN_EOF, "EOF", *line};

    if (isalpha(**src)) {
        Token t = {TOKEN_IDENT, "", *line};
        int i = 0;
        while (isalnum(**src)) t.text[i++] = *(*src)++;
        t.text[i] = '\0';
        if (strcmp(t.text, "let") == 0 || strcmp(t.text, "fn") == 0) t.type = TOKEN_KEYWORD;
        return t;
    }
    if (isdigit(**src)) {
        Token t = {TOKEN_NUMBER, "", *line};
        int i = 0;
        while (isdigit(**src)) t.text[i++] = *(*src)++;
        t.text[i] = '\0';
        return t;
    }
    if (**src == '=') { (*src)++; return (Token){TOKEN_ASSIGN, "=", *line}; }
    if (**src == '+') { (*src)++; return (Token){TOKEN_PLUS, "+", *line}; }

    (*src)++;
    return (Token){TOKEN_EOF, "UNKNOWN", *line};
}

💡 Análise Passo a Passo do Código

1. Ignora Espaços e Quebras: O ponteiro de leitura avança sobre espaços em branco e incrementa o contador de linhas para relatórios de erro.
2. Reconhecimento de Identificadores e Palavras-Chave: Acumula caracteres alfanuméricos e compara com let ou fn para diferenciar keywords de variáveis.
3. Estrutura de Token Completa: Retorna uma tupla contendo o tipo, o texto bruto e a linha exata no código-fonte.

🎯 3. Próximos Passos & Sequência Didática