Compilador - Compiler

Na computação , um compilador é um programa de computador que traduz o código de computador escrito em uma linguagem de programação (a linguagem de origem ) para outra linguagem (a linguagem de destino ). 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 nível inferior (por exemplo , linguagem assembly , código-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 no qual o compilador cruzado é executado. Um compilador de bootstrap é escrito na linguagem que pretende compilar. 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 ou transpilador de origem para origem . Um reescritor de linguagem geralmente é um programa que traduz a forma das expressões sem uma mudança de linguagem. Um compilador-compilador é um compilador que produz um compilador (ou parte de um).

Um compilador é susceptível de realizar alguns ou todos os seguintes operações, muitas vezes chamados de fases: pré-processamento , análise lexical , ao analisar , análise semântica ( tradução dirigida pela sintaxe ), conversão de programas de entrada para uma representação intermédia , optimização de código e de geração de código . Os compiladores geralmente implementam essas fases como componentes modulares, promovendo design eficiente e correção de 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 do compilador investem um esforço significativo para garantir a correção do compilador .

Compiladores não são o único processador de linguagem usado para transformar programas de origem. Um intérprete é um software de computador que transforma e, em seguida, executa as operações indicadas. O processo de tradução influencia o design das linguagens de computador, o que leva a uma preferência pela 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 um (um compilador ou um interpretador).

História

Um diagrama da operação de um compilador multi-linguagem e multi-destino típico

Os 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 de máquina subjacente. No final dos anos 1940, as linguagens assembly foram criadas para oferecer uma abstração mais funcional das arquiteturas de computador. A capacidade de memória limitada 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 de front-end produzem os produtos de análise usados ​​pelos programas de back-end para gerar o código de destino. À medida que a tecnologia do computador fornecia mais recursos, os designs do compilador podiam se alinhar melhor com o processo de compilação.

Normalmente, é mais produtivo para um programador usar uma linguagem de alto nível, de modo que o desenvolvimento de linguagens de alto nível se seguiu naturalmente aos recursos oferecidos pelos computadores digitais. Linguagens de alto nível são linguagens formais estritamente definidas por sua sintaxe e semântica que formam a arquitetura de 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;
  • Idioma , qualquer conjunto de strings em um alfabeto.

As sentenças em um idioma podem ser definidas por um conjunto de regras chamado gramática.

A forma Backus – Naur (BNF) descreve a sintaxe de "sentenças" de uma linguagem e foi usada 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 se tornaram ferramentas padrão para descrever a sintaxe de 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é os anos 1970, ele apresentou conceitos vistos posteriormente no APL projetado por Ken Iverson no final dos anos 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 de fórmulas) para aplicações em engenharia e ciências é considerada a primeira linguagem de alto nível.
  • COBOL (Common Business-Oriented Language) evoluiu de A-0 e FLOW-MATIC para se tornar a linguagem de alto nível dominante para aplicativos de negócios.
  • LISP (List Processor) para computação simbólica.

A tecnologia do compilador evoluiu da necessidade de uma transformação estritamente definida do programa de origem de alto nível em um programa de destino 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 de destino mais eficiente.

Alguns marcos iniciais no desenvolvimento da tecnologia do compilador:

  • 1952 : Um compilador Autocode desenvolvido por Alick Glennie para o computador Manchester Mark I na Universidade de Manchester é considerado por alguns como a primeira linguagem de programação compilada.
  • 1952 : A equipe de Grace Hopper na Remington Rand escreveu o compilador para a linguagem de programação A-0 (e cunhou o termo compilador para descrevê-la), embora o compilador A-0 funcionasse 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 linguagem de alto nível. Em 1957, eles completaram um compilador FORTRAN que geralmente é creditado como tendo introduzido o primeiro compilador inequivocamente completo.
  • 1959 : A Conferência sobre Linguagem de Sistemas de Dados (CODASYL) iniciou o desenvolvimento do COBOL . O projeto COBOL baseou-se em A-0 e FLOW-MATIC. No início dos anos 1960, o COBOL foi compilado em várias arquiteturas.
  • 1958–1962 : John McCarthy no MIT projetou o LISP . Os recursos de processamento de símbolo forneceram recursos úteis para a pesquisa de inteligência artificial. Em 1962, o lançamento do LISP 1.5 apresentou 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 software foram escritos em linguagem assembly. Na década de 1960 e no início da década de 1970, o uso de linguagens de alto nível para programação de sistema ainda era controverso devido às limitações de recursos. No entanto, vários esforços de pesquisa e da indústria começou a mudança para sistemas de alto nível linguagens de programação, por exemplo, BCPL , BLISS , B , e C .

BCPL (Basic Combined Programming Language) projetado em 1966 por Martin Richards na Universidade de Cambridge foi originalmente desenvolvido como uma ferramenta de escrita de compilador. Vários compiladores foram implementados, o livro de Richards fornece insights sobre a linguagem e seu compilador. BCPL não foi apenas uma linguagem de programação de sistemas influente que ainda é usada em pesquisas, mas também forneceu uma base para o projeto 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 Carnegie Mellon University (CMU) de WA Wulf. 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 compartilhamento de tempo, envolveu o MIT , Bell Labs , General Electric (mais tarde Honeywell ) e foi liderado por Fernando Corbató do MIT. Multics foi escrito na linguagem PL / I desenvolvida pela IBM e IBM User Group. O objetivo da IBM era satisfazer os requisitos de programação de negócios, científicos e de sistemas. Havia outras linguagens que poderiam ser consideradas, mas PL / I ofereceu a solução mais completa, embora não tenha sido implementada. Nos primeiros anos do projeto Multics, um subconjunto da linguagem pode ser compilado para a 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 boot para o PL / I completo pudesse ser desenvolvido.

Bell Labs deixou o projeto Multics em 1969: "Com o tempo, a esperança foi substituída pela frustração, pois o esforço do grupo inicialmente falhou em produzir um sistema economicamente útil." A participação contínua aumentaria os custos de suporte do projeto. Portanto, os pesquisadores se voltaram para outros esforços de desenvolvimento. Uma linguagem de programação de sistema B baseada em conceitos BCPL foi escrita por Dennis Ritchie e Ken Thompson . Ritchie criou um compilador de inicialização para B e escreveu o sistema operacional Unics (Uniplexed Information and Computing Service) para um PDP-7 em B. Unics eventualmente se tornou Unix.

Bell Labs iniciou o desenvolvimento e expansão de C com base em B e BCPL. O compilador BCPL foi transportado para Multics pela Bell Labs e BCPL era a linguagem preferida na Bell Labs. Inicialmente, um programa front-end para o compilador B da Bell Labs foi usado enquanto um compilador C era 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 Compilador C Portátil (PCC) para suportar o redirecionamento de compiladores C para novas máquinas.

A programação orientada a objetos (OOP) ofereceu algumas possibilidades interessantes para o desenvolvimento e manutenção de aplicativos. Os conceitos de OOP são mais antigos, mas faziam parte do LISP e da ciência da linguagem Simula . Na Bell Labs, o desenvolvimento de C ++ tornou-se interessado em OOP. C ++ foi usado pela primeira vez em 1980 para programação de sistemas. O projeto inicial aproveitou os recursos de programação de sistemas em 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 da linguagem C84. Nos anos subsequentes, vários compiladores C ++ foram desenvolvidos à medida que a popularidade do C ++ crescia.

Em muitos domínios de aplicativo, a ideia de usar uma linguagem de nível superior rapidamente pegou. 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 do destino. O PQCC tentou estender o termo compilador-compilador além do significado tradicional como um gerador de analisador (por exemplo, Yacc ) sem muito sucesso. O PQCC pode ser mais apropriadamente conhecido como gerador de compilador.

A pesquisa do PQCC no processo de geração de código buscou 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 máquina virtual (middle end) e tradução para o destino (back end). TCOL foi desenvolvido para a pesquisa PQCC para lidar com construções específicas da linguagem na representação intermediária. Variações de TCOL suportavam vários idiomas. O projeto PQCC investigou técnicas de construção de compiladores automatizados. Os conceitos de design provaram ser úteis na otimização de compiladores e compiladores para a linguagem de programação 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 Ada da NYU / ED apoiou os 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 ao longo das 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 começou no 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 de 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. 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 direcionadas ao Motorola 68020 em uma avaliação do 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 a GNU Compiler Collection (GCC), que fornece uma capacidade central para suportar vários idiomas e destinos. A versão Ada GNAT é um dos compiladores Ada mais usados. GNAT é gratuito, mas também há suporte comercial, por exemplo, AdaCore, foi fundada em 1994 para fornecer soluções de software comerciais para Ada. GNAT Pro inclui o GNU GCC baseado em GNAT 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 do compilador. As áreas de foco incluíram otimização e geração automática de código. Tendências em linguagens de programação e ambientes de desenvolvimento influenciaram a tecnologia do compilador. Mais compiladores foram incluídos nas distribuições de linguagem (PERL, Java Development Kit) e como um componente de um IDE (VADS, Eclipse, Ada Pro). A inter-relação e interdependência das tecnologias cresceu. 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 do User Shell desenvolvidos com linguagens para escrever programas shell. Os primeiros designs do Windows ofereciam uma capacidade de programação em lote simples. A transformação convencional dessa linguagem 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 do desenvolvedor. Linguagens de script modernas incluem PHP, Python, Ruby e Lua. (Lua é amplamente usada no desenvolvimento de jogos.) Todos eles têm suporte para interpretador e compilador.

"Quando o campo da compilação começou no final dos anos 50, seu foco estava 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 entrelaçado com outras disciplinas, incluindo arquitetura de computador, linguagens de programação, métodos formais, engenharia de software e segurança de computador. " O artigo "Pesquisa do compilador: os próximos 50 anos" observou a importância das linguagens orientadas a objetos e do Java. Segurança e computação paralela foram citadas entre os alvos de pesquisas futuras.

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 projeto do compilador pode definir uma solução ponta a ponta ou lidar com um subconjunto definido que faz interface com outras ferramentas de compilação, por exemplo, pré-processadores, montadores, linkers. Os requisitos de design incluem interfaces rigorosamente definidas tanto internamente entre os componentes do compilador quanto 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 de computador a ser processada, pela experiência da (s) pessoa (s) que a projetava 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 a complexidade do idioma de origem aumenta, o projeto pode ser dividido em várias fases interdependentes. Fases separadas fornecem melhorias de design que focam o desenvolvimento nas funções do processo de compilação.

Compiladores one-pass versus multi-pass

A classificação de compiladores pelo número de passagens tem como pano de fundo as limitações de recursos de hardware dos computadores. Compilar 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 fazendo uma passagem sobre a fonte (ou alguma representação dela), realizando algumas das análises e traduções necessárias.

A capacidade de compilar em uma única passagem classicamente foi vista como um benefício porque simplifica o trabalho de escrever um compilador e os compiladores de uma passagem geralmente executam compilações mais rápido do que os compiladores de várias passagens . Assim, parcialmente impulsionadas pelas limitações de recursos dos sistemas anteriores, muitas linguagens iniciais 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 sobre o 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. Neste caso, a primeira passagem precisa reunir informações sobre as declarações que aparecem após as declarações que afetam, com a tradução real acontecendo durante uma passagem subsequente.

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 muitas vezes, mas analisar outra expressão apenas 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

Projeto do compilador

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

  • O front end examina a entrada e verifica a sintaxe e a semântica de acordo com um idioma de origem específico. Para linguagens tipadas estaticamente, ele executa a verificação de tipo coletando informações de tipo. Se o programa de entrada estiver sintaticamente incorreto ou tiver um erro de tipo, ele gera mensagens de erro e / ou advertência, geralmente identificando o local no código-fonte onde o problema foi detectado; em alguns casos, o erro real pode ser (muito) anterior no programa. Aspectos do front-end incluem análise lexical, análise de sintaxe e análise semântica. O front end transforma o programa de entrada em uma representação intermediária (IR) para processamento posterior pelo middle end. Este IR é geralmente uma representação de nível inferior do programa em relação ao código-fonte.
  • A extremidade intermediária executa otimizações no IR que são independentes da arquitetura de CPU que está sendo direcionada. Essa independência de código-fonte / código de máquina tem o objetivo de permitir que otimizações genéricas sejam compartilhadas entre as versões do compilador que oferecem suporte a diferentes linguagens e processadores de destino. Exemplos de otimizações intermediárias são a remoção de código inútil ( eliminação de código morto ) ou inacessível ( análise de acessibilidade ), descoberta e propagação de valores constantes ( propagação constante ), realocação de computação para um local executado com menos frequência (por exemplo, fora de um loop) , ou especialização de computação com base no contexto. Eventualmente produzindo o IR "otimizado" que é usado pelo back-end.
  • O back-end pega o IR otimizado do meio. Ele pode realizar mais análises, transformações e otimizações que são específicas para a arquitetura de CPU de destino. O backend gera o código de montagem dependente do destino, realizando a alocação de registro no processo. O backend executa o agendamento de instruções , que reordena as instruções para manter as unidades de execução paralela ocupadas, preenchendo os slots de atraso . Embora a maioria dos problemas de otimização sejam NP-difíceis , as técnicas heurísticas para resolvê-los são bem desenvolvidas e atualmente implementadas em compiladores de qualidade de produção. Normalmente, a saída de um back end é um código de máquina especializado para um determinado processador e sistema operacional.

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

A parte dianteira

Léxico e analisador 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 , literal de número ou operador . A última seqüência é transformada pelo analisador em uma árvore de sintaxe , que é então tratada pelas fases restantes do compilador. O scanner e o analisador tratam das partes regulares e 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 front-end 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 front-end é dividido em três fases: análise lexical (também conhecida como lexing ou varredura), análise de sintaxe (também conhecida como varredura ou análise) e análise semântica . Lexing e parsing compreendem a análise sintática (sintaxe de palavra e sintaxe de frase, respectivamente), e em casos simples, esses módulos (o lexer e analisador) podem ser gerados automaticamente a partir de uma gramática para a linguagem, embora em casos mais complexos eles exijam modificação manual . A gramática lexical e a gramática de frase são geralmente gramáticas livres de contexto , o que simplifica a análise significativamente, 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 parcial ou totalmente automatizada usando gramáticas de atributos . Essas fases em si podem ser divididas ainda mais: lexing como varredura e avaliação e análise sintática como 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 e pré - processamento da linha , mas são raras.

As principais fases do front end incluem o seguinte:

  • A reconstrução de linha converte a sequência de caracteres de entrada em uma forma canônica pronta para o analisador. Linguagens queeliminamsuas palavras-chave ou permitem espaços arbitrários nos identificadores exigem essa fase. Osanalisadores decima para baixo,de descida recursiva ebaseados em tabela usados ​​na década de 1960, normalmente liam a origem um caractere por vez e não exigiam uma fase de tokenização separada. Atlas AutocodeeImp(e algumas implementações deALGOLeCoral 66) são exemplos de linguagens stropped cujos compiladores teriam umafase deReconstrução de Linha.
  • O pré-processamento suportasubstituição de macro e compilação condicional . Normalmente, 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 tokens lexicais em vez de formas sintáticas. No entanto, algumas linguagens, como Scheme, oferecem suporte a substituições de macro com base em formas sintáticas.
  • A análise lexical (também conhecida como lexing ou tokenização ) divide o texto do código-fonte em uma sequência de pequenos pedaços chamados tokens lexicais . Essa fase pode ser dividida em dois estágios: a varredura , que segmenta o texto de entrada em unidades sintáticas chamadas lexemas e atribui a elas uma categoria; e a avaliação , que converte lexemas em um valor processado. Um token é um par que consiste em um nome de token e um valor de token opcional. As categorias de tokens comuns podem incluir identificadores, palavras-chave, separadores, operadores, literais e comentários, embora o conjunto de categorias de tokens varie em diferentes linguagens de programação . A sintaxe do lexema é tipicamente uma linguagem regular , portanto, um autômato de estado finito construído a partir de uma expressão regular pode ser usado para reconhecê-la. O software que faz a 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 , caso em que a análise é feita no nível do personagem, não no nível do token.
  • A análise de sintaxe (também conhecida como análise ) envolve a análise da sequência de token para identificar a estrutura sintática do programa. Esta fase normalmente constrói uma árvore de análise , que substitui a sequência linear de tokens por 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 análise geralmente é analisada, aumentada e transformada por fases posteriores no compilador.
  • A análise semântica adiciona informações semânticas à árvore de análise 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 de variáveis ​​e funções com suas definições) ou atribuição definitiva (exigindo que todas as variáveis ​​locais sejam inicializadas antes do uso), rejeitando programas incorretos ou emitindo avisos. A análise semântica geralmente requer uma árvore de análise completa, o que significa que esta fase segue logicamente afase de análise e logicamente precede afase de geração de código , embora seja frequentemente possível dobrar várias fases em uma passagem sobre o código em uma implementação de compilador.

Fim do meio

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:

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

O escopo da análise e otimizações do compilador variam muito; seu escopo pode variar de operar dentro de um bloco básico , a procedimentos inteiros, ou mesmo a todo o programa. Há uma compensação entre a granularidade das otimizações e o custo da compilação. Por exemplo, as otimizações de olho mágico 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. Em contraste, 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.

A análise e otimizações interpretativas 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 interprocedurais poderosas, mas está mudando a este 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 a 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.

Processo interno

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 da máquina : otimizações que dependem dos detalhes da arquitetura da CPU que o compilador visa. Um exemplo proeminente são as otimizações de olho mágico , 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 nativado sistema. Isso envolve decisões de recursos e armazenamento, como decidir quais variáveis ​​caber nos registros e na memória e a seleção e agendamento de instruções de máquina apropriadas junto com seus modos de endereçamento associados(consulte 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 correção do compilador é o ramo da engenharia de software que trata de tentar mostrar que um compilador se comporta de acordo com a especificação de sua 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

As linguagens de programação de nível superior 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 às vezes é chamada de linguagem interpretada e C compilada, apesar da existência de compiladores BASIC e interpretadores C.

A interpretação não substitui completamente a compilação. Ele apenas o oculta do usuário e o torna gradual. Mesmo que um intérprete possa ser interpretado, um programa executado diretamente é necessário em algum lugar na parte inferior da pilha de execução (consulte a linguagem de máquina ).

Além disso, para otimização, os compiladores podem conter funcionalidade de intérprete e os intérpretes podem incluir técnicas de compilação antecipadas. Por exemplo, quando uma expressão pode ser executada durante a compilação e os resultados inseridos no programa de saída, evita que seja necessário recalculá-la toda vez que o programa for executado, o que pode acelerar bastante o programa final. As tendências modernas em direção à 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 explicam que as implementações devem incluir um recurso de compilação; por exemplo, Common Lisp . No entanto, não há nada inerente à definição de Common Lisp que o impeça de ser interpretado. Outras linguagens têm 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 fornecidos com uma biblioteca de tempo de execução que inclui uma versão do próprio compilador.

Tipos

Uma classificação de compiladores é pela plataforma em que seu código gerado é executado. Isso é conhecido como plataforma de destino.

Um compilador nativo ou hospedado é aquele cuja saída se destina a ser executado 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 freqüentemente usados ​​ao desenvolver software para sistemas embarcados que não se destinam a oferecer suporte a 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 do compilador que a produziu. Por esse motivo, esses compiladores geralmente não são classificados como compiladores nativos ou cruzados.

A linguagem de nível inferior que é o destino 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 ++ , usava C como sua linguagem de destino. O código C gerado por tal compilador geralmente não se destina a ser lido e mantido por humanos, portanto, o estilo de indentação e a criação de um código intermediário em C são ignorados. Alguns dos recursos do C que o tornam uma boa linguagem de destino incluem a #linediretiva, que pode ser gerada pelo compilador para suportar a depuração da fonte original, e o amplo suporte de plataforma disponível com compiladores C.

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

  • Compiladores de código-fonte são um tipo de compilador que usa uma linguagem de alto nível como entrada e produz uma linguagem de alto nível. Por exemplo, um compilador automático de paralelização freqüentemente tomará um programa de linguagem de alto nível como uma entrada e, em seguida, transformará o código e fará anotações nele com anotações de código paralelas (por exemplo, OpenMP ) ou construções de linguagem (por exemplo, DOALLdeclarações de Fortran ). Outros termos para compiladores de origem para origem são tradutor de linguagem, conversor de linguagem ou reescritor de linguagem . O último termo é geralmente aplicado a traduções que não envolvem uma mudança de idioma.
  • Compiladores de bytecode compilam para linguagem assembly de uma máquina teórica, como algumas implementações de Prolog
    • Esta máquina Prolog também é conhecida como Warren Abstract Machine (ou WAM).
    • Compiladores de bytecode para Java , Python também são exemplos desta categoria.
  • Compiladores just -in-time (compilador JIT) adiam a compilação até o tempo de execução. Existem compiladores JIT para muitas línguas modernas, incluindo Python , JavaScript , Smalltalk , Java , Microsoft .NET da Common Intermediate Language (CIL) e outros. Um compilador JIT geralmente é executado dentro de um interpretador. Quando o interpretador detecta que um caminho de código é "quente", o que significa que é executado com frequência, o compilador JIT será chamado e compilará o código "quente" para aumentar o desempenho.
    • Para algumas linguagens, como Java, os aplicativos são compilados primeiro usando um compilador de bytecode e entregues em uma representação intermediária independente da máquina . Um interpretador de bytecode executa o bytecode, mas o compilador JIT irá traduzir o bytecode em código de máquina quando for necessário um melhor desempenho.
  • 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 é direcionada ao hardware de computador em um nível muito baixo, por exemplo, um field-programmable gate array (FPGA) ou um circuito integrado específico de aplicativo estruturado (ASIC). Esses compiladores são chamados de compiladores de hardware, porque o código-fonte que eles compilam controla efetivamente a configuração final do hardware e como ele opera. A saída da compilação é apenas uma interconexão de transistores ou tabelas de pesquisa .
    • Um exemplo de compilador de hardware é o XST, a ferramenta de síntese Xilinx usada para configurar FPGAs. Ferramentas semelhantes estão disponíveis na Altera, Synplicity, Synopsys e outros fornecedores de hardware.
  • Um montador é um programa que compila a linguagem assembly legível por humanos em código de máquina , as instruções reais executadas pelo hardware. O programa inverso que traduz o código de máquina em linguagem assembly é chamado de desmontador .
  • Um programa que traduz de uma linguagem de baixo nível para uma de nível superior é um descompilador .
  • 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 código para aplicativos incorporados.
  • Um programa que reescreve o código do objeto de volta no mesmo tipo de código do objeto enquanto aplica otimizações e transformações é um recompilador binário .

Veja também

Referências

Leitura adicional

links externos