Dar ao aluno a noção formal de algoritmo, computabilidade, decidibilidade e dos formalismos para definição de linguagens, de modo a conscientizá-lo dos limites teóricos da ciência da computação. Dar ao aluno as noções da teoria e das técnicas de construção de compiladores de linguagens de programação de alto nível.
Definição formal de algoritmo; Máquina de Turing; Tese de Church: Problemas Indecidíveis: Formalismos para geração e reconhecimento de linguagens: Gramáticas e Autômatos; Tipos de Linguagens e Autômatos: Linguagens Regulares e Autômatos Finitos; Linguagens Livre de Contexto e Autômatos com Pilha; Aplicação das noções anteriores na construção de um compilador para uma linguagem de alto nível simples: analisador léxico e analisador sintático recursivo descendente; tabela de símbolos e análise semântica.
Linguagens Regulares: Autômatos finitos determinísticos e não-determinísticos; expressões regulares. Linguagens Livres de Contexto: Gramáticas Livres de Contexto; derivações; árvores de derivação; ambigüidade; autômatos com pilha. Linguagens Dependentes de Contexto e Linguagens com Estrutura de Frase: Máquinas de Turing com Fita Limitada e Máquinas de Turing; definições básicas e a relação das Máquinas de Turing com a noção de um algoritmo/programa. Poder das Máquinas de Turing e Tese de Church- Turing. lndecibilidade: Máquinas de Turing Universais: Limitações sobre a nossa habilidade de computar: problemas indecidíveis clássicos. Conceitos básicos da compilação. Análise léxica e técnicas de implementação de analisadores léxicos. Análise sintática ascendente e implementação de analisadores descendentes recursivos. Análise semântica e tabela de símbolos. Tratamento de erros léxicos, sintáticos e semânticos. Noções de geração de código objeto. Definição de uma linguagem simples e implementação de um front-end de um compilador.
Livro Texto: ROSA, J. L. G. (2010), Linguagens Formais e Autômatos, ISBN 9788521617518. Editora LTC, GEN - Grupo Editorial Nacional, Rio de Janeiro, Brasil, 166 páginas.AHO,A.V et alli - . Compilers, Principles, Techniques, and Tools, Addison-Wesley Company, 1986. HAREL, D. – Algorithmics – The Spirit of Computing, Addison-Wesley, 1992, 1a edição.SIPSER, M.- Introduction to the Theory of Computation,. PWS, 1997, 2a edição.HOPCROFT, V. AND ULLMAN, V.D. Introduction to Automata Theory Language and Computation, Addison-Wesley, 2001. Bibliografia Complementar:KOWALTOWSKY, T. – Implementação de Linguagens de Programação, Guanabara Dois, 1983.AHO, A.V.; ULLMAN, J.D.; SETHI, R. – Compiladores: Princípios, Técnicas e Ferramentas, Editora LTC, 1995.DIVERIO, T. A. E MENEZES, P.B. Teoria da Computação - Máquinas Universais e Computabilidade, Série Livros Didáticos Número 5, Instituto de Informática, da UFRGS, Editora Sagra Luzzatto, 2a edição, 2000.MENEZES, P.B. Linguagens Formais e Autômatos, Série Livros Didáticos Número 3, Instituto de Informática, da UFRGS, Editora Sagra Luzzatto, 4a edição, 2001. PRICE, A.M.A.; TOSCANI, S.S. – Implementação de Linguagens de Programação: Compilador, Editora Sagra Luzzatto, 2001.LOUDEN, K.C. – Compiladores: Princípios e Práticas, Editora Thompson Learning. 2004.
