Linguagens formais e compiladores

Disponível somente no TrabalhosFeitos
  • Páginas : 58 (14427 palavras )
  • Download(s) : 0
  • Publicado : 23 de novembro de 2012
Ler documento completo
Amostra do texto
Universidade Federal de Santa Catarina
Centro Tecnológico

Departamento de Informática e de Estatística




LINGUAGENS FORMAIS E COMPILADORES

(Prof. Olinto José Varela Furtado)


Capítulo I – Introdução


I.1 - Introdução a Compiladores
I.2 - Introdução a Teoria da Computação
I.3 - Introdução a Teoria das Linguagens Formais


I.1 – Introdução a CompiladoresI.2 - Introdução a Teoria da Computação

O Que é Teoria da Computação?
A Teoria da Computação pode ser vista como um guia (um roteiro) que nos orienta no sentido de informar o que pode e o que não pode ser efetivamente computável, explicando porque, de que forma e com que complexidade. Neste sentido, a Teoria da Computação classifica os problemas computacionais em três classes:a) Problemas Indecidíveis (ou impossíveis de serem solucionados);
b) Problemas Intratáveis (possíveis com recursos ilimitados, porém impossíveis com recursos limitados);
c) Problemas Tratáveis (possíveis de serem solucionadas com recursos limitados).


Esta classificação engloba problemas de toda a natureza, envolvendo desde problemas clássicos que fundamentam a teoria dacomputação até problemas (ou instâncias de problemas) práticos da ciência da computação, tais como:
1 – Existe programa para solucionar um determinado problema?
2 – Qual o poder de expressão de um determinado modelo de especificação?
3 – Dado um programa qualquer, ele sempre tem parada garantida?
4 – Dois programas P1 e P2 são equivalentes entre si?
5 – Uma determinadasolução é a melhor solução para um dado problema?
6 – Qual o significado de um determinado programa?
7 – Dado um programa qualquer, este programa está correto?


Esta lista poderia ser expandida e detalhada, contudo, seu objetivo é enfatizar a abrangência da teoria da computação. Dos tópicos aqui listados, complexidade (5), semântica (6) e correção/construção (7), costumam ser tratadoscomo disciplinas específicas e independentes, enquanto que os demais se classificam como problemas básicos da teoria da computação. Todos os problemas computacionais podem ser tratados (estudados) sob a ótica da Teoria das Linguagens Formais e Autômatos.
Segundo esta ótica, a teoria da computação pode ser vista como um conjunto de modelos formais (juntamente com suas propriedades) quefundamentam a ciência da computação. Tais modelos incluem Autômatos (Finitos, de Pilha e Máquinas de Turing) e Gramáticas, enquanto que as propriedades de interesse envolvem questões de decidibilidade, Inter-relacionamento entre modelos (abrangência, equivalência, etc...) e complexidade computacional.
Nesta apostila, abordaremos a Teoria da Computação segundo a ótica da Teoria das Linguagens Formaise Autômatos.





I.2.1 - Conceitos e Propósitos Fundamentais da Teoria da Computação


Com o objetivo de melhor fundamentar as questões cobertas pela teoria da computação e de identificar claramente a possibilidade de reduzir tais questões a problemas pertinentes a Teoria das Linguagens Formais, apresentaremos nesta seção alguns conceitos fundamentais e comentamos alguns dosprincipais propósitos que sustentam a teoria da computação.





Procedures e Algorítmos


O conceito de algoritmo é fundamental dentro da ciência da computação e pode ser definido formalmente segundo vários propósitos da teoria da computação (como será visto no final desta seção) ou informalmente em função da definição de procedure (como veremos a seguir).


Procedure: É m conjuntofinito de passos (instruções), os quais podem ser executados mecanicamente em uma quantidade fixa de tempo e com uma quantidade fixa de esforço. Um bom exemplo de uma procedure é um programa de computador escrito em linguagem de máquina, pois tal programa possui um número finito de passos, todos executáveis mecanicamente com uma quantidade fixa de recursos.

Algoritmo: É uma procedure que...
tracking img