“Object-oriented programming is an exceptionally bad idea which could only have originated in California.”
Edsger Dijkstra
Compiladores são programas que traduzem código de uma linguagem em outra, ou ainda, programas que criam programas. O compilador recebe um programa na linguagem fonte e o traduz para a linguagem de destino ou objeto. Por exemplo, da linguagem C para Assembly (linguagem de montagem).
No caso de um interpretador, cada instrução do programa é convertida, uma de cada vez, e processada, ao invés de traduzir o programa inteiro e gerar um novo arquivo em nova linguagem. As instruções anteriores já traduzidas não ficam armazenadas, devendo ser convertidas sempre que o programa é executado novamente. Quando um interpretador está processando um arquivo de código-fonte, ele segue um fluxo de execução linear e usa a pilha e o heap para manter informações sobre o estado atual do programa.
Há ainda uma terceira opção, o tradutor, que converte a linguagem original em uma intermediária que pode ser compilada ou interpretada.
Há dois tipos de atividades básicas em compiladores:
Em fases, podemos descrever que o compilador executa o seguinte:
Algumas diferenças entre compiladores e interpretadores:
As fases de análise léxica e sintática são componentes essenciais de um compilador, responsáveis por processar e analisar as menores unidades de um programa, sua estrutura e a validade de um código fonte. Cada etapa desempenha um papel fundamental na transformação do código fonte em uma representação interna adequada para posterior tradução, otimização ou execução.
A análise léxica também é chamada de “scanning” ou processo de escanear o código por lexemas. Os lexemas são representações dos tokens, que são as unidades significativas do código fonte, como palavras-chave, identificadores, operadores e constantes. Cada lexema é então convertido em um token na forma
$$ \langle \text{nome-token}\;,\;\text{valor atribuído}\rangle $$Os tokens são organizados e enviados para a próxima fase, de análise sintática. O “nome-token” é um símbolo que será usado na análise sintática e o “valor atribuído” será armazenado na tabela de símbolos para esse token.
Por exemplo, dado o trecho de código em C:
int soma = a + b;
Os lexemas e seus respectivos tokens seriam identificados, como "int" (palavra-chave), "soma" (identificador), "=" (operador de atribuição), "a" (identificador), "+" (operador de adição), "b" (identificador), e ";" (ponto e vírgula). Espaços vazios e comentários são descartados durante a geração dos tokens, ou seja, não tem utilidade prática para o compilador, são apenas marcações para que os programadores possam entender de forma mais rápida e clara o que foi escrito no programa. Se um lexema inválido for encontrado, isso geralmente indica um erro no código-fonte. O analisador léxico deve lidar com esses erros, gerando mensagens de erro informativas para ajudar os desenvolvedores a identificar e corrigir problemas.
Na fase de análise sintática, ou parsing, o analisador utiliza o que foi gerado pela análise léxica para gerar uma árvore que retrata a estrutura gramatical do programa. Essa "árvore sintática" é organizada de forma que seja possível identificar as operações executadas, na correta ordem, e as variáveis envolvidas entre elas. Cada sentença do programa deve ser válida dentro das regras da linguagem, isto é, o analisador deve ser capaz de reconhecer comandos aceitos e rejeitar os inválidos. Com este processo será possível gerar o programa equivalente em outra linguagem. Por exemplo, considerando o mesmo trecho de código em C visto anteriormente, a análise sintática iria verificar se a sequência de tokens segue as regras sintáticas da linguagem, como a declaração de uma variável utilizando a palavra-chave "int" seguida por um identificador válido, um sinal de atribuição "=", e uma expressão válida.
Na definição de sintaxe utilizamos uma notação chamada de "gramática livre de contexto" ou "gramática". Uma gramática especifica uma estrutura válida dos programas. Por exemplo, a gramática de uma condição if em Java é:
$$ \text{stmt} \rightarrow \text{if ( expr ) stmt else stmt} $$onde a seta quer dizer "pode ter a forma". É uma regra estrutural que também se chama "produção". Quando temos um if e parênteses, chamamos esses elementos de terminais. "expr" : Isso representa uma expressão entre parênteses, que é a condição que será avaliada. A expressão entre parênteses é avaliada como verdadeira ou falsa, determinando qual ramo da instrução condicional será executado. "stmt": Este é o símbolo não terminal que representa uma instrução em Java. Em linguagens de programação, uma instrução é uma unidade de código que realiza uma ação específica, como uma atribuição, um loop ou, no caso dessa gramática, uma instrução if.
As regras de produção, também conhecidas como regras de substituição ou regras de derivação, são usadas para descrever como os símbolos da linguagem podem ser combinados e substituídos para gerar uma sequência válida de símbolos. Cada regra de produção é composta por um símbolo não-terminal (à esquerda) e uma sequência de símbolos terminais e/ou não-terminais (à direita). Os terminais são os símbolos que aparecem no código-fonte real, como palavras-chave, identificadores, operadores e literais. Os não terminais são símbolos que representam classes de elementos, como expressões, instruções ou declarações. Elas indicam como um símbolo não-terminal pode ser substituído por uma sequência de símbolos.
Por exemplo, considerando uma gramática simples para expressões aritméticas:
$$ E \rightarrow E + T \\ E \rightarrow T \\ T \rightarrow T * F \\ T \rightarrow F \\ F \rightarrow ( E ) \\ F \rightarrow id $$Nesse caso, as regras de produção descrevem como as expressões aritméticas podem ser construídas a partir de símbolos não-terminais (E, T, F) e símbolos terminais (+, *, (, ), id). As regras indicam que um não-terminal pode ser substituído por outra sequência de símbolos, permitindo a derivação de diferentes expressões aritméticas.
A gramática também especifica um símbolo inicial, que é geralmente um não terminal, representando o ponto de partida para análise sintática do código-fonte. Isso indica como o programa começa a ser construído.
Uma gramática livre de contexto tem quatro componentes principais:
Essa tabela é uma estrutura de dados utilizada para armazenar principalmente os nomes de variáveis, funções, classes, objetos, etc., utilizados no programa original, além de atributos e valores de cada um. Esses atributos normalmente consistem em tipagem, escopo, argumentos, tipos de retornos, etc.
Cada registro na tabela está ligado a uma variável e pode ser estruturada para permitir ao compilador maior eficiência na pesquisa de um determinado item nas fases subsequentes a sua criação.
A tabela de símbolos desempenha um papel fundamental na análise semântica, que verifica se o programa segue as regras de significado da linguagem. Durante essa fase, a tabela de símbolos é atualizada com informações adicionais, como o tipo de dados associado a cada identificador. Isso permite que o compilador verifique se as operações em identificadores são compatíveis com seus tipos de dados.
Em muitos compiladores, é gerado um código intermediário que é uma representação de nível mais baixo do programa, mais próxima do código de máquina. A tabela de símbolos é usada para rastrear informações sobre os identificadores que aparecem no código intermediário, como seus endereços de memória ou registradores associados.
Durante a otimização de código, o compilador pode realizar várias transformações para melhorar o desempenho do programa. A tabela de símbolos é consultada para obter informações sobre como os identificadores são usados, o que pode afetar as decisões de otimização.
Na última fase, o compilador gera o código de máquina ou código objeto a partir do código intermediário. A tabela de símbolos é usada para resolver referências a identificadores e para mapear os identificadores para endereços de memória ou registradores reais.
Quando tratamos do contexto de uma linguagem, ou seja, a menção de um termo anterior ao objeto que se atua, muitos problemas complexos aparecem. As regras semânticas da linguagem são utilizadas para avaliar atributos dos símbolos, que fornecem mais informações sobre a operação. Ao definirmos as regras sintáticas podemos atribuir regras semânticas associadas a cada uma, de tal forma que: $b=f(c_1,c_2,...,c_k)$, o formato usual, onde b é um atributo gerado a partir de seus filhos em uma árvore sintática (sintetizado) e $c_i$ são ditos símbolos gramaticais.
Um esquema de tradução é uma gramática de atributos sem dependência de contexto onde as funções semântica não têm efeitos colaterais. Um esquema de tradução dirigido por sintaxe pode ser construído utilizando-se de:
Uma árvore sintática, também conhecida como árvore de análise sintática ou árvore de parse, é uma estrutura de dados hierárquica que representa a estrutura gramatical de um programa em uma linguagem de programação. Ela é uma parte fundamental do processo de análise sintática em compiladores e é usada para organizar e representar a hierarquia de elementos do código-fonte.
Quando o código está sendo executado em uma máquina, frequentemente é necessário disponibilizar determinados serviços, bibliotecas, variáveis de ambiente e outras ferramentas para que tudo funcione corretamente. Esses recursos compõe o ambiente em que o código é executado. Pode ser que o programa suba essa estrutura de execução para melhorar a eficiência na comunicação entre seu processo principal e o ambiente de execução.
Um programa qualquer tem diversas instruções que podem ser agrupadas em procedimentos, ou seja, um objeto com começo e fim definidos, chamados de corpo do procedimento. Uma ativação é a execução de um procedimento e contém os dados necessários para aquele bloco. Alguns parâmetros são utilizados nesse momento como:
A representação intermediária de código desempenha um papel crucial no processo de compilação, atuando como uma ponte entre o código-fonte de alto nível e o código de máquina final. Ela é uma forma intermediária que captura a essência semântica do código-fonte original e facilita a otimização e a geração de código eficiente. Esse conceito é uma peça fundamental dos compiladores modernos, pois permite que as etapas subsequentes do processo de compilação sejam mais organizadas, eficientes e passíveis de manutenção.
A principal função da representação intermediária é fornecer uma forma mais simplificada e padronizada do código-fonte original, tornando mais fácil a análise, transformação e otimização. Ela é criada durante a etapa de análise sintática e semântica do compilador, quando o código-fonte é analisado e estruturado em uma forma mais compreensível para a máquina.
Existem diferentes formas de representação intermediária, cada uma com suas próprias características e finalidades. Algumas das representações intermediárias comuns incluem:
Árvores Sintáticas Abstratas (AST): As ASTs capturam a estrutura hierárquica do código-fonte, eliminando detalhes irrelevantes e deixando apenas a estrutura lógica do programa. Isso facilita a análise semântica e a geração subsequente de código.
Representação de Três Endereços: Nessa representação, as instruções são expressas em uma forma mais simples, normalmente com três operandos. Isso torna a análise de código mais direta e facilita a aplicação de otimizações.
Código de Três Endereços: É uma extensão da representação de três endereços, onde as instruções são expressas com operações e operandos, semelhantes às instruções de uma linguagem de montagem simplificada.
Representações de Fluxo de Controle: Algumas representações intermediárias focam na estrutura de controle do programa, capturando fluxos de execução, condições e ciclos.
A representação intermediária permite que o compilador realize diversas otimizações, como otimização de expressões, eliminação de código morto, redução de redundâncias e reorganização de instruções. Além disso, simplifica a geração de código de máquina, já que a partir da representação intermediária é possível criar instruções específicas para a arquitetura de destino.
Nesta fase o analisador semântico utiliza a árvore sintática gerada na fase anterior (análise sintática) para avaliar a consistência semântica do programa com base nas definições da linguagem. A checagem de tipos, por exemplo, faz parte desse processo (verificar se um vetor é indexado por inteiros, que a atribuição a um tipo char tem o tamanho correto, conversões de tipo (float para int ou vice-versa), etc…).
O gerador de código recebe como entrada uma representação intermediária do programa fonte e produz o código na linguagem de destino. Se essa linguagem é em código de máquina, se faz necessário definir registradores e endereços de memória para armazenar os dados do programa. Um exemplo de código Assembly, intermediário, que será traduzido em linguagem de máquina está abaixo:
LDF R2, id3
MULF R2, R2, #60.0
LDF R1, id2
ADDF R1, R1, R2
STF id1, R1
Decisões sobre armazenamento das variáveis podem ocorrer tanto durante a geração de código intermediário ou na geração de código.
Nesta fase há uma tentativa de melhorar o código gerado para a arquitetura escolhida. Uma otimização escolhida pode ser a velocidade, ou código menor, que utiliza menos CPU, etc… Esse processo pode ser bem custoso e lento, com resultados importantes para o código final no quesito performance em geral. Inclusive, muitas opções podem ser utilizadas diretamente na linha de comando para experimentar com alternativas de compilação, tendo resultados expressivos sem precisar alterar o código original.
Um dos principais problemas do novo código gerado é saber como ele se compara com outras possibilidades. Obviamente há infinitas formas de reorganizar o programa, mas apenas algumas que vão cumprir os requisitos definidos antecipadamente. A questão então é como definir quais caminhos seguir em determinado arranjo de palavras em um código para que seja mais eficiente quando executado? Outro problema é sobre a execução em máquinas com múltiplos processadores e compartilhamento de memória com GPUs? O rigor matemático nos ajuda a investigar essa questão e podemos utilizar grafos, matrizes e programação linear para produzir código bem otimizado. Porém, há ainda muitos problemas indecidíveis.
Alguns objetivos básicos devem ser seguidos pelo processo de otimização:
A pilha de execução armazena o registro de ativação do procedimento sendo executado e quando há chamada para outro procedimento, o primeiro fica em suspensão até o término da execução daquele que foi chamado. A árvore de ativação contém a sequência de chamadas para controle e transferência do procedimento em execução.
Quando incluímos arquivos externos em um programa o compilador precisa tomar algumas ações para localizar essas referências e incluí-las de maneira otimizada no código, analisando se de fato há chamadas que utilizam o que foi incluído nas diretivas. Esse processo de referenciar arquivos externos leva ao conceito de modularização de código e também indica ao compilador como efetuar a compilação dos arquivos de forma separada gerando um mesmo arquivo ou vários. Esses módulos podem então ser utilizados para compor o programa principal.
As bibliotecas são conjuntos de funções ou classes com métodos utilizados de maneira recorrente e que podem ser reaproveitados, ou seja, não precisam ser codificados novamente pelo desenvolvedor.
A compilação de arquivos em separado está na base dos ambientes de desenvolvimento modernos com diversos projetos dentro de uma solução que os agrupa. Para referenciar um projeto no outro, por exemplo em C#, precisamos compilá-lo, gerando um arquivo .dll (Dynamic-link Library) que pode então ser copiado para a pasta de referencias externa, debug ou release, dependendo do tipo de execução do código.
Referências: