Compilador

Na computação, um compilador é um programa de computador que traduz código de computador escrito em uma linguagem de programação (a linguagem fonte) para outra linguagem (a linguagem destino idioma). O nome "compilador" é usado principalmente para programas que traduzem o código-fonte de uma linguagem de programação de alto nível para uma linguagem de programação de baixo nível (por exemplo, linguagem assembly, código de objeto ou código de máquina) para criar um programa executável.

Existem muitos tipos diferentes de compiladores que produzem saída em diferentes formas úteis. Um compilador cruzado produz código para uma CPU ou sistema operacional diferente daquele em que o próprio compilador cruzado é executado. Um compilador bootstrap geralmente é um compilador temporário, usado para compilar um compilador mais permanente ou melhor otimizado para uma linguagem.

Incluir software relacionado, um programa que traduz de uma linguagem de baixo nível para uma de nível superior é um descompilador; um programa que traduz entre linguagens de alto nível, geralmente chamado de compilador fonte a fonte ou transpiler. Um reescritor de linguagem geralmente é um programa que traduz a forma de expressões sem uma mudança de idioma. Um compilador-compilador é um compilador que produz um compilador (ou parte de um), muitas vezes de forma genérica e reutilizável para poder produzir muitos compiladores diferentes.

É provável que um compilador execute algumas ou todas as seguintes operações, geralmente chamadas de fases: pré-processamento, análise léxica, análise sintática, análise semântica (tradução dirigida pela sintaxe), conversão de programas de entrada em uma representação intermediária, otimização de código e máquina geração de código específico. Os compiladores geralmente implementam essas fases como componentes modulares, promovendo o design eficiente e a correção das transformações da entrada de origem para a saída de destino. Falhas de programa causadas por comportamento incorreto do compilador podem ser muito difíceis de rastrear e contornar; portanto, os implementadores de compiladores investem um esforço significativo para garantir a exatidão do compilador.

Os compiladores não são o único processador de linguagem usado para transformar programas fonte. Um interpretador é um software de computador que transforma e executa as operações indicadas. O processo de tradução influencia o design de linguagens de computador, o que leva a uma preferência de compilação ou interpretação. Em teoria, uma linguagem de programação pode ter um compilador e um interpretador. Na prática, as linguagens de programação tendem a ser associadas a apenas uma (um compilador ou um interpretador).

História

Um diagrama da operação de um compilador multilíngue, multi-alvo típico

Conceitos teóricos de computação desenvolvidos por cientistas, matemáticos e engenheiros formaram a base do desenvolvimento da computação digital moderna durante a Segunda Guerra Mundial. As linguagens binárias primitivas evoluíram porque os dispositivos digitais só entendem uns e zeros e os padrões de circuito na arquitetura da máquina subjacente. No final da década de 1940, as linguagens assembly foram criadas para oferecer uma abstração mais funcional das arquiteturas de computador. A capacidade limitada de memória dos primeiros computadores levou a desafios técnicos substanciais quando os primeiros compiladores foram projetados. Portanto, o processo de compilação precisava ser dividido em vários pequenos programas. Os programas front-end produzem os produtos de análise usados pelos programas back-end para gerar o código-alvo. Como a tecnologia de computador fornecia mais recursos, os projetos de compilador podiam se alinhar melhor com o processo de compilação.

Geralmente é mais produtivo para um programador usar uma linguagem de alto nível, então o desenvolvimento de linguagens de alto nível seguiu naturalmente os recursos oferecidos pelos computadores digitais. As linguagens de alto nível são linguagens formais estritamente definidas por sua sintaxe e semântica que formam a arquitetura da linguagem de alto nível. Os elementos dessas linguagens formais incluem:

• Alfabeto, qualquer conjunto finito de símbolos;
• String, uma sequência finita de símbolos;
• Língua, qualquer conjunto de cordas em um alfabeto.

As sentenças em uma língua podem ser definidas por um conjunto de regras chamado gramática.

A forma Backus–Naur (BNF) descreve a sintaxe das "frases" de uma linguagem e foi usado para a sintaxe de Algol 60 por John Backus. As ideias derivam dos conceitos de gramática livre de contexto de Noam Chomsky, um linguista. "BNF e suas extensões tornaram-se ferramentas padrão para descrever a sintaxe das notações de programação e, em muitos casos, partes de compiladores são geradas automaticamente a partir de uma descrição BNF."

Na década de 1940, Konrad Zuse projetou uma linguagem de programação algorítmica chamada Plankalkül ("Plan Calculus"). Embora nenhuma implementação real tenha ocorrido até a década de 1970, ela apresentou conceitos vistos posteriormente no APL projetado por Ken Iverson no final da década de 1950. APL é uma linguagem para cálculos matemáticos.

O design de linguagem de alto nível durante os anos de formação da computação digital forneceu ferramentas de programação úteis para uma variedade de aplicações:

• FORTRAN (Tradução Formula) para aplicações de engenharia e ciência é considerada a primeira língua de alto nível.
• COBOL (Common Business-Oriented Language) evoluiu de A-0 e FLOW-MATIC para se tornar a língua dominante de alto nível para aplicações empresariais.
• LISP (processador List) para computação simbólica.

A tecnologia do compilador evoluiu da necessidade de uma transformação estritamente definida do programa-fonte de alto nível em um programa-alvo de baixo nível para o computador digital. O compilador pode ser visto como um front-end para lidar com a análise do código-fonte e um back-end para sintetizar a análise no código-alvo. A otimização entre o front-end e o back-end pode produzir um código-alvo mais eficiente.

Alguns marcos iniciais no desenvolvimento da tecnologia de compiladores:

• 1952: Um compilador Autocode desenvolvido por Alick Glennie para o computador Manchester Mark I na Universidade de Manchester é considerado por alguns para ser a primeira linguagem de programação compilada.
• 1952: A equipe de Grace Hopper em Remington Rand escreveu o compilador para a linguagem de programação A-0 (e cunhou o termo Compilador para descrevê-lo), embora o compilador A-0 funcione mais como um carregador ou linker do que a noção moderna de um compilador completo.
• 1954-1957: Uma equipe liderada por John Backus na IBM desenvolveu FORTRAN, que geralmente é considerada a primeira língua de alto nível. Em 1957, eles concluíram um compilador FORTRAN que é geralmente creditado como tendo introduzido o primeiro compilador inequívoco.
• 1959: A Conferência sobre a linguagem dos sistemas de dados (CODASYL) iniciou o desenvolvimento do COBOL. O projeto COBOL desenhou A-0 e FLOW-MATIC. No início da década de 1960, o COBOL foi compilado em várias arquiteturas.
• 1958-1960: Algol 58 foi o precursor da ALGOL 60. Algol 58 introduziu blocos de código, um avanço chave na ascensão da programação estruturada. ALGOL 60 foi a primeira língua a implementar definições de função aninhada com escopo lexical. Incluiu recursão. Sua sintaxe foi definida usando BNF. ALGOL 60 inspirou muitas línguas que a seguiram. Tony. Hoare comentou: "... não foi apenas uma melhoria em seus antecessores, mas também em quase todos os seus sucessores."
• 1958–1962: John McCarthy no MIT projetou LISP. Os recursos de processamento de símbolos forneceram recursos úteis para a pesquisa de inteligência artificial. Em 1962, a versão LISP 1.5 observou algumas ferramentas: um intérprete escrito por Stephen Russell e Daniel J. Edwards, um compilador e montador escrito por Tim Hart e Mike Levin.

Os primeiros sistemas operacionais e softwares foram escritos em linguagem assembly. Nos anos 1960 e início dos anos 1970, o uso de linguagens de alto nível para programação de sistemas ainda era controverso devido às limitações de recursos. No entanto, vários esforços de pesquisa e indústria começaram a mudar para linguagens de programação de sistemas de alto nível, por exemplo, BCPL, BLISS, B e C.

BCPL (Linguagem de Programação Combinada Básica) projetada em 1966 por Martin Richards na Universidade de Cambridge foi originalmente desenvolvida como uma ferramenta de escrita de compiladores. Vários compiladores foram implementados, Richards' livro fornece insights para a linguagem e seu compilador. BCPL não foi apenas uma linguagem de programação de sistemas influente que ainda é usada em pesquisa, mas também forneceu uma base para o design de linguagens B e C.

BLISS (Linguagem básica para implementação de software de sistema) foi desenvolvido para um computador PDP-10 da Digital Equipment Corporation (DEC) pela equipe de pesquisa da W.A. Wulf's Carnegie Mellon University (CMU). A equipe CMU desenvolveu o compilador BLISS-11 um ano depois, em 1970.

Multics (Multiplexed Information and Computing Service), um projeto de sistema operacional de tempo compartilhado, envolveu MIT, Bell Labs, General Electric (mais tarde Honeywell) e foi liderado por Fernando Corbató do MIT. O Multics foi escrito na linguagem PL/I desenvolvida pela IBM e pelo IBM User Group. O objetivo da IBM era satisfazer os requisitos de programação de sistemas, científicos e de negócios. Havia outras linguagens que poderiam ter sido consideradas, mas PL/I oferecia a solução mais completa, embora não tivesse sido implementada. Nos primeiros anos do projeto Multics, um subconjunto da linguagem poderia ser compilado para linguagem assembly com o compilador Early PL/I (EPL) de Doug McIlory e Bob Morris da Bell Labs. A EPL apoiou o projeto até que um compilador de inicialização para o PL/I completo pudesse ser desenvolvido.

Bell Labs deixou o projeto Multics em 1969, e desenvolveu uma linguagem de programação de sistema B baseada em conceitos BCPL, escrita por Dennis Ritchie e Ken Thompson. Ritchie criou um compilador de boot-strapping para B e escreveu o sistema operacional Unics (Uniplexed Information and Computing Service) para um PDP-7 em B. Unics acabou se tornando Unix.

Bell Labs iniciou o desenvolvimento e expansão de C baseado em B e BCPL. O compilador BCPL foi transportado para o Multics pela Bell Labs e BCPL era a linguagem preferida na Bell Labs. Inicialmente, um programa front-end para o Bell Labs' O compilador B foi usado enquanto um compilador C foi desenvolvido. Em 1971, um novo PDP-11 forneceu o recurso para definir extensões para B e reescrever o compilador. Em 1973, o design da linguagem C estava essencialmente completo e o kernel Unix para um PDP-11 foi reescrito em C. Steve Johnson iniciou o desenvolvimento do Portable C Compiler (PCC) para suportar o redirecionamento de compiladores C para novas máquinas.

A programação orientada a objetos (OOP) oferecia algumas possibilidades interessantes para o desenvolvimento e manutenção de aplicativos. Os conceitos OOP são mais antigos, mas faziam parte da ciência da linguagem LISP e Simula. No Bell Labs, o desenvolvimento de C++ se interessou por OOP. C++ foi usado pela primeira vez em 1980 para programação de sistemas. O projeto inicial alavancou os recursos de programação de sistemas de linguagem C com os conceitos do Simula. Recursos orientados a objetos foram adicionados em 1983. O programa Cfront implementou um front-end C++ para o compilador de linguagem C84. Nos anos subsequentes, vários compiladores C++ foram desenvolvidos à medida que a popularidade do C++ crescia.

Em muitos domínios de aplicativos, a ideia de usar uma linguagem de alto nível pegou rapidamente. Devido à expansão da funcionalidade suportada por linguagens de programação mais recentes e à crescente complexidade das arquiteturas de computador, os compiladores se tornaram mais complexos.

A DARPA (Agência de Projetos de Pesquisa Avançada de Defesa) patrocinou um projeto de compilador com a equipe de pesquisa CMU de Wulf em 1970. O projeto PQCC do Compilador-Compilador de Qualidade de Produção produziria um Compilador de Qualidade de Produção (PQC) a partir de definições formais da linguagem fonte e o alvo. PQCC tentou estender o termo compilador-compilador além do significado tradicional como um gerador de parser (por exemplo, Yacc) sem muito sucesso. PQCC pode ser mais apropriadamente referido como um gerador de compilador.

A pesquisa do PQCC no processo de geração de código procurou construir um sistema de escrita de compilador verdadeiramente automático. O esforço descobriu e projetou a estrutura de fases do PQC. O compilador BLISS-11 forneceu a estrutura inicial. As fases incluíram análises (front-end), tradução intermediária para a máquina virtual (middle-end) e tradução para o destino (back-end). O TCOL foi desenvolvido para a pesquisa do PQCC para lidar com construtos específicos da linguagem na representação intermediária. Variações de TCOL suportam vários idiomas. O projeto PQCC investigou técnicas de construção automatizada de compiladores. Os conceitos de design provaram ser úteis na otimização de compiladores e compiladores para a linguagem de programação (desde 1995, orientada a objetos) Ada.

O documento Ada STONEMAN formalizou o ambiente de suporte ao programa (APSE) junto com o kernel (KAPSE) e mínimo (MAPSE). Um intérprete de Ada NYU/ED apoiou esforços de desenvolvimento e padronização com o American National Standards Institute (ANSI) e a International Standards Organization (ISO). O desenvolvimento inicial do compilador Ada pelos Serviços Militares dos EUA incluiu os compiladores em um ambiente de design integrado completo, de acordo com as linhas do documento STONEMAN. O Exército e a Marinha trabalharam no projeto Ada Language System (ALS) voltado para a arquitetura DEC/VAX, enquanto a Força Aérea iniciou o Ada Integrated Environment (AIE) voltado para a série IBM 370. Embora os projetos não tenham fornecido os resultados desejados, eles contribuíram para o esforço geral no desenvolvimento de Ada.

Outros esforços do compilador Ada começaram na Grã-Bretanha na Universidade de York e na Alemanha na Universidade de Karlsruhe. Nos Estados Unidos, a Verdix (posteriormente adquirida pela Rational) entregou o Verdix Ada Development System (VADS) ao Exército. A VADS forneceu um conjunto de ferramentas de desenvolvimento, incluindo um compilador. O Unix/VADS pode ser hospedado em uma variedade de plataformas Unix, como DEC Ultrix e Sun 3/60 Solaris direcionado ao Motorola 68020 em uma avaliação CECOM do Exército. Logo havia muitos compiladores Ada disponíveis que passaram nos testes de validação Ada. O projeto GNU da Free Software Foundation desenvolveu o GNU Compiler Collection (GCC), que fornece um recurso básico para suportar vários idiomas e alvos. A versão Ada GNAT é um dos compiladores Ada mais usados. O GNAT é gratuito, mas também oferece suporte comercial, por exemplo, AdaCore, foi fundado em 1994 para fornecer soluções de software comercial para Ada. O GNAT Pro inclui o GNAT baseado em GNU GCC com um conjunto de ferramentas para fornecer um ambiente de desenvolvimento integrado.

As linguagens de alto nível continuaram a impulsionar a pesquisa e o desenvolvimento de compiladores. As áreas de foco incluíam otimização e geração automática de código. Tendências em linguagens de programação e ambientes de desenvolvimento influenciaram a tecnologia de compiladores. Mais compiladores foram incluídos em distribuições de linguagem (PERL, Java Development Kit) e como um componente de um IDE (VADS, Eclipse, Ada Pro). A inter-relação e a interdependência das tecnologias cresceram. O advento dos serviços da web promoveu o crescimento das linguagens da web e das linguagens de script. Os scripts remontam aos primeiros dias das interfaces de linha de comando (CLI), onde o usuário podia inserir comandos a serem executados pelo sistema. Conceitos de shell de usuário desenvolvidos com linguagens para escrever programas de shell. Os primeiros designs do Windows ofereciam um recurso simples de programação em lote. A transformação convencional dessas línguas utilizou um intérprete. Embora não sejam amplamente usados, os compiladores Bash e Batch foram escritos. Mais recentemente, linguagens interpretadas sofisticadas tornaram-se parte do kit de ferramentas dos desenvolvedores. As linguagens de script modernas incluem PHP, Python, Ruby e Lua. (Lua é amplamente usado no desenvolvimento de jogos.) Todos eles têm suporte a interpretador e compilador.

"Quando o campo da compilação começou no final dos anos 50, seu foco era limitado à tradução de programas de linguagem de alto nível em código de máquina... O campo do compilador está cada vez mais interligado com outras disciplinas, incluindo arquitetura de computadores, linguagens de programação, métodos formais, engenharia de software e segurança de computadores." A pesquisa "Pesquisa do compilador: os próximos 50 anos" artigo observou a importância de linguagens orientadas a objetos e Java. Segurança e computação paralela foram citadas entre os futuros alvos de pesquisa.

Construção do compilador

Um compilador implementa uma transformação formal de um programa de origem de alto nível para um programa de destino de baixo nível. O design do compilador pode definir uma solução de ponta a ponta ou lidar com um subconjunto definido que faz interface com outras ferramentas de compilação, por exemplo, pré-processadores, montadores, ligadores. Os requisitos de design incluem interfaces rigorosamente definidas internamente entre os componentes do compilador e externamente entre os conjuntos de ferramentas de suporte.

No início, a abordagem adotada para o projeto do compilador era diretamente afetada pela complexidade da linguagem do computador a ser processada, pela experiência da(s) pessoa(s) que o projeta(m) e pelos recursos disponíveis. As limitações de recursos levaram à necessidade de passar pelo código-fonte mais de uma vez.

Um compilador para uma linguagem relativamente simples escrita por uma pessoa pode ser um software único e monolítico. No entanto, à medida que o idioma de origem cresce em complexidade, o design pode ser dividido em várias fases interdependentes. Fases separadas fornecem melhorias de design que concentram o desenvolvimento nas funções no processo de compilação.

Compiladores de uma passagem versus várias passagens

A classificação de compiladores por número de passagens tem como pano de fundo as limitações de recursos de hardware dos computadores. A compilação envolve muito trabalho e os primeiros computadores não tinham memória suficiente para conter um programa que fizesse todo esse trabalho. Assim, os compiladores foram divididos em programas menores, cada um passando pela fonte (ou alguma representação dela), realizando algumas das análises e traduções necessárias.

A capacidade de compilar em uma única passagem tem sido classicamente vista como um benefício porque simplifica o trabalho de escrever um compilador e os compiladores de uma passagem geralmente executam compilações mais rapidamente do que os compiladores de múltiplas passagens. Assim, em parte devido às limitações de recursos dos primeiros sistemas, muitas linguagens antigas foram projetadas especificamente para que pudessem ser compiladas em uma única passagem (por exemplo, Pascal).

Em alguns casos, o design de um recurso de linguagem pode exigir que um compilador execute mais de uma passagem pelo código-fonte. Por exemplo, considere uma declaração que aparece na linha 20 da fonte que afeta a tradução de uma declaração que aparece na linha 10. Nesse caso, a primeira passagem precisa coletar informações sobre as declarações que aparecem após as declarações que afetam, com a tradução real acontecendo durante uma passagem subseqüente.

A desvantagem de compilar em uma única passagem é que não é possível realizar muitas das otimizações sofisticadas necessárias para gerar código de alta qualidade. Pode ser difícil contar exatamente quantas passagens um compilador de otimização faz. Por exemplo, diferentes fases de otimização podem analisar uma expressão várias vezes, mas apenas analisar outra expressão uma vez.

Dividir um compilador em pequenos programas é uma técnica usada por pesquisadores interessados em produzir compiladores comprovadamente corretos. Provar a correção de um conjunto de pequenos programas geralmente requer menos esforço do que provar a correção de um programa maior, único e equivalente.

Estrutura do compilador de três estágios

Design de compiladores

Independentemente do número exato de fases no design do compilador, as fases podem ser atribuídas a um dos três estágios. Os estágios incluem um front-end, um meio-termo e um back-end.

• O extremidade dianteira varre a entrada e verifica a sintaxe e a semântica de acordo com uma linguagem de origem específica. Para linguagens de tipo estático executa a verificação de tipo coletando informações do tipo. Se o programa de entrada estiver sinteticamente incorreto ou tiver um erro de tipo, ele gera mensagens de erro e/ou aviso, geralmente identificando a localização no código fonte onde o problema foi detectado; em alguns casos o erro real pode ser (muito) anteriormente no programa. Os aspectos da extremidade frontal incluem análise lexical, análise de sintaxe e análise semântica. A extremidade frontal transforma o programa de entrada em uma representação intermediária (IR) para processamento posterior até a extremidade média. Este IR é geralmente uma representação de nível inferior do programa em relação ao código fonte.
• O fim médio executa otimizações no IR que são independentes da arquitetura de CPU sendo alvo. Esta independência de código-fonte/máquina destina-se a permitir que as otimizações genéricas sejam compartilhadas entre versões do compilador que suportam diferentes idiomas e processadores de destino. Exemplos de otimizações de extremidade média são a remoção de código inútil (eliminação de código morto) ou código não alcançável (análise de alcance), a descoberta e a propagação de valores constantes (propagação constante), a deslocação da computação para um lugar menos frequentemente executado (por exemplo, fora de um loop), ou a especialização da computação com base no contexto, eventualmente produzindo o IR "otimizado" que é usado pela extremidade traseira.
• O back end leva o IR otimizado da extremidade média. Pode realizar mais análises, transformações e otimizações específicas para a arquitetura de CPU de destino. A extremidade traseira gera o código de montagem dependente do alvo, executando a alocação do registro no processo. A extremidade traseira executa o agendamento de instruções, que re-ordena as instruções para manter unidades de execução paralelas ocupadas preenchendo slots de atraso. Embora a maioria dos problemas de otimização sejam NP-hard, as técnicas heurísticas para resolvê-los são bem desenvolvidas e atualmente implementadas em compiladores de qualidade de produção. Tipicamente, a saída de uma extremidade traseira é o código da máquina especializado para um determinado processador e sistema operacional.

Essa abordagem front/middle/back-end torna possível combinar front-ends para diferentes linguagens com back-ends para diferentes CPUs enquanto compartilha as otimizações do meio-termo. Exemplos práticos dessa abordagem são o GNU Compiler Collection, o Clang (compilador C/C++ baseado em LLVM) e o Amsterdam Compiler Kit, que possuem vários front-ends, otimizações compartilhadas e vários back-ends.

Extremidade frontal

Lexer e parser exemplo para C. A partir da sequência de caracteres "if(net>0.0)total+=net*(1.0+tax/100.0);", o scanner compõe uma sequência de tokens e categoriza cada um deles, por exemplo, como identificador, Palavra reservada, número literalou operador. A última sequência é transformada pelo parser em uma árvore de sintaxe, que é então tratada pelas fases restantes do compilador. O scanner e o parser lidam com as partes regulares e corretamente livres de contexto da gramática para C, respectivamente.

O front-end analisa o código-fonte para construir uma representação interna do programa, chamada de representação intermediária (IR). Ele também gerencia a tabela de símbolos, uma estrutura de dados que mapeia cada símbolo no código-fonte para informações associadas, como localização, tipo e escopo.

Embora o frontend possa ser uma única função ou programa monolítico, como em um analisador sem scanner, ele foi tradicionalmente implementado e analisado como várias fases, que podem ser executadas sequencialmente ou simultaneamente. Este método é favorecido devido à sua modularidade e separação de interesses. Mais comumente hoje, o frontend é dividido em três fases: análise léxica (também conhecida como lexing ou digitalização), análise sintática (também conhecida como digitalização ou análise) e análise semântica. Lexing e parsing compreendem a análise sintática (sintaxe da palavra e sintaxe da frase, respectivamente) e, em casos simples, esses módulos (o lexer e o parser) podem ser gerados automaticamente a partir de uma gramática para o idioma, embora em casos mais complexos eles requeiram modificação manual. A gramática lexical e a gramática de frases são geralmente gramáticas livres de contexto, o que simplifica significativamente a análise, com a sensibilidade ao contexto tratada na fase de análise semântica. A fase de análise semântica é geralmente mais complexa e escrita à mão, mas pode ser parcialmente ou totalmente automatizada usando gramáticas de atributos. Essas próprias fases podem ser ainda mais divididas: lexing como varredura e avaliação e análise como a construção de uma árvore de sintaxe concreta (CST, árvore de análise) e, em seguida, transformando-a em uma árvore de sintaxe abstrata (AST, árvore de sintaxe). Em alguns casos, fases adicionais são usadas, principalmente reconstrução de linha e pré-processamento, mas são raras.

As principais fases do front-end incluem o seguinte:

• Reconstrução de linha converte a sequência de caracteres de entrada em uma forma canônica pronta para o parser. Linguagens que alteram suas palavras-chave ou permitem espaços arbitrários dentro dos identificadores requerem esta fase. O top-down, recorrente-decente, mesa-driven parsers usado na década de 1960 tipicamente ler a fonte um personagem de cada vez e não exigiu uma fase de tokenização separada. Atlas Autocode and Imp (e algumas implementações da ALGOL e Coral 66) são exemplos de linguagens passadas cujos compiladores teriam um Reconstrução de linha fase.
• Pré-processamento suporta substituição macro e compilação condicional. Tipicamente, a fase de pré-processamento ocorre antes da análise sintática ou semântica; por exemplo, no caso de C, o pré-processador manipula fichas lexicais em vez de formas sintáticas. No entanto, algumas linguagens como Scheme suportam substituições macro baseadas em formas sintáticas.
• Análise Lexical (também conhecido como lexing ou tokenization) quebra o texto de código fonte em uma sequência de pequenas peças chamadas Tokens lexical. Esta fase pode ser dividida em duas fases: a digitalização, que segmenta o texto de entrada em unidades sintáticas chamadas Iexemes e atribui-lhes uma categoria; e avaliação, que converte lexemes em um valor processado. Um token é um par que consiste em um Nome do símbolo e um opcional valor token. As categorias de token comuns podem incluir identificadores, palavras-chave, separadores, operadores, literais e comentários, embora o conjunto de categorias de tokens varia em diferentes linguagens de programação. A sintaxe lexeme é tipicamente uma linguagem regular, então um autômato de estado finito construído a partir de uma expressão regular pode ser usado para reconhecê-la. O software fazendo análise lexical é chamado de analisador lexical. Esta pode não ser uma etapa separada - pode ser combinada com a etapa de análise na análise sem scanner, em que a análise de caso é feita no nível do personagem, não no nível de token.
• Análise da sintaxe (também conhecido como análise) envolve analisar a sequência de token para identificar a estrutura sintática do programa. Esta fase normalmente constrói uma árvore de parsa, que substitui a sequência linear de tokens com uma estrutura de árvore construída de acordo com as regras de uma gramática formal que define a sintaxe da linguagem. A árvore de parse é frequentemente analisada, aumentada e transformada por fases posteriores no compilador.
• Análise semântica adiciona informações semânticas à árvore de parse e constrói a tabela de símbolos. Esta fase realiza verificações semânticas, como verificação de tipo (verificação de erros de tipo), ou vinculação de objeto (associação de referências variáveis e função com suas definições), ou atribuição definida (requerendo que todas as variáveis locais sejam inicializadas antes de usar), rejeitando programas incorretos ou emissão de avisos. A análise semântica geralmente requer uma árvore de parse completa, o que significa que esta fase segue logicamente a fase de análise, e logicamente precede a fase de geração de código, embora muitas vezes seja possível dobrar várias fases em uma passagem sobre o código em uma implementação de compilador.

Meio-termo

O middle end, também conhecido como otimizador, realiza otimizações na representação intermediária para melhorar o desempenho e a qualidade do código de máquina produzido. A extremidade intermediária contém as otimizações que são independentes da arquitetura de CPU que está sendo direcionada.

As principais fases do meio-termo incluem o seguinte:

• Análise: Esta é a coleta de informações do programa da representação intermediária derivada da entrada; análise de fluxo de dados é usada para construir cadeias de definição de uso, juntamente com análise de dependência, análise de alias, análise de ponteiro, análise de fuga, etc. A análise precisa é a base para qualquer otimização do compilador. O gráfico de fluxo de controle de cada função compilada e o gráfico de chamadas do programa geralmente também são construídos durante a fase de análise.
• Otimização: a representação da linguagem intermediária é transformada em formas funcionalmente equivalentes, mas mais rápidas (ou menores). Otimizações populares são expansão inline, eliminação de código morto, propagação constante, transformação de loop e até mesmo paralelização automática.

A análise do compilador é o pré-requisito para qualquer otimização de compilador e eles trabalham juntos. Por exemplo, a análise de dependência é crucial para a transformação de loop.

O escopo da análise e otimizações do compilador varia muito; seu escopo pode variar desde a operação dentro de um bloco básico, até procedimentos inteiros, ou até mesmo o programa inteiro. Há uma compensação entre a granularidade das otimizações e o custo da compilação. Por exemplo, as otimizações peephole são rápidas de executar durante a compilação, mas afetam apenas um pequeno fragmento local do código e podem ser executadas independentemente do contexto em que o fragmento de código aparece. Por outro lado, a otimização interprocedural requer mais tempo de compilação e espaço de memória, mas permite otimizações que só são possíveis considerando o comportamento de várias funções simultaneamente.

Análise e otimizações interprocessuais são comuns em compiladores comerciais modernos da HP, IBM, SGI, Intel, Microsoft e Sun Microsystems. O software livre GCC foi criticado por muito tempo por carecer de otimizações interprocedimentais poderosas, mas está mudando a esse respeito. Outro compilador de código aberto com infraestrutura completa de análise e otimização é o Open64, que é usado por muitas organizações para fins comerciais e de pesquisa.

Devido ao tempo e espaço extras necessários para análise e otimizações do compilador, alguns compiladores os ignoram por padrão. Os usuários precisam usar as opções de compilação para informar explicitamente ao compilador quais otimizações devem ser habilitadas.

Back-end

O back-end é responsável pelas otimizações específicas da arquitetura da CPU e pela geração de código.

As principais fases do back-end incluem o seguinte:

• Otimizações dependentes de máquinas: otimizações que dependem dos detalhes da arquitetura da CPU que o compilador tem como alvo. Um exemplo proeminente é otimizações de peephole, que reescreve sequências curtas de instruções do montador em instruções mais eficientes.
• Geração de código: a linguagem intermediária transformada é traduzida para a linguagem de saída, geralmente a linguagem de máquina nativa do sistema. Isso envolve decisões de recursos e armazenamento, como decidir quais variáveis cabem em registros e memória e a seleção e agendamento de instruções apropriadas da máquina junto com seus modos de endereçamento associados (veja também o algoritmo Sethi-Ullman). Os dados de depuração também podem precisar ser gerados para facilitar a depuração.

Correção do compilador

A exatidão do compilador é o ramo da engenharia de software que trata de tentar mostrar que um compilador se comporta de acordo com sua especificação de linguagem. As técnicas incluem o desenvolvimento do compilador usando métodos formais e testes rigorosos (geralmente chamados de validação do compilador) em um compilador existente.

Linguagens compiladas versus interpretadas

Linguagens de programação de alto nível geralmente aparecem com um tipo de tradução em mente: projetada como linguagem compilada ou linguagem interpretada. No entanto, na prática, raramente há algo sobre uma linguagem que exija que ela seja exclusivamente compilada ou interpretada exclusivamente, embora seja possível projetar linguagens que dependem de reinterpretação em tempo de execução. A categorização geralmente reflete as implementações mais populares ou difundidas de uma linguagem - por exemplo, BASIC é algumas vezes chamada de linguagem interpretada, e C de linguagem compilada, apesar da existência de compiladores BASIC e interpretadores C.

A interpretação não substitui a compilação completamente. Ele apenas o esconde do usuário e o torna gradual. Mesmo que um interpretador possa ser interpretado, um conjunto de instruções de máquina executadas diretamente é necessário em algum lugar na parte inferior da pilha de execução (consulte linguagem de máquina).

Além disso, para otimização, os compiladores podem conter a funcionalidade do interpretador, e os interpretadores podem incluir técnicas de compilação antecipadas. Por exemplo, onde uma expressão pode ser executada durante a compilação e os resultados inseridos no programa de saída, isso evita que ela seja recalculada toda vez que o programa é executado, o que pode acelerar bastante o programa final. As tendências modernas de compilação just-in-time e interpretação de bytecode às vezes confundem ainda mais as categorizações tradicionais de compiladores e interpretadores.

Algumas especificações de linguagem especificam que as implementações devem incluir um recurso de compilação; por exemplo, Common Lisp. No entanto, não há nada inerente na definição de Common Lisp que o impeça de ser interpretado. Outras linguagens possuem recursos que são muito fáceis de implementar em um interpretador, mas tornam a escrita de um compilador muito mais difícil; por exemplo, APL, SNOBOL4 e muitas linguagens de script permitem que os programas construam código-fonte arbitrário em tempo de execução com operações de string regulares e, em seguida, executem esse código passando-o para uma função de avaliação especial. Para implementar esses recursos em uma linguagem compilada, os programas geralmente devem ser enviados com uma biblioteca de tempo de execução que inclua uma versão do próprio compilador.

Tipos

Uma classificação de compiladores é pela plataforma na qual o código gerado é executado. Isso é conhecido como a plataforma de destino.

Um compilador nativo ou hospedado é aquele cuja saída deve ser executada diretamente no mesmo tipo de computador e sistema operacional em que o próprio compilador é executado. A saída de um compilador cruzado é projetada para ser executada em uma plataforma diferente. Compiladores cruzados são frequentemente usados no desenvolvimento de software para sistemas embarcados que não se destinam a suportar um ambiente de desenvolvimento de software.

A saída de um compilador que produz código para uma máquina virtual (VM) pode ou não ser executada na mesma plataforma que o compilador que a produziu. Por esse motivo, esses compiladores geralmente não são classificados como compiladores nativos ou cruzados.

A linguagem de baixo nível que é o alvo de um compilador pode ser uma linguagem de programação de alto nível. C, visto por alguns como uma espécie de linguagem assembly portátil, é frequentemente a linguagem-alvo de tais compiladores. Por exemplo, Cfront, o compilador original para C++, usou C como sua linguagem-alvo. O código C gerado por tal compilador geralmente não se destina a ser legível e mantido por humanos, portanto, o estilo de indentação e a criação de um código C intermediário bonito são ignorados. Alguns dos recursos do C que o tornam um bom idioma de destino incluem a diretiva #line, que pode ser gerada pelo compilador para dar suporte à depuração do código-fonte original e o amplo suporte à plataforma disponível com os compiladores C.

Enquanto um tipo de compilador comum gera código de máquina, existem muitos outros tipos:

• Compiladores de origem a fonte são um tipo de compilador que leva uma linguagem de alto nível como sua entrada e produz uma linguagem de alto nível. Por exemplo, um compilador paralelizante automático frequentemente levará em um programa de linguagem de alto nível como uma entrada e, em seguida, transformará o código e anotá-lo-á com anotações de código paralelo (por exemplo, OpenMP) ou construções de linguagem (ex. DOALL declarações). Outros termos para um compilador de origem a fonte são transcompiladores ou transpiladores.
• Compiladores de Bytecode compilam a linguagem de montagem de uma máquina teórica, como algumas implementações Prolog
  • Esta máquina Prolog também é conhecida como a Warren Abstract Machine (ou WAM).
  • Compiladores Bytecode para Java, Python também são exemplos desta categoria.
• Compiladores (compilador JIT) deferem compilação até o tempo de execução. Compiladores JIT existem para muitos idiomas modernos, incluindo Python, JavaScript, Smalltalk, Java, Microsoft. Língua Intermediária Comum (CIL) e outros. Um compilador JIT geralmente é executado dentro de um intérprete. Quando o interpretador detecta que um caminho de código é "quente", o que significa que é executado frequentemente, o compilador JIT será invocado e compilar o código "quente" para o aumento do desempenho.
  • Para alguns idiomas, como Java, as aplicações são compiladas pela primeira vez usando um compilador de bytecode e entregues em uma representação intermediária independente de máquina. Um interpretador de bytecode executa o bytecode, mas o compilador JIT traduzirá o bytecode ao código da máquina quando o desempenho aumentado for necessário.
• Compiladores de hardware (também conhecidos como ferramentas de síntese) são compiladores cuja entrada é uma linguagem de descrição de hardware e cuja saída é uma descrição, na forma de uma netlist ou de outra forma, de uma configuração de hardware.
  • A saída desses compiladores visa o hardware do computador em um nível muito baixo, por exemplo, um array de portão programável de campo (FPGA) ou circuito integrado específico de aplicação estruturado (ASIC). Tais compiladores são ditos como compiladores de hardware, porque o código fonte que compilam efetivamente controla a configuração final do hardware e como ele funciona. A saída da compilação é apenas uma interconexão de transistores ou tabelas de pesquisa.
  • Um exemplo de compilador de hardware é XST, a Ferramenta de Sintese Xilinx usada para configurar FPGAs. Ferramentas semelhantes estão disponíveis a partir de Altera, Synplicity, Synopsys e outros fornecedores de hardware.
• Um Montador é um programa que compila linguagem de montagem legível humana ao código da máquina, as instruções reais executadas pelo hardware. O programa inverso que traduz o código da máquina para a linguagem de montagem é chamado de desmontagem.
• Um programa que se traduz de uma linguagem de baixo nível para um nível superior é um decompilador.
• Um programa que se traduz em um formato de código de objeto que não é suportado na máquina de compilação é chamado de compilador cruzado e é comumente usado para preparar o código para a execução em aplicativos de software embarcados.
• Um programa que reescreve o código de objeto de volta para o mesmo tipo de código de objeto ao aplicar otimizações e transformações é um recompilador binário.