Departamento de Informática e Estatística

Programas de Ensino
Visitante (Entrar)

Programa de Ensino 20231

Aprovado pelo Departamento em: 3-11-2022

  1. Identificação: Visualizar em PDF
    • Disciplina: INE5421 - Linguagens Formais e Compiladores
    • Carga horária: 72 horas-aula      Teóricas: 72      Práticas: 0
    • Período: 1º semestre de 2023 até a presente data
  2. Curso(s):
    • Ciências da Computação (208)
  3. Requisito(s):
    • Ciências da Computação (208)
      • INE5415 - Teoria da Computação
  4. 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.
  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 léxica e sintática.
  6. Conteúdo Programático:
    • Apresentação da Disciplina e seu Contexto [4 horas-aula]
      • Teoria da Computação
      • Teoria das Linguagens Formais
      • Compiladores
    • Gramáticas[10 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 Gramáticas Sensíveis ao Contexto
    • Linguagens 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 Gramáticas Regulares
      • Minimização de AFD
      • Conjuntos regulares e Expressões Regulares (ER)
      • Relação entre AF e ER
      • Implementação de AF
      • Propriedades e problemas de decisão das Linguagens Regulares
    • Análise Léxica [06 horas-aula]
      • Contexto da análise Léxica
      • Analisadores Léxicos
      • Conversão de ER para AFD
      • Implementação de Geradores de analisadores léxicos
    • Linguagens Livres de Contexto [14 horas-aula]
      • Gramáticas Livres de Contexto (GLC)
      • Árvore de derivação e formas de derivação em GLC
      • Gramáticas ambíguas
      • Transformações em GLC
      • Tipos especiais de GLC
      • Autômatos de Pilha e equivalência com GLCs
      • Propriedades e problemas de decisão das Linguagens Livres de Contexto (LLC)
      • Aplicações
    • Análise Sintática[22 horas-aula]
      • Contexto da Análise Sintática
      • Analisadores Sintáticos
        • Analisadores ascendentes determinísticos e Não determinísticos
        • Analisadores descendentes determinísticos e Não determinísticos
      • Implementação de geradores de Analisadores Sintáticos
  7. Bibliografia Básica:
    • 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.
  8. Bibliografia Complementar:
    • HOPCROFT, J. E., ULLMAM, J. D. Formal Languagens and Their Relations to Automata. Addison-Wesley, 1969.
    • SIPSER, M., Introdução a Teoria da Computação, 2a. Edição, Cengage Learning, 2012.
    • LEWIS, H. R. e PAPADIMITRIOU, C. H. , Elementos de Teoria da Computação, Ed. Bookmam, 2. edição, 1998.