Aula 05: Expressões Regulares e Scanners

Data de Publicação

17/03/2026

Data de Modificação

17/03/2026

Objetivos

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

  • Dominar Expressões Regulares como ferramenta de especificação de tokens.
  • Construir AFN a partir de ER (Algoritmo de Thompson) e AFD a partir de AFN (Construção de Subconjuntos).
  • Compreender a cadeia ER → AFN → AFD → código e o papel da minimização do AFD.
  • Identificar limitações das linguagens regulares e implicações para desempenho (backtracking, autômatos).

Motivação em Engenharia de Computação

Em compiladores reais (e em inúmeras ferramentas de Engenharia de Software), Expressões Regulares são usadas para:

  • Especificar padrões de tokens em linguagens de programação (identificadores, números, operadores, palavras-chave).
  • Escrever ferramentas de análise de logs, geradores de código, formatadores e linters.
  • Filtrar e validar entradas em sistemas embarcados e aplicações de rede.

Dominar ERs vai além de “decorar sintaxe”: é entender as limitações teóricas (o que é ou não regular) e as implicações de desempenho (evitar backtracking explosivo, escolher construções otimizáveis em autômatos).

Visão geral: da especificação ao código

O caminho desde a especificação dos tokens até o código do scanner segue uma pipeline bem definida. O diagrama abaixo resume as etapas e as estruturas produzidas em cada uma.

flowchart LR
  subgraph spec [Especificação]
    ER[Expressões Regulares]
  end
  subgraph automata [Autômatos]
    AFN[AFN com epsilon]
    AFD[AFD]
    AFDmin[AFD mínimo]
  end
  subgraph code [Implementação]
    Código[Código do Scanner]
  end
  ER -->|Thompson| AFN
  AFN -->|Subconjuntos| AFD
  AFD -->|Hopcroft| AFDmin
  AFDmin -->|Tabela ou switch| Código

Cada etapa tem um objetivo claro: Thompson gera um autômato não determinístico que reconhece exatamente a linguagem da ER; Construção de Subconjuntos elimina o não-determinismo para obter um AFD simulável de forma eficiente; Minimização reduz o número de estados para economizar memória e simplificar o código gerado.

Conteúdo

1. Definição formal de Expressões Regulares

Para construir um scanner de forma rigorosa, precisamos de uma linguagem formal para especificar os padrões dos tokens. As Expressões Regulares (ER) são o padrão da indústria e correspondem exatamente às linguagens regulares (aceitas por autômatos finitos).

Definição. Seja \(\Sigma\) um alfabeto finito. As expressões regulares sobre \(\Sigma\) e as linguagens que elas denotam são definidas recursivamente:

  1. \(\emptyset\) é uma ER; denota a linguagem vazia \(\emptyset\).
  2. \(\epsilon\) é uma ER; denota a linguagem \(\{\epsilon\}\) (apenas a string vazia).
  3. Para cada \(a \in \Sigma\), \(a\) é uma ER; denota \(\{a\}\).
  4. Se \(r\) e \(s\) são ERs que denotam \(L(r)\) e \(L(s)\), então:
    • \((r|s)\) (união) é ER; denota \(L(r) \cup L(s)\).
    • \((rs)\) (concatenação) é ER; denota \(L(r)L(s) = \{ xy \mid x \in L(r),\, y \in L(s) \}\).
    • \((r^*)\) (fechamento de Kleene) é ER; denota \(L(r)^* = \bigcup_{k \ge 0} L(r)^k\).

Por convenção, omitimos parênteses quando a precedência é clara: \(*\) tem maior precedência, depois concatenação, depois \(|\). Exemplo: \(a|bc^*\) equivale a \((a|(b(c^*)))\).

Exemplos de ER e linguagens:

ER Linguagem (descrição)
\(a^*\) Zero ou mais \(a\)’s
\((ab)^*\) Repetições de \(ab\)
\(a|b\) Um \(a\) ou um \(b\)
\([0\text{--}9]+\) Um ou mais dígitos (notação prática)
\(\texttt{id} = [a\text{--}z]([a\text{--}z0\text{--}9])^*\) Identificadores começando com letra

2. Limitações das linguagens regulares

Nem toda linguagem é regular. Em particular, linguagens que exigem “contagem” ou aninhamento balanceado não podem ser descritas por ER (nem reconhecidas por AFD/AFN).

  • Parênteses balanceados como \(\{ (^n )^n \mid n \ge 0 \}\) não são regulares (exige pilha).
  • Palíndromos sobre um alfabeto com mais de um símbolo não são regulares.
  • Duplicação de palavra \(\{ ww \mid w \in \Sigma^* \}\) não é regular.

Por isso, a análise léxica usa ER (tokens são padrões lineares), e a análise sintática usa gramáticas livres de contexto (estrutura aninhada).

3. De ER para AFN: Algoritmo de Thompson

A primeira etapa da pipeline é construir um Autômato Finito Não-Determinístico (AFN) que aceita exatamente a linguagem da ER. O algoritmo de Thompson faz isso de forma estrutural: cada operador da ER (\(\epsilon\), símbolo, união, concatenação, estrela) é traduzido em um pequeno “bloco” de estados e transições; depois os blocos são encaixados conforme a estrutura da ER.

Regras de construção:

  • Símbolo \(a\): dois estados \(q_0\), \(q_1\); uma transição \(q_0 \xrightarrow{a} q_1\); \(q_0\) inicial, \(q_1\) final.
  • \(\epsilon\): dois estados com uma transição \(\epsilon\) entre eles.
  • União \(r|s\): novo estado inicial com \(\epsilon\) para os inícios de \(r\) e \(s\); novos estados finais de \(r\) e \(s\) com \(\epsilon\) para um único estado final.
  • Concatenação \(rs\): o estado final de \(r\) coincide com o estado inicial de \(s\) (fusão).
  • Estrela \(r^*\): um novo estado inicial e um novo estado final; \(\epsilon\) do inicial para o início de \(r\) e para o final; \(\epsilon\) do final de \(r\) de volta para o início de \(r\) e para o novo final.

O resultado é um AFN com um único estado inicial, um único estado final, e todas as transições ou por um símbolo de \(\Sigma\) ou por \(\epsilon\). O número de estados é linear no tamanho da ER.

flowchart LR
  subgraph thompson [Construção de Thompson]
    A[ER] --> B[Blocos por operador]
    B --> C[Montagem AFN]
    C --> D[AFN com epsilon]
  end

4. De AFN para AFD: Construção de Subconjuntos

Um AFN pode ter várias transições possíveis (incluindo \(\epsilon\)) para um mesmo símbolo; simular isso “adivinhando” caminhos é caro. A construção de subconjuntos produz um AFD em que cada estado representa um conjunto de estados do AFN em que poderíamos estar após ler um prefixo da entrada.

Ideia:

  • Estado inicial do AFD = \(\varepsilon\text{-closure}(\{s_0\})\), onde \(s_0\) é o estado inicial do AFN e \(\varepsilon\)-closure é o conjunto de todos os estados alcançáveis por zero ou mais transições \(\epsilon\).
  • Para cada estado \(Q\) do AFD e cada símbolo \(a\), calcular o próximo conjunto: \(Q' = \varepsilon\text{-closure}(\text{move}(Q, a))\), onde \(\text{move}(Q,a)\) são os estados alcançáveis a partir de \(Q\) por uma transição com \(a\).
  • Um estado do AFD é final se contiver algum estado final do AFN.

O AFD resultante tem no máximo \(2^n\) estados (onde \(n\) é o número de estados do AFN), mas na prática muitas gramáticas léxicas produzem AFDs bem menores. A simulação do AFD é então um loop: em cada caractere, uma única transição determinística.

flowchart TB
  subgraph subset [Construção de Subconjuntos]
    S0[Estado AFD = conjunto de estados AFN]
    S1[Para cada símbolo a]
    S2[Novo estado = epsilon_closure move]
    S3[Repetir até fixo]
    S0 --> S1 --> S2 --> S3
  end

5. Minimização do AFD (Hopcroft)

O AFD obtido pela construção de subconjuntos pode ter estados redundantes: dois estados que sempre “se comportam igual” (para qualquer sufixo, ambos aceitam ou ambos rejeitam) podem ser fundidos. O algoritmo de Hopcroft (ou a minimização por partição) produz o AFD mínimo — único a menos de isomorfismo para a mesma linguagem.

Um AFD mínimo reduz o tamanho da tabela de transição e simplifica o código gerado por ferramentas como Flex.

6. Exemplo prático: ER para inteiros e identificadores

Suponha que queiramos reconhecer:

  • Inteiro: um ou mais dígitos, ER = \(\texttt{digit}^+\) (onde \(\texttt{digit} = [0\text{--}9]\)).
  • Identificador: letra seguida de zero ou mais letras ou dígitos, ER = \(\texttt{letter}(\texttt{letter}|\texttt{digit})^*\).

Em notação mais comum (como em Flex):

  • [0-9]+ para inteiros.
  • [a-zA-Z][a-zA-Z0-9]* para identificadores.

A ferramenta combina todas as ERs em uma única ER (união) com marcas de qual padrão foi reconhecido, aplica Thompson, construção de subconjuntos e minimização, e gera um programa que mantém um estado (número do estado do AFD) e, a cada caractere, consulta a tabela de transição. Quando atinge um estado final, executa a ação associada (por exemplo, retornar o token NUMBER ou ID) e opcionalmente devolve o lexema.

7. Resumo do fluxo e decisões de implementação

flowchart TD
  ER[Especificação ER] --> Thompson[Thompson]
  Thompson --> AFN[AFN]
  AFN --> Subset[Subconjuntos]
  Subset --> AFD[AFD]
  AFD --> Hopcroft[Minimização]
  Hopcroft --> Tab[Tabela de transição]
  Tab --> Sim[Simulador / Código]
  • Por que AFN primeiro? Construir um AFD diretamente a partir da ER é mais complexo; Thompson é simples e correto.
  • Por que AFD? Simulação em tempo \(O(1)\) por caractere, sem backtracking.
  • Por que minimizar? Menos estados ⇒ tabela menor e código mais enxuto.

Conexões com o projeto Mini-Pascal

  • Na Etapa 2 você implementa um scanner manual; mesmo sem usar Thompson na mão, conhecer a pipeline ER → AFN → AFD ajuda a entender como ferramentas como Flex/ANTLR geram o analisador léxico.
  • Na Etapa 4, ao usar ANTLR, as regras léxicas são especificadas de forma próxima a ERs; o gerador aplica internamente construções análogas a Thompson e subconjuntos.
  • Definir bem os tokens (por ER ou equivalente) evita ambiguidades (por exemplo, palavras-chave vs identificadores) e garante que o parser receba uma sequência estável de tokens.

Resumo

  • ERs definem linguagens regulares de forma algébrica (união, concatenação, estrela).
  • Linguagens que exigem pilha (ex.: parênteses balanceados) não são regulares.
  • Pipeline do scanner: ER → AFN (Thompson) → AFD (Subconjuntos) → AFD mínimo (Hopcroft) → código.
  • Thompson: construção modular por operador; AFN com \(\epsilon\).
  • Construção de subconjuntos: estado do AFD = conjunto de estados do AFN; elimina não-determinismo.
  • Minimização reduz o número de estados e o tamanho da tabela.

Perguntas de reflexão

  • Por que não usar apenas AFN na implementação do scanner, em vez de converter para AFD?
  • Dê um exemplo de padrão de token em uma linguagem real que exija lookahead (ex.: == vs =) e discuta como a ordem das regras ou a especificação da ER pode resolver o conflito.
  • Pesquise: em que casos ferramentas como Flex ou expressões regulares em linguagens de programação (ex.: Python, Java) podem ter comportamento exponencial? Como isso se relaciona com backtracking?

Leitura complementar e referências

  • Aho, A. V., Lam, M. S., Sethi, R., & Ullman, J. D. (2006). Compilers: Principles, Techniques, and Tools (2ª ed.). Cap. 3: Lexical Analysis (seções sobre ER, AFN, AFD, construção de subconjuntos, minimização).
  • Cooper, K., & Torczon, L. (2011). Engineering a Compiler. Capítulos sobre análise léxica e geração de scanners.
  • Documentação do Flex: especificação de regras e comportamento em caso de empate (maximal munch, ordem das regras).

Materiais da aula

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

De volta ao topo