Programa de Ensino 20231
Aprovado pelo Departamento em: 3-11-2022
- Identificação:
- 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
- Curso(s):
- Ciências da Computação (208)
- Requisito(s):
- Ciências da Computação (208)
- INE5415 - Teoria da Computação
- 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.
- 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 léxica e sintática.
- 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
- 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.
- 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.