INE5317 Linguagens Formais e

Compiladores

Ricardo Azambuja SilveiraINE-CTC-UFSC

E-Mail: silveira@inf.ufsc.brURL: www.inf.ufsc.br/~silveira

09/13/06 Prof. Ricardo Silveira 2/21

Plano de Ensino● OBJETIVO GERAL:

– Estudar a teoria das linguagens formais visando sua aplicação na especificação de linguagens de programação e na construção de compiladores.

09/13/06 Prof. Ricardo Silveira 3/21

Plano de Ensino● OBJETIVOS ESPECÍFICOS:

– Dar uma visão geral do processo de compilação sob o ponto de vista de implementação.

– Dar uma visão geral da Teoria da Computação sob a ótica da Teoria das Linguagens Formais.

– Dar ao aluno noções de linguagens formais e suas representações.

– Estudar autômatos e gramáticas, enfatizando seus aspectos teóricos e suas aplicações.

– Estudar as técnicas formais de análise sintática.

09/13/06 Prof. Ricardo Silveira 4/21

Programa1)Introdução: Compiladores, Teoria da computação. Teoria das

linguagens formais. 8hs2)Gramáticas: Motivação. Definição formal. Derivação e

redução. Sentença, forma sentencial e linguagens. Tipos de gramáticas. Sentença vazia. Recursividade das G.S.C.18hs

3)Autômatos finitos: Determinísticos (AFD) e Não Determinísticos (AFND). Transformação de AFND para AFD. Relação entre AF e GR. Minimização de AFD. Conjuntos regulares e Expressões Regulares. Implementação de AF. Propriedades e problemas de decisão das L.R. Aplicações de A.F. e E.R. 16hs

09/13/06 Prof. Ricardo Silveira 5/21

Programa

4)Gramáticas livre de contexto (GLC) e autômatos de pilha (PDA): Introdução. Árvore de derivação. Formas de derivação em GLC. Gramática ambígua. Transformações em GLC. Tipos especiais de GLC. PDA. Equivalência entre PDA e GLC. Propriedades e problemas de decisão das LLC. Aplicações. 14Hs

5)Análise Sintática: Introdução. Classes de analisadores. Analisadores ascendentes e descendentes: Estudo das principais técnicas existentes. 16hs

09/13/06 Prof. Ricardo Silveira 6/21

CronogramaDATA ASSUNTO13/09 Plano de Ensino – Conceitos Básicos15/09 Estrutura geral doscompiladores20/09 Introdução a Teoria da Computação22/09 Gramaticas27/09 Automatos Finitos29/09 Automatos Finitos04/10 Conjuntos Regulares e Expressões Regulares06/10 Conjuntos Regulares e Expressões Regulares11/10 Gramaticas regulares13/10 EXERCICIOS18/10 Prova I: 20/10 Gramaticas regulares25/10 Gramaticas regulares27/10 Gramaticas regulares01/11 Gramaticas regulares03/11 EXERCÍCIOS08/11 Automatos finitos com saída10/11 Automatos finitos com saída

09/13/06 Prof. Ricardo Silveira 7/21

CronogramaDATA ASSUNTO15/11 FERIADO17/11 Linguagens livres de contexto22/11 Linguagens livres de contexto24/11 Linguagens livres de contexto29/11 Propriedades das Linguagens Livre de Contexto01/12 Propriedades das Linguagens Livre de Contexto06/12 EXERCÍCIOS08/12 PROVA II02/02 Análise Sintática07/02 Análise Sintática09/02 Análise Sintática14/02 Análise Sintática16/02 Entrega do trabalho21/02 Feriado23/02 Feriado28/02 Tira dúvidas02/03 Recuperação

09/13/06 Prof. Ricardo Silveira 8/21

Avaliação

● Critérios– Será aprovado na disciplina o aluno que obtiver

frequência superior a 75% e média final igual ou superior a 6.0 através da seguinte fórmula:

● MF = (P1 + P2 + T) / 3● onde: T = (T1 + T2 + 2TP) / 4

– Recuperação: Se MF for maior ou igual 3 e menor que 6, o aluno poderá fazer uma prova de recuperação onde

● NF= (MF + NR)/2. Caso contrário, NF = MF.

09/13/06 Prof. Ricardo Silveira 9/21

Bibliografia1. FURTADO, O. J. V. Apostila de Linguagens Formais e

Compiladores – versão 2 - UFSC, 2002.2. WOOD, D. Theory of Computation. Ed. John Wiley & Sons,

1987.3. AHO, A. V., SETHI, R.,ULLMAN, J. D.. Compiler-Principles,

Techniques and tools. Ed. Addison-Wesley, 1986.4. HOPCROFT, J. E., ULLMAM, J. D. Formal Languagens and

Their Relations to Automata. Addison-Wesley, 1969.5. HOPCROFT, J. F., ULLMAN, J. D.. Introduction to Automata

Theory, Languagens and Computation. Ed. Addison-Wesley, 1979.

09/13/06 Prof. Ricardo Silveira 10/21

Bibliografia6. SUDKAMP, T. A. Languages and Machines – An Introduction to

the Theory of Computer Science, 2. edição, Ed. Addison Wesley, 1997.

7. MENEZES, P. B. Linguagens Formais e Autômatos, Ed. Sagra Luzzato, 5. edição, 2005.

8. LEWIS, H. R. e PAPADIMITRIOU, C. H. , Elementos de Teoria da Computação, Ed. Bookmam, 2. edição, 1998.

9. AHO, A. V., ULLMAN, J. D. The Theory of Parsing, Translation, and Compiling. Volume I: Parsing. Ed Prentice-Hall, Inc. 1972, 542p

10. DIVERIO, T. A., MENEZES, P. B., Teoria da Computação – Máquinas Universais e Computabilidade. Ed. Sagra Luzzatto, Porto Alegre, 1999

09/13/06 Prof. Ricardo Silveira 11/21

Definições Preliminaresbaseado em material produzido pelo prof Olinto José Varela Furtado

● Tradutor– É um programa que traduz um programa fonte

escrito em uma linguagem qualquer (denominada linguagem fonte) para um programa objeto equivalente escrito em outra linguagem (denominada linguagem objeto)

Pf / Lf Tradutor Po / Lo

09/13/06 Prof. Ricardo Silveira 12/21

Definições Preliminares● Compilador

– É um Tradutor em que a linguagem fonte é uma linguagem de alto nível e a linguagem objeto é uma linguagem de baixo nível (assembly ou máquina)

Po / La

Pf / Lan Compilador

Po / Lm

09/13/06 Prof. Ricardo Silveira 13/21

Definições Preliminares● Interpretador

– É um programa que interpreta diretamente as instruções do programa fonte, gerando o resultado.

Pf / Lq Interpretador Resultados

09/13/06 Prof. Ricardo Silveira 14/21

Definições Preliminares● Tradutor/Interpretador

– Esquema híbrido para implementação de linguagens de programação

Pf / Lan Tradutor Po / Lint

Interpretador

Resultados

09/13/06 Prof. Ricardo Silveira 15/21

Definições Preliminares● Montador

– É um Tradutor em que o programa fonte está escrito em linguagem assembly e o programa objeto resultante está em linguagem de máquina

Pf / La Montador Po / Lm

09/13/06 Prof. Ricardo Silveira 16/21

Definições Preliminares● Pré-processador

– É um Tradutor em que tanto o programa fonte quanto o programa objeto estão escritos em linguagens de alto nível

Pf/Lan1 Pré-Proc. Po/Lan2

09/13/06 Prof. Ricardo Silveira 17/21

Definições Preliminares●Cross-Compiler

● Compilador que gera código para uma máquina diferente da utilizada na compilação.

09/13/06 Prof. Ricardo Silveira 18/21

Estrutura geral de um compilador

P. FonteCompilador

Análise

Análise Léxica

Análise Sintática

Análise Semântica

Síntese

Geração de Código Intermediário

Otimização de Código

Geração de Código

P. Objeto

09/13/06 Prof. Ricardo Silveira 19/21

Formas de Implementação de Compiladores

● Fase– Procedimento que realiza uma função bem definida

no processo de compilação.● Passo

– Passagem completa do programa compilador sobre o programa fonte que está sendo compilado.

09/13/06 Prof. Ricardo Silveira 20/21

Formas de Implementação● Compiladores de 1 e de vários passos

– Quantidade de vezes que o P.F. é analisado até que o código objeto seja gerado

– Diferentes composições ● (agrupamento de fases)

09/13/06 Prof. Ricardo Silveira 21/21

Critérios para def. do num. de passos

● Memória disponível● Tempo de Compilação● Tempo de execução● Características da Linguagem ● Referências futuras● Características das Aplicações● Importância da Otimização● Tamanho / Experiência da Equipe● Disponibilidade de Ferramentas de Apoio● Prazo para desenvolvimento