Departamento de Informática e Estatística

Planos de Ensino
Visitante (Entrar)

Plano de Ensino

Aprovado pelo Departamento em: 3-3-2015

  1. Identificação: Visualizar em PDF
    • Disciplina: INE5421 - Linguagens Formais e Compiladores
    • Turma(s): 05208
    • Carga horária: 72 horas-aula      Teóricas: 72      Práticas: 0
    • Período: 1º semestre de 2015
  2. Curso(s):
    • Ciências da Computação (208)
  3. Requisito(s):
    • Ciências da Computação (208)
      • INE5415 - Teoria da Computação
  4. Professor(es):
    • Olinto José Varela Furtado (olinto.furtado@ufsc.br)
  5. Ementa:
    • O processo de compilação. Linguagens e suas representações. Gramáticas: definição formal, classificação (Hierarquia de Chomsky), propriedades, problemas de decisão e aplicações. Gramáticas regulares, autômatos finitos, conjuntos regulares e expressões regulares. Gramáticas livres de contexto. Autômatos de pilha. Teoria de Parsing. Análise léxica e sintática.
  6. 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.
      • 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.
  7. 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.
  8. Metodologia:
    As aulas serão expositivas, com realização de exercícios intra e extra-classe para fixação do conteúdo. Através de exemplos, de exercícios e de trabalhos (práticos e teóricos) incentivar-se-á o aluno a correlacionar a teoria abordada com sua aplicação prática.
  9. Avaliação:
    Será aprovado o aluno que obtiver Média Final (MF) igual ou superior a 6.0 e freqüência igual ou superior a 75%. A Média Final (MF) será calculada pela seguinte fórmula:

    MF = (Prova I + Prova II + Prova III + MTE) / 4

    onde: MTE = (T1 + T2 + MLE) / 3 e MLE = (LE0 + ... + LE4) / 5
    LE0 = média dos exercícios de fixação (de 8 a 12) dados de uma aula para a outra
    LE1 a LE4 = Listas de exercícios referentes aos itens 2 a 5 do programa

    Conforme parágrafo 2º do artigo 70 da Resolução 17/CUn/97, o aluno com frequência suficiente (FS) e média final no período (MF) entre 3,0 e 5,5 terá direito a uma nova avaliação ao final do semestre (REC), sendo a nota final (NF) calculada conforme parágrafo 3º do artigo 71 desta resolução, ou seja: NF = (MF + REC) / 2.

  10. Cronograma:
    Tópico Avaliado / Forma / Semana Provável
    Itens 1 e 2 / Prova I / 6a
    Itens 3 e 4 / Prova II / 13a
    Itens 4 e 5 / Prova III / 17a
    Itens 1 a 5 / Exercícios / variável
    Itens 2 a 5 / Trab. I e II / variável
    Recuperação (REC) : Prova envolvendo toda a matéria, a ser realizada na última semana de aula.
  11. 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
  12. Bibliografia Complementar:
    • RAMOS, M. V. M., NETO, J. J., VEJA, I. S., Linguagens Formais: Teoria, Modelagem e Implementação. Ed. Bookman, 2009.
    • HOPCROFT, J. F., ULLMAN, J. D., MOTWANI, R. Introdução à Teoria de Autômatos, Linguagens e Computação, Tradução da segunda edição Americana,Elsevier Editora Ltda, 2003.
    • 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 / Ed. Addison Wesley 2008.
    • MENESES, P. B. Linguagens Formais e Autômatos, Ed. Sagra Luzzato, 5. edição, 2005.
    • FISHER, C. N., CYTRON, R. K., LeBLANNC Jr., R. J.. Crafting a Compiler. Ed. Addison Wesley, 2009.
    • 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.