ATC

INTRODUÇÃO
No primeiro módulo da presente disciplina, será apresentada uma revisão da Hierarquia de Chomsky, bem como da máquina de estados finitos, tópicos estes estudados em disciplina anterior. Em seguida, será apresentada a Máquina de Turing, modelo que simula procedimentos computacionais mais gerais que a máquina de estados finitos. Ao final, a definição formal da Máquina de Turing será aduzida. HIERARQUIA DE CHOMSKY Noam Chomsky classificou as Linguagens em quatro tipos, a saber: Linguagens Regulares; Linguagens Livres de Contexto;
Linguagens Dependentes de Contexto; Linguagens Irrestritas. Em uma Linguagem de Programação (Java, C#, por exemplo) ocorrem três componentes da Hierarquia de Chomsky: a componente regular, a livre de contexto e a dependente de contexto. O compilador, que é o software que traduz a Linguagem de Programação de alto nível para a Linguagem de Máquina, emprega algoritmos advindos do do estudo das Linguagens Regulares e Livres de Contexto.
A análise de cada palavra de um programa escrito em uma Linguagem de Programação qualquer, denominada Análise Léxica, usa os algoritmos obtidos do estudo das Linguagens Regulares. Estes algoritmos são a realização do modelo computacional denominado Máquina de Estados Finitos.
A análise de cada comando (if, while, atribuição) e demais estruturas sintáticas (classes, declarações de variáveis, etc.) de um programa desenvolvido em uma Linguagem de Programação, a Análise Sintática, emprega algoritmos advindos de estudo das Linguagens Livres de Contexto.
A componente Dependente de Contexto em uma Linguagem de Programação pode ser identificada na concordância entre a declaração de tipos das variáveis de uma variável, e uso das mesmas, na concordância entre o número de parâmetros na declaração de um método de uma classe e o número de argumentos no uso do método de um objeto, em sobrecarga de métodos, etc. Como será visto na disciplina Compiladores, tais problemas são resolvidos computacionalmente