Reconhecer
Decidir se uma cadeia pertence a uma linguagem simples.
CEDIS | Universidade de Brasília (UnB)
Nivelamento: autômatos e expressões regulares para análise léxica
Da linguagem regular à regra Flex e ao token
CEDIS · COMP1Por que este nivelamento existe
A avaliação diagnóstica indicou lacunas em autômatos, expressões regulares, gramáticas regulares e análise léxica. A resposta pedagógica é uma ponte curta, prática e verificável, não uma repetição completa de LFA.
CEDIS · COMP1Ao final, você deve conseguir
Descrever
Escrever expressões regulares para classes de lexemas.
Explicar
Diferenciar padrão, lexema, token e ação.
Transferir
Relacionar a definição formal a uma regra Flex.
CEDIS · COMP1Roteiro de estudo
- 01Linguagem, cadeia e padrão
- 02Expressões regulares como especificações
- 03Autômatos como reconhecedores
- 04Tokenização e regras Flex
- 05Prática guiada com o GitHub COMP1
CEDIS · COMP1Três peças mínimas
Alfabeto
Conjunto finito de símbolos disponíveis. Ex.: Σ = {0,1}.
Cadeia
Sequência finita de símbolos. Ex.: 1001.
Linguagem
Conjunto de cadeias que obedecem a uma regra.
CEDIS · COMP1Exemplo rápido de linguagem
Regra
Cadeias sobre Σ = {a,b} que começam com a e terminam com b.
Consequência
- ab é válida
- aab é válida
- ba é inválida
- aa é inválida
CEDIS · COMP1atividade
Atividade 1 · Pertinência
Qual cadeia pertence à linguagem: começa com a e termina com b?
CEDIS · COMP1Feedback da atividade 1
- abab começa com a e termina com b.
- ba falha no primeiro símbolo.
- aa falha no último símbolo.
- bbb falha nos dois critérios.
CEDIS · COMP1Operadores que mais importam no scanner
concatenação
ab significa a seguido de b.
alternância |
a|b significa a ou b.
repetição *
zero ou mais ocorrências.
repetição +
uma ou mais ocorrências.
opcional ?
zero ou uma ocorrência.
CEDIS · COMP1Uma expressão regular é uma decisão
O padrão não é apenas “texto estranho”: ele descreve exatamente quais lexemas devem ser reconhecidos.
- [0-9]+ reconhece inteiros positivos.
- [a-zA-Z_][a-zA-Z0-9_]* reconhece identificadores simples.
CEDIS · COMP1atividade
Atividade 2 · Previsão
Qual lexema NÃO é reconhecido por [a-zA-Z_][a-zA-Z0-9_]*?
CEDIS · COMP1Feedback da atividade 2
- O primeiro caractere deve ser letra ou sublinhado.
- Depois do primeiro caractere, dígitos são permitidos.
- 2valor começa com dígito; por isso, não encaixa no padrão.
CEDIS · COMP1Duas perguntas diferentes
O que reconhece?
Pergunta extensional: listar cadeias aceitas e rejeitadas.
Por que reconhece?
Pergunta conceitual: explicar a regra que separa aceitas de rejeitadas.
CEDIS · COMP1
AFD: memória finita da leitura
Cada estado resume o que importa sobre o prefixo lido. Para terminar em 01, basta saber se o sufixo atual é vazio, 0 ou 01.
CEDIS · COMP1atividade
Atividade 3 · Simulação
No AFD apresentado, a cadeia 1001 termina em qual estado?
CEDIS · COMP1Feedback da atividade 3
- 1001 termina em 01.
- O estado q2 é final.
- Em AFD, não há escolha de caminho: cada símbolo determina uma transição.
CEDIS · COMP1AFD e AFN: o que muda para o estudante?
AFD
Para cada estado e símbolo, há uma próxima transição definida.
AFN
Pode haver múltiplos caminhos ou transições vazias.
Para o scanner
A ferramenta pode converter especificações regulares em mecanismos eficientes de reconhecimento.
CEDIS · COMP1A ponte completa
A análise léxica usa padrões para produzir categorias que o parser consegue consumir.
CEDIS · COMP1
Lexema e token não são sinônimos
Confundir os dois impede compreender o contrato entre Flex e Bison.
CEDIS · COMP1Quatro termos que não podem se misturar
Padrão
Expressão regular usada na regra.
Lexema
Trecho concreto reconhecido na entrada.
Token
Categoria devolvida ao parser.
Ação
Código executado quando o padrão casa.
CEDIS · COMP1atividade
Atividade 4 · Classificação
Na regra "if" { return IF; }, o que é IF?
CEDIS · COMP1Feedback da atividade 4
- "if" é o lexema/padrão literal reconhecido.
- IF é a categoria enviada ao parser.
- A ação return IF materializa o contrato com o Bison.
CEDIS · COMP1Semana 02 e semana 03 no GitHub
Semana 02
- Guia de expressões regulares no Flex
- exemplo.l e exemplo.y
- entrada.txt e Makefile
Semana 03
- scanner.l
- palavras reservadas
- identificadores, números, operadores
- comentários e caractere desconhecido
CEDIS · COMP1atividade
Atividade 5 · Leia uma regra
Explique, em 3 linhas, o papel da regra [0-9]+(\.[0-9]+)? em um scanner simples.
Resposta aberta · até 600 caracteres
CEDIS · COMP1Modelo de resposta da atividade 5
- A parte [0-9]+ exige ao menos um dígito.
- (\.[0-9]+)? permite uma parte decimal opcional.
- A regra separa lexemas numéricos para gerar um token, como NUMBER.
CEDIS · COMP1Erros comuns no início
Padrão amplo demais
Ex.: aceitar 2abc como identificador.
Ordem de regras
Palavras reservadas devem ser tratadas antes de identificadores genéricos.
Erro silencioso
Ignorar caracteres inválidos pode esconder problemas.
Token sem valor
Números e identificadores muitas vezes precisam transportar yytext/yylval.
CEDIS · COMP1atividade
Atividade 6 · Depuração
Se a regra de ID aparece antes da regra "while", qual risco surge?
CEDIS · COMP1Feedback da atividade 6
- O Flex escolhe a melhor correspondência e usa a ordem em empates relevantes.
- Palavras reservadas devem aparecer antes do padrão genérico de identificadores.
- Esse erro afeta o token enviado ao parser.
CEDIS · COMP1Mini laboratório sugerido
1
1. Execute
Compile o exemplo da semana 03 e rode entradas curtas.
2
2. Preveja
Antes de executar, escreva quais tokens devem aparecer.
3
3. Modifique
Acrescente um operador ou palavra reservada.
4
4. Justifique
Explique a mudança usando padrão, lexema e token.
CEDIS · COMP1Critério de saída deste módulo
Consigo prever
Dada uma entrada simples, antecipo os tokens gerados.
Consigo explicar
Dada uma regra Flex, separo padrão, ação, lexema e token.
Consigo modificar
Crio uma nova regra sem quebrar as anteriores.
CEDIS · COMP1O objetivo não é decorar sintaxe de expressão regular; é entender qual linguagem cada padrão reconhece e qual token ele produz.
CEDIS · COMP1Próximo passo
Use este módulo como ponte para a prática de Flex. Ao chegar ao scanner.l, explique cada regra antes de executá-la.
CEDIS · COMP1Referências
- Freitas, S. A. A. (2026). Relatório de análise da avaliação diagnóstica FGA0003 – Compiladores 1, semestre 2026/2. Universidade de Brasília.
- Freitas, S. A. A. (2025). Semana 02 – Fundamentos de linguagens formais e autômatos. FGA0003 – Compiladores 1. Universidade de Brasília.
- Freitas, S. A. A. (2025). Guia rápido das expressões regulares mais usadas no Flex. Repositório COMP1.
- Freitas, S. A. A. (2025). Repositório COMP1: exemplos progressivos com Flex e Bison. Universidade de Brasília.
- Aho, A. V., Lam, M. S., Sethi, R., & Ullman, J. D. (2006). Compilers: Principles, techniques, and tools (2nd ed.). Pearson.