Teoria da computação e compiladores

Por onde começar

Esta unidade integra Algoritmos e programação, na disciplina Informática e TIC. Para começar, os slides «Introdução à Teoria da Computação» apresentam perguntas sobre computação, algoritmos e propriedades matemáticas de hardware e software. Em seguida, o mapa «Linguagens Formais e Automatos» organiza conceitos de linguagens formais e autômatos, incluindo alfabetos e símbolos.

Use os slides para identificar as perguntas centrais e o mapa para relacionar os termos. Ao estudar, procure reconhecer como os conceitos aparecem nos exemplos e nas questões dos outros recursos da página.

Gramáticas e análise sintática

As notas sobre gramáticas EBNF, BNF e ambíguas abordam a ordem de interpretação de números e operações, incluindo parênteses, multiplicação e divisão. Há também notas sobre fatoração de gramáticas e análise sintática. Estas últimas apresentam exemplos de remoção de recursão direta à esquerda e de fatoração de regras.

Depois de consultar as notas, use «Exercícios - Árvore de Derivação» para praticar a identificação de regras de produção em uma árvore. O quiz sobre ambiguidade oferece outra forma de retomar o tema. Compare as questões com as anotações para localizar os conceitos que precisam de mais atenção.

Autômatos e computabilidade

O quiz «Automatos Limitados Linearmente» traz questões sobre autômatos linearmente limitados e máquinas de Turing. A página também lista quizzes sobre máquinas de Turing determinísticas e sobre o lema do bombeamento. Eles podem ser usados depois da consulta aos mapas sobre linguagens formais e autômatos.

Para ampliar a revisão, os mapas «Computabilidade», «Complexidade computacional» e «Problema de Decisão» apresentam outros tópicos da unidade. Neste último aparecem termos como decidibilidade e classes de complexidade. Consulte o mapa antes de voltar às questões e use os termos como guia para organizar sua revisão.

Da teoria à compilação

As notas «Compilação x Interpretação» distinguem a tradução de programas de sua execução. O mapa «Mecanismos de Conversões de linguagens» reúne, entre outros elementos, pré-processador, montador, compilador e interpretadores. Também há mapas sobre o processo de compilação e uma introdução à compilação.

Uma sequência possível é ler as notas, observar os mecanismos no mapa e depois retomar a análise sintática. Assim, os recursos podem ser consultados em conjunto, sem precisar seguir uma única ordem. Escolha um tema da página e monte seu próprio mapa ou conjunto de flashcards para organizar a revisão.