Programa de Ensino 20091
Aprovado pelo Departamento em: 1-4-2009
- Identificação:
- Disciplina: INE5317 - Linguagens Formais e Compiladores
- Carga horária: 72 horas-aula
Teóricas: 72
Práticas: 0
- Período:
1º semestre de 2009 até a presente data
- Curso(s):
- Ciências da Computação (208)
- Requisito(s):
- Ciências da Computação (208)
- INE5364 - Programação em Lógica
- INE5381 - Fundamentos Matemáticos da Informática
- INE5384 - Estruturas de Dados
- Ementa:
- Linguagens e suas representações. Gramáticas. Autômatos finitos e conjuntos regulares. Gramáticas livre de contexto. Autômatos de pilha. Visão geral do processo de compilação. Técnicas de análise léxica e análise sintática.
- Objetivo(s):
- Geral: Conhecer a teoria das linguagens formais visando sua aplicação na especificação de linguagens de programação e na construção de compiladores.
- Específicos:
- Adquirir uma visão geral do processo de compilação sob o ponto de vista de implementação.
- Correlacionar a Teoria das Linguagens Formais com a Teoria da Computação e esta com a Ciência da Computação.
- Adquirir sólidas noções de linguagens formais e suas representações.
- Ser capaz de especificar linguagens através de autômatos e gramáticas.
- Conhecer e saber usar as técnicas formais de análise sintática.
- Conteúdo Programático:
- Introdução [8 horas-aula]
- Compiladores
- Teoria da Computação
- Teoria das Linguagens Formais
- Gramáticas [18 horas-aula]
- 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.
- Autômatos finitos e Conjuntos Regulares [16 horas-aula]
- 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.
- Gramáticas livre de contexto (GLC) e autômatos de pilha (PDA)[14 horas-aula]
- Introdução
- Árvore de derivação e 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
- Análise Sintática [16 horas-aula]
- Introdução
- Classes de analisadores
- Analisadores ascendentes
- Analisadores descendentes
- Estudo das principais técnicas existentes.
- Bibliografia Básica:
- FURTADO, O. J. V. Apostila de Linguagens Formais e Compiladores – versão 2 - UFSC, 2002, disponível em www.inf.ufsc.br/~olinto
- Bibliografia Complementar:
- AHO, A. V., SETHI, R.,ULLMAN, J. D.. Compiladores – Princípios, Técnicas e Ferramentas, LTC – Livros Técnicos e Científicos Editora S. A., 1995.
- MENESES, P. B. Linguagens Formais e Autômatos, Ed. Sagra Luzzato, 5. edição, 2005.
- HOPCROFT, J. E., ULLMAM, J. D. Formal Languagens and Their Relations to Automata. Addison-Wesley, 1969.
- HOPCROFT, J. F., ULLMAN, J. D.. Introduction to Automata Theory, Languagens and Computation. Ed. Addison-Wesley, 1979.
- SUDKAMP, T. A. Languages and Machines – An Introduction to the Theory of Computer Science, 2. edição, Ed. Addison Wesley, 1997.
- LEWIS, H. R. e PAPADIMITRIOU, C. H. , Elementos de Teoria da Computação, Ed. Bookmam, 2. edição, 1998.
- DIVERIO, T. A., MENEZES, P. B., Teoria da Computação – Máquinas Universais e Computabilidade. Ed. Sagra Luzzatto, Porto Alegre, 1999
- WOOD, D. Theory of Computation. Ed. John Wiley & Sons, 1987.