INSCREVA-SE

Linguagens Formais, Autômatos e Compiladores


Codigo Carga Horária
T E L/P CHT
ECM253 2 0 2 160

Ementa

ELEMENTOS DE MATEMÁTICA DISCRETA: Conjuntos e Relações, Funções, Relações de Equivalência, Indução Matemática, Lógica Proposicional e de Predicados, Aplicações da Lógica de Primeira Ordem, Revisão de Grafos, Dígrafos e Árvores. ELEMENTOS DE ANÁLISE DE ALGORITMOS: aplicações de conceitos de Matemática Discreta à Análise de Algoritmos. INTRODUÇÃO AOS MODELOS TEÓRICOS DE COMPUTAÇÃO: Autômatos Finitos, Máquinas de Turing, Computabilidade, Problemas de Decisão, Problema da Parada, Complexidade Computacional, Problemas Intratáveis e Completude NP. GRAMÁTICAS E LINGUAGENS, Relação entre linguagens, Autômatos e Máquinas de Turing, Classificação das Gramáticas: a hierarquia de Chomsky, Gramáticas Regulares, Gramáticas Livres de Contexto. ELEMENTOS DA TEORIA DOS COMPILADORES: Varredura de Código, Análise Sintática, Metalinguagem EBNF, Análise Semântica, Gramáticas de Atributos, Tabela de Símbolos, Tipos e Verificação de Tipos, Ambientes de Execução, Organização da Memória, Mecanismos de Passagem de Parâmetros, Técnicas de Geração de Código, Otimizações de Código.

Descrição

A disciplina Linguagens Formais, Autômatos e Compiladores abrange a teoria, técnicas e ferramentas que permitirão ao Engenheiro de Computação resolver problemas computacionais específicos associados à tradução, interpretação e compilação de linguagens de programação. Essas linguagens podem variar de simples expressões até uma linguagem completa, com comandos tipicamente encontrados nas linguagens de programação tradicionais (C, C++, Python, SQL para citar algumas). A sua aplicabilidade também é ampla: elementos das teorias a serem estudadas nesta disciplina podem ser encontrados diariamente em aplicações tais como editores de texto (por exemplo, em corretores ortográficos, pesquisa e substituição de palavras), na WEB e em aplicações móveis (por exemplo, em sistemas que facilitam a busca, correção e preenchimento de palavras e comandos, interpretação de URLs de páginas e de email, interpretação de XML, interpretação de comandos de voz) e em programação, com linguagens específicas de domínio, embutidas ou não em outras aplicações (o conceito de macro das planilhas é um exemplo). Além disso, esta disciplina possui relacionamentos com outras disciplinas do currículo da Engenharia de Computação, tais como Arquitetura de Computadores e Sistemas Operacionais, oferecendo assim uma oportunidade de integrar seus conhecimentos com os conhecimentos aprendidos nessas disciplinas.

Responsável

Foto Professor

Marco Antonio Furlan de Souza

Mais Informações

Bibliografia

Básica

  • AHO, Alfred V. Compiladores: princípios, técnicas e ferramentas. VIEIRA, Daniel (Trad.). 2. ed. São Paulo: Pearson Addison-Wesley, c2008. 634 p. ISBN 978858639249.
  • COOPER, Keith D.; TORCZON, Linda. Construindo compiladores. VIEIRA, Daniel (Trad.). 2. ed. Rio de Janeiro: Elsevier, c2014. 656 p. ISBN 9788535255645.
  • GERSTING, Judith L. Fundamentos matemáticos para a ciência da computação. 7. ed. Rio de Janeiro, RJ/Brasília, DF: LTC, 2021. 884 p. ISBN 9788521632597.

Complementar

  • DOS REIS, Anthony J. Compiler construction using Java, Java CC, and Yacc. Hoboken, N. J: John Wiley & Sons, c2012. 635 p. ISBN 9780470949597.
  • HOLUB, Allen I. Compiler design in C. Englewood Cliffs, NJ: Prentice-Hall, c1990. 924 p. ISBN 0131550454.
  • JOHNSONBAUGH, Richard. Discrete mathematics. New York: Macmillan, 1989. 480 p. (Maxwell Macmillan International Edition).
  • LEWIS, Harry R; PAPADIMITRIOU, Christos H. Elements of the theory of computation. 2. ed. Upper Saddle River: Prentice Hall, c1998. 361 p. ISBN 0132624788.
  • LOUDEN, Kenneth C. Compiladores: princípios e práticas. SILVA, Flávio Soares Corrêa (Trad.). São Paulo: Pioneira Thomson Learning, c2004. 569 p. ISBN 8522104220.
  • MENEZES, Paulo Blauth. Matemática discreta para computação e informática. 4. ed. Porto Alegre: Bookman, 2013. 348 p. (Livros didáticos Informática UFRGS, 16). ISBN 9788582600245.
  • SOMMERHALDER, Rudolph; VAN WESTRHENEN, S. C. The theory of computability: programs, machines, effectiveness and feasibility. Washington, DC: Addison-Wesley, 1988. 441 p. ISBN 0201142147.
  • TAYLOR, R. Gregory. Models of computation and formal languages. New York, N.Y: Oxford University Press, 1998. 667 p. ISBN 019510983X.