Linguagens de Programaçã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:

Problemas Indecidíveis (ou impossíveis de serem solucionados);
Problemas Intratáveis (possíveis com recursos ilimitados, porém impossíveis com recursos limitados);
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 da computaçã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 determinada solução é a melhor solução para um dado problema? COMPLEXIDADE
6 – Qual o significado de um determinado programa? SEMÂNTICA
7 – Dado um programa qualquer, este programa está correto? CORREÇÃO/CONSTRUÇÃO

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) que fundamentam 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.

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 conjunto finito 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 sempre pára; ou seja, uma procedure cuja execução chegará ao final, independentemente de quais sejam suas entradas. Adicionalmente, dizemos que uma procedure termina para uma determinada entrada, se existe um número finito t, tal que após a execução de t instruções (não necessariamente distintas), ou não existem mais instruções a serem executadas, ou a última instrução executada foi uma instrução “halt”.

Conjuntos Recursivos e Conjuntos Recursivamente Enumeráveis

Um conjunto é dito Recursivamente Enumerável se ele pode ser representado (solucionado) por uma procedure, e Recursivo se ele pode ser representado (solucionado) por um algoritmo. Como procedures e algoritmos podem ser definidos formalmente através de vários modelos (gramáticas e autômatos, por exemplo), podemos também definir conjuntos recursivos e recursivamente enumeráveis em função de tais modelos.

Problemas Decidíveis e Indecidíveis X Algoritmos e Procedures

Um problema é decidível (tratável ou não) se e somente se ele é resolvível por um algoritmo, para qualquer entrada pertencente ao seu domínio; caso contrário ele é um problema indecidível.

A partir das definições acima, podemos notar claramente a relação entre problemas decidíveis e indecidíveis com conjuntos recursivos e recursivamente enumeráveis; ou seja, um problema é decidível se o conjunto de soluções das diversas instâncias deste problema é um conjunto recursivo, e indecidível caso tal conjunto seja recursivamente enumerável. Assim sendo, torna-se evidente que a questão da decidibilidade pode ser tratada formalmente através dos modelos que compõem a Teoria das Linguagens e Autômatos.

A classe dos problemas indecidíveis é significativamente representada pelo “HALTING PROBLEM” (problema da parada) que consiste em: “Dado uma procedure Z e uma entrada X, decidir (determinar) se Z termina quando aplicado a X. A indecidibilidade deste problema é extremamente útil para demonstrar a indecidibilidade de outros problemas através da redução destes para o ”halting problem ““.

Propósitos da Teoria da Computação

Até aqui definimos procedures e algoritmos de maneira intuitiva e informal. Contudo eles podem ser definidos rigorosamente (precisamente) através de vários formalismos conhecidos como propósitos (ou princípios) da Teoria da Computação. Tais formalismos tem sido explorados largamente na Ciência da Computação, onde servem como modelos na solução de diversos problemas práticos. Dentre os formalismos mais importantes, podemos citar:

Máquinas de Turing (Turing, 1936);
Gramáticas (Chomsky, 1959);
Algoritmos de Markov (Markov, 1951);
Lambda Calculus (Church, 1941);
Sistemas Post e Sistemas de Produção (Emil Post, 1936);
Funções Recursivas (Kleene, 1936).

Um ponto importante a ressaltar aqui, é que toda procedure (ou algoritmo) descrita por algum destes formalismos, pode também ser descrita através de qualquer um dos demais; fato este que sugere a equivalência entre os formalismos.

A aceitação destes formalismos dentro da teoria da computação é, em grande parte, decorrente da hipótese (conhecida como Tese de Church) de que todo processo computável – passível de ser descrito por uma procedure – pode ser realizado por uma Máquina de Turing. Esta tese, apesar de não ter sido provada formalmente, também não foi contradita e continua sendo universalmente aceita. Conseqüentemente podemos afirmar que Máquinas de Turing constituem o formalismo mais genérico para a representação de procedure e que qualquer outro formalismo será significativo se for considerado equivalente às máquinas de Turing. A demonstração formal da equivalência entre os diversos formalismos citados e máquinas de Turing, reforça a tese de Church.

O que é a Teoria das Linguagens Formais?

Para respondermos esta questão precisamos primeiro responder o que é Linguagem Formal, e para isto precisamos antes responder o que é Linguagem.

Inicialmente, de maneira bastante informal, podemos definir uma linguagem como sendo uma forma de comunicação. Elaborando um pouco mais esta definição, podemos definir uma linguagem como sendo “um conjunto de elementos (símbolos) e um conjunto de métodos (regras) para combinar estes elementos, usado e entendido por uma determinada comunidade”.

Exemplos:

1 - Linguagens Naturais (ou idiomáticas)

2 - Linguagens de Programação, de Controle, de Consulta

3 – Protocolos de Comunicação

Contudo, apesar de intuitiva, esta definição não nos permite responder satisfatoriamente as duas primeiras questões; precisamos antes dar um sentido formal para a definição de linguagem. Faremos isto nas duas próximas seções.

Linguagens e suas Representações

Representações de Linguagens: O estudo de linguagens está intimamente relacionado ao estudo das formas de representação dessas linguagens. O problema de representação de uma linguagem, por sua vez, está relacionado com o fato dela ser finita ou infinita:

Linguagem Finita: É uma Linguagem que pode ser representada por enumeração.

Exemplo: A linguagem definida como sendo o conjunto dos inteiros positivos pares maiores que 0 e menores que 20, pode ser representado por: L = {2, 4, 6, 8, 10, 12, 14, 16, 18}.

Linguagem Infinita: Neste caso, na impossibilidade de usarmos enumeração, precisamos encontrar uma representação finita para estas linguagens.

Exemplo:

A linguagem definida como sendo o conjunto dos inteiros pares poderia ser representada por V ={2, 4, 6, 8, 10,...} que, que apesar de intuitiva, não é finita e nem precisa. As representações finitas de linguagens classificam-se em Reconhecedores e Sistemas

Geradores:

Reconhecedores – São dispositivos formais que nos permitem verificar se uma determinada sentença pertence ou não a uma determinada linguagem (é uma representação das sentenças de uma linguagem sob o ponto de vista do reconhecimento de tais sentenças). Esses dispositivos denominam-se autômatos; autômatos finitos, autômatos de pilha e máquinas de turing, por exemplo, podem ser destacados como importantes classes de autômatos.

Sistemas Geradores – São dispositivos formais dotados de mecanismos que permitem a geração sistemática das sentenças de uma linguagem (representação sob o ponto de vista da geração das sentenças de uma linguagem). Os principais sistemas geradores disponíveis são as gramáticas, dentre as quais, por exemplo, podemos destacar as gramáticas de CHOMSKY. Observações: Todo reconhecedor e todo sistema gerador pode ser representado por algorítmos e/ou procedures.

Linguagens Formais: São linguagens que podem ser representadas de maneira finita e precisa através de sistemas com sustentação matemática (dispositivos formais ou modelos matemáticos).

Linguagem Recursiva: Uma linguagem é recursiva se existe um algoritmo capaz de reconhecer ou gerar as sentenças que compõem essa linguagem.

Linguagem Recursivamente Enumerável: É toda a linguagem cujas sentenças podem ser reconhecidas ou geradas por procedures.

Teoria das Linguagens Formais e dos Autômatos

Entende-se por Teoria das Linguagens Formais e dos Autômatos o estudo de modelos matemáticos que possibilitam a especificação e o reconhecimento de linguagens (no sentido amplo da palavra), suas classificações, estruturas, propriedades, características e inter- relacionamentos.

A importância desta Teoria na Ciência da Computação é dupla: Ela tanto apóia outros aspectos teóricos da Ciência da Computação (decidibilidade, computabilidade, complexidade computacional, por exemplo), como fundamenta diversas aplicações computacionais tais como processamento de linguagens, reconhecimento de padrões, modelagem de sistemas.

Autômatos Finitos e Conjuntos Regulares

– A.F.D - Autômato Finito Determinístico
– A.F.N.D. - Autômato Finito Não Determinístico
– Transformação de A.F.N.D. para A.F.D.
– Relação Entre G.R. e A.F. - Gramática Regular e Autômato Finito
– Minimização de Autômatos Finitos
– Conjuntos Regulares e Expressões Regulares
– Implementação de Autômatos Finitos
– Propriedades e Problemas de Decisão sobre Conjuntos Regulares
– Aplicações de A.F. e E.R. - Autômato Finito e Expressões Regulares

Aplicações de A.F. e E.R.

Apesar da simplicidade destas ferramentas, existe uma grande variedade de software cuja especificação e/ou implementação pode ser bastante simplificada se realizada em termos de A.F. e E.R., resultando em software´s mais eficientes. Dentre as diversas aplicações que fazem uso de A.F. e E.R. podemos citar:

1. Analisador Léxico: Os tokens (símbolos básicos) de uma linguagem de programação geralmente podem ser especificados eficientemente através de E.R., as quais podem ser automaticamente convertidas para A.F.D. equivalentes, cuja implementação (o analisador léxico propriamente dito) é trivial.

Isto permite inclusive, a geração automática de um analisador léxico a partir da especificação formal dos “tokens” de uma linguagem de programação.

2. Editores de Texto: As operações de busca e substituição de cadeias de caracteres em um texto, podem ser eficientemente realizadas, se a cadeia for expressa em termos de E.R. e a operação realizada em termos de um A.F. usufruindo da possibilidade da conversão automática de E.R. para A.F., de forma transparente ao usuário.

3. Além das aplicações acima (tidas como as principais) podemos também destacar o uso destas ferramentas nas seguintes áreas:

Protocolos de comunicação
Projeto (modelagem) de sistemas operacionais
Path Expression
Problemas específico tais como: segurança de arquivos, desorientação em sistemas de hipertexto, modelagem de redes neurais, compressão de dados, etc...

Gramáticas Livres de Contexto e Autômatos de Pilha

– Árvore de Derivação (A.D.) ou Árvore Sintática (A.S)
– Limite de uma Árvore de Derivação
– Derivação mais a Esquerda e mais a Direita
– Gramáticas Ambíguas
– Transformações (Simplificações) em G.L.C.
1. – Eliminação de Símbolos Inúteis
2. – Transformação de G.L.C. em G.L.C. e - Livre
3. – Eliminação (Remoção) de Produções Simples
4. – Fatoração de G.L.C.
5. – Eliminação de Recursão a Esquerda
– Tipos Especiais de G.L.C
– Autômatos de Pilha (PDA)
– Equivalência entre PDA e G.L.C.
– Propriedades e Problemas de Decisão das LLC
– Aplicações

Dentre os quatro tipos de gramáticas estudadas, as G.L.C. são as mais importantes na área de compiladores e linguagens de programação, pelo fato de especificarem eficientemente as construções sintáticas usuais.

Classes de Analisadores

Existem duas classes fundamentais de analisadores sintáticos, definidos em função da estratégia utilizada na análise:

Analisadores Descendentes (Top-down)

Consistem em uma tentativa de chegar-se a sentença a partir do símbolo inicial de G, olhando a sentença ou parte dela para decidir que produção deverá ser usada na derivação.

Analisadores Ascendentes (Bottom-up)

Consistem em uma tentativa de chegar-se ao símbolo inicial de G a partir da sentença a ser analisada, olhando a sentença ou parte dela para decidir que produção deverá ser usada na redução.

V.2.1– Analisadores Descendentes (Top-Down)

A idéia geral desta classe de analisadores resume-se a uma tentativa de construir a derivação mais à esquerda da sentença de entrada, ou equivalentemente, uma tentativa de construir a A.D. da sentença a partir do símbolo inicial da gramática em questão. Estes analisadores podem ser implementados com (analisadores não-deterministicos) ou sem back- track (analisadores deterrminísticos):

A. A utilização de back-track permite que um conjunto maior de G.L.C.(incluindo gramáticas ambíguas) possa ser analisado, entretanto apresenta várias desvantagens (todas decorrentes do Não-Determinismo), dentre as quais podemos destacar:

1 – Maior tempo necessário para a análise;

2 – Dificuldade na recuperação de erros;

3 – Problemas na análise semântica e geração de código.

Os analisadores descendentes não-determinísticos (dentre os quais destaca-se a técnica da Força bruta), nada mais são do que implementações diretas da idéia geral dessa classe de analisadores, ou seja: consistem em uma tentativa de construção (explicita) da árvore de derivação da sentença em análise, a partir do símbolo inicial da gramática. O uso do mecanismo de back-track faz-se necessário em função da possível presença de não- determinismo neste processo.

B. As implementações sem back-track apesar de limitarem a classe de gramáticas que podem ser analisadas – como veremos adiante – tornam-se mais vantajosas pelo fato de serem técnicas determinísticas e superarem as deficiências praticas das implementações com back- track. Assim sendo, enfatizaremos neste curso as técnicas determinísticas (ou seja, as técnicas que não fazem uso do mecanismo de back-track).

Técnicas de Implementação

Descendente Recursivo: Esta técnica consiste basicamente na construção de um conjunto de procedimentos (normalmente recursivos), um para cada símbolo não terminal da gramática em questão.

A principal desvantagem desta técnica é que ela não é geral, ou seja, os procedimentos são específicos para cada gramática; além disso, o tempo de análise é maior (se comparado com a técnica que veremos a seguir) e existe a necessidade de uma linguagem que permita recursividade para sua implementação.

Por outro lado, a principal vantagem desta técnica, é a simplicidade de implementação e a facilidade para inserir as diferentes funções do processo de compilação, diretamente nos procedimentos que realizam a análise sintática de cada não-terminal da gramática; contudo esta vantagem verifica-se apenas para gramáticas/linguagens pequenas e simples.

Outro inconveniente desta técnica é a dificuldade para validação do analisador construído, uma vez que os procedimentos não estão livres de erros de programação e ou erros decorrentes da não adequação da gramática para esta classe de analisadores (por exemplo, a presença de ambigüidade ou recursões à esquerda indiretas, não percebidas pelo projetista).

Analisadores Ascendentes

A formulação dos algoritmos de análise sintática ascendente baseia-se em um algoritmo primitivo denominado Algoritmo Geral Shift-Reduce (Avança-Reduz). Este algoritmo utiliza:

a) Uma Pilha Sintática (inicialmente vazia);

b) Um Buffer de Entrada (contendo a sentença a ser analisada);

c) Uma G.L.C. (com as produções numeradas de 1 a p);

d) Um procedimento de análise sintática, o qual consiste em transferir (“Shiftar”) os símbolos da entrada (um a um) para a pilha até que o conteúdo da pilha (ou parte dele) coincida com o lado direito de uma produção. Quando isto ocorrer, o lado direito da produção deve ser substituído pelo (reduzido ao) lado esquerdo da produção em questão. Este processo deve ser repetido ate que toda a sentença de entrada tenha sido analisada.

Observações:

1 – As reduções são prioritárias em relação ao shifts.
2 – Se ao final do processo a Entrada estiver vazia e a pilha sintática contiver apenas o símbolo inicial de G, então a sentença analisada estará sintaticamente correta.

Deficiências do Algoritmo Shift-Reduce

Embora esta técnica de análise sintática possa ser aplicada a qualquer GLC (esta é sua grande vantagem), ela apresenta várias deficiências que inviabilizam seu uso na prática. São elas:

1   – Requer muito tempo para analise;
2   – Só detecta erro sintático após consumir toda a sentença a ser analisada e, além disso, não identifica o ponto onde ocorreu o erro.
3   – Pode rejeitar sentenças corretas – pelo fato de que nem sempre que o lado direito de uma produção aparece na pilha a ação correta é uma redução, fato este que caracteriza o Não- Determinismo do método.

O problema do não-determinismo pode ser contornado através do uso da técnica de Back-Tracking; contudo, o uso desta técnica inviabiliza o método na pratica (em função da complexidade de tempo e espaço).
Na prática, as técnicas de análise sintática ascendente usuais superam as deficiências da técnica Shift-Reduce com Back-Tracking (apesar de fundamentarem-se nela), apresentando as seguintes características:

1 – Tempo de análise diretamente proporcional ao tamanho da sentença;

2 – Detecção de erros sintáticos no momento da ocorrência;
3 – São técnicas Determinísticas, isto é, em qualquer situação, haverá sempre uma única ação a ser efetuada.

Contudo, estas características tem um custo associado: a imposição de restrições às GLC, para que as mesmas possam ser analisadas deterministicamente. Uma restrição comum à todas as técnicas deterministicas, é a exigência de que a GLC não seja ambígua.

Principais Técnicas de Análise Sintática Ascendente

A classe de analisadores ascendentes determinísticos é composta por uma série de técnicas, dentres as quais destacam-se grandemente duas famílias de técnicas:

1 – Analisadores de Precedência (Simples, estendida e de operadores) - Estes analisadores baseiam-se no algoritmo Shift-Reduce, acrescido de relações de precedência entre os símbolos da gramática; relações estas que definem, de forma determinística a ação a ser efetuada em uma dada situação.
2 - Analisadores LR - Esta família de analisadores também baseia-se nas operações shift e reduce (é, na verdade, uma evolução natural do algoritmo geral shift-reduce). A diferença fundamental é que estas operações (shift e reduce) são realizados sempre deterministicamente, com base no estado corrente da análise e nas propriedades estruturais da gramática em questão.

Além de teoricamente importante, a família LR (especialmente as técnicas SLR(1) e LALR(1)) é a mais utilizada na implementação de analisadores sintáticos, e por isso será estudada de forma mais detalhada neste curso.

linguagens de programação

Linguagem de programação

O artigo ou secção Linguagem de programação de alto nível deverá ser fundido aqui. (desde março de 2019)
Se discorda, discuta esta fusão aqui.

Trecho de programa na linguagem de programação C.

A linguagem de programação é um método padronizado para comunicar instruções para um computador.[1] É um conjunto de regras sintáticas e semânticas usadas para definir um programa de computador.[2][Nota 1] Permite que um programador especifique precisamente sobre quais dados um computador vai atuar, como estes dados serão armazenados ou transmitidos e quais ações devem ser tomadas sob várias circunstâncias. Linguagens de programação podem ser usadas para expressar algoritmos com precisão.

O conjunto de palavras (lexemas classificados em tokens), compostos de acordo com essas regras, constituem o código fonte de um software.[3] Esse código fonte é depois traduzido para código de máquina, que é executado pelo microprocessador.[3]

Uma das principais metas das linguagens de programação é que programadores tenham uma maior produtividade, permitindo expressar suas intenções mais facilmente do que quando comparado com a linguagem que um computador entende nativamente (código de máquina).[4] Assim, linguagens de programação são projetadas para adotar uma sintaxe de nível mais alto, que pode ser mais facilmente entendida por programadores humanos. Linguagens de programação são ferramentas importantes para que programadores e engenheiros de software possam escrever programas mais organizados e com maior rapidez.

Linguagens de programação também tornam os programas menos dependentes de computadores ou ambientes computacionais específicos (propriedade chamada de portabilidade[5]). Isto acontece porque programas escritos em linguagens de programação são traduzidos para o código de máquina do computador no qual será executado em vez de ser diretamente executado. Uma meta ambiciosa do Fortran, uma das primeiras linguagens de programação, era esta independência da máquina onde seria executada.[6][7]

Índice

História

O primeiro trabalho de linguagem de programação foi criado por Ada Lovelace, grande amiga de Charles Babbage.[8] O projeto da primeira calculadora mecânica programável foi idealizado por Charles Babbage[9] que, após gastar fortunas e um longo tempo, não conseguiu concretizar o projeto.[10] A linguagem de programação ADA foi batizada em homenagem a esta primeira programadora.[11]

Uma das primeiras linguagens de programação para computadores foi provavelmente Plankalkül, criada por Konrad Zuse na Alemanha Nazista,[12]mas que teve pouco ou nenhum impacto no futuro das linguagens de programação.

O primeiro compilador foi escrito por Grace Hopper,[13] em 1952, para a linguagem de programação A-0.[14] A primeira linguagem de programação de alto nível amplamente usada foi Fortran, criada em 1954.[14][15] Em 1957 foi criada B-0, sucessora da A-0, que daria origem a Flow-Matic (1958), antecessor imediato de COBOL, de 1959.[16] O COBOL foi uma linguagem de ampla aceitação para uso comercial.[16] A linguagem ALGOL foi criada em 1958-1960[17] O ALGOL-60 teve grande influência no projeto de muitas linguagens posteriores.[18]

A linguagem Lisp foi criada em 1958 e se tornou amplamente utilizada na pesquisa na área de ciência da computação mais proeminentemente na área de Inteligência Artificial.[19] Outra linguagem relacionada ao campo da IA que surge em 1972 é a linguagem Prolog, uma linguagem do paradigma lógico.[20]

A orientação a objetos é outro marco importante na história das linguagens de programação. A linguagem Simula 67 introduz o conceito de classes.[21] A linguagem Smalltalk[22][23] expande o conceito de classes e se torna a primeira linguagem de programação que oferecia suporte completo à programação orientada a objetos.[24] A linguagem C++ (originalmente conhecida como C com classes) populariza a orientação a objetos.[25]

Diversas linguagens de programação surgiram desde então. Entre estas incluem-se C#,[26] VB.NET, Java, Object Pascal, Objective-C, PHP, Python,[27]SuperCollider, linguagem D[28] e Ruby.[29][Nota 2]

Interpretação e compilação

O processo da compilação.

Uma linguagem de programação pode ser convertida, ou traduzida, em código de máquina por compilação ou interpretada por um processo denominado interpretação. Em ambas ocorre a tradução do código fonte para código de máquina.[30]

Se o método utilizado traduz todo o texto do programa (também chamado de código), para só depois executar[Nota 3] o programa, então diz-se que o programa foi compilado e que o mecanismo utilizado para a tradução é um compilador (que por sua vez nada mais é do que um programa).[31] A versão compilada do programa tipicamente é armazenada, de forma que o programa pode ser executado um número indefinido de vezes sem que seja necessária nova compilação, o que compensa o tempo gasto na compilação. Isso acontece com linguagens como Pascal[32] e C.

Se o texto do programa é executado à medida que vai sendo traduzido, como em JavaScript, BASIC, Python ou Perl, num processo de tradução de trechos seguidos de sua execução imediata, então diz-se que o programa foi interpretado e que o mecanismo utilizado para a tradução é um interpretador. Programas interpretados são geralmente mais lentos do que os compilados, mas são também geralmente mais flexíveis, já que podem interagir com o ambiente mais facilmente.[33]

Embora haja essa distinção entre linguagens interpretadas e compiladas, as coisas nem sempre são tão simples. Há linguagens compiladas para um código de máquina virtual (sendo esta máquina virtual apenas mais um software, que emula a máquina virtual sendo executado em uma máquina real), como Java[34] (compila para a plataforma Java[35]) e C# (compila para a plataforma CLI[36]). E também há outras formas de interpretar em que os códigos fontes, ao invés de serem interpretados linha-a-linha, têm blocos "compilados" para a memória, de acordo com as necessidades, o que aumenta a performance dos programas quando os mesmos módulos são chamados várias vezes, técnica esta conhecida como JIT.

Como exemplo, podemos citar a linguagem Java. Nela, um compilador traduz o código java para o código intermediário (e portável) da JVM. As JVMs originais interpretavam esse código, de acordo com o código de máquina do computador hospedeiro, porém atualmente elas compilam, segundo a técnica JIT o código JVM para código hospedeiro.

A tradução é tipicamente feita em várias fases, sendo as mais comuns a análise léxica, a análise sintática (ou parsing), a geração de código e a otimização.[37]Em compiladores também é comum a geração de código intermediário.[Nota 4]

Conceitos

Programação estruturada

Programação estruturada é uma forma de programação de computadores que preconiza que todos os programas possíveis podem ser reduzidos a apenas três estruturas: sequência, decisão e repetição.[38] Um dos primeiros a preconizar a programação estruturada foi Haskell B. Curry[39][Nota 5] Tendo, na prática, sido transformada na Programação modular, a Programação estruturada orienta os programadores para a criação de estruturas simples em seus programas, usando as sub-rotinas e as funções. Foi a forma dominante na criação de software entre a programação linear e a programação orientada por objetos.[40] Apesar de ter sido sucedida pela programação orientada por objetos, pode-se dizer que a programação estruturada ainda é marcantemente influente, uma vez que grande parte das pessoas ainda aprendem programação através dela. Porém, a orientação a objetos superou o uso das linguagens estruturadas no mercado.[41]

Programação modular

Niklaus Wirth em 2005. Criador da linguagem Pascal entre outras.

Programação modular é uma forma de programação no qual o desenvolvimento das rotinas de programação é feito através de módulos, que são interligados entre si através de uma interface comum.[42] Foi apresentado originalmente pela Information & Systems Institute, Inc. no National Symposium on Modular Programming em 1968, com a liderança de Larry Constantine. Exemplos de linguagens que orientaram seu projeto para este aspecto estão as linguagens Modula-2,[43][44]desenvolvida por Niklaus Wirth e a Modula-3.[45]

Programação orientada a objetos

Orientação a objetos, também conhecida como Programação Orientada a Objetos (POO), ou ainda em inglês Object-Oriented Programming (OOP) é um paradigma de análise, projeto e programação de sistemas de software baseado na composição e interação entre diversas unidades de software chamadas de objetos. O extensivo uso de objetos, particularmente em conjunção com o mecanismo de herança, caracteriza o estilo de programação orientada a objetos.[46] Em alguns contextos, prefere-se usar modelagem orientada ao objeto (UML), em vez de programação. De fato, o paradigma "orientação a objetos" tem bases conceituais e origem no campo de estudo da cognição, que influenciou a área de inteligência artificial e da lingüística no campo da abstração de conceitos do mundo real. Na qualidade de método de modelagem, é tida como a melhor estratégia, e mais natural, para se eliminar o "gap semântico", dificuldade recorrente no processo de modelar o mundo real, no domínio do problema, em um conjunto de componentes de software que seja o mais fiel na sua representação deste domínio.

Facilitaria a comunicação do profissional modelador e do usuário da área alvo, na medida em que a correlação da simbologia e conceitos abstratos do mundo real e da ferramenta de modelagem (conceitos, terminologia, símbolos, grafismo e estratégias) fosse a mais óbvia, natural e exata possível. A análise e projeto orientados a objetos tem como meta identificar o melhor conjunto de objetos para descrever um sistema de software.[47] O funcionamento deste sistema se dá através do relacionamento e troca de mensagens entre estes objetos. Na programação orientada a objetos, implementa-se um conjunto de classes que definem os objetos presentes no sistema de software. Cada classe determina o comportamento (definido nos métodos) e estados possíveis (atributos) de seus objetos, assim como o relacionamento com outros objetos.[42]

Programação linear

Em matemática, problemas de Programação Linear são problemas de otimização nos quais a função objetivo e as restrições são todas lineares.[48]Programação Linear é uma importante área da otimização por várias razões. Muitos problemas práticos em pesquisa operacional podem ser expressos como problemas de programação linea

problemas de otimização funcionam resolvendo problemas de PL como sub-problemas. Historicamente, ideias da programação linear inspiraram muitos dos conceitos centrais de teoria da otimização, tais como dualidade, decomposição, e a importância da convexidade e suas generalizações.

Classificação

As linguagens de programação podem ser classificadas e sub-classificadas de várias formas.

Classificação da ACM

A ACM mantém um sistema de classificação[49] com os seguintes sub-itens:

Linguagens aplicativas, ou de aplicação
Linguagens concorrentes, distribuídas e paralelas
Linguagens de fluxo de dados
Linguagens de projeto
Linguagens extensíveis
Linguagens de montagem e de macro
Linguagens de microprogramação
Linguagens não determinísticas
Linguagens não procedurais
Linguagens orientadas a objeto
Linguagens de aplicação especializada
Linguagens de altíssimo nível[Nota 6]

Quanto ao paradigma

Diferentes linguagens de programação podem ser agrupadas segundo o paradigma que seguem para abordar a sua sintaxe e semântica. Os paradigmas se dividem em dois grandes grupos: imperativo e declarativo.[50]

Paradigmas Imperativos

Os paradigmas imperativos são aqueles que facilitam a computação por meio de mudanças de estado.[50] Se dividem em:

O paradigma procedural. Neste paradigma, os programas são executados através de chamadas sucessivas a procedimentos separados. Exemplos de linguagens deste paradigma são o Fortran e o BASIC.
O paradigma de estruturas de blocos.[50] A característica marcante deste paradigma são os escopos aninhados. Exemplos de linguagens deste paradigma são o Algol 60, Pascal[32] e C.
O paradigma de orientação a objetos. Este paradigma descreve linguagens que suportam a interação entre objetos. Exemplos de linguagens deste paradigma são C++,[25] linguagem D,[51] Java, Python[27] e Ruby.[29]
O paradigma da computação distribuída. Este paradigma suporta que mais de uma rotina possa executar independentemente.[52] Um exemplos de linguagem deste paradigma é a linguagem Ada.

Paradigmas Declarativos

Os paradigmas declarativos são aqueles nos quais um programa especifica uma relação ou função.[50] Se dividem em:

O paradigma funcional. Linguagens deste paradigma não incluem qualquer provisão para atribuição ou dados mutáveis[53] Na programação funcional, o mapeamento entre os valores de entrada e saída são alcançados mais diretamente. Um programa é uma função (ou grupo de funções), tipicamente constituída de outras funções mais simples.[54] Exemplos de linguagens deste paradigma são as linguagens Lisp,[55] Scheme[56] e Haskell[57]
O paradigma da programação lógica. Este paradigma se baseia na noção de que um programa implementa uma relação ao invés de um mapeamento.[58]Exemplos de linguagens deste paradigma são o Prolog[59] e a linguagem Gödel.[60]

Quanto a estrutura de tipos

As linguagens de progração podem ser definidas de duas formas ortogonais quanto a sua estrutura de tipos.

Forte ou Fracamente Tipada

Fracamente tipada, como PHP e Smalltalk, onde o tipo da variável muda dinamicamente conforme a situação.
Fortemente tipada, como Java, Ruby e Python onde o tipo da variável, uma vez atribuído, se mantém o mesmo até ser descartada da memória.[61]

Dinâmica cou Estaticamente Tipada

Dinamicamente tipada, como SNOBOL, APL, Awk, Perl, Python e Ruby, onde o tipo da variável é definido em tempo de execução.[61]
Estaticamente tipada, como Java e C, onde o tipo da variável é definido em tempo de compilação.[62]

Quanto ao grau de abstração

Linguagem de programação de baixo nível, cujos símbolos são uma representação direta do código de máquina que será gerado, onde cada comando da linguagem equivale a um "opcode" do processador, como Assembly.[63]
Linguagem de programação de médio nível,[Nota 7] que possui símbolos que podem ser convertidos diretamente para código de máquina (goto, expressões matemáticas, atribuição de variáveis), mas também símbolos complexos que são convertidos por um compilador. Exemplo: C, C++
Linguagem de programação de alto nível, composta de símbolos mais complexos, inteligível pelo ser humano e não-executável diretamente pela máquina, no nível da especificação de algoritmos, como Pascal,[32] Fortran, ALGOL,Java e SQL.[63]

Quanto à geração

A classificação das linguagens de programação em gerações é uma questão que apresenta divergências de autor para autor. Segundo Maclennan,[64] as linguagens se dividem em cinco gerações com as seguintes características:

Primeira geração - São linguagens onde suas estruturas de controle são aparentemente orientadas a máquina. As instruções condicionais não são aninhadas e dependem fortemente de instruções de desvio incondicional como o GOTO. Uma linguagem típica desta geração é a linguagem Fortran.[64]

Segunda geração - São linguagens onde as estruturas de controle são estruturadas de forma a minimizar ou dispensar o uso de instruções GOTO. A segunda geração elaborou melhor e generalizou diversas estruturas de controle das linguagens de primeira geração. Uma das grandes contribuições desta geração foi suas estruturas de nomes, que eram hierarquicamente aninhadas. Isto permitiu melhor controle de espaços de nomes e uma eficiente alocação dinâmica de memória. Uma linguagem típica desta geração é o Algol 60.[64]

Terceira geração - São linguagens que dão ênfase a simplicidade e eficiência. Uma linguagem típica desta geração é a linguagem Pascal.[32] As estruturas de dados desta geração mostram um deslocamento da máquina para a aplicação. As estruturas de controle são mais simples e eficientes.[64]

Quarta geração - Esta geração é essencialmente o sinônimo para linguagens com abstração de dados. A maioria das linguagens desta geração focam na modularização e no encapsulamento. Uma linguagem típica desta geração é a linguagem Ada.[64]

Quinta geração - Nesta geração, Maclennan agrupa diversos paradigmas como a orientação a objeto e o paradigma funcional, paradigma lógico.[64]

Henri Bal e Dick Grune, já apresentam uma classificação em gerações de forma diferente, enfatizando mais o aspecto da aplicação. São elencadas 6 gerações.[65]

Primeira geração - linguagem de máquina.
Segunda geração - linguagens de montagem (assembly).
Terceira geração - Linguagens procedurais.
Quarta geração - Linguagens aplicativas.
Quinta geração - Linguagens voltadas a Inteligência artificial como as linguagens lógicas (Prolog) e as linguagens funcionais (Lisp).
Sexta geração - Redes neurais.

Doris Apleby e Julius J. VandeKopple dividem as linguagens em quatro gerações que coincidem com as quatro primeiras gerações elencadas por Henri Bal e Dick Grune.[50]