86

Um compilador é programado em qual linguagem? Todos os compiladores de uma linguagem são iguais ou pode existir um melhor que outro?

1

1 Resposta 1

94
+100

Pra não ficar muito amplo vou fazer um resumo (é, isso é um resumo :P). E farei algumas simplificações. Certamente cabem perguntas mais específicas para aprofundar em alguns pontos.

Diversas técnicas

Os compiladores, como qualquer aplicação, podem ser feitos de várias maneiras. Existem várias técnicas estudadas que funcionam melhor, mas não há unanimidade de qual é melhor. E provavelmente cada uma pode ser melhor em cada linguagem e objetivos diferentes. Esse é um dos assuntos mais estudados na computação.

O que se sabe é que este é um dos problemas mais estudados na computação, é um problema bem específico e que atrai muita gente. E sempre há novidades, recentemente houve uma revolução na forma de construir compiladores, ainda que a base seja a mesma.

Alguns exemplos de maneiras de fazer uma das principais fases da compilação podem ser encontrados em outra pergunta minha.

O parsing pode ser escrito manualmente (a maioria dos bons compiladores fazem isso) ou pode ser gerado por um software especializado, também descrito em outra pergunta.

A escolha da melhor técnica pode dar uma diferença brutal na velocidade, qualidade da detecção de erros, facilidade de manutenção, etc.

Há variações de como a análise da árvore é feita, por exemplo: iniciando de cima para baixo (top-down) ou de baixo para cima (bottom-up*).

Compiladores fazem uso extensivo de recursão. Esse é um dos domínios onde realmente isto é bastante útil.

Linguagens usadas

Eles podem ser escritos em qualquer linguagem, como qualquer problema que pode ser resolvido computacionalmente. O compilador de uma linguagem pode até mesmo ser escrito na própria linguagem.

Opa, como isto pode ser possível? Não é o problema do ovo e da galinha?

Isso se chama bootstrapping. O compilador de uma linguagem começa ser escrito em outra linguagem e depois aos poucos ou no final do processo ele é reescrito usando a linguagem que ele compila. O problema foi resolvido da mesma forma do ovo e a galinha, não houve um primeiro, houve mutação (a visão religiosa é a não-explicação, ou seja, é o que hoje se chama boa prática, "siga o que eu disse e cale a boca").

Um dia só existia o código de máquina, ele foi usado para escrever um montador Assembly (que é parecido com um compilador, só que mais simples), que foi usado para criar a primeira linguagem de alto nível (mainstream), o Fortran, que depois foi usado para criar outros compiladores, e assim por diante.

Um exemplo disso é o o compilador do C# que originalmente foi escrito em C++ e mais recentemente foi reescrito em C#. C obviamente fez isso e muitas linguagens hoje fazem o mesmo até para mostrar o quanto elas são capazes. Linguagens com baixa performance evitam fazer porque compiladores precisam ser rápidos. Por sinal grande parte dos compiladores são escritos em C ou C++, já que são linguagens poderosas, onipresentes e permitem alta performance.

Seu funcionamento

O compilador pega um texto, o analisa caractere por caractere, tenta achar padrões reconhecíveis por uma gramática preestabelecida, faz uma análise se tudo faz sentido e gera um conjunto de dados que permitirá a criação do programa a ser executado. Não tem muito segredo, a ideia básica é bem simples. É claro que as relações entre todos os elementos da linguagem começam complicar. A complexidade dele se dá principalmente pela complexidade da linguagem.

As fases de compilação podem variar de compilador para compilador. E se será feito em um ou mais passos também (fase e passo são coisas diferentes, o primeiro pode ocorrer em separado mas ocorrer no meu passo). Isto depende do arquitetura do compilador e da necessidade da linguagem. Por isso fazer um montador é muito mais simples que um compilador. Um montador trabalha com regras muito simples.

Muitas vezes o compilador é dividido em front-end (cuida mais da linguagem fonte) e back-end (cuida mais da plataforma alvo), e até mesmo middle-end, dividindo bem algumas das fases.

Fluxo de compilação

Análise léxica

A análise básica (scanning) onde tenta achar determinados padrões é chamada de análise léxica. Nela a procura é por tokens reconhecíveis. Esses tokens serão elementos que poderão ser usados para produzir algum entendimento no código. Exemplos de tokens: operadores, palavras-chave, identificadores, literais, etc. Se achar trechos de texto que não podem ser considerados tokens já permite o compilador gerar um erro sintático.

Nessa fase cada caractere vai sendo lido e vendo se ele pode ser algo reconhecível. Por exemplo:

  • ele acha um i, não sabe nada o que fazer com isso;
  • depois acha um f, ainda não dá para ter certeza que isto é algo útil;
  • então acha um espaço e agora pode descobrir que o if anterior é possivelmente uma palavra-chave;
  • agora acha um x, e não sabe o que fazer com isto;
  • acha um = e ainda não tem condições de uma decisão a não ser que há um possível identificar antes, tem que fazer uma análise mais ampla pra ter certeza;
  • acha um = e não dá para ter certeza do que se trata;
  • acha um 1, agora ele sabe que o que tinha achado anteriormente era um operador, até pode identificar qual;
  • agora acha uma quebra de linha, e pode ter certeza que o 1 era um literal numérico.

Pré-processamento

Aqui pode haver um processamento prévio que é uma tradução muito simplificada de alguns tokens por outros. É uma troca muito simples normalmente sem maiores verificações.

Análise sintática

Depois vem a análise sintática (parsing) que organiza esses tokens todos formando construções que podem ser entendidas de forma isolada. Ele usa o método de dividir para conquistar. Normalmente uma árvore de tokens é montada chamada de AST. Neste processo é verificado se a construção encontrada é correta para o que se espera naquela linguagem. Se não for, o compilador tem que gerar um erro sintático.

Os bons compiladores, fazem uma análise mais profunda para gerar erros mais precisos que podem ajudar mais o programador saber do que se trata sem causar confusões. Entre essas análises ele verifica se em um local que espera uma variável tem isto, se espera uma expressão ela está lá, etc.

Usando o exemplo anterior, nesta fase ele verá se o if cabe naquele lugar, se depois vem uma expressão, como deve ser, verifica se a expressão tem uma forma correta, por exemplo se tem um operador e dois operandos em cada lado, verifica se não tem mais nada que esteja atrapalhando. Claro, isso é uma enorme simplificação do processo.

Parsing

A ideia aqui é usar o bom e velho dividir para conquistar que é usado em tudo na computação, e que é a melhor forma de resolver boa parte dos problemas mesmo por humanos (algoritmos servem para humanos também), e muitos não sabem disto (resolva uma parte de cada vez), a não ser que o problema seja a divisão, aí a união é solução. Desculpe pelo offtopic mas alguns humanos resolveram o problema das massas com o dividir e conquistar, políticos e religiosos, por exemplo, por isso está cada vez mais fácil eles comandarem o mundo, estamos cada vez mais divididos

Análise semântica

Depois vem a análise semântica que procura se as relações entre os tokens estão de acordo com o esperado para a linguagem. Ele analisa se os tipos de dados são adequados em cada lugar, se uma operação é possível, se não faltou alguma coisa necessária para completar uma operação, etc. Se algo assim não der certo, o compilador gerará um erro semântico. Nesta fase informações adicionais serão coletadas para ajudar na otimização e geração de código. Ela pode também organizar melhor e simplificar a árvore sintática.

Pelo exemplo anterior uma das muitas análises que serão feitas é que se a expressão da condição resultará em um booleano, que é necessário para todo if. Também verificará se o operador == pode ser usado com x de acordo com seu tipo e com um literal numérico. Note que essas verificações, apesar de relacionadas e uma dependente da outra são feitas separadamente.

Se tivesse vários operadores faria a seleção da precedência, o que alteraria a árvore.

Exemplo de árvore abstrata de sintaxe:

AST

Análise de tipagem

Pode ser uma variação da análise semântica. Em linguagens de tipagem complexa pode ser útil ter isso separado.

Otimização de código

Uma fase opcional seguinte é a da otimização. Aí algumas mudanças podem ser feitas na árvore sintática (embora a fase possa ocorrer em outro momento e tentar modificar outra representação). Essas mudanças visam fazer o código ficar melhor para economizar processamento e memória, ou seja, poder executar a mesma operação, obtendo o mesmo resultado, aproveitando melhor a capacidade de processamento do alvo deste programa.

Técnicas de otimização comumente usadas.

Geração de código

A última fase é da geração de código. Partindo da árvore sintática analisada e modificada já é possível gerar a saída, que, em geral, é um código em outra linguagem, como assembly ou o código de máquina para um processador específico. Em geral é uma sequência de bytes que o processador ou uma máquina virtual entende.

Usando nosso exemplo acima, hipoteticamente, ele poderia gerar uma instrução para o processador para fazer uma comparação numérica (CMP) e depois um desvio condicional (JZ).

Em alguns casos é possível que esta geração seja de um código intermediário que pode passar por outra otimização e geração de um código final. Esta técnica ajuda muito o compilador ser construído para atender várias plataformas diferentes.

Veja um exemplo do fluxo do compilador.

Outras fases podem ser usadas, não há uma regra que compiladores precisam ser assim. Hoje em dia compiladores modernos são mais modulares para poderem ser usados em outras ferramentas que precisam de algumas dessas fases isoladamente. Ótimo para syntax highlighters, refatoradores, analisadores estáticos, ferramentas de AOP, geradores de código, REPL, formatadores, etc.

Variações

Quando um compilador gera um código para outra linguagem de alto nível nessa última fase, é costume ser chamado de transpilador.

Quando essa fase executa comandos em vez de gerar um código binário ou fonte em outra linguagem ele funciona como um interpretador. Normalmente a interpretação funciona um pouco diferente, já que a compilação e execução vão ocorrendo em pequenos blocos. Mas isto tem mudado, os interpretadores estão se beneficiando de uma análise mais global.

Nem falei em outros tipos como o Just-in-time compiler.

Conclusão

Todo programador deveria aprender como funciona um compilador. Mesmo que ele nunca vá escrever um. Há uma diferença enorme na qualidade do programador que entende isto (e outros assuntos) e do que não entende. Não precisa ser um profundo conhecedor, mas precisa saber como é para usar as ferramentas do seu dia a dia de forma melhor. Só precisa evitar o cargo cult.

Vejo muitos programadores que sofrem muito fazendo coisas erradas porque não entendem o funcionamento da matemática, das línguas, da ciência, do computador, do sistema operacional, das linguagens e compiladores, das estruturas de dados e algoritmos, dos paradigmas, das metodologias, etc. E o pior é que alguns, mesmo não sabendo de nada disso, acham que sabem tudo o que precisa e não tem necessidade de aprender mais, de melhorar. Quer saber o que está fazendo? Se dedique, não ache que já sabe tudo. Sempre tem algo para aprender. E compilação é uma das áreas mais fascinantes da computação.

Referências

Informações adicionais.

Wikipedia.

O livro canônico sobre o assunto é o Dragon's Book (considerado obsoleto por muitos).

Exemplo de gramática - Linguagem C - Exemplo de compilador.

Construção moderna de compiladores [vídeo].

Mais algumas referências:

Coloquei no GitHub para referência futura.

4
  • 3
    Excelente "resumo"!! hahaha vale até virar um wiki.
    – Brittz
    Commented 29/07/2016 às 20:54
  • @bigown no caso o montador não seria "Assembler" e "Assembly" uma linguagem ? Posso estar errado, não tenho certeza...
    – MagicHat
    Commented 14/08/2016 às 1:16
  • @MagicHat precisamente.
    – Maniero
    Commented 14/08/2016 às 8:22
  • 1
    O livro do dragão é bom, mas deixa muito a desejar na parte do back-end do compilador. Li recentemente o Engineering a Compiler e é bastante completo, indo de A a Z. Acredito ser um ótimo livro pra quem quer estudar mais a fundo o assunto. Commented 8/05/2018 às 4:36

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .