Aula 05: Expressões Regulares e Scanners

Objetivos

  • Dominar Expressões Regulares como ferramenta de especificação.
  • Algoritmo de Thompson e Construção de Subconjuntos.

Conteúdo

Para construir um scanner, 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.

Definição Formal de ER

Seja \(\Sigma\) um alfabeto. As ERs sobre \(\Sigma\) são definidas recursivamente: 1. \(\epsilon\) é uma ER que denota a linguagem \(\{\epsilon\}\). 2. Se \(a \in \Sigma\), então \(a\) é uma ER que denota \(\{a\}\). 3. Se \(r\) e \(s\) são ERs, então: - \(r|s\) (União) é ER. - \(rs\) (Concatenação) é ER. - \(r^*\) (Fechamento de Kleene) é ER.

De ER para Código: A Trilha do Compilador

Como uma ferramenta como o LEX transforma uma ER em código C/Java? 1. ER \(\to\) AFN (Autômato Finito Não-Determinístico): - Usa-se o Algoritmo de Thompson. É uma construção estrutural (“lego”) onde cada operador da ER vira um pequeno bloco de estados. - Produz um autômato com transições \(\epsilon\) (mi) e múltiplos caminhos possíveis.

  1. AFN \(\to\) AFD (Autômato Finito Determinístico):
    • Computadores digitais não lidam bem com não-determinismo (“adivinhar” o caminho).
    • Usa-se o Algoritmo de Construção de Subconjuntos (Subset Construction).
    • Ideia chave: O estado atual do AFD representa um conjunto de estados possíveis do AFN em que poderíamos estar simultaneamente.
    • Elimina transições \(\epsilon\).
  2. Minimização do AFD:
    • O AFD gerado pode ter estados redundantes. O Algoritmo de Hopcroft funde estados equivalentes, gerando o menor autômato possível para aquela linguagem.

Referências

  • Aho, A. V., Lam, M. S., Sethi, R., & Ullman, J. D. (2006). Compilers: Principles, Techniques, and Tools.
  • Cooper, K., & Torczon, L. (2011). Engineering a Compiler.
Back to top