Aula 1 - Introdução

Prévia do material em texto

LINGUAGENS FORMAIS E 
COMPILADORES
MATHEUS BRUNORO DILEM
MATHEUSDILEM@PROFESSOR.MULTIVIX.EDU.BR
2025/2
MULTIVIX
Gramáticas Formais e Autômatos. Gramáticas Regulares e Autômatos Finitos. 
Gramáticas Livres de Contexto. Gramáticas Sensíveis ao Contexto. Linguagens 
Recursivas. Organização e estrutura de compiladores. Análise léxica. Análise 
sintática. Alocação e gerência de memória. Formas internas de programas fonte. 
Análise semântica. Geração de código. Otimização de código.
Ementa
• BARBOSA, Cynthia da Silva et al. Compiladores. Porto Alegre: SAGAH, 2021. E-
book. ISBN 9786556902906. Disponível em: 
https://integrada.minhabiblioteca.com.br/books/9786556902906/
• MENEZES, Paulo Blauth. Linguagens formais e autômatos. 6. ed. Porto Alegre: 
Grupo A, 2011. E-book. ISBN 9788577807994. Disponível em: 
https://integrada.minhabiblioteca.com.br/books/9788577807994/
• LOUDEN, Kenneth C. Compiladores: princípios e práticas. São Paulo: Cengage
Learning, 2004. E-book. ISBN 9788522128532. Disponível em: 
https://integrada.minhabiblioteca.com.br/books/9788522128532/
Bibliografia Básica
• SANTOS, Pedro Reis; LANGLOIS, Thibault. Compiladores: da teoria à prática. 
São Paulo: Grupo GEN, 2018. E-book. ISBN 9788521635161. Disponível em: 
https://integrada.minhabiblioteca.com.br/books/9788521635161/
• SOUSA, Carlos Estevão Bastos et al. Linguagens formais e autômatos. Porto 
Alegre: SAGAH, 2021. E-book. ISBN 9786556901138. Disponível em: 
https://integrada.minhabiblioteca.com.br/books/9786556901138/
• SEBESTA, Robert W. Conceitos de linguagens de programação. Porto Alegre: 
Grupo A, 2018. E-book. ISBN 9788582604694. Disponível em: 
https://integrada.minhabiblioteca.com.br/#/books/9788582604694/
Bibliografia Complementar
• SANTOS, Marcela G.; SARAIVA, Maurício O.; FÁTIMA, Priscila G. Linguagem de 
programação. Porto Alegre: Grupo A, 2018. E-book. ISBN 9788595024984. 
Disponível em: 
https://integrada.minhabiblioteca.com.br/#/books/9788595024984/
• SILVA, Fabrício Machado da; LEITE, Márcia Cristina Domingues; OLIVEIRA, Diego 
Bittencourt de. Paradigmas de programação. Porto Alegre: SAGAH, 2019. E-
book. ISBN 9788533500426. Disponível em: 
https://integrada.minhabiblioteca.com.br/#/books/9788533500426/
Bibliografia Complementar
1) Introdução
1.1) Introdução a Compiladores
1.2) Introdução a Linguagens Formais
Agenda
1) Introdução
1.1) Introdução a Compiladores
1.2) Introdução a Linguagens Formais
Agenda
• Tradução x Interpretação
• Para transformar um código fonte, de uma linguagem de alto nível (C, C++, Java, Python, 
...), para um código de máquina legível por um computador (em um formato binário), é 
necessária uma “máquina” capaz de realizar o processo de conversão
• Métodos de conversão: Tradução x Interpretação
• Interpretação: nesse processo, cada instrução do programa, escrito em linguagem de alto 
nível, é examinada, decodificada e executada imediatamente
• Tradução: nesse processo, o programa, escrito em linguagem de alto nível, é primeiro 
convertido para um programa em uma linguagem de máquina para então ser executado 
• Quais as vantagens de se programar em linguagem de alto nível e/ou diretamente em 
linguagem de máquina??? 
Introdução a Compiladores
• Compilador
• Um compilador é uma “máquina” capaz de realizar o processo de tradução
• Um compilador produz, em geral, um programa escrito em linguagem Assembly que, 
posteriormente, vai ser convertido, por um montador, em um programa em código binário
• A linguagem Assembly varia para 
cada computador, portanto o 
compilador deve saber como 
converter uma linguagem de alto 
nível para cada linguagem 
Assembly individual
Introdução a Compiladores
• Um compilador é um componente que faz parte 
de uma série de ferramentas de programas que 
são utilizados para a criação de executáveis a 
partir do código-fonte
• Geralmente, quando um único comando é 
chamado para compilar um programa, toda uma 
sequência de programas é chamada em segundo 
plano, na qual temos os programas utilizados 
para a compilação de um código-fonte para a 
linguagem Assembly
Introdução a Compiladores
• Pré-processador
• Prepara o código fonte para o compilador adequado
• Em linguagem C e C++, por exemplo, verifica todas as linhas iniciadas
com # como o #include, abrindo o arquivo nomeado e seu conteúdo
• Compilador
• Verifica e analisa o código-fonte
• Executa a verificação de tipos e outras semânticas
• Otimiza o código e gera a linguagem Assembly como saída
• Montador (Assembler)
• Recebe o código do Assembly e produz o código-objeto
• O código-objeto ainda não é executável, ainda não conhece os endereços de memória, etc
• Carregador (linker)
• Carrega um ou mais arquivos objeto bem como as bibliotecas
• Gera o programa executável completo com a seleção dos locais de memória finais, onde o código e 
dados serão carregados
Introdução a Compiladores
• Fases do processo de compilação
• O trabalho realizado por um compilador é dividido em algumas etapas, 
sendo agrupadas em duas partes: análise e síntese
• Na análise, chamada de front-end do compilador, é verificada a 
estrutura gramatical, que será utilizada para criar uma representação
intermediária do programa de origem
• Caso o programa esteja mal formatado ou com sintática incorreta, ela
vai informar ao usuário. Além disso, nessa etapa, informações são
coletas e armazenadas em uma estrutura chamada tabela de símbolos
• Na síntese, chamada de back-end, o programa de destino é construído
com base na representação intermediária e nas informações na tabela 
de símbolos
Introdução a Compiladores
• Fases do processo de compilação
• Análise Léxica:
• É a primeira fase da compilação
• Nessa fase o fluxo de caracteres do programa de origem é lido e também
ocorre o agrupamento dos caracteres em sequencia (lexemas)
• Para cada um desses lexemas, o analisador léxico vai produzir um token
como saída
• Essas informações do token são úteis para a tabela de símbolos
Introdução a Compiladores
• Fases do processo de compilação
• Análise Sintática:
• Nessa fase o analisador utiliza os primeiros componentes dos tokens
produzidos pela análise léxica e cria uma representação intermediária 
semelhante a uma árvore que representa a estrutura gramatical do fluxo 
de tokens
• Nessa árvore, é possível ver a ordem em que as operações devem ser
realizadas
Introdução a Compiladores
• Fases do processo de compilação
• Análise Semântica:
• Nessa fase o analisador verifica se há consistência semântica, de acordo
com a linguagem definida, tomando como base a tabela de símbolos
• A verificação de tipo (typechecking) é uma parte crucial dessa fase
(ex: utilização de inteiro como índice de vetor) 
Introdução a Compiladores
• Fases do processo de compilação
• Geração de Código Intermediário:
• Um compilador pode construir uma ou mais representações intermediárias
do programa de origem
• Grande parte dos compiladores passa a gerar uma representação 
intermediária explícita de baixo nível ou semelhante a uma máquina após
a análise de sintaxe e semântica do programa de origem
Introdução a Compiladores
• Fases do processo de compilação
• Otimização de Código:
• Nessa fase o otimizador tenta aprimorar o código intermediário para que o
código de destino seja melhor em termos de velocidade, tamanho, etc
• Um algoritmo simples de geração de código intermediário seguido pela
otimização do código é uma maneira razoável de gerar um bom código-alvo
Introdução a Compiladores
• Fases do processo de compilação
• Geração de Código:
• Nessa fase a entrada é a representação intermediária do programa de 
origem e, em seguida, é feito o mapeamento para a linguagem de destino
• Depois disso, temos a tradução das instruções intermediárias em sequencias
de instruções de máquina que executam a mesma tarefa
Introdução a Compiladores
• Resumindo...
• O compilador é usado para converter um código em qualquerlinguagem de programação, 
compreensível por humanos para uma linguagem compreensível por máquina, ou seja, o 
binário
• Assim, o computador pode ler as informações e realizar as operações e gerar uma saída 
com base no que se deseja
• Dessa forma, é preciso entender seu
funcionamento e quais são as etapas
de compilação necessárias para que 
isso aconteça
Introdução a Compiladores
1) Introdução
1.1) Introdução a Compiladores
1.2) Introdução a Linguagens Formais
Agenda
• Para entender o que são Linguagens Formais, é necessário primeiro entender o 
que é Linguagem
• De maneira informal, uma Linguagem pode ser definida como sendo uma forma 
de comunicação
• Avançando um pouco mais, ela pode ser definida como “um conjunto de 
elementos (símbolos) e um conjunto de métodos (regras) para combinar esses 
elementos, usado e entendido por uma determinada comunidade”
• Ex:
• Linguagens Naturais (ou idiomáticas) 
• Linguagens de Programação
• Protocolos de Comunicação
Introdução a Linguagens Formais
• Conceitos Básicos
• Alfabeto (ou vocabulário):
• É um conjunto finito, não vazio, de símbolos (elementos)
• Ex1: V = {a, b, c, ... , z}
• Ex2: V = {0, 1}
• Ex3: V = {a, e, i, o, u}
• Sentenças:
• Uma sentença sobre um alfabeto V, é uma sequencia (ou cadeia) finita de símbolos do alfabeto
• Ex: Para o alfabeto V = {a, b}, existem as sentenças a, b, aa, ab, bb, aaa, aab, aba, baa, ...
• Tamanha de uma sentença:
• Seja w uma sentença, o tamanho da sentença w, denotado por |w|, é definido pelo número de 
símbolos (elementos do alfabeto) que compõem w
• Ex: Seja V = {a, b, c}
• Se w = aba, então |w| = 3
• Se w = c, então |w| = 1
Introdução a Linguagens Formais
• Conceitos Básicos
• Sentença vazia:
• É uma sentença constituída de nenhum símbolo, isto é, uma sentença de tamanho 0 (zero)
• A sentença vazia é representada pelo símbolo ε (epsilon)
• Por definição, |ε| = 0
• Potencia de uma sentença:
• Seja w uma sentença, a n-ésima potencia de w (wn ), significa w repetido n vezes
• Ex: Se w = ab, então w3 = ababab
• Para todo w, w0 = ε
• Fechamento de um Alfabeto:
• Seja V um alfabeto
• O fechamento reflexivo (fechamento) de V, representado por V*, é dado pelo conjunto de todas 
as possíveis sequencias que podem ser formadas a partir de V, inclusive ε
• O fechamento transitivo (fechamento positivo) de V, representado por V+, é dado por V* - {ε}
• Seja V = {0,1}, tem-se que V* = {ε , 0, 1, 00, 01, 11, 000, ...} e V+ = {0, 1, 00, 01, 11, 000, ...}
Introdução a Linguagens Formais
• Linguagens e suas Representações
• Linguagem:
• Uma Linguagem L sobre um alfabeto V, é um subconjunto de V*, isto é L ⊆ V*
• Representações de Linguagens:
• O estudo de linguagens está intimamente relacionado ao estudo das formas de representação 
dessas linguagens
• O problema de representação de uma linguagem, está relacionado com ela ser finita ou infinita
• Linguagem Finita:
• É uma linguagem que pode ser representada por enumeração
• Ex: A linguagem definida como sendo o conjunto dos inteiros positivos pares maiores que 0 e 
menores que 20, pode ser representado por: L = {2, 4, 6, 8, 10, 12, 14, 16, 18}
• Linguagem Infinita: 
• Neste caso, na impossibilidade de usar enumeração, é preciso encontrar uma representação finita 
para estas linguagens
• Ex: A linguagem definida como sendo o conjunto dos inteiros pares poderia ser representada por 
V = {2, 4, 6, 8, 10, ...} que, apesar de intuitiva, não é finita e nem precisa
Introdução a Linguagens Formais
• Linguagens e suas Representações
• As representações finitas de linguagens classificam-se em Reconhecedores e Sistemas 
Geradores:
• Reconhecedores:
• São dispositivos formais que permitem verificar se uma determinada sentença pertence ou não a 
uma determinada linguagem (é uma representação das sentenças de uma linguagem sob o ponto 
de vista do reconhecimento de tais sentenças)
• Esses dispositivos denominam-se autômatos; autômatos finitos, autômatos de pilha e máquinas de 
Turing, por exemplo, podem ser destacados como importantes classes de autômatos
• Sistemas Geradores
• São dispositivos formais dotados de mecanismos que permitem a geração sistemática das 
sentenças de uma linguagem (representação sob o ponto de vista da geração das sentenças de 
uma linguagem)
• Os principais sistemas geradores disponíveis são gramáticas, dentre as quais, pode-se destacar, 
as gramáticas de CHOMSKY.
Introdução a Linguagens Formais
• Linguagens e suas Representações
• Linguagens Formais:
• São linguagens que podem ser representadas de maneira finita e precisa através de sistemas com 
sustentação matemática (dispositivos formais ou modelos matemáticos)
• Linguagem Recursiva:
• Uma linguagem é recursiva se existe um algoritmo capaz de reconhecer ou gerar as sentenças que 
compõem essa linguagem
• Linguagem Recursivamente Enumerável:
• É toda a linguagem cujas sentenças podem ser reconhecidas ou geradas por procedures
Introdução a Linguagens Formais
• Resumindo...
• Teoria das Linguagens Formais:
• Estudo de modelos matemáticos que possibilitam a especificação e o reconhecimento de 
linguagens, suas classificações, estruturas, propriedades, características e o inter-relacionamento 
entre linguagens
• Importância da Teoria das Linguagens:
• Apoia aspectos básicos da Teoria da Computação (dicidibilidade, computabilidade, 
complexidade computacional)
• Fundamenta aplicações computacionais (processamento de linguagens, reconhecimento de 
padrões, modelagem de sistemas)
Introdução a Linguagens Formais
1) Introdução
1.1) Introdução a Compiladores
1.2) Introdução a Linguagens Formais
Agenda