Como um compilador pode se compilar?

168

Estou pesquisando o CoffeeScript no site http://coffeescript.org/ , e ele tem o texto

O compilador CoffeeScript é ele próprio escrito em CoffeeScript

Como um compilador pode se compilar, ou o que essa declaração significa?

AlexanderRD
fonte
14
Outro termo para um compilador que pode se compilar é um self-hostingcompilador. Veja programmers.stackexchange.com/q/263651/6221
ou
37
Por que um compilador não pode se compilar?
user253751
48
Há pelo menos duas cópias do compilador envolvidas. Um pré-existente compila uma nova cópia. O novo pode ou não ser idêntico ao antigo.
precisa
12
Você também pode estar interessado no Git: seu código-fonte é rastreado, é claro, em um repositório Git.
Greg d'Eon
7
É como perguntar "Como uma impressora Xerox pode imprimir os esquemas para si mesma?" Compiladores compilam texto em código de bytes. Se o compilador puder compilar com qualquer código de bytes utilizável, você poderá escrever o código do compilador no respectivo idioma e depois passar o código pelo compilador para gerar a saída.
RLH 21/06

Respostas:

219

A primeira edição de um compilador não pode ser gerada por máquina a partir de uma linguagem de programação específica; sua confusão é compreensível. Uma versão posterior do compilador com mais recursos de idioma (com a fonte reescrita na primeira versão do novo idioma) pode ser criada pelo primeiro compilador. Essa versão pode então compilar o próximo compilador e assim por diante. Aqui está um exemplo:

  1. O primeiro compilador CoffeeScript foi escrito em Ruby, produzindo a versão 1 do CoffeeScript
  2. O código-fonte do compilador CS é reescrito no CoffeeScript 1
  3. O compilador CS original compila o novo código (gravado no CS 1) na versão 2 do compilador
  4. Alterações são feitas no código-fonte do compilador para adicionar novos recursos de idioma
  5. O segundo compilador CS (o primeiro escrito em CS) compila o novo código-fonte revisado na versão 3 do compilador
  6. Repita as etapas 4 e 5 para cada iteração

Nota: Não sei exatamente como as versões do CoffeeScript são numeradas, isso foi apenas um exemplo.

Esse processo geralmente é chamado de inicialização . Outro exemplo de um compilador de inicialização é rustco compilador da linguagem Rust .

Ben N
fonte
5
A outra rota para inicializar um compilador é escrever um intérprete para (um subconjunto) do seu idioma.
Aron
Como mais uma alternativa ao bootstrap com um compilador ou intérprete escrito em outro idioma, a rota mais antiga seria montar manualmente a fonte do compilador. Chuck Moore explica como fazer isso para um intérprete Forth no capítulo 9, "Programas que iniciam", no final de Programar uma linguagem orientada a problemas ( web.archive.org/web/20160327044521/www.colorforth.com/POL .htm ), com base em ter feito isso duas vezes antes manualmente. A entrada de código aqui é feita através de um painel frontal que permite o armazenamento direto de valores nos endereços de memória controlados pelos comutadores de bits.
Jeremy W. Sherman
59

No artigo Reflexões sobre Confiança na Confiança , Ken Thompson, um dos criadores do Unix, escreve uma visão geral fascinante (e de fácil leitura) de como o compilador C se compila. Conceitos semelhantes podem ser aplicados ao CoffeeScript ou a qualquer outra linguagem.

A idéia de um compilador que compila seu próprio código é vagamente semelhante a um quine : código fonte que, quando executado, produz como saída o código fonte original. Aqui está um exemplo de uma solução CoffeeScript. Thompson deu este exemplo de uma coluna C:

char s[] = {
    '\t',
    '0',
    '\n',
    '}',
    ';',
    '\n',
    '\n',
    '/',
    '*',
    '\n',
    … 213 lines omitted …
    0
};

/*
 * The string s is a representation of the body
 * of this program from '0'
 * to the end.
 */

main()
{
    int i;

    printf("char\ts[] = {\n");
    for(i = 0; s[i]; i++)
        printf("\t%d,\n", s[i]);
    printf("%s", s);
}

Em seguida, você pode se perguntar como é ensinado ao compilador que uma sequência de escape como '\n'representa o código ASCII 10. A resposta é que, em algum lugar do compilador C, existe uma rotina que interpreta os literais de caracteres, contendo algumas condições como esta para reconhecer as seqüências de barra invertida:

…
c = next();
if (c != '\\') return c;        /* A normal character */
c = next();
if (c == '\\') return '\\';     /* Two backslashes in the code means one backslash */
if (c == 'r')  return '\r';     /* '\r' is a carriage return */
…

Então, podemos adicionar uma condição ao código acima…

if (c == 'n')  return 10;       /* '\n' is a newline */

... para produzir um compilador que saiba que '\n'representa o ASCII 10. Curiosamente, esse compilador e todos os compiladores subseqüentes compilados por ele "conhecem" esse mapeamento; portanto, na próxima geração do código-fonte, você pode alterar a última linha para

if (c == 'n')  return '\n';

… E fará a coisa certa! O 10vem do compilador e não precisa mais ser definido explicitamente no código-fonte do compilador. 1

Esse é um exemplo de recurso de linguagem C que foi implementado no código C. Agora, repita esse processo para cada recurso de idioma único e você terá um compilador "auto-hospedado": um compilador C escrito em C.


1 A reviravolta na trama descrita no artigo é que, como o compilador pode ser "ensinado" a fatos como esse, também pode ser mal ensinado a gerar executáveis ​​de Troia de uma maneira que é difícil de detectar, e esse ato de sabotagem pode persistir. em todos os compiladores produzidos pelo compilador contaminado.

200_success
fonte
7
Embora essa seja uma informação interessante, não acho que ela responda à pergunta. Seus exemplos pressupõem que você já possui um compilador de inicialização, ou em qual idioma o compilador C está escrito?
Arturo Torres Sánchez
9
@ ArturoTorresSánchez Diferentes explicações funcionam bem para pessoas diferentes. Não pretendo reiterar o que foi dito em outras respostas. Em vez disso, acho que as outras respostas falam em um nível superior ao que eu gosto de pensar. Pessoalmente, prefiro uma ilustração concreta de como um único recurso é adicionado e deixar o leitor extrapolar a partir disso, em vez de uma visão superficial.
200_success
5
OK, eu entendo sua perspectiva. É que a pergunta é mais "como um compilador pode se compilar se o compilador para compilá-lo não existe" e menos "como adicionar novos recursos a um compilador de inicialização".
Arturo Torres Sánchez
17
A questão em si é ambígua e aberta. Parece que algumas pessoas o interpretam como "como um compilador CoffeeScript pode se compilar?". A resposta irreverente, como apresentada em um comentário, é "por que não deveria ser capaz de se compilar, assim como compila qualquer código?" Eu interpreto como "como um compilador auto-hospedado pode existir?", E deu uma ilustração de como um compilador pode ser ensinado sobre um de seus próprios recursos de linguagem. Ele responde à pergunta de uma maneira diferente, fornecendo uma ilustração de baixo nível de como ela é implementada.
200_success
1
@ ArturoTorresSánchez: "[Em qual idioma o compilador C está escrito?" Há muito tempo, mantive o compilador C original anotado no antigo apêndice K&R (o do IBM 360.) Muitas pessoas sabem que primeiro havia BCPL, depois B e que C era uma versão melhorada de B. Na verdade, havia muitos partes do antigo compilador que ainda eram escritas em B e nunca haviam sido reescritas para C. As variáveis ​​tinham o formato de letra / dígito único, não se supunha que a aritmética dos ponteiros fosse dimensionada automaticamente etc. bootstrapping de B para C. O primeiro compilador "C" foi escrito em B.
Eliyahu Skoczylas
29

Você já recebeu uma resposta muito boa, no entanto, quero lhe oferecer uma perspectiva diferente, que, espero, será esclarecedora para você. Vamos primeiro estabelecer dois fatos com os quais podemos concordar:

  1. O compilador CoffeeScript é um programa que pode compilar programas escritos em CoffeeScript.
  2. O compilador CoffeeScript é um programa escrito em CoffeeScript.

Tenho certeza de que você pode concordar que os números 1 e 2 são verdadeiros. Agora, observe as duas declarações. Você vê agora que é completamente normal que o compilador CoffeeScript consiga compilar o compilador CoffeeScript?

O compilador não se importa com o que compila. Desde que seja um programa escrito em CoffeeScript, ele pode compilá-lo. E o próprio compilador CoffeeScript é um programa desse tipo. O compilador CoffeeScript não se importa que seja o próprio compilador CoffeeScript que está compilando. Tudo o que vê é algum código CoffeeScript. Período.

Como um compilador pode se compilar, ou o que essa declaração significa?

Sim, é exatamente o que essa afirmação significa, e espero que você possa ver agora como essa afirmação é verdadeira.

Jörg W Mittag
fonte
2
Eu não sei muito sobre script de café, mas você pode esclarecer o ponto 2 afirmando que ele foi escrito em script de café, mas foi compilado e é, então, código de máquina. De qualquer forma, você poderia, por favor, explicar o problema do ovo e da galinha? Se o compilador foi escrito em uma linguagem para a qual ainda não havia sido escrito, como o compilador pode ser executado ou compilado?
barlop
6
Sua declaração 2 é incompleta / imprecisa e muito enganosa. como a primeira resposta diz, a primeira não foi escrita em café. Isso é muito relevante para a pergunta dele. E quanto a "Como um compilador pode se compilar, ou o que essa declaração significa?" Você diz "Sim", suponho que sim (embora minha mente seja um pouco pequena), vejo que ela é usada para compilar versões anteriores de si mesma, e não de si mesma. Mas é usado para se compilar também? Eu supunha que seria inútil.
barlop
2
@barlop: Altere a declaração 2 para " Hoje , o compilador CoffeeScript é um programa escrito em CoffeeScript". Isso ajuda você a entender melhor? Um compilador é "apenas" um programa que converte uma entrada (código) em uma saída (programa). Portanto, se você possui um compilador para o idioma Foo, escreva o código-fonte de um Foo-compilador no idioma Foo e alimente essa fonte ao seu primeiro Foo-compilador, você obtém um segundo Foo-compilador como saída. Isso é feito por várias linguagens (por exemplo, todos os compiladores C que eu conheço estão escritos em ... C).
DarkDust
3
O compilador não pode se compilar. O arquivo de saída não é a mesma instância que o compilador que produz o arquivo de saída. Espero que você possa ver agora como essa afirmação é falsa.
Pabrams
3
@pabrams Por que você assume isso? A saída pode muito bem ser idêntica ao compilador usado para produzi-la. Por exemplo, se eu compilar o GCC 6.1 com o GCC 6.1, recebo uma versão do GCC 6.1 compilada com o GCC 6.1. E se eu usar isso para compilar o GCC 6.1, também recebo uma versão do GCC 6.1 compilada com o GCC 6.1, que deve ser idêntica (ignorando coisas como registros de data e hora).
user253751
9

Como um compilador pode se compilar, ou o que essa declaração significa?

Isso significa exatamente isso. Primeiro de tudo, algumas coisas a considerar. Há quatro objetos que precisamos examinar:

  • O código fonte de qualquer programa arbitrário do CoffeScript
  • A montagem (gerada) de qualquer programa arbitrário do CoffeScript
  • O código fonte do compilador CoffeScript
  • O assembly (gerado) do compilador CoffeScript

Agora, deve ficar óbvio que você pode usar o assembly gerado - o executável - do compilador CoffeScript para compilar qualquer programa arbitrário do CoffeScript e gerar o assembly para esse programa.

Agora, o próprio compilador CoffeScript é apenas um programa CoffeScript arbitrário e, portanto, pode ser compilado pelo compilador CoffeScript.

Parece que sua confusão decorre do fato de que, quando você cria seu novo idioma, ainda não possui um compilador, mas pode usá-lo para compilá-lo. Isso certamente parece um problema de ovo de galinha , certo?

Apresente o processo chamado inicialização .

  1. Você escreve um compilador em uma linguagem já existente (no caso do CoffeScript, o compilador original foi escrito em Ruby) que pode compilar um subconjunto da nova linguagem
  2. Você escreve um compilador que pode compilar um subconjunto do novo idioma no próprio idioma. Você só pode usar os recursos de linguagem que o compilador da etapa acima pode compilar.
  3. Você usa o compilador da etapa 1 para compilar o compilador da etapa 2. Isso deixa você com um assembly que foi originalmente escrito em um subconjunto do novo idioma e que é capaz de compilar um subconjunto do novo idioma.

Agora você precisa adicionar novos recursos. Digamos que você tenha implementado apenas while-loops, mas também deseja for-loops. Isso não é um problema, pois você pode reescrever qualquer forloop de forma que ele seja um whileloop. Isso significa que você só pode usar- whileloops no código-fonte do seu compilador, já que o assembly que você tem em mãos só pode compilá-los. Mas você pode criar funções dentro do seu compilador que podem forexecutar e compilar- loops com ele. Então você usa o assembly que você já possui e compila a nova versão do compilador. E agora você tem uma montagem de um compilador que também pode analisar e compilar- forloops! Agora você pode voltar ao arquivo de origem do seu compilador e reescrever quaisquer whileloops que você não deseja em forloops.

Enxágue e repita até que todos os recursos de idioma desejados possam ser compilados com o compilador.

whilee, forobviamente, foram apenas exemplos, mas isso funciona para qualquer novo recurso de idioma que você desejar. E então você está na situação em que o CoffeScript está agora: O compilador se compila.

Há muita literatura por aí. Reflexões sobre confiança Confiança é um clássico que todos os interessados ​​nesse tópico devem ler pelo menos uma vez.

Polygnome
fonte
5
(A frase "O compilador CoffeeScript é em si escrito em CoffeeScript", é verdade, mas "Um compilador pode compilar em si" é falsa.)
pabrams
4
Não, é completamente verdade. O compilador pode se compilar. Isso simplesmente não faz sentido. Digamos que você tenha o executável que pode compilar a Versão X do idioma. Você escreve um compilador que pode compilar a versão X + 1 e compila-o com o compilador que você possui (que é a versão X). Você acaba com um executável que pode compilar a versão X + 1 do idioma. Agora você pode usar esse novo executável para recompilar o compilador. Mas com que finalidade? Você já tem o executável que faz o que deseja. O compilador pode compilar qualquer programa válido, para que possa se compilar completamente!
Polygnome
1
De fato, não é incomum criar algumas vezes, o iirc freepascal moderno constrói o compilador um total de 5 vezes.
plugwash
1
@pabrams Escrever "Não toque" e "Objeto quente. Não toque" não faz diferença para a mensagem pretendida da frase. Desde que o público-alvo da mensagem (programadores) entenda a mensagem da frase (Uma compilação do compilador pode compilar sua fonte) independentemente de como ela esteja escrita, essa discussão será inútil. Como está agora, seu argumento é inválido. A menos que você consiga mostrar que o público-alvo da mensagem não é programador, então, e somente então, você está correto.
DarkDestry
2
@pabrams 'Bom inglês' é o inglês que comunica idéias claramente ao público-alvo e da maneira que o escritor ou orador pretendeu. Se o público-alvo é programador, e os programadores o entendem, é um bom inglês. Dizer "A luz existe como partículas e ondas" é fundamentalmente equivalente a "A luz existe como fótons e ondas eletromagnéticas". Para um físico, eles significam literalmente a mesma coisa. Isso significa que devemos sempre usar a expressão mais longa e clara? Não! Porque complica a leitura quando o significado já está claro para o público-alvo.
DarkDestry
7

Um pequeno mas importante esclarecimento

Aqui, o termo compilador encobre o fato de que há dois arquivos envolvidos. Um é um executável que recebe como arquivos de entrada escritos no CoffeScript e produz como arquivo de saída outro executável, um arquivo de objeto vinculável ou uma biblioteca compartilhada. O outro é um arquivo de origem CoffeeScript, que apenas descreve o procedimento de compilação do CoffeeScript.

Você aplica o primeiro arquivo ao segundo, produzindo um terceiro que é capaz de executar o mesmo ato de compilação que o primeiro (possivelmente mais, se o segundo arquivo definir recursos não implementados pelo primeiro) e, portanto, poderá substituir o primeiro se você tão desejo.

nbro
fonte
4
  1. O compilador CoffeeScript foi escrito pela primeira vez em Ruby.
  2. O compilador CoffeeScript foi reescrito no CoffeeScript.

Como a versão Ruby do compilador CoffeeScript já existia, ela foi usada para criar a versão CoffeeScript do compilador CoffeeScript.

insira a descrição da imagem aqui Isso é conhecido como um compilador auto-hospedado .

É extremamente comum e geralmente resulta do desejo de um autor de usar seu próprio idioma para manter o crescimento desse idioma.

Trevor Hickey
fonte
3

Não é uma questão de compiladores aqui, mas uma questão de expressividade da linguagem, pois um compilador é apenas um programa escrito em alguma linguagem.

Quando dizemos que "um idioma é escrito / implementado", na verdade queremos dizer que um compilador ou intérprete para esse idioma foi implementado. Existem linguagens de programação nas quais você pode escrever programas que implementam a linguagem (são compiladores / intérpretes para a mesma linguagem). Esses idiomas são chamados de idiomas universais .

Para entender isso, pense em um torno de metal. É uma ferramenta usada para moldar metal. É possível, usando exatamente essa ferramenta, criar outra ferramenta idêntica, criando suas partes. Assim, essa ferramenta é uma máquina universal. Obviamente, o primeiro foi criado usando outros meios (outras ferramentas) e provavelmente era de qualidade inferior. Mas o primeiro foi usado para construir novos com maior precisão.

Uma impressora 3D é quase uma máquina universal. Você pode imprimir a impressora 3D inteira usando uma impressora 3D (não é possível construir a ponta que derrete o plástico).

Paul92
fonte
Eu gosto da analogia do torno. Porém, diferentemente da analogia do torno, imperfeições na primeira iteração do compilador são passadas para todos os compiladores subseqüentes. Por exemplo, uma resposta acima menciona a adição de um recurso de loop for, onde o compilador original usa apenas loops while. A saída compreende loops for, mas a implementação é com loops while. Se a implementação original do loop while for falha ou ineficiente, sempre será!
@ Física-computação que está simplesmente errada. Na ausência de malícia, os defeitos geralmente não se propagam ao compilar um compilador.
plugwash
As traduções de montagem certamente passam de iteração para iteração até que a tradução de montagem seja corrigida. Novos recursos que criam recursos antigos não alteram a implementação subjacente. Pense nisso por um tempo.
@plugwash Veja "Reflexões sobre Confiando Trust" por Ken Thompson - ece.cmu.edu/~ganger/712.fall02/papers/p761-thompson.pdf
3

Prova por indução

Passo indutivo

A n + 1ª versão do compilador é escrita em X.

Assim, ele pode ser compilado pela enésima versão do compilador (também escrita em X).

Caso base

Mas a primeira versão do compilador escrita em X deve ser compilada por um compilador para X escrito em um idioma diferente de X. Essa etapa é chamada de inicialização do compilador.

Guy Argo
fonte
1
O primeiro compilador da linguagem X pode ser facilmente escrito em X. Como isso é possível, é que este primeiro compilador possa ser interpretado . (Por um intérprete X escrito em um idioma diferente de X).
Kaz
0

Os compiladores pegam uma especificação de alto nível e a transformam em uma implementação de baixo nível, como pode ser executada no hardware. Portanto, não há relação entre o formato da especificação e a execução real além da semântica da linguagem que está sendo direcionada.

Os compiladores cruzados passam de um sistema para outro, enquanto os compiladores de idiomas compilam uma especificação de idioma em outra especificação de idioma.

Basicamente, compilar é uma tradução justa, e o nível geralmente é de nível superior para o nível inferior, mas existem muitas variantes.

Os compiladores de inicialização são os mais confusos, é claro, porque compilam o idioma em que foram escritos. Não se esqueça da etapa inicial na inicialização, que requer pelo menos uma versão existente mínima que seja executável. Muitos compiladores inicializados trabalham primeiro nos recursos mínimos de uma linguagem de programação e adicionam recursos adicionais de linguagem complexa a partir de agora, desde que o novo recurso possa ser expresso usando os recursos anteriores. Se não fosse esse o caso, seria necessário que essa parte do "compilador" fosse desenvolvida em outro idioma previamente.

nbro
fonte