Departamento de Informática e Estatística

Programas de Ensino
Visitante (Entrar)

Programa de Ensino 20091

Aprovado pelo Departamento em: 1-4-2009

  1. Identificação: Visualizar em PDF
    • 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
  2. Curso(s):
    • Ciências da Computação (208)
  3. 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
  4. 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.
  5. 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:
      1. Adquirir uma visão geral do processo de compilação sob o ponto de vista de implementação.
      2. Correlacionar a Teoria das Linguagens Formais com a Teoria da Computação e esta com a Ciência da Computação.
      3. Adquirir sólidas noções de linguagens formais e suas representações.
      4. Ser capaz de especificar linguagens através de autômatos e gramáticas.
      5. Conhecer e saber usar as técnicas formais de análise sintática.
  6. 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.
  7. 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
  8. 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.