Prévia do material em texto
O Compilador
O processo de tradução para criação de um código em linguagem de máquina, apresentando os passos da
compilação, a estrutura funcional de um compilador e seus componentes.
Prof. Sidney Nicolau Venturi Filho
1. Itens iniciais
Propósito
Apresentar as diferenças entre os diversos tipos de tradutores e compreender o funcionamento básico de um
compilador.
Objetivos
Descrever os processos de tradução de um programa escrito em uma linguagem de programação para
linguagem de máquina.
Identificar os passos do processo de compilação e de seus produtos.
Analisar a estrutura funcional do compilador e de seus componentes.
Introdução
Você já parou para pensar como um programa escrito em uma linguagem de programação qualquer é
convertido para um conjunto de comandos que podem ser executados por um computador?
Uma CPU somente consegue manipular 0 e 1, ou seja bits, de forma que, para um programa ser executado, ele
deve passar por um processo de transformação de suas instruções, escritas em alguma linguagem de alto
nível, para um conjunto de instruções em linguagem de máquina, que é aquela que efetivamente o
processador consegue executar. Este processo de transformações é, de uma forma geral, denominado
tradução, podendo ser realizado de várias formas.
Neste tema, iremos apresentar as diversas formas de tradução e nos deteremos mais especificamente na
compilação.
•
•
•
1. Processos de tradução de um programa
Como os computadores executam suas instruções
Considere a arquitetura simplificada de um computador apresentada na imagem a seguir. Nela, apresentamos
o processador com três registradores (R0, R1 e R2), os barramentos de dados e endereços e a memória que
possui 8 células, numeradas de 0 a 7. Vários componentes como registrador de instruções, contador de
instruções unidade aritmética e lógica e outros componentes foram intencionalmente omitidos para focarmos
apenas nos que são interessantes em nossa explicação.
Arquitetura simplificada.
Imagine agora que você deseja executar a seguinte operação:
Onde A, B e C são variáveis mapeadas respectivamente para as posições 5, 6 e 7 da memória.
Considere ainda que B e C possuem os valores 10 e 8 e já estão armazenados na memória, conforme será
apresentado na imagem a seguir. Para fins meramente didáticos, os valores são apresentados em decimal e
não em binário, como efetivamente, ficam na memória.
B e C na memória.
Um processador executa comando em linguagem de máquina cujos comandos podem ser, de forma
simplificada, divididos em código de operação e um ou mais endereços, constituindo, cada um deles, um
conjunto de bits.
A := B + C
Formato de instrução.
Para continuarmos nosso exemplo, vamos considerar que o processador possui as seguintes instruções:
Nr Instrução Código de
operação
1 Ler um dado da memória para um registrador. 00
2
Somar um dado de um registrador com o R0 armazenando o
resultado em R0.
01
3 Gravar o dado de um registrador em uma posição de memória. 10
Sidney Nicolau Venturi Filho.
A partir deste conjunto de instruções, o programa seria então traduzido como:
assembly
LER B para R0
LER C para R1
SOMAR R0 a R1
GRAVAR R0 em A
Em linguagem de máquina, iria corresponder:
Instrução Linguagem
Máquina Observação
LER B para
R0
00 110 000
Onde 00 é o código da operação, 110 a posição de
memória 6, que corresponde à B e 000 o registrador R0.
LER C para
R1
00 111 001
Onde 00 é o código da operação, 111 a posição de
memória 7, que corresponde à C e 001 o registrador R1.
SOMAR R0 a
R1
01 001
Onde 01 é o código da operação e 001 corresponde ao
registrador 1.
GRAVAR R0
em A
10 000 101
Onde 10 é o código da operação, 000 o registrador R0 e
101 a posição de memória 5, que corresponde à A.
Sidney Nicolau Venturi Filho.
Após execução, as posições memória e os registradores estariam com os valores mostrados na imagem a
seguir.
Situação após a execução dos comandos.
Montadores e linguagem de montagem
Conforme observamos na seção anterior, uma
simples operação de alto nível gera um
conjunto de instruções em linguagem de
máquina.
Se voltarmos no tempo para a época dos
primeiros computadores, poderíamos observar
que eles programavam diretamente em
linguagem de máquina, ou seja, o programa
nada mais era que uma sequência enorme de 0
e 1. Isto, obviamente, dificultava muito o
trabalho, pois a possibilidade de escrever um
comando errado e a dificuldade de fazer a correção eram enormes.
Surgiu então, a primeira ideia de facilitar o trabalho, criar uma linguagem de programação de baixo nível, que
se aproxime da lógica da máquina e que mantenha uma relação de 1 para 1, ou seja, um comando na
linguagem irá corresponder a um único comando em linguagem de máquina.
A partir desta ideia, foram criados mnemónicos, ou seja, conjuntos de letras para representar as instruções.
Voltando para a linguagem de nosso processador hipotético, poderíamos associar os mnemónicos às
instruções, conforme a tabela abaixo:
Nr Instrução Mnemónico
1 Ler um dado da memória para um registrador. LOAD
2
Somar um dado de um registrador com o R0 armazenando o resultado
em R0.
ADD
3 Gravar o dado de um registrador em uma posição de memória.
MOV
Sidney Nicolau Venturi Filho.
Além disso, o endereçamento passou a ser feito por nomes lógicos e não mais pelo endereço do registrador
ou da memória. Dessa forma, o programa anterior ficaria assim:
Instrução Linguagem de máquina Linguagem de baixo nível
LER B para R0 00 110 000 LOAD B R0
LER C para R1 00 111 001 LOAD C R1
SOMAR R0 a R1 01 001 ADD R1
GRAVAR R0 em A 10 000 101 MOV RO A
Sidney Nicolau Venturi Filho.
Este tipo de linguagem é denominado linguagem de montagem, ou assembly, e é intimamente associado à
arquitetura de um determinado processador. Muito bem, dado o programa:
assembly
LOAD B R0
LOAD C R1
ADD R1
MOV RO A
Após analisar o código acima, é possível afirmar que ele irá executar diretamente? Nada disso! O processador
continua apenas entendendo a linguagem de máquina e precisamos então fazer a tradução do assembly para
a linguagem de máquina. É aqui que surge o programa tradutor, chamado montador.
Montador, também denominado assembler, é um programa que traduz para linguagem de máquina a
linguagem de baixo nível. O processo de montagem está ilustrado na imagem.
Processo de montagem.
Essa tradução é relativamente simples, já que a linguagem mantém uma relação de 1 para 1 com as instruções
do processador e, durante este processo, o montador fará também uma verificação da correção da escrita do
código, observando se não existem erros de digitação de comando etc.
Além da tradução dos mnemônicos, o montador precisa ainda lidar com os nomes de variáveis que precisam
ser mapeadas para posições de memória. Na realidade, o processo de montagem acontece, normalmente, em
dois passos:
1. Definição de símbolos armazenados em uma tabela.
2. Tradução do programa utilizando a tabela do passo 1.
Confira mais detalhes sobre cada passo a seguir!
Passo 1
No passo 1, o montador faz uma primeira passagem pelo código e levanta os símbolos existentes a
partir da análise das operações existentes no programa e cria uma tabela de símbolos cujas entradas
possuem, resumidamente, dois campos:
• Símbolo – contém o próprio identificador do símbolo, por exemplo A, B ou C do nosso exemplo.
• Posicionamento – localização do símbolo em relação ao ponto de início de carga do programa na
memória.
Passo 2
No passo dois, utilizando as informações geradas, é realizada efetivamente a tradução, onde ocorrem
as seguintes operações:
• São gerados os códigos de máquina correspondentes às instruções.
• São gerados relatórios de erros, se houver.
• São produzidas as informações necessárias ao processo de ligação.
Ligação e carga
A tradução foi realizada, agora vai direto para a execução? Não, ainda temos dois passos: a ligação e a carga.
Um programa, normalmente, é composto de vários procedimentos, que nada maissão que objetos
independentes que necessitam ser associados como um único programa.
A imagem a seguir mostra o processo completo de tradução e carga em uma linguagem de montagem.
Processo de montagem e carga.
Parte 1
Quem faz esta ligação é o ligador (linker),
que une os diversos procedimentos em um
único módulo de carga.
Parte 2
O módulo de carga é o programa
executável que será carregado na
memória pelo carregador, quando,
finalmente, o programa será executado.
Linguagem de alto nível
Conforme vimos, o assembly é denominado como uma linguagem de baixo nível, pois sua lógica de
programação se aproxima da lógica de execução de programas da máquina. Este tipo de linguagem apesar de
ser um avanço em relação à programação diretamente em linguagem de máquina, apresenta alguns
inconvenientes para o desenvolvimento de sistemas complexos.
Se vocês se lembram, para realizar aquela simples operação do exemplo A := B + C foram necessários quatro
comandos de assembly:
assembly
LOAD B R0
LOAD C R1
ADD R1
MOV RO A
Porém, pela lógica humana, seria apenas um comando. Dessa forma, ao longo dos anos, os projetistas de
linguagem de programação (LP) desenvolveram uma solução que denominamos linguagem de alto nível,
visando facilitar a implementação de sistemas, já que estas LP’s possuem uma lógica de programação similar a
nossa e não a da máquina.
Imagine um programa que você desejasse ler dois valores digitados por um usuário, somá-los e exibir o
resultado na tela. Em termos de algoritmos, este programa seria:
Variáveis
A, B, C inteiro
Início
Exiba (“B:”);
Receba B;
Exiba (“C:”);
Receba C;
A := B + C
Exiba (“B + C = “, A)
Fim
Dá para imaginar que este pequeno código para ser escrito em linguagem de baixo nível implicaria na
manipulação de buffer de entrada e saída, leituras e escrita na memória etc. Já em qualquer linguagem de alto
nível, como C, Pascal, Java, seria praticamente igual ao algoritmo. Veja a listagem abaixo referente ao mesmo
programa escrito em C.
c
#include
int main(void)
{
int a, b, c;
printf("b: ");
scanf("%d", &b);
printf("c: ");
scanf("%d", &c);
a = b + c;
printf("b + c = %d\n", a);
return 0;
}
Listagem 1 – Programa de soma em C.
Neste código, podemos notar a presença de funções de biblioteca (printf e scanf) e a inclusão da biblioteca
que os contêm (stdio.h). Lembram da ligação? É necessário por causa do uso de bibliotecas, pois o código
desta tem que ser anexado ao código do programa.
A tradução deste tipo de programa é bem mais complexa que a realizada pelo montador, pois um único
comando pode implicar e, quase com certeza, implica na geração de várias linhas de comando em linguagem
de máquina.
Existem basicamente três tipos de tradutores para linguagens de alto nível:
Interpretadores
Compiladores
Híbridos
Cada um possui vantagens e desvantagens. Vamos a eles.
Interpretadores
•
•
•
Interpretadores são tradutores que fazem a conversão do programa fonte comando a comando. Eles não
geram o código objeto, de certa forma, é como se o código fonte fosse o objeto, já que será executado
diretamente.
No processo de interpretação, o código fonte é traduzido linha a linha, fazendo as análises sintática e
semântica e, se não houver erro, o comando é executado. Após a execução bem sucedida de um comando, é
buscado o próximo.
Processo de interpretação.
Como o programa vai sendo executado à medida em que vai sendo traduzido, sem geração de código objeto,
a cada execução o programa necessita ser novamente interpretado.
O interpretador pode ser visto como uma virtualização da máquina hospedeira que consegue lidar diretamente
com a linguagem de alto nível, ao contrário do hardware real, que lida com linguagem de máquina.
A interpretação possui as seguintes vantagens e desvantagens:
Vantagens
Como cada instrução é traduzida individualmente, se ocorrer um erro, a correção é
fácil, pois é rápido identificar onde ele ocorreu.
O código não precisa ser compilado antes da execução.
Qualquer alteração no programa fonte será interpretada normalmente, não exigindo
qualquer tratamento.
Desvantagens
A execução do programa é bem mais lenta, pois é necessário primeiro fazer a
tradução.
•
•
•
•
O código fonte tem que estar disponível, pois é a partir deste que a interpretação e
posterior execução é realizada.
Se ocorrer um erro de tradução, a execução do programa é interrompida.
Sidney Nicolau Venturi Filho.
Além de linguagem de programação, como LISP e BASIC, que são interpretadas, os comandos de shell script
de sistemas operacionais, bem como várias linguagens da web, como PHP, utilizam este tipo de tradução.
Devido às características apresentadas, a execução de um programa interpretado é concomitante a sua
tradução. Isto é, elas ocorrem no mesmo movimento, conforme ilustrado na imagem, não havendo um
movimento de tradução inicial, como vimos no montador e, posteriormente, o movimento de execução do
programa.
Execução de um programa por um interpretador.
Compiladores
Um compilador é um programa tradutor que faz a transformação do programa fonte em um programa
executável que pode ser carregado na memória e executado.
Geração de executável com a compilação.
Como o código executável é totalmente dependente da arquitetura do sistema, onde será executado, implica
que o programa compilado para um determinado ambiente computacional não irá executar em outro. Dessa
forma, o programa deve ser recompilado se desejarmos portá-lo para um computador com arquitetura
diferente.
•
•
Na compilação, temos então dois movimentos distintos:
1. A geração do programa executável pelo processo de compilação.
2. A carga e a execução do programa que pode ser realizado muito tempo depois da compilação.
A compilação possui as seguintes vantagens e desvantagens:
Vantagens
A execução do código compilado é mais rápida que o do interpretado.
Somente o código executável é necessário para rodar o programa, o que mantém a
confidencialidade do código fonte original.
O código pode ser otimizado pelo compilador.
O executável somente é gerado se não houver nenhum erro no código fonte, dessa
forma, o programa somente será abortado em tempo de execução por erros de
execução, mas nunca por erros de tradução.
Desvantagens
Para ser executado, o código fonte necessita passar por todo o processo de
compilação, o que pode levar um tempo considerável.
A depuração do código e correção de erros é mais complexa, já que é gerado um
relatório final com todos os erros da compilação, o que torna a localização do erro
mais difícil e a verificação de sua correção mais demorada, pois o programa deverá
ser novamente todo compilado.
Qualquer alteração na lógica do programa exigirá uma nova compilação.
Sidney Nicolau Venturi Filho.
Exemplos de linguagem que usam compilação são: C, C++, Pascal, ADA, Cobol.
Tradutores híbridos
•
•
•
•
•
•
•
Conforme vimos nas seções anteriores, compilação e interpretação possuem abordagens bem distintas em
relação à forma de gerar os comandos de máquina:
Compilação
Na compilação, é gerado um executável para
uma determinada arquitetura computacional
que, se tiver que ser portado para outra deverá
passar por um novo processo de tradução.
Interpretação
Na interpretação, o código do programa a ser
executado é sempre o mesmo, pois está em
linguagem de alto nível, o que muda de uma
arquitetura computacional para outra é o
interpretador. Ou seja, para executar o
programa em uma arquitetura A, utilizamos um
interpretador, para executar em outra
arquitetura B, outro tradutor adequado terá que
ser empregado
Cada uma dessas abordagens possui vantagens e desvantagens, o que levou alguns projetistas de linguagens
de programação a utilizar uma abordagem hibrida, juntando uma compilação inicial seguida por um processo
de interpretação.
Linguagens como Java ou Python são exemplos desta abordagem. Vejamoscom mais detalhes a solução
Java.
Java
Os ambientes de desenvolvimento Java incluem um compilador que não traduz o código fonte diretamente
para a linguagem de máquina, na realidade, a tradução é realizada para um código intermediário constituído
de bytecodes, que são a Linguagem da Máquina Virtual Java (JVM).
Em uma implementação simples, a JVM funciona com um interpretador a partir do código intermediário
(bytecode), realizando a sua execução.
Execução de programa com a JVM com interpretador.
Com a evolução da tecnologia, as JVM passaram a incluir um compilador interno que traduz o bytecode para a
linguagem nativa do computador onde ela está instalada. Isso foi chamado de compilação Just in Time, ou JIT
e visa melhorar o desempenho do programa em tempo de execução.
Embora, atualmente, o código Java utilize JIT para obter uma maior velocidade, os applets Java são
descarregados do servidor na forma de bytecode.
Execução de programa com a JVM com JIT.
Cabe observar que, mesmo os interpretadores reais, utilizam algum tipo de tradução intermediária para
facilitar a execução, evitando a perda de tempo de interpretar instrução a instrução no momento de cada
tradução.
Também é muito comum que linguagens compiladas para código nativo de uma máquina tenham um runtime
acoplado (sistema de tempo de execução) que se destine ao suporte durante a execução, o que, de certa
forma, insere algum nível de interpretação.
Portanto, é muito difícil em casos reais fazer uma total separação de interpretação e compilação, na realidade,
as duas utilizam técnicas parecidas para a tradução e muitas vezes, conforme vimos, atuam efetivamente
juntas.
runtime
Refere-se ao ambiente de execução que um determinado programa irá executar e não deve ser
confundido com o ciclo de vida de execução de um programa, quando o ambiente de execução estará
em operação.
A evolução do processo de tradução
Neste vídeo, conheça mais sobre a evolução do processo de tradução.
Conteúdo interativo
Acesse a versão digital para assistir ao vídeo.
Verificando o aprendizado
Questão 1
Os computadores compreendem apenas bits, portanto, é necessário que exista um tradutor que transforme o
código fonte criado pelo programador para uma sequência que possa ser entendida pelos processadores.
Para o Java, é utilizado um método de tradução híbrido envolvendo, inicialmente, uma compilação e, depois,
uma interpretação. Em Java, o produto da fase de compilação denomina-se:
A
Código fonte.
B
Código objeto.
C
Executável.
D
ByteCode.
A alternativa D está correta.
Ao contrário da compilação pura, em que, a partir do código fonte, é gerado um código objeto a ser
submetido ao montador para a tradução da linguagem de máquina em JAVA, a fase de compilação gera um
formato intermediário a ser passado ao JVM, que é o interpretador para execução. Esse formato
intermediário denomina-se Bytecode.
Questão 2
Os diversos processos de tradução possuem características próprias que irão definir em que situação eles são
melhores aplicados, de acordo com as vantagens e desvantagens de cada método. A interpretação possui
várias desvantagens em relação à compilação, uma delas é:
A
A identificação e correção de erros é dificultada.
B
Alterações no programa fonte exigem uma nova tradução.
C
A execução é mais lenta que o programa compilado.
D
O Programa precisa ser instalado na máquina para permitir sua execução.
A alternativa C está correta.
De fato, como a tradução é realizada à medida que o programa vai sendo executado, na realidade, o tempo
de processamento é maior que o do programa compilado.
2. Passos do processo de compilação e de seus produtos
Etapas da compilação
Conforme vimos, um compilador faz a tradução do código fonte para um código executável. Este processo, na
realidade, pode ser dividido em três fases: a primeira realizada pelo compilador propriamente dito, a segunda
por um montador e a terceira por um ligador, sendo que, na maioria das vezes, estes dois últimos são parte
integrante do próprio software de compilação, porém, executando atividades específicas.
Analisando a imagem a seguir podemos ver que o compilador gera um arquivo em linguagem de baixo nível
(Código Intermediário) correspondendo a fase 1. A seguir este código será transformado em Código Objeto
pelo montador, correspondendo a fase 2 e, na sequência, o ligador faz a associação dos códigos de biblioteca
gerando o executável em linguagem de máquina perfazendo a fase 3. A partir da criação do executável, o
usuário pode comandar a sua execução quando desejar, momento em que o programa será carregado na
memória pelo carregador.
Geração de executável pelo compilador de montador.
Etapas da compilação
A atividade do compilador, propriamente dita, pode ser dividida em duas etapas bem distintas:
Análise ou Front End
A partir da gramática de uma determinada
linguagem de programação, visa verificar se o
código fonte foi escrito conforme as regras de
sintaxe da linguagem e se está livre de erros,
gerando como produto uma representação
intermediária.
Síntese ou Back End
Utilizando otimizações e gerenciando a tabela
de símbolos, visa criar o melhor código
intermediário a ser submetido ao montador.
Agora, observe a imagem a seguir.
Etapas da compilação.
Análise ou Front End
A etapa de análise é dividida em três passos:
Análise Léxica
Converte o texto do programa fonte em um fluxo de palavras (tokens).
Análise Sintática
Determina se a sequência de tokens gerados no passo anterior corresponde a uma sentença na
linguagem-fonte gerando uma árvore sintática.
Análise Semântica
Neste passo, é analisado o contexto do programa, incluindo a verificação dos tipos das variáveis
utilizadas no programa fonte e a depuração de outros erros semânticos, sendo então gerada a
representação intermediária a ser utilizada na fase de Back End.
A imagem mostra os passos desta etapa:
Passos da análise.
Na imagem anterior, vemos que o resultado é a Representação Intermediária, vejamos a que isso se refere.
Representação Intermediária (IR)
O último passo da etapa de análise implica na geração de algum tipo de representação intermediária do
código fonte.
Atenção
Vários formatos de IR podem ser utilizados pelos compiladores, dependendo da linguagem de
programação utilizada no programa fonte, da linguagem alvo para a qual se deseja traduzi-lo e das
transformações que o compilador utiliza.
Algumas representações utilizam um grafo, outras se parecem com um programa escrito em assembly
sequencial. Veja o código abaixo:
assembly
t0 ← a x 2
t1 ← t0 x b;
t2 ← t1 x c
t3 ← t2 x d
a ← t3
Ele seria uma possível representação intermediária para a seguinte expressão em linguagem de alto nível:
O nosso exemplo foi muito simples, pois a sua representação foi basicamente separar as diversas operações
da expressão em expressões mais simples que geram resultados intermediários. Porém, linguagens reais
possuem construções muito mais complexas (if, loop, etc) e o compilador necessita ter uma estratégia para
gerar o IR para cada uma delas.
Linguagens e gramáticas
Na etapa de análise, as verificações, particularmente, a léxica e a sintática, são dependentes da gramática
específica da linguagem de programação que está sendo traduzida.
Existe toda uma teoria por detrás do desenvolvimento de linguagens de programação baseado nos conceitos
de linguagens formais. Alguns conceitos fundamentais que temos que ter são:
Linguagem
O conjunto de símbolos e de regras que determinam como se pode combinar esses símbolos em
sentenças corretas do ponto de vista sintático.
Símbolo
É uma entidade abstrata, por exemplo, as letras e os dígitos. Do ponto de vista léxico, eles são
ordenáveis, podendo ser comparáveis quanto à igualdade ou à precedência. São utilizados,
principalmente, como elementos atômicos em linguagens.
Sentença
Também denominada palavra, constitui de uma sequência finita de símbolos.
Alfabeto
É um conjunto finito de símbolos. Por exemplo,o alfabeto das vogais {a, e, i, o, u}.
A partir desses conceitos básicos, podemos definir que uma linguagem L é um conjunto de sentenças
formadas a partir dos símbolos de um determinado alfabeto V. Uma linguagem pode ser:
Finita
Quando é composta por um conjunto finito de
sentenças.
Infinita
Quando é composta por um conjunto infinito de
sentenças.
Uma linguagem pode ser definida por uma descrição algébrica e, para verificar se uma sentença pertence a
uma linguagem, podemos utilizar os reconhecedores que podem ser implementados em autômatos finitos,
autômatos de pilha ou máquinas de Turing.
Já para gerar, sistematicamente sentenças de uma linguagem, usamos os geradores que tem como exemplo
as gramáticas.
As linguagens segundo Chomsky podem ser classificadas como:
Linguagem Regular (ou tipo 3)
Linguagem Livre de Contexto (ou tipo 2)
Linguagem Sensível ao Contexto (ou tipo 1)
•
•
•
Linguagem Irrestrita (ou tipo 0)
Atenção
Sendo que uma linguagem do tipo 3 é também do tipo 2, mas nem toda linguagem do tipo 2 é do tipo 3.
Isso acontece de forma recursiva, ou seja, uma do tipo 2 é do tipo 1, mas a recíproca não é verdadeira, e
assim sucessivamente.
As linguagens do tipo 3 geram as chamadas expressões regulares que podem ser processadas por autômatos
finitos e permitem a criação de analisadores léxicos.
Já as de tipo 2 são adequadas à criação de linguagens de programação, isso acontece devido ao fato das
linguagens livre de contexto e sua gramática (Gramática Livre de Contexto - GLC) permitirem a especificação
adequada das estruturas sintáticas, como: construções aninhadas, parêntesis balanceado etc. Elas são
processadas por autômatos de pilha e permitem a eficiente criação de analisadores sintáticos.
Você pode estar se perguntando, o que é uma gramática?
Uma gramática define regras para a combinação de símbolos de um alfabeto, de forma que apenas
determinadas combinações de símbolos formem uma sentença válida.
Uma gramática G é definida como uma quádrupla G = (N, T, P, S), onde:
N é um conjunto de símbolos não-terminais, usados na descrição da linguagem.
T é um conjunto de símbolos terminais, constituindo os símbolos da linguagem propriamente
ditos.
P define as regras de produção (ou gramaticais) para a combinação dos símbolos da
linguagem em pares (a, b).
S é o símbolo inicial da gramática pertencente à N.
Sidney Nicolau Venturi Filho.
Vejamos um exemplo de uma gramática que especifica a linguagem dos números inteiros sem sinal:
Onde:
•
G = (N, T, P, S)
Síntese ou Back End
A etapa de síntese é dividida em 3 passos:
Geração de código intermediário
A partir da representação intermediária gerada na etapa de análise gera uma sequência de código
que funciona em uma máquina abstrata com duas propriedades importantes:
• Deve ser fácil de ser produzido.
• Deve ser fácil de traduzir para a linguagem alvo no código de montagem.
Otimização de código
Realiza a otimização do código buscando uma melhor utilização da memória e diminuição do tempo
de execução.
Geração de código
É o último passo que finalmente gera o código de montagem.
A imagem mostra os passos da síntese:
Passos da síntese.
Dessa forma, o processo de compilação pode ser resumido, como apresentado na imagem.
Processo completo de compilação.
Observando a imagem anterior, podemos notar que apareceram dois novos elementos: tratamento de erros e
tabelas. Vamos ver a que eles se referem.
Tratamento de erros
Em todos os passos da etapa de análise (Léxica, Sintática e Semântica), deve ser possível detectar erros no
programa fonte que está sendo compilado.
Logicamente, esses erros devem ser tratados, porém, ao contrário da interpretação, o erro ao ser
detectado não pode interromper o processo de compilação. Portanto, a etapa de análise deve
continuar até o fim e, então, gerar um relatório com todos os erros detectados. Isto é realizado a
partir de mecanismos de recuperação de erros, encarregados de evitar que um erro inicial se
propague para outros pontos do programa fonte.
A recuperação é conseguida ao se ressincronizar o passo da análise que está sendo processada com o ponto
do texto do programa fonte onde foi detectado o erro, ou seja, é fundamental que o compilador prossiga com
a tradução após detectar algum erro, evitando sua propagação e realizando a análise de todo código fonte.
Tabelas
As tabelas são estruturas de armazenamento e as rotinas que as manipulam. Elas são utilizadas em todos os
passos da compilação.
Temos tabelas constantes para cada linguagem de programação diferente, como: a tabela de palavras
reservadas, de delimitadores, de operadores etc.
Atenção
No entanto, existe uma tabela que é gerada durante o processo de tradução, que possui importância
fundamental: a tabela de símbolos.
Esta tabela armazena os dados de:
Declarações de variáveis
•
Declarações dos procedimentos ou sub-rotinas
Parâmetros de sub-rotinas
Entre outros
Quando é percebida a ocorrência de um identificador no programa fonte, a tabela é consultada à procura do
identificador.
Se ele existir, as informações da tabela são comparadas com as obtidas a partir da fonte, se algum dado novo
for percebido ou o identificador não existir, ele será inserido na tabela.
As informações a serem armazenadas dependem da linguagem fonte, da linguagem alvo da tradução e do
projeto do compilador. Entretanto, comumente, são registrados os seguintes atributos:
Para variáveis
Classe (var), tipo, endereço no texto, precisão,
tamanho.
Parâmetros formais
Classe (par), tipo, mecanismo de passagem.
Procedimentos/sub-rotinas
Classe (proc), número de parâmetros.
A estrutura da tabela de símbolos deve permitir uma manipulação rápida e eficiente, tanto para a
inserção quanto para a consulta e deve ainda ser o mais compacta possível.
Exemplo do funcionamento de um compilador
Para exemplificar o processo de compilação, vamos considerar que desejamos traduzir a seguinte expressão
que calcula o perímetro de um trapézio.
Inicialmente, devemos converter os elementos da expressão em variáveis associadas.
Utilizaremos então a seguinte associação:
ELEMENTO VARIÁVEL
Perímetro A
•
•
•
ELEMENTO VARIÁVEL
Lado1 B
Lado2 C
Lado3 D
Lado4 E
Sidney Nicolau Venturi Filho.
Nossa expressão ficaria então:
O primeiro passo do processo será a Análise Léxica que, a partir da tabela de símbolos da linguagem,
identificará os tokens que, neste caso, seriam os da imagem.
Tokens gerados.
Atenção
Espaços em branco, marcadores de final de linha e demais elementos que não interessam para tradução,
como comentários, são ignorados.
O segundo passo é a Análise Sintática, onde será verificado se as variáveis do programa (A, B, C, D e E) são
reconhecidas. Para isso, será consultada a tabela interna de símbolos ou as declarações explícitas do código.
A seguir, serão verificas as expressões “←” e “+” e o seu significado no contexto da linguagem de
programação do código fonte. A saída seria uma árvore de execução, como a da imagem a seguir.
Arvore sintática.
O terceiro passo, o analisador semântico irá transformar a árvore sintática em algum tipo de representação
intermediária que a represente de uma forma que possa ser entendida por uma máquina. Em nosso exemplo,
esta representação poderia ser a exibida na imagem anterior, onde T1, T2 e T3 representam resultados
intermediários da imagem a seguir.
Representação intermediária.
Terminada a etapa de análise, o compilador começa a síntese com o passo onde será produzido o código de
montagem. Inicialmente, ele irá procurar criar um código intermediário que possa ser executado por uma
máquina abstrata genérica.
Por exemplo, a representação intermediaria da Figura 19 poderia gerar o código intermediário da imagem.
Código intermediário.
A seguir, ele tentará otimizar o código, por exemplo, poderia reduzir um passo armazenando diretamente em A
o resultado da soma de B com T2, como pode ser visto na imagem.
Código otimizado.Finalmente, seria gerado o código em linguagem de montagem, considerando os comandos vistos no módulo
1, o código poderia ser o presente na imagem:
Código de montagem.
A imagem mostra todos os passos da compilação e seus produtos:
Passos da compilação e seus produtos.
As etapas do processo de compilação
Neste vídeo, conheça mais sobre as etapas do processo de compilação.
Conteúdo interativo
Acesse a versão digital para assistir ao vídeo.
Verificando o aprendizado
Questão 1
O processo de tradução envolve diversas etapas, como as Análises Léxica, Sintática e Semântica. Cada uma
destas etapas, normalmente, produz uma representação, que será a entrada para a próxima etapa.
Considerando que você deseja realizar a operação A := B + C observe agora a seguinte representação:
Ela corresponde ao produto do passo:
A
Análise Léxica.
B
Análise Sintática.
C
Análise Semântica.
D
Geração de Código.
A alternativa B está correta.
Os produtos de cada umas das fases listadas é:
• Análise Léxica - lista de tokens
• Análise Sintática - árvore sintática
• Análise Semântica – representação intermediária
• Geração de Código – código de montagem
No caso, a representação apresentada corresponde a uma árvore sintática, portanto, é o produto da
Análise Sintática.
Questão 2
A compilação pode ser dividida em duas etapas distintas: Front End ou Análise e Back End ou Síntese. Cada
uma destas etapas é dividida em passos que são necessários para a geração do código final. Um dos passos
da etapa de Back End é:
A
Análise Semântica.
B
Otimização.
C
Análise Sintática.
D
Montagem.
A alternativa B está correta.
O processo de tradução realizado pelo compilador envolve duas etapas: Análise também chamada de Front
End e Síntese denominada também Back End. A etapa de Síntese possui 3 passos:
• Geração de Código Intermediário
• Otimização
• Geração de Código ou Geração de Código de Montagem
Portanto, a resposta é Otimização.
Convém observar ainda que a montagem é realizada pelo montador a partir do Código de Montagem
gerado pelo compilador.
3. Estrutura funcional do compilador e de seus componentes
Linguagem de Programação de Exemplo (LPE) - Definição
Léxica
Conforme vimos no módulo anterior, os passos do compilador são executados por componentes específicos:
Passo 1
Analisador Léxico
Passo 2
Analisador Sintático
Passo 3
Analisador Semântico
Passo 4
Gerador de Código Intermediário
Passo 5
Otimizador
Passo 6
Gerador de Código de Montagem
Vamos a partir de agora estudar com mais detalhes cada um deles, mas antes de passarmos a este estudo,
vamos definir uma Linguagem de Programação de Exemplo (LPE) a ser utilizada para o entendimento do
funcionamento dos diversos componentes.
Linguagem de Programação de Exemplo (LPE) - Definição Léxica
A nossa LPE possui sua definição léxica estabelecida na notação BNF (Backus Naur Form). Esta notação utiliza
regras de derivação na forma:
Onde é um não terminal e a expressão é um conjunto de símbolos. Por exemplo, considere essa
BNF possível para um aluno:
Exemplo
::= ::= ::=
::=
"-"
Isto se traduz para o português como:
Um cliente consiste no nome, seguido pelo endereço.
O nome consiste no primeiro nome seguido pelo último nome, seguido pelo fim de linha
(FDL).
Um endereço consiste no nome da rua, seguido pelo número do imóvel, seguido do
especificador de apartamento opcional, seguido por um fim-da-linha.
A parte do CEP consiste no CEP, seguido pelo nome da cidade, por um hífen, pelo código do
Estado, e por um fim-da-linha.
Sidney Nicolau Venturi Filho.
Em nossa LPE a sua especificação seria então:
Identificadores
Devem começar com uma letra e depois podem ser seguidos por letras ou dígitos
Identificador ::= {L} + {L}|{D}
L ::= A..Z a..z
D ::= 0..9
Observe na definição o seguinte:
• { } - explicita que o termo envolvido pode ser repetido n vezes (se o termo estiver entre [ ] ele é
opcional).
• + - após um termo envolvido por {} indica que deve existir pelo menos uma ocorrência do termo.
• I – permite a escolha entre os termos.
• Os termos em negrito são os símbolos da linguagem.
• Símbolos separados por .. indicam intervalo, ou seja, todos os valores entre os dois símbolos.
Palavras reservadas
Se
Então
Senão
Inteiro
Real
String
Programa
Tipos
Inteiro ::= {D}+
Real ::= {D} + [.{D}+] | .{D}
String ::= ‘{C}’
Operadores
Operador: =
Significado: Igual
Operador: >
Significado: Maior que
Operador:
Significado: Diferente
Operador: >=
Significado: Maior ou igual
Operador:de erros referente a linha 3 já que != não é um token válido na LPE.
Analisador sintático
O analisador sintático é o responsável pela execução do segundo passo da compilação. Ele agrupa os tokens
gerados pelo analisador léxico em estruturas sintáticas (por exemplo, expressões, comandos) e as analisa
verificando se atendem às regras de sintaxe da gramática da linguagem, gerando, se for o caso, um relatório
com os erros encontrados.
O analisador sintático produz (explícita ou implicitamente) uma árvore sintática. Em muitos compiladores, a
árvore produzida não representa todo o código fonte, mas uma arvore compactada que visa a eliminar as
redundâncias e demais elementos supérfluos.
Os algoritmos de análise sintática podem ser de duas classes:
Análise ascendente
Quando a construção da árvore sintática é
executada de baixo para cima, ou seja, das
folhas para a raiz. Apesar de tratarem um maior
número de gramáticas, são de difícil
implementação e, geralmente, utilizados em
geradores de analisadores sintáticos.
Análise descendente
Quando a construção da árvore ocorre da raiz
para as folhas. É o mais utilizado para a
construção dos analisadores devido a sua maior
facilidade de implementação.
Geradores de analisadores sintáticos são programas que geram analisadores sintáticos a partir da
especificação de uma gramática.A interação do analisador sintático com os demais componentes da etapa de
análise está presente na imagem.
Interação léxico/sintático/semântico.
Voltando a nossa LPE, vamos considerar as seguintes definições de sintaxe em BNF, onde em negrito temos
os símbolos da linguagem:
::=
programa {bloco_de_comando}
::= inteiro | real | string
::= { [{comando}] }
comando ::= bloco_comando | declaração_variavel | comando_se | atribuição
declaração_variavel ::= [ {, } ];
comando_se ::=
se (expressão)
então
[senão ] ;
::=
;
::= :=
::=
|
|
|
|
|
::= + | - | * | /
= | > | = |
::= inteiro | real | string
::= {L} + {L}|{D}
::= {D}+
::= {D} + [.{D}+] | .{D}
::= ‘{C}’
L ::= A..Z a..z
D ::= 0..9
A partir da definição desta sintaxe, analisemos o seguinte programa:
plain-text
Programa exemplo
{
Inteiro A,B,C;
B := 6;
C := 7;
A := B+C;
}
A primeira linha corresponde à declaração do programa e está correta.
A segunda linha corresponde à abertura de um bloco de comando que se fecha na última linha, de forma que
está correto.
A terceira linha corresponde à declaração de variáveis e está de acordo com a gramática.
As linhas 4, 5 e 6 correspondem a atribuições, sendo que a linha 6 inclui um operador aritmético e estão
corretas.
Desta forma, o programa está sintaticamente correto e geraria a árvore compactada da imagem.
Árvore sintática.
Considere agora o seguinte comando:
plain-text
Se (A > B )
Então
A := A + 5;
B := B – 5;
Senão
{
A := A - 5;
B := B + 5;
}
Ele está correto? Vamos analisar! A cláusula Se está de acordo com a sintaxe. O Então possui dois comandos,
mas o bloco não foi aberto, ao contrário do que aconteceu no Senão, que utilizou as chaves {}. Portanto, o
programa possui um erro sintático, pois o analisador irá considerar que existe apenas um comando no Então e,
ao encontrar o Senão, interpretará que existe um Senão sem o Se/Então, erro que será relatado pelo
analisador.
Analisador semântico
Em muitos compiladores, o analisador semântico trabalha integrado ao analisador sintático. Sua finalidade é
verificar se as estruturas sintáticas fazem sentido em seu contexto, por exemplo, verificar se uma variável é
utilizada como tal, bem como fazer a verificação de tipo.
Estas análises são realizadas a partir da árvore sintática gerada no passo anterior e das informações
existentes na tabela de símbolos e produz como resultado uma representação intermediária do programa.
Dos passos da análise, este é o mais difícil, pois envolve interpretar o significado das construções sintáticas
do programa fonte. Vejamos um exemplo a partir do seguinte programa:
plain-text
Programa exemplo
{
Inteiro A, C;
String B
B := ‘C’;
A := B;
}
Note que o programa está do ponto de vista léxico e sintático correto. Porém, do ponto de vista semântico,
possui um erro, já que a variável A foi definida como sendo do tipo INTEIRO e, portanto, não pode sofrer a
atribuição de uma STRING. Este erro então deverá ser relatado pelo analisador.
Etapa de síntese
Apesar de, academicamente, consideramos que a etapa de síntese engloba 3 passos (geração de código
intermediário, otimização e geração de código final), nos casos reais, eles atuam em conjunto, interagindo
entre si, recursivamente, e tendo como grande produto, o código de montagem. Dessa forma, vamos abordá-
los como um todo.
Relembrando
Devemos lembrar que o código de montagem é totalmente dependente da arquitetura da máquina, onde
irá rodar e, para cada código fonte, existem infinitos programas objetos equivalentes, ou seja, produzem
a mesma saída a partir da mesma entrada.
A representação intermediária recebida da etapa de análise apresenta as instruções na ordem em que foram
encontradas. Dessa forma, ela apresenta um programa com estratégias de implementação gerais que
funcionarão em qualquer contexto. Porém, como o programa será “compilado” para uma determinada
arquitetura, o código será executado em um contexto mais restrito e previsível e o gerador de código irá
reescrever o programa para uma execução mais eficiente em um ambiente específico.
Após receber o produto da etapa de análise, o compilador começa a realizar transformações na representação
e otimizações.
Na busca da otimização, o compilador busca
detectar padrões que possam ser substituídos
por construções equivalentes, mas que sejam
mais eficientes. Esses padrões podem ser
globais ou locais e a substituição pode ser
dependente ou independente da máquina.
Esta otimização pode gerar um grande custo
computacional, portanto, nas implementações
reais, dificilmente, será produzido o melhor
programa objeto possível, mas o melhor dentro
de um custo aceitável. Dessa forma, a
otimização teria uma descrição mais exata
como melhoria de código.
As otimizações, normalmente, consistem em uma análise e uma transformação, sendo que a análise
visa determinar onde o compilador pode aplicar a técnica com segurança e que gera um ganho no
desempenho.
Vários tipos de análise podem ser utilizados para suportar as transformações, por exemplo, análise de fluxo de
dados ou análise de dependências.
Já quanto às transformações, elas podem ser de vários tipos, por exemplo, encontrar cálculos que não
mudam, que estejam em um laço e movê-los para locais executados com menor frequência.
No passo de geração do código de montagem, ocorre a seleção de instruções, que consiste em
mapear as operações da IR (representação intermediária), após a otimização, e reescrevê-las para
comandos assembly equivalentes aos comandos de máquina do processador alvo.
Por exemplo, o código otimizado da imagem A poderia ser reescrito no código de montagem da imagem B.
Seleção de instruções.
Durante esta primeira reescrita, o compilador ignora totalmente as limitações do hardware quanto à
quantidade de registradores, ele considera que existem infinitos registradores virtuais.
Ocorre então, uma segunda reescrita denominada alocação de registradores, onde os registradores virtuais
são mapeados para os registradores reais. Durante este processo, o gerador de código determinará quais
valores permanecemnos registradores reais e quais serão deslocados para a memória.
Finalmente, uma terceira fase de reescrita ocorre correspondendo ao escalonamento de instruções quando as
operações são reordenadas para melhor lidar com as restrições de desempenho da máquina alvo. Este
escalonamento decorre da diferença de velocidade de execução de algumas instruções e da dependência de
determinadas operações do resultado de outras operações.
Geradores de compiladores
Escrever um compilador pode ser uma tarefe hercúlea. Para facilitar e dar suporte ao desenvolvimento dessas
ferramentas, foram desenvolvidos programas que auxiliam a sua construção.
Estes programas variam desde simples reconhecedores de linguagens regulares até complexos otimizadores
de código objeto.
Exemplos desses produtos são:
GALS
Possui uma interface gráfica e permite a geração automática de
analisadores Léxico e Sintático a partir da definição de seus tokens e de
sua gramática.
Possui recursos didáticos que permitem a visualização das tabelas de
símbolos.
Possui ainda um simulador léxico e um simulador sintático.
LEX
Projetado para o processamento léxico de caracteres.
Trabalha a partir de definição de uma linguagem regular.
Produz um programa em C que permite realizar a análise léxica a partir da
gramática especificada como entrada.
YACC
Utilizado, normalmente junto com o LEX, foi projetado para reconhecer
linguagens recursivamente enumeráveis, trabalhando desta forma com
linguagens de programação.
Realiza a geração de um analisador sintático na linguagem C a partir de
uma especificação de entrada.
JavaCC
Gera um analisador sintático em Java a partir de uma gramática
especificada como entrada.
Gera, de forma subjacente, um analisador léxico também.
Utilizar uma abordagem top down.
•
•
•
•
•
•
•
•
•
•
•
Sidney Nicolau Venturi Filho.
Construindo um programa
Neste vídeo, conheça mais sobre a construçãode um programa.
Conteúdo interativo
Acesse a versão digital para assistir ao vídeo.
Verificando o aprendizado
Questão 1
A primeira etapa da análise da compilação é realizada pelo analisador léxico e serve como intermediário entre
o programa fonte e o analisador sintático. Durante a análise léxica, a ocorrência de um símbolo da linguagem
no programa fonte é denominada:
A
Token.
B
Lexema.
C
Sentença.
D
Estrutura léxica.
A alternativa B está correta.
Os símbolos da linguagem constituem os seus tokens. Durante a fase de análise léxica, o compilador irá
procurar as suas ocorrências no código fonte para, posteriormente, passá-las ao analisador sintático. Estas
ocorrências são denominadas lexemas.
Questão 2
Durante a fase final da síntese, o código passa por várias reescritas. O mapeamento das instruções do código
otimizado para as instruções específicas da máquina denomina-se:
A
Escalonamento de instruções.
B
Geração de código binário.
C
Seleção de instruções.
D
Montagem.
A alternativa C está correta.
A seleção de instruções corresponde ao mapeamento das operações em representação intermediária que o
gerador de código Intermediário e o otimizador geraram para as instruções em linguagem de baixo nível
(assembly) da arquitetura da máquina para a qual o programa está sendo traduzido.
4. Conclusão
Considerações finais
Ao longo deste tema, fizemos uma viagem pelos conceitos relacionados ao processo de tradução, onde
pudemos conhecer os vários tipos de tradutores de programas fonte para linguagem de máquina.
Iniciamos estudando o que é uma linguagem de máquina e como ela funciona, a seguir, conhecemos o
montador, um tipo de tradutor de programas em linguagem de baixo nível para a linguagem de máquina.
Nossa próxima parada foi nas linguagens de alto nível, vendo suas características, e os vários tipos de
tradutores para esta linguagem como interpretadores, compiladores e tradutores híbridos.
A seguir, tratamos especificamente do compilador e vimos as etapas de análise e síntese, descrevendo os
passos que compõem cada uma das etapas.
Finalmente, em nossa parada final, estudamos com mais detalhes os vários componentes do compilador,
como os analisadores léxico, sintático e semântico e os componentes do Back End.
Podcast
Para encerrar, ouça sobre o compilador.
Conteúdo interativo
Acesse a versão digital para ouvir o áudio.
Explore+
Para saber mais sobre os assuntos explorados neste tema:
Acesse a página do projeto GALS e se familiarize com este gerador de compiladores.
Referências
AHO, A. V.; LAM, M. S.; JEFFREY, R. S. Compiladores: princípios, técnicas e ferramentas. 2 ed. São Paulo:
Pearson, 2008.
LOUDEN, K. C. Compiladores: princípios e práticas. São Paulo: Cengage Learning, 2004.
SANTOS, P. R.; LANGLOIS, T. Compiladores: da teoria à prática. Rio de Janeiro: LTC, 2018.
SEBESTA, R. W. Conceitos de linguagens de programação. 11. ed. Porto Alegre: Bookman, 2018.
•
TANENBAUM, A. S. Organização Estruturada de Computadores. 5 ed. São Paulo: Pearson, 2006.
O Compilador
1. Itens iniciais
Propósito
Objetivos
Introdução
1. Processos de tradução de um programa
Como os computadores executam suas instruções
Montadores e linguagem de montagem
Passo 1
Passo 2
Ligação e carga
Linguagem de alto nível
Interpretadores
Compiladores
Tradutores híbridos
Compilação
Interpretação
Java
A evolução do processo de tradução
Conteúdo interativo
Verificando o aprendizado
2. Passos do processo de compilação e de seus produtos
Etapas da compilação
Etapas da compilação
Análise ou Front End
Síntese ou Back End
Análise ou Front End
Análise Léxica
Análise Sintática
Análise Semântica
Representação Intermediária (IR)
Atenção
Linguagens e gramáticas
Linguagem
Símbolo
Sentença
Alfabeto
Finita
Infinita
Atenção
Síntese ou Back End
Geração de código intermediário
Otimização de código
Geração de código
Tratamento de erros
Tabelas
Atenção
Para variáveis
Parâmetros formais
Procedimentos/sub-rotinas
Exemplo do funcionamento de um compilador
Atenção
As etapas do processo de compilação
Conteúdo interativo
Verificando o aprendizado
Questão 1
3. Estrutura funcional do compilador e de seus componentes
Linguagem de Programação de Exemplo (LPE) - Definição Léxica
Passo 1
Passo 2
Passo 3
Passo 4
Passo 5
Passo 6
Linguagem de Programação de Exemplo (LPE) - Definição Léxica
Exemplo
Identificadores
Palavras reservadas
Tipos
Operadores
Delimitadores
Terminador de comando
Analisador léxico
Token
Lexema
Atenção
Analisador sintático
Análise ascendente
Análise descendente
Analisador semântico
Etapa de síntese
Relembrando
Geradores de compiladores
Construindo um programa
Conteúdo interativo
Verificando o aprendizado
4. Conclusão
Considerações finais
Podcast
Conteúdo interativo
Explore+
Referências