Como Compiladores funcionam?
Compiladores são ferramentas usadas diariamente por programadores e desempenham um papel crucial no desenvolvimento de software. Eles atuam como uma ponte entre o código escrito em linguagem de alto nível (entendida pelos humanos) e a linguagem de baixo nível (interpretada pelas máquinas).
Neste artigo, desejo apresentar a você, caro leitor, de maneira simples e clara, como se dá o processo de compilação e quais são suas principais etapas. Desvendando um pouco do “mistério” que, por vezes, parece envolver esse tema.
Como é feito uma compilação?
O compilador é uma ferramenta que traduz o código fonte escrito por um desenvolvedor em uma determinada linguagem (C++ ou Java por exemplo) para uma linguagem de máquina, ou seja, Código de Bytes ou Assembly. Que pode ser diretamente executada por um sistema operacional.
Para realizar esta compilação, o processo costuma ser divido em 7 etapas, estas são:
1. Análise Léxica: O código fonte escrito pelo humano é transformado em uma sequência de tokens. Estes tokens nada mais são, do que uma sequência de caracteres que representam uma unidade lógica do código fonte. Como por exemplo:
int x = 5;O processo de análise léxica irá dividir o código nos seguintes tokens:
1. “int”: Indica que foi declarado uma variável do tipo inteiro;
2. “x”: Indica o nome desta variável;
3. “=”: Caracter de atribuição lógica;
4. “5”: O valor literal do inteiro;
5. “;”: Fim da instrução;
No final o compilador terá uma sequência de tokens desta forma:
[INT_KEYWORD, IDENTIFIER("x"), ASSIGN_OPERATOR, INTEGER_LITERAL(5), SEMICOLON]Este processo costuma ser feito através do uso de Expressões Regulares ou Autômatos Finitos, e são usados para reconhecer padrões no código fonte.
Como por exemplo, uma expressão regular para identificar números inteiros seria [0-9]+ , ou para identificar caracteres [a-zA-Z_][a-zA-Z0-9_]* .
Outro exemplo, se fossemos gerar a sequência de tokens do algoritmo abaixo, teriamos o seguinte resultado:
function int soma(int a, int b) {
return a + b;
}
int x = soma(5, 3);[
// Para a definição da função
FUNCTION_KEYWORD,
INT_KEYWORD,
IDENTIFIER("soma"),
LEFT_PARENTHESIS,
INT_KEYWORD,
IDENTIFIER("a"),
COMMA,
INT_KEYWORD,
IDENTIFIER("b"),
RIGHT_PARENTHESIS,
LEFT_BRACE,
RETURN_KEYWORD,
IDENTIFIER("a"),
ADDITION_OPERATOR,
IDENTIFIER("b"),
SEMICOLON,
RIGHT_BRACE,
// Para a invocação da função
INT_KEYWORD,
IDENTIFIER("x"),
ASSIGN_OPERATOR,
IDENTIFIER("soma"),
LEFT_PARENTHESIS,
INTEGER_LITERAL(5),
COMMA,
INTEGER_LITERAL(2),
RIGHT_PARENTHESIS,
SEMICOLON
]Após a etapa da geração dos tokens, estas informações são passadas para próxima fase.
2. Análise Sintática (Parsing): Com a sequência já pronta, agora ela será transformada em uma Árvore de Sintaxe Abstrata (AST, do inglês “Abstract Syntax Tree”). Utilizando o primeiro código anterior, a estrutura ficaria da seguinte forma:
Declaration
|
|-- Type: int
|-- Identifier: x
|-- Assignment
|
|-- Value: 5Essa árvore indica que temos uma declaração (Declaration) de uma variável do tipo int com o identificador x que está sendo atribuído um valor 5.
O parser trabalha com base na gramática da linguagem de programação utilizada para construir a árvore. Pois é a gramática que define como os tokens podem ser combinados.
Existem diferentes algoritmos para realizar o parsing, como por exemplo LL ou LR. A estratégia para escolha depende das características da linguagem e dos requisitos do compilador.
Quando digo que ele trabalha com base nas regras de gramática da linguagem de programação, quero dizer que, se a sequência de tokens for inválida, um erro será gerado no processo. É como se tivéssemos escrito o seguinte código:
int x 5; // --> Faltando o símbolo de atribuição '='.Vamos agora montar a AST utilizando a expressão abaixo:
function int soma(int a, int b) {
return a + b;
}
int x = soma(5, 3);Program
|
|-- Function Declaration
|-- Return Type: int
|-- Function Name: soma
|-- Parameters
|-- Parameter
|-- Type: int
|-- Name: a
|-- Parameter
|-- Type: int
|-- Name: b
|-- Function Body
|-- Return Statement
|-- Binary Expression
|-- Left: a
|-- Operator: +
|-- Right: b
|-- Variable Declaration
|-- Type: int
|-- Name: x
|-- Assignment
|-- Function Call
|-- Function Name: soma
|-- Arguments
|-- Argument: 5 (Literal)
|-- Argument: 3 (Literal)Lembre-se de que essa é uma representação textual da AST. Na prática, essa árvore seria estruturada em memória usando estruturas de dados apropriadas.
Esta fase sendo concluída, garante que a ordem de combinação dos tokens faça sentido, ou seja, a estrutura esta correta. Portando podemos continuar.
3. Análise Semântica: Esta fase verifica se o código fonte faz sentido em termos de sua operação, tipos e estruturas. Pois mesmo que sua sintaxe esteja correta, isso não significa que sua semântica faça sentido. Por exemplo a expressão 3 + “hello” .
Sintaticamente essa expressão pode estar correta, dependendo da linguagem de programação, mas semanticamente não faz sentido somar um valor inteiro com uma string, portanto existe um erro semântico.
Logo a etapa de análise semântica verifica o significado lógico e operacional do programa.
Suponhamos que temos o código:
int x = "hello world";Neste exemplo há um erro semântico, pois estamos tentando atribuir uma string a uma variável do tipo inteiro. Então por mais que sua estrutura esteja correta a operação lógica não faz sentido. Outro exemplo:
function int soma(int a, int b) {
return a + b;
}
int x = soma(5, "Hello");Estamos passando uma string como argumento para uma função que espera dois inteiros. Esta falha será capturada durante o processo de verificação semântica, e o compilador poderá gerar um erro como: Error: Invalid argument to expression “soma”.
Então após garantirmos que o programa faça sentido lógico e operacional, podemos continuar com o processo.
4. Geração de Código Intermediário: O objetivo principal do código intermediário é fornecer uma representação que pode ser facilmente otimizada e posteriormente traduzida para código de máquina.
Vamos imaginar que escrevemos a expressão:
int x = 5;
int y = 3;
int z = x + y;O compilador irá gerar um código intermediário para esta expressão, criando 3 endereços (variáveis) temporários para guardar os dados. Logo teriamos algo como:
t1 = 5
x = t1
t2 = 3
y = t2
t3 = x + y
z = t3Esta forma é usada para simplificar a tradução das instruções, pois ao invés de executar a operação x + y em uma única etapa, a instrução é desagregada em várias outras intermediárias.
Isso ajuda o compilador a trabalhar com as operações de forma mais individualizada e otimizar o processo. Pois divindo as expressões em variavéis temporárias, o compilador pode avaliar melhor cada cenário, trazendo mais otimização para o processo de compilação.
Por exemplo, se houvesse outra expressão no código que também usasse o valor de x + y , o compilador reutilizaria o valor de t3 , ao invés de recalcular a soma. E isto pode ajudar na alocação de registradores de memória e em outras otimizações para consumo de recursos da máquina.
Ou seja, caso tivessemos outra expressão que recebe o valor de x + y não seria criado um novo registrador para a expressão, o compilador removeria essas instruções comuns. Mas esta otimização só ocorre na próxima etapa.
Estas variáveis temporárias não necessariamente existirão no código final de máquina ou assembly. Elas são apenas formas de simplificar, desagregar e otimizar o código original.
5. Otimização do Código Intermediário: O código intermediário é geralmente representado em uma forma que é mais abstrata do que o código de máquina, mas menos abstrada do que uma linguagem fonte.
O processo de otimização do código intermediário serve para tornar mais eficiente o uso das expressões, como explicamos na etapa anterior.
Para melhorar sua interpretação sobre a responsabilidade desta etapa, vamos imaginar o seguinte caso com a expressão abaixo:
int a = 10;
int b = 20;
int c = 30;
int x = a * b + c;
int y = a * b - c;O código intermediário (sem otimização) deste bloco ficaria assim:
t1 = 10
a = t1
t2 = 20
b = t2
t3 = 30
c = t3
t4 = a * b
x = t4 + c
t5 = a * b
y = t5 - cAqui, a subexpressão a * b é calculada duas vezes e armazenada em duas variáveis temporárias diferentes (t4 e t5).
Com o processo de otimização do código teriamos algo como:
t1 = 10
a = t1
t2 = 20
b = t2
t3 = 30
c = t3
t4 = a * b
x = t4 + c
y = t4 - cApós a otimização, a multiplicação a * b é calculada apenas uma vez e o resultado é reutilizado. Essa otimização é benéfica pois pode reduzir o número de cálculos caros (como multiplicações) e, portanto, acelerar o código. Também pode ajudar a reduzir o tamanho do código gerado.
Claro, existem situações em que a reutilização não é possível devido a efeitos colaterais ou outras complicações, e a análise precisa para determinar subexpressões comuns verdadeiramente redundantes pode ser complexa dependendo da expressão. No entanto, a ideia básica é reduzir operações lógicas repetidas para melhorar a eficiência, evitando consumo de recursos desnecessários.
6. Geração de Código: Finalmente, após o código ter sido convertido e otimizado para o intermediário, agora o compilador trabalhará na geração do código que será interpretado pela máquina.
Esta etapa envolve a tradução do código intermediário otimizado para uma linguagem de máquina, como assembly ou código de bytes.
Seguindo o nosso exemplo anterior, a conversão do nosso código intermediário para um código fictício de máquina ficaria algo como:
LOADI R1, #10 -> Carrega o valor 10 no registrador R1 (representa t1 = 10)
LOAD R2, R1 -> Carrega o valor de R1 no registrador R2 (representa a = 10)
LOADI R3, #20 -> Carrega o valor 20 no registrador R3 (representa t2 = 20)
LOAD R4, R3 -> Carrega o valor de R3 no registrador R4 (representa b = 20)
LOADI R5, #30 -> Carrega o valor 30 no registrador R5 (representa t3 = 30)
LOAD R6, R5 -> Carrega o valor de R5 no registrador R6 (representa c = 30)
MUL R7, R2, R4 -> Multiplica os valores de R2 e R4 e armazena no registrador R7
(representa t4 = a * b)
ADD R8, R7, R6 -> Soma os valores de R7 e R6 e armazena no registrador R8
(representa x = t4 + c)
SUB R9, R7, R6 -> Subtrai os valores de R7 e R6 e armazena no registrador R9
(representa y = t4 - c)Repare que o código traduzido para máquina, seguindo uma arquitetura de CPU, envolve muitos detalhes adicionais, como gerenciamento de registradores, chamadas de função, acesso à memória e mais dependendo do código a ser convertido.
Pode haver também outras otimizações nesta etapa da geração do código, como utilizar instruções mais eficientes ou reordenar para melhorar a utilização da CPU.
O exemplo acima é apenas uma simplificação para mostrar o conceito de como é feito. Mas se pegarmos um código de uma aplicação real esta etapa é muito mais complexa, e pode levar em conta o tipo de arquitetura da CPU a ser utilizada.
7. Linking (Ligação): Por fim, mas não menos importante, iremos para última etapa do processo, a ligação. Esta etapa consiste na combinação de diferentes unidades de compilação e bibliotecas, para formar um único arquivo executável ou uma biblioteca.
Imagine que você está desenvolvendo um programa que tem duas partes:
- Uma função principal (
main) que está em um arquivo chamadomain.c:
#include "helper.h"
int main() {
int result = helperFunction(5, 3);
return 0;
}2. Uma função auxiliar (helperFunction) que está em um arquivo chamado helper.c. Além disso, essa função auxiliar usa uma biblioteca de matemática para algumas operações:
#include <math.h>
int helperFunction(int a, int b) {
return (int)pow(a, b);
}Primeiro ocorrerá a compilação dos dois arquivos separadamente, e como estamos usando linguagem C como exemplo, teremos dois arquivos objetos: gcc -c main.c -o main.o gcc -c helper.c -o helper.o
Na etapa de ligação, esses arquivos objeto são combinados para formar um único executável. Além disso, as funções da biblioteca de matemática que helperFunction usa (neste caso, pow) serão ligadas ao programa a partir de uma biblioteca de sistema.
gcc main.o helper.o -lm -o myProgramO flag -lm indica ao linker (sistema de ligação) que ele deve ligar a biblioteca de matemática ao programa. O resultado é um arquivo executável chamado myProgram.
Durante a ligação, o linker resolve todas as referências de funções e variáveis entre os arquivos. Por exemplo, a chamada para helperFunction em main.c é resolvida para a definição real em helper.c. Se helperFunction não fosse encontrado em nenhum arquivo objeto ou biblioteca fornecida, o linker geraria um erro.
Além de ligar várias unidades de compilação, o linker também pode realizar outras tarefas, como alocar espaço para variáveis globais, definir o ponto de entrada do programa (geralmente a função main para programas em C) e ligar funções de bibliotecas dinâmicas em tempo de execução.
Por fim, temos nosso processo de compilação completo, e o código já pode ser executado pela máquina. : )
Pontos finais…
Espero que tenha gostado do artigo e obtido uma compreensão mais clara sobre como o processo de compilação transforma o código fonte, escrito por nós desenvolvedores, em instruções compreensíveis para as máquinas.
O objetivo deste artigo foi apresentar as etapas mais comuns adotadas por vários compiladores disponíveis no mercado. No entanto, é importante salientar que esse processo pode variar significativamente, dependendo do tipo de compilador e da linguagem de programação em questão.
Por isso, existem inúmeras empresas com equipes de excelentes cientistas e profissionais dedicando-se diariamente para otimizar e tornar este processo cada vez mais eficiente.
