Um compilador é um programa de sistema que traduz um programa descrito em uma linguagem de alto nível para um programa equivalente em código de máquina para um processador. Em geral, um compilador não produz diretamente o código de máquina mas sim um programa em linguagem simbólica (assembly) semanticamente equivalente ao programa em linguagem de alto nível. O programa em linguagem simbólica é então traduzido para o programa em linguagem de máquina através de montadores.
Para desempenhar suas tarefas, um compilador deve executar dois tipos de atividade. A primeira atividade é a análise do código fonte, onde a estrutura e significado do programa de alto nível são reconhecidos. A segunda atividade é a síntese do programa equivalente em linguagem simbólica. Embora conceitualmente seja possível executar toda a análise e apenas então iniciar a síntese, em geral estas duas atividades ocorrem praticamente em paralelo.
Para apresentar um exemplo das atividades que um compilador deve
desempenhar, considere o seguinte trecho de um programa em C:
Para o compilador, este segmento nada mais é do que uma seqüência de caracteres em um arquivo texto. O primeiro passo da análise é reconhecer que agrupamentos de caracteres têm significado para o programa -- por exemplo, saber que int é uma palavra-chave da linguagem e que a e b serão elementos individuais neste programa. Posteriormente, o compilador deve reconhecer que a seqüência int a corresponde a uma declaração de uma variável inteira cujo identificador recebeu o nome a.
As regras de formação de elementos e frases válidas de uma linguagem são expressos na gramática da linguagem. O processo de reconhecer os comandos de uma gramática é conhecido como reconhecimento de sentenças. Gramáticas e reconhecimento de sentenças serão estudados na Seção 3.1.
A aplicação do conceito de reconhecimento de sentenças para agrupar as seqüências de caracteres em ``palavras'' é a análise léxica. Os elementos reconhecidos nessa primeira etapa da compilação são denominados itens léxicos ou tokens. Para o exemplo acima, a seguinte lista de tokens seria reconhecida pelo compilador:
| No. token | Valor token | No. token | Valor token |
|---|---|---|---|
| 1 | int | 14 | 20 |
| 2 | a | 15 | ; |
| 3 | , | 16 | valor |
| 4 | b | 17 | = |
| 5 | , | 18 | a |
| 6 | valor | 19 | * |
| 7 | ; | 20 | ( |
| 8 | a | 21 | b |
| 9 | = | 22 | + |
| 10 | 10 | 23 | 20 |
| 11 | ; | 24 | ) |
| 12 | b | 25 | ; |
| 13 | = |
Para desempenhar a análise léxica, o compilador deve ter conhecimento de quais são os tokens válidos da linguagem, assim como suas palavras chaves e regras para formação de identificadores. Por exemplo, a declaração
int 1var;deve resultar em erro nessa etapa da análise, pois 1var não é uma constante ou identificador válido. Se um programa contendo esta declaração fosse compilado usando o compilador gcc, por exemplo, a esta linha seria associado o erro ``nondigits in number and not hexadecimal'', mostrando que o compilador esperava que 1var fosse um número, já que inicia com um algarismo. A análise léxica será estudada na Seção 3.2.
O segundo passo da análise desempenhado pelo compilador é a análise sintática, onde a estrutura do programa é analisada a partir do agrupamento de tokens. Nesta etapa, que será estudada na Seção 3.4, o compilador deverá reconhecer que a seqüência de tokens obtida do segmento de código apresentado no início da seção corresponde a quatro comandos, sendo o primeiro deles um comando de declaração de variáveis e os três restantes de atribuição. Adicionalmente, deverá reconhecer que o último dos comandos de atribuição contém subexpressões que deverão ser avaliadas para completar a atribuição na execução do programa.
Para que este passo possa ser realizado pelo compilador, ele deve ter conhecimento de como são formados os comandos válidos da linguagem. Por exemplo, um comando de declaração de variáveis como
int int x;deve resultar em erro nesta etapa -- o compilador gcc indicaria o erro com uma mensagem ``two or more data types in declaration of `x' ''.
Após realizada a análise, na fase de síntese o compilador deverá gerar o código em linguagem simbólica equivalente ao código analisado. Por exemplo, para um compilador C gerando código para a linguagem simbólica do processador 68000 os seguintes mapeamentos poderiam estar preparados:
| C | Assembly 68K | ||
|---|---|---|---|
| int V | V | DS.W | 1 |
| L + R | MOVE.W | L,D1 | |
| ADD.W | R,D1 | ||
| MOVE.W | D1,VTMP | ||
| L * R | MOVE.W | L,D1 | |
| MULS.W | R,D1 | ||
| MOVE.W | D1,VTMP | ||
| L = R | MOVE.W | R,D1 | |
| MOVE.W | D1,L | ||
Na verdade, compiladores não trabalham diretamente com o código de um processador específico. Normalmente o código gerado nessa fase é expresso em alguma linguagem intermediária, próxima do assembly mas independente de processador, que depois pode ser mapeada para diversos processadores distintos.
Com base nesse mapeamento, o compilador poderia gerar o seguinte trecho
de código em linguagem simbólica para o exemplo apresentado:
Este é um código correto sob o ponto de vista de que as tarefas executadas correspondem semanticamente ao programa C original. Entretanto, uma simples observação demonstra que o código gerado poderia ser muito mais sucinto através da eliminação de alguns comandos desnecessários
A melhoria do código gerado pelo compilador é a fase final da
compilação, que é a otimização de código. No exemplo acima,
por simples inspeção verifica-se que há algumas linhas de código
redundantes, como as linhas 8 e 9 e as linhas 14 e 15. O mesmo código
poderia ser reduzido para o seguinte programa equivalente:
Em programas mais complexos, há muitas outras situações onde o código gerado automaticamente pelo compilador pode ser melhorado. O objetivo da fase de otimização é detectar tais situações automaticamente e aplicar estratégias heurísticas para permitir a melhoria desse código. A geração e otimização de código são objetos da Seção 3.6.