História da construção do compilador - History of compiler construction

Na computação , um compilador é um programa de computador que transforma o código-fonte escrito em uma linguagem de programação ou linguagem de computador (a linguagem de origem ), em outra linguagem de computador (a linguagem de destino , muitas vezes tendo uma forma binária conhecida como código-objeto ou código de máquina ). O motivo mais comum para transformar o código-fonte é criar um programa executável .

Qualquer programa escrito em uma linguagem de programação de alto nível deve ser traduzido em código-objeto antes de ser executado, portanto, todos os programadores que usam essa linguagem usam um compilador ou um interpretador . Portanto, os compiladores são muito importantes para os programadores. Aprimoramentos em um compilador podem levar a um grande número de recursos aprimorados em programas executáveis.

O Production Quality Compiler-Compiler , no final dos anos 1970, introduziu os princípios de organização do compilador que ainda são amplamente usados ​​hoje (por exemplo, uma sintaxe e semântica de manipulação de front-end e um back-end de geração de código de máquina).

Primeiros compiladores

O software para os primeiros computadores foi escrito principalmente em linguagem assembly e, antes disso, diretamente em código de máquina . Normalmente, é mais produtivo para um programador usar uma linguagem de alto nível, e os programas escritos em uma linguagem de alto nível podem ser reutilizados em diferentes tipos de computadores . Mesmo assim, demorou um pouco para os compiladores se estabelecerem, porque eles geravam código que não funcionava tão bem quanto um assembler escrito à mão, eram projetos de desenvolvimento assustadores por si próprios e a capacidade de memória muito limitada dos primeiros computadores criou muitos problemas técnicos para implementações práticas de compiladores.

O primeiro compilador prático foi escrito por Corrado Böhm , em 1951, para sua tese de doutorado . O primeiro compilador implementado foi escrito por Grace Hopper , que também cunhou o termo "compilador", referindo-se ao seu sistema A-0 que funcionava como um carregador ou linker , não a noção moderna de um compilador. O primeiro Autocode e compilador no sentido moderno foram desenvolvidos por Alick Glennie em 1952 na Universidade de Manchester para o computador Mark 1 . A equipe FORTRAN liderada por John W. Backus na IBM apresentou o primeiro compilador disponível comercialmente, em 1957, que levou 18 anos-pessoa para ser criado.

O primeiro compilador ALGOL 58 foi concluído no final de 1958 por Friedrich L. Bauer , Hermann Bottenbruch, Heinz Rutishauser e Klaus Samelson para o computador Z22 . Bauer et al. tinha trabalhado na tecnologia de compilador para o Sequentielle Formelübersetzung (isto é, tradução de fórmula sequencial ) nos anos anteriores.

Em 1960, um compilador Fortran estendido, ALTAC, estava disponível no Philco 2000, portanto, é provável que um programa Fortran tenha sido compilado para as arquiteturas de computador IBM e Philco em meados de 1960. A primeira linguagem de alto nível de plataforma cruzada demonstrada conhecida foi COBOL . Em uma demonstração em dezembro de 1960, um programa COBOL foi compilado e executado no UNIVAC II e no RCA 501.

Compiladores de auto-hospedagem

Como qualquer outro software, há benefícios em implementar um compilador em uma linguagem de alto nível. Em particular, um compilador pode ser auto-hospedado - isto é, escrito na linguagem de programação que ele compila. Construir um compilador self-hosting é um problema de bootstrap , isto é, o primeiro compilador para uma linguagem deve ser um código de máquina escrito à mão ou compilado por um compilador escrito em outra linguagem, ou compilado executando o compilador em um interpretador .

Corrado Böhm Dissertação de Doutorado

Corrado Böhm desenvolveu uma linguagem, uma máquina e um método de tradução para compilar essa linguagem na máquina em sua dissertação de doutorado de 1951. Ele não apenas descreveu um compilador completo, mas também definiu pela primeira vez esse compilador em sua própria linguagem. A linguagem era interessante em si mesma, porque cada instrução (incluindo instruções de entrada, instruções de saída e instruções de controle) era um caso especial de instrução de atribuição .

NELIAC

O Compilador ALGOL Internacional do Laboratório de Eletrônica da Marinha ou NELIAC foi um dialeto e uma implementação do compilador da linguagem de programação ALGOL 58 desenvolvida pelo Laboratório de Eletrônica Naval em 1958.

O NELIAC foi ideia de Harry Huskey - então presidente da ACM e um conhecido cientista da computação (e posteriormente supervisor acadêmico de Niklaus Wirth ), e apoiado por Maury Halstead, chefe do centro computacional da NEL. A versão mais antiga foi implementada no computador protótipo USQ-17 (chamado de Condessa) no laboratório. Foi o primeiro compilador autocompilável do mundo - o compilador foi primeiro codificado de forma simplificada em linguagem assembly (o bootstrap ), depois reescrito em sua própria linguagem e compilado pelo bootstrap e, finalmente, recompilado por si mesmo, tornando o bootstrap obsoleto.

Lisp

Outro compilador de auto-hospedagem inicial foi escrito para Lisp por Tim Hart e Mike Levin no MIT em 1962. Eles escreveram um compilador Lisp em Lisp, testando-o dentro de um interpretador Lisp existente. Depois que eles aprimoraram o compilador a ponto de poder compilar seu próprio código-fonte, ele passou a se hospedar sozinho.

O compilador, conforme existe na fita do compilador padrão, é um programa em linguagem de máquina que foi obtido fazendo com que a definição da expressão S do compilador trabalhasse em si mesma por meio do interpretador. (AI Memo 39)

Esta técnica só é possível quando já existe um intérprete para a mesma linguagem a ser compilada. Ele toma emprestado diretamente da noção de executar um programa em si mesmo como entrada, que também é usada em várias provas na ciência da computação teórica , como a prova de que o problema da parada é indecidível .

Adiante

Forth é um exemplo de compilador self-hosting. Os recursos de autocompilação e compilação cruzada do Forth são comumente confundidos com metacompilação e metacompiladores . Como Lisp , Forth é uma linguagem de programação extensível . São os recursos de linguagem de programação extensível de Forth e Lisp que os permitem gerar novas versões de si mesmos ou se portar para novos ambientes.

Gramáticas e analisadores livres de contexto

Um analisador é um componente importante de um compilador. Ele analisa o código-fonte de uma linguagem de programação de computador para criar alguma forma de representação interna. As linguagens de programação tendem a ser especificadas em termos de uma gramática livre de contexto porque analisadores rápidos e eficientes podem ser escritos para elas. Os analisadores podem ser escritos manualmente ou gerados por um gerador de analisador . Uma gramática livre de contexto fornece um mecanismo simples e preciso para descrever como as construções da linguagem de programação são construídas a partir de blocos menores . O formalismo das gramáticas livres de contexto foi desenvolvido em meados da década de 1950 por Noam Chomsky .

A estrutura de blocos foi introduzida nas linguagens de programação de computador pelo projeto ALGOL (1957–1960), que, como consequência, também apresentou uma gramática livre de contexto para descrever a sintaxe ALGOL resultante.

Gramáticas livres de contexto são simples o suficiente para permitir a construção de algoritmos de análise eficientes que, para uma determinada string, determinam se e como ela pode ser gerada a partir da gramática. Se um designer de linguagem de programação está disposto a trabalhar dentro de alguns subconjuntos limitados de gramáticas livres de contexto, analisadores mais eficientes são possíveis.

Análise LR

O analisador LR (da esquerda para a direita) foi inventado por Donald Knuth em 1965 em um artigo, "On the Translation of Languages ​​from Left to Right". Um analisador LR é um analisador que lê a entrada de L EFT para a direita (como apareceria se visualmente exibido) e produz um R derivação ightmost . O termo analisador LR ( k ) também é usado, onde k se refere ao número de símbolos de entrada lookahead não consumidos que são usados ​​na tomada de decisões de análise.

Knuth provou que as gramáticas LR ( k ) podem ser analisadas com um tempo de execução essencialmente proporcional ao comprimento do programa, e que toda gramática LR ( k ) para k  > 1 pode ser transformada mecanicamente em uma gramática LR (1) para o mesmo língua. Em outras palavras, é necessário apenas ter um símbolo antecipado para analisar qualquer gramática livre de contexto determinística (DCFG).

Korenjak (1969) foi o primeiro a mostrar que analisadores para linguagens de programação poderiam ser produzidos usando essas técnicas. Frank DeRemer desenvolveu as técnicas mais práticas Simple LR (SLR) e Look-ahead LR (LALR), publicadas em sua dissertação de doutorado no MIT em 1969. Esse foi um avanço importante, porque os tradutores LR (k), conforme definido por Donald Knuth, eram grandes demais para implementação em sistemas de computador nas décadas de 1960 e 1970.

Na prática, o LALR oferece uma boa solução; o poder adicionado dos analisadores LALR (1) sobre os analisadores SLR (1) (ou seja, LALR (1) pode analisar gramáticas mais complexas do que SLR (1)) é útil e, embora LALR (1) não seja comparável com LL ( 1) (Veja abaixo) (LALR (1) não pode analisar todas as gramáticas LL (1)), a maioria das gramáticas LL (1) encontradas na prática podem ser analisadas por LALR (1). As gramáticas LR (1) são mais poderosas novamente do que LALR (1); entretanto, uma gramática LR (1) requer um analisador LR canônico que seria extremamente grande em tamanho e não é considerado prático. A sintaxe de muitas linguagens de programação é definida por gramáticas que podem ser analisadas com um analisador LALR (1) e, por essa razão, os analisadores LALR são frequentemente usados ​​por compiladores para realizar a análise de sintaxe do código-fonte.

Um analisador de subida recursivo implementa um analisador LALR usando funções mutuamente recursivas em vez de tabelas. Assim, o analisador é codificado diretamente na linguagem hospedeira semelhante à descendência recursiva . A codificação direta geralmente produz um analisador que é mais rápido do que seu equivalente baseado em tabela pela mesma razão que a compilação é mais rápida do que a interpretação. Também é (em princípio) possível editar manualmente um analisador de subida recursivo, enquanto uma implementação tabular é quase ilegível para o ser humano médio.

A ascensão recursiva foi descrita pela primeira vez por Thomas Pennello em seu artigo "Análise LR muito rápida" em 1986. A técnica foi posteriormente exposta por GH Roberts em 1988, bem como em um artigo de Leermakers, Augusteijn, Kruseman Aretz em 1992 na revista Theoretical Ciência da Computação .

Análise LL

Um analisador LL analisa a entrada a partir de L eft para a direita, e constrói um L derivação eftmost da frase (daí LL, em oposição a LR). A classe de gramáticas analisáveis ​​dessa maneira é conhecida como gramáticas LL . As gramáticas LL são uma classe ainda mais restrita de gramáticas livres de contexto do que as gramáticas LR. No entanto, eles são de grande interesse para os escritores de compiladores, porque tal analisador é simples e eficiente de implementar.

Gramáticas LL (k) podem ser analisadas por um analisador descendente recursivo que geralmente é codificado à mão, embora uma notação como META II possa ser usada como alternativa.

O projeto do ALGOL desencadeou a investigação da descendência recursiva, uma vez que a própria linguagem ALGOL é recursiva. O conceito de análise descendente recursiva foi discutido na edição de janeiro de 1961 da Communications of the ACM em documentos separados por AA Grau e Edgar T. "Ned" Irons . Richard Waychoff e colegas também implementaram a descida recursiva no compilador Burroughs ALGOL em março de 1961; os dois grupos usaram abordagens diferentes, mas estavam pelo menos em contato informal.

A ideia de gramáticas LL (1) foi introduzida por Lewis e Stearns (1968).

A descendência recursiva foi popularizada por Niklaus Wirth com PL / 0 , uma linguagem de programação educacional usada para ensinar a construção de compiladores na década de 1970.

A análise LR pode lidar com uma gama maior de linguagens do que a análise LL e também é melhor no relatório de erros (isso é contestável, REFERÊNCIA é necessária), ou seja, detecta erros sintáticos quando a entrada não está em conformidade com a gramática o mais rápido possível.

Earley parser

Em 1970, Jay Earley inventou o que ficou conhecido como parser Earley . Os analisadores Earley são atraentes porque podem analisar todas as linguagens livres de contexto de maneira razoavelmente eficiente.

Linguagens de descrição gramatical

John Backus propôs "fórmulas metalinguísticas" para descrever a sintaxe da nova linguagem de programação IAL, hoje conhecida como ALGOL 58 (1959). O trabalho de Backus foi baseado no sistema canônico Post desenvolvido por Emil Post .

O desenvolvimento posterior do ALGOL levou ao ALGOL 60 ; em seu relatório (1963), Peter Naur nomeou a notação Backus de forma normal (BNF) de Backus e a simplificou para minimizar o conjunto de caracteres usado. No entanto, Donald Knuth argumentou que o BNF deveria ser lido como forma Backus-Naur , e esse se tornou o uso comumente aceito.

Niklaus Wirth definiu a forma Backus – Naur estendida (EBNF), uma versão refinada do BNF, no início dos anos 1970 para PL / 0. A forma Backus-Naur aumentada (ABNF) é outra variante. EBNF e ABNF são amplamente usados ​​para especificar a gramática de linguagens de programação, como entradas para geradores de analisador e em outros campos, como definição de protocolos de comunicação.

Geradores de analisador

Um gerador de analisador gera a parte do analisador léxico de um compilador. É um programa que pega uma descrição de uma gramática formal de uma linguagem de programação específica e produz um analisador para essa linguagem. Esse analisador pode ser usado em um compilador para aquela linguagem específica. O analisador detecta e identifica as palavras reservadas e os símbolos do idioma específico de um fluxo de texto e os retorna como tokens para o código que implementa a validação sintática e a tradução em código-objeto. Esta segunda parte do compilador também pode ser criada por um compilador-compilador usando uma descrição de sintaxe de regras de precedência formal como entrada.

O primeiro compilador-compilador a usar esse nome foi escrito por Tony Brooker em 1960 e foi usado para criar compiladores para o computador Atlas na Universidade de Manchester , incluindo o compilador Atlas Autocode . No entanto, era um pouco diferente dos compiladores-compiladores modernos e hoje provavelmente seria descrito como algo entre um compilador genérico altamente personalizável e uma linguagem de sintaxe extensível . O nome "compilador-compilador" era muito mais apropriado para o sistema de Brooker do que para a maioria dos compiladores-compiladores modernos, que são descritos com mais precisão como geradores de analisador. É quase certo que o nome "Compilador-Compilador" entrou em uso comum devido ao Yacc, e não ao trabalho de Brooker sendo lembrado.

No início dos anos 1960, Robert McClure, da Texas Instruments, inventou um compilador-compilador chamado TMG , nome tirado de "transmogrificação". Nos anos seguintes, o TMG foi portado para vários computadores mainframe UNIVAC e IBM.

O projeto Multics , uma joint venture entre o MIT e a Bell Labs , foi um dos primeiros a desenvolver um sistema operacional em uma linguagem de alto nível. PL / I foi escolhido como a linguagem, mas um fornecedor externo não pôde fornecer um compilador funcional. A equipe Multics desenvolveu seu próprio subconjunto de dialeto de PL / I conhecido como Early PL / I (EPL) como sua linguagem de implementação em 1964. TMG foi portado para a série GE-600 e usado para desenvolver EPL por Douglas McIlroy , Robert Morris e outros .

Não muito depois de Ken Thompson escrever a primeira versão do Unix para o PDP-7 em 1969, Douglas McIlroy criou a primeira linguagem de nível superior do novo sistema: uma implementação do TMG de McClure. TMG também foi a ferramenta definição compilador usado por Ken Thompson para escrever o compilador para a linguagem B em seu PDP-7 em 1970. B foi o ancestral imediato de C .

Um dos primeiros geradores de analisador LALR era chamado de "TWS", criado por Frank DeRemer e Tom Pennello.

XPL

XPL é um dialeto da linguagem de programação PL / I , usado para o desenvolvimento de compiladores para linguagens de computador. Ele foi projetado e implementado em 1967 por uma equipe com William M. McKeeman , James J. Horning e David B. Wortman na Universidade de Stanford e na Universidade da Califórnia, Santa Cruz . Foi anunciado pela primeira vez na Fall Joint Computer Conference de 1968 , em San Francisco.

XPL apresentou um sistema de escrita de tradutor relativamente simples denominado ANALYZER , baseado em uma técnica de análise de precedência de compilador de baixo para cima chamada MSP (precedência de estratégia mista). XPL foi inicializado através de Burroughs Algol no computador IBM System / 360 . (Algumas versões subsequentes de XPL usadas em projetos internos da Universidade de Toronto utilizaram um analisador SLR (1), mas essas implementações nunca foram distribuídas).

Yacc

Yacc é um gerador de parser (vagamente, compilador-compilador ), não deve ser confundido com lex , que é um analisador léxico freqüentemente usado como um primeiro estágio pelo Yacc. Yacc foi desenvolvido por Stephen C. Johnson na AT&T para o sistema operacional Unix . O nome é um acrônimo para " Yet Another Compiler Compiler ". Ele gera um compilador LALR (1) baseado em uma gramática escrita em uma notação semelhante à forma Backus – Naur.

Johnson trabalhou no Yacc no início dos anos 1970 no Bell Labs . Ele estava familiarizado com TMG e sua influência pode ser vista no Yacc e no design da linguagem de programação C. Como o Yacc era o gerador de compilador padrão na maioria dos sistemas Unix, ele foi amplamente distribuído e usado. Derivados como GNU Bison ainda estão em uso.

O compilador gerado pelo Yacc requer um analisador léxico . Geradores de analisadores lexicais, como lex ou flex estão amplamente disponíveis. O padrão IEEE POSIX P1003.2 define a funcionalidade e os requisitos para Lex e Yacc.

Coco / R

Coco / R é um gerador de analisador que gera analisadores LL (1) em Modula-2 (com plug-ins para outras linguagens) a partir de gramáticas de entrada escritas em uma variante de EBNF. Foi desenvolvido por Hanspeter Mössenböck no Instituto Federal Suíço de Tecnologia em Zurique (ETHZ) em 1985.

ANTLR

ANTLR é um gerador de analisador que gera analisadores LL (*) em Java a partir de gramáticas de entrada escritas em uma variante de EBNF. Ele foi desenvolvido por Terence Parr na Universidade de San Francisco no início de 1990 como um sucessor de um gerador anterior chamado PCCTS.

Metacompiladores

Os metacompiladores diferem dos geradores de analisador, tomando como entrada um programa escrito em uma metalinguagem . Sua entrada consiste em fórmulas de análise gramatical combinadas com operações de transformação incorporadas que constroem árvores de sintaxe abstratas ou simplesmente geram strings de texto reformatadas que podem ser códigos de máquina de pilha.

Muitos podem ser programados em sua própria metalinguagem, permitindo que eles se compilem, tornando-os auto-hospedados em compiladores de linguagem extensível.

Muitos metacompiladores se baseiam no trabalho de Dewey Val Schorre . Seu compilador META II , lançado em 1964, foi o primeiro metacompilador documentado. Capaz de definir sua própria linguagem e outras, o META II aceitou a fórmula de sintaxe com saída embutida (produção de código) . Também se traduziu em uma das primeiras instâncias de uma máquina virtual . A análise lexical foi realizada por funções de reconhecimento de tokens construídos: .ID, .STRING e .NUMBER. Strings entre aspas na fórmula de sintaxe reconhecem lexemas que não são mantidos.

TREE-META , um metacompilador Schorre de segunda geração, apareceu por volta de 1968. Ele estendeu as capacidades do META II, adicionando regras não comparáveis ​​que separam a produção de código da análise gramatical. As operações de transformação de árvore na fórmula de sintaxe produzem árvores de sintaxe abstratas nas quais as regras não comparadas operam. A correspondência de padrão de árvore não analisada forneceu capacidade de otimização de olho mágico .

O CWIC , descrito em uma publicação ACM de 1970, é um metacompilador Schorre de terceira geração que adicionou regras de lexing e operadores de retrocesso à análise gramatical. O LISP 2 foi casado com as regras incomparáveis ​​de TREEMETA na linguagem do gerador CWIC. Com o processamento LISP 2 [[]], o CWIC pode gerar código totalmente otimizado. O CWIC também forneceu geração de código binário em seções de código nomeadas. Compilações simples e múltiplas podem ser implementadas usando CWIC.

CWIC compilado para instruções de código de máquina endereçáveis ​​por byte de 8 bits projetadas principalmente para produzir código IBM System / 360.

As gerações posteriores não são documentadas publicamente. Uma característica importante seria a abstração do conjunto de instruções do processador de destino, gerando um conjunto de instruções de pseudo máquina, macros, que poderiam ser definidas separadamente ou mapeadas para as instruções de uma máquina real. Otimizações aplicadas a instruções sequenciais podem então ser aplicadas à pseudo instrução antes de sua expansão para o código de máquina alvo.

Compilação cruzada

Um compilador cruzado é executado em um ambiente, mas produz código-objeto para outro. Compiladores cruzados são usados ​​para desenvolvimento embarcado, onde o computador de destino tem recursos limitados.

Um dos primeiros exemplos de compilação cruzada foi AIMICO, onde um programa FLOW-MATIC em um UNIVAC II foi usado para gerar a linguagem assembly para o IBM 705 , que foi então montado no computador IBM.

O compilador ALGOL 68C gerou saída ZCODE , que poderia então ser compilada no código da máquina local por um tradutor ZCODE ou executado interpretado. ZCODE é uma linguagem intermediária baseada em registro. Essa capacidade de interpretar ou compilar ZCODE encorajou a portabilidade do ALGOL 68C para várias plataformas de computador diferentes.

Otimizando compiladores

A otimização do compilador é o processo de melhorar a qualidade do código do objeto sem alterar os resultados que produz.

Os desenvolvedores do primeiro compilador FORTRAN tiveram como objetivo gerar um código melhor do que o montador codificado à mão médio, para que os clientes realmente usassem seu produto. Em um dos primeiros compiladores reais, eles frequentemente eram bem-sucedidos.

Compiladores posteriores, como o compilador Fortran IV da IBM, deram mais prioridade a bons diagnósticos e execução mais rápida, em detrimento da otimização do código de objeto . Não foi até a série IBM System / 360 que a IBM forneceu dois compiladores separados - um verificador de código de execução rápida e um mais lento e otimizador.

Frances E. Allen , trabalhando sozinha e em conjunto com John Cocke , apresentou muitos dos conceitos de otimização. O artigo de Allen de 1966, Program Optimization, introduziu o uso de estruturas de dados de gráfico para codificar o conteúdo do programa para otimização. Seus artigos de 1970, Control Flow Analysis e A Basis for Program Optimization, estabeleceram intervalos como o contexto para análise e otimização de fluxo de dados eficiente e eficaz. Seu artigo de 1971 com Cocke, A Catalog of Optimizing Transformations , forneceu a primeira descrição e sistematização das transformações de otimização. Seus artigos de 1973 e 1974 sobre análise de fluxo de dados interprocedural estenderam a análise a programas inteiros. Seu artigo de 1976 com Cocke descreve uma das duas principais estratégias de análise usadas na otimização de compiladores hoje.

Allen desenvolveu e implementou seus métodos como parte dos compiladores do IBM 7030 Stretch - Harvest e do experimental Advanced Computing System . Este trabalho estabeleceu a viabilidade e a estrutura dos modernos otimizadores independentes de máquina e linguagem. Ela passou a estabelecer e liderar o projeto PTRAN sobre a execução paralela automática de programas FORTRAN. Sua equipe PTRAN desenvolveu novos esquemas de detecção de paralelismo e criou o conceito de gráfico de dependência do programa, o método de estruturação principal usado pela maioria dos compiladores de paralelização.

Linguagens de programação e seus compiladores, de John Cocke e Jacob T. Schwartz , publicado no início de 1970, dedicou mais de 200 páginas a algoritmos de otimização. Ele incluiu muitas das técnicas agora familiares, como eliminação de código redundante e redução de força .

Otimização de olho mágico

A otimização do olho mágico é uma técnica de otimização simples, mas eficaz. Foi inventado por William M. McKeeman e publicado em 1965 no CACM. Foi usado no compilador XPL que McKeeman ajudou a desenvolver.

Otimizador Capex COBOL

Capex Corporation desenvolveu o "COBOL Optimizer" em meados da década de 1970 para COBOL . Esse tipo de otimizador dependia, neste caso, do conhecimento dos "pontos fracos" no compilador IBM COBOL padrão e, na verdade, substituía (ou corrigia ) as seções do código-objeto por um código mais eficiente. O código de substituição pode substituir uma pesquisa linear de tabela por uma pesquisa binária, por exemplo, ou às vezes simplesmente substituir uma instrução relativamente "lenta" por uma conhecida mais rápida que, de outra forma, seria funcionalmente equivalente em seu contexto. Essa técnica agora é conhecida como " redução de força ". Por exemplo, no hardware IBM System / 360, a instrução CLI era, dependendo do modelo específico, entre duas e cinco vezes mais rápida que uma instrução CLC para comparações de byte único.

Compiladores modernos geralmente fornecem opções de otimização para permitir que os programadores escolham se querem ou não executar um passo de otimização.

Diagnóstico

Quando um compilador recebe um programa sintaticamente incorreto, uma mensagem de erro boa e clara é útil. Da perspectiva do redator do compilador, geralmente é difícil de conseguir.

O compilador WATFIV Fortran foi desenvolvido na Universidade de Waterloo , Canadá, no final dos anos 1960. Ele foi projetado para fornecer mensagens de erro melhores do que os compiladores Fortran da IBM da época. Além disso, o WATFIV era muito mais utilizável, porque combinava a compilação, a vinculação e a execução em uma única etapa, enquanto os compiladores da IBM tinham três componentes separados para executar.

PL / C

PL / C era uma linguagem de programação de computador desenvolvida na Cornell University no início dos anos 1970. Embora PL / C fosse um subconjunto da linguagem PL / I da IBM, ele foi projetado com o objetivo específico de ser usado para ensinar programação. Os dois pesquisadores e professores acadêmicos que projetaram o PL / C foram Richard W. Conway e Thomas R. Wilcox. Eles enviaram o famoso artigo "Projeto e implementação de um compilador de diagnóstico para PL / I" publicado nas Comunicações da ACM em março de 1973.

O PL / C eliminou alguns dos recursos mais complexos do PL / I e adicionou recursos extensivos de depuração e recuperação de erros. O compilador PL / C tinha a capacidade incomum de nunca deixar de compilar qualquer programa, por meio do uso de correção automática extensiva de muitos erros de sintaxe e pela conversão de quaisquer erros de sintaxe restantes em instruções de saída.

Compilação just-in-time

A compilação just-in-time (JIT) é a geração de código executável em tempo real ou o mais próximo possível de sua execução real, para aproveitar as métricas de tempo de execução ou outras opções de aprimoramento de desempenho.

Representação intermediária

A maioria dos compiladores modernos possui um lexer e um analisador que produzem uma representação intermediária do programa. A representação intermediária é uma sequência simples de operações que pode ser usada por um otimizador e um gerador de código que produz instruções na linguagem de máquina do processador de destino. Como o gerador de código usa uma representação intermediária, o mesmo gerador de código pode ser usado para muitas linguagens de alto nível diferentes.

Existem muitas possibilidades para a representação intermediária. O código de três endereços , também conhecido como quádruplo ou quádruplo, é uma forma comum, em que há um operador, dois operandos e um resultado. O código de dois endereços ou triplos têm uma pilha na qual os resultados são gravados, em contraste com as variáveis ​​explícitas do código de três endereços.

Static Single Assignment (SSA) foi desenvolvido por Ron Cytron , Jeanne Ferrante , Barry K. Rosen , Mark N. Wegman e F. Kenneth Zadeck , pesquisadores da IBM na década de 1980. No SSA, uma variável recebe um valor apenas uma vez. Uma nova variável é criada em vez de modificar uma existente. SSA simplifica a otimização e geração de código.

Geração de código

Um gerador de código gera instruções em linguagem de máquina para o processador de destino.

Registro de alocação

O algoritmo Sethi – Ullman ou numeração Sethi – Ullman é um método para minimizar o número de registros necessários para manter as variáveis.

Compiladores notáveis

Veja também

Referências

Leitura adicional

links externos