Definir
alfabeto, cadeia e linguagem formal
CEDIS | Universidade de Brasília (UnB)
Fundamentos de linguagens formais e autômatos
FGA0003 — Compiladores 1 · Semana 2 · Aula teórica
CEDISResultado da avaliação diagnóstica
Preencher oralmente em sala, conforme o número atualizado de respostas e de estudantes matriculados.
- Respondentes: ______
- Total da turma: ______
- Percentual de participação: ______
- Observação: valores atualizados no momento da aula.
CEDISObjetivos de aprendizagem
Interpretar
componentes e produções de uma gramática
Comparar
classes da Hierarquia de Chomsky
Simular
o processamento de uma cadeia em um AFD
Relacionar
autômatos, análise léxica e Flex
CEDISMapa da aula
- 01Revisão: símbolos e cadeias
- 02Conceito central: linguagens e gramáticas
- 03Exemplo guiado: derivação
- 04Aplicação: Hierarquia de Chomsky e autômatos
- 05Fixação: cinco atividades interativas
- 06Síntese: conexão com Flex
CEDISTrês conceitos fundamentais
- Σ fornece os símbolos permitidos.
- Σ* contém todas as cadeias finitas sobre Σ.
- Uma linguagem L é um subconjunto de Σ*.
CEDISExemplo: começa com a e termina com b
Pertencem à linguagem
- ab
- aab
- aaab
- abab
Não pertencem
- ba
- bb
- aa
- bbaa
CEDISatividade
Alfabeto e cadeia
Qual afirmação distingue corretamente alfabeto e cadeia?
CEDIS
Estrutura de uma gramática
- V: variáveis ou não terminais
- Σ: símbolos terminais
- R: regras de produção
- S: símbolo inicial
CEDISExemplo de gramática
Variáveis
V = {S}
Terminais
Σ = {a, b}
Produções
S → aSb | ab
Início
S
Linguagem gerada
{aⁿbⁿ | n ≥ 1}
CEDISDerivação guiada de aaabbb
A cada passo, uma ocorrência de S é substituída por uma produção.
CEDISatividade
Derivação de uma cadeia
Com S → aSb | ab, qual derivação gera aaabbb?
CEDIS
Classes de linguagens formais
As classes internas estão contidas nas externas, mas o reconhecedor necessário torna-se mais poderoso.
CEDISRegulares e livres de contexto
Linguagens regulares
- Padrões locais
- Expressões regulares
- Autômatos finitos
- Aplicação: tokens
Linguagens livres de contexto
- Estruturas aninhadas
- Gramáticas livres de contexto
- Autômatos com pilha
- Aplicação: sintaxe
CEDISatividade
Classe e reconhecedor
Qual associação está correta na Hierarquia de Chomsky?
CEDISAFD e AFN
AFD
- Uma transição por símbolo em cada estado
- Próximo estado determinado
- Execução com um único caminho
AFN
- Pode haver múltiplas transições
- Pode admitir transições ε
- Aceita se algum caminho aceitar
CEDISAFD para cadeias terminadas em 01
- q0: nenhum sufixo relevante
- q1: o último símbolo é 0
- q2: os dois últimos símbolos são 01
CEDISComo simular uma cadeia no AFD
1
1. Iniciar
posicione-se em q0
2
2. Ler
consuma um símbolo por vez
3
3. Transitar
aplique δ(estado, símbolo)
4
4. Encerrar
consuma toda a cadeia
5
5. Decidir
aceite somente se o estado final for q2
CEDISatividade
Reconhecimento pelo AFD
Qual cadeia é rejeitada pelo AFD de sufixo 01?
CEDISGramáticas geram; autômatos reconhecem
Visão geradora
- Parte de um símbolo inicial
- Aplica regras de produção
- Constrói cadeias da linguagem
Visão reconhecedora
- Recebe uma cadeia
- Processa símbolos
- Aceita ou rejeita a entrada
CEDISFlex no fluxo da análise léxica
1
Especificar
expressões regulares no arquivo .l
2
Gerar
Flex produz o analisador em C
3
Compilar
GCC cria o executável
4
Executar
o analisador percorre o código-fonte
5
Emitir
lexemas são classificados como tokens
CEDISatividade
Aplicação em compiladores
Qual é o papel principal de Flex em um compilador?
CEDISSíntese da aula
Símbolos
formam cadeias sobre um alfabeto
Linguagens
selecionam cadeias por uma propriedade
Gramáticas
geram cadeias por produções
Autômatos
reconhecem pertinência a linguagens
Compiladores
aplicam esses modelos na análise do código
CEDISReferências
- Aho, A. V., Lam, M. S., Sethi, R., & Ullman, J. D. (2006). Compilers: Principles, techniques, and tools (2nd ed.). Addison-Wesley.
- Hopcroft, J. E., Motwani, R., & Ullman, J. D. (2006). Introduction to automata theory, languages, and computation (3rd ed.). Addison-Wesley.
- Sipser, M. (2012). Introduction to the theory of computation (3rd ed.). Cengage Learning.
- Tremblay, J. P., & Sorenson, P. G. (1985). The theory and practice of compiler writing. McGraw-Hill.
- Wirth, N. (2005). Compiler construction. ETH Zürich.
CEDISDa linguagem formal ao analisador léxico
Próxima etapa: transformar expressões regulares em um analisador com Flex. FGA0003 — Compiladores 1 · CEDIS/UnB