PT | EN

MINISTÉRIO DA EDUCAÇÃO

UNIVERSIDADE FEDERAL DE SANTA CATARINA

CENTRO TECNOLÓGICO

DEPARTAMENTO DE INFORMÁTICA E ESTATÍSTICA

PROGRAMA DE ENSINO

1. Identificação

Disciplina:INE5421 - Linguagens Formais e Compiladores
Nível:Graduação
Carga Horária:72 horas-aula (Teórica: 72)
Vigência:De 2023-1 até a presente data

2. 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.

3. Cursos Relacionados

4. Objetivos

4.1 Objetivo 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.

4.2 Objetivos 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.

5. Conteúdo Programático

  1. Apresentação da Disciplina e seu Contexto [4 horas-aula]
    1. Teoria da Computação
    2. Teoria das Linguagens Formais
    3. Compiladores
  2. Gramáticas[10 horas-aula]
    1. Motivação
    2. Definição formal
    3. Derivação e redução
    4. Sentença, forma sentencial e linguagens
    5. Tipos de gramáticas
    6. Sentença vazia
    7. Recursividade das Gramáticas Sensíveis ao Contexto
  3. Linguagens Regulares [16 horas-aula]
    1. Autômatos finitos Determinísticos (AFD) e Não Determinísticos (AFND)
    2. Transformação de AFND para AFD
    3. Relação entre AF e Gramáticas Regulares
    4. Minimização de AFD
    5. Conjuntos regulares e Expressões Regulares (ER)
    6. Relação entre AF e ER
    7. Implementação de AF
    8. Propriedades e problemas de decisão das Linguagens Regulares
  4. Análise Léxica [06 horas-aula]
    1. Contexto da análise Léxica
    2. Analisadores Léxicos
    3. Conversão de ER para AFD
    4. Implementação de Geradores de analisadores léxicos
  5. Linguagens Livres de Contexto [14 horas-aula]
    1. Gramáticas Livres de Contexto (GLC)
    2. Árvore de derivação e formas de derivação em GLC
    3. Gramáticas ambíguas
    4. Transformações em GLC
    5. Tipos especiais de GLC
    6. Autômatos de Pilha e equivalência com GLCs
    7. Propriedades e problemas de decisão das Linguagens Livres de Contexto (LLC)
    8. Aplicações
  6. Análise Sintática[22 horas-aula]
    1. Contexto da Análise Sintática
    2. Analisadores Sintáticos
      1. Analisadores ascendentes determinísticos e Não determinísticos
      2. Analisadores descendentes determinísticos e Não determinísticos
    3. Implementação de geradores de Analisadores Sintáticos

6. Bibliografia Básica

  1. 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.
  2. 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.

7. Bibliografia Complementar

  1. HOPCROFT, J. E., ULLMAM, J. D. Formal Languagens and Their Relations to Automata. Addison-Wesley, 1969.
  2. SIPSER, M., Introdução a Teoria da Computação, 2a. Edição, Cengage Learning, 2012.
  3. LEWIS, H. R. e PAPADIMITRIOU, C. H. , Elementos de Teoria da Computação, Ed. Bookmam, 2. edição, 1998.