Escrevendo um compilador em seu próprio idioma

https://stackoverflow.com/questions/193560

10-07-2019
|

Pergunta

Intuitivamente, seria parece que um compilador para Foo linguagem não pode em si ser escrito em Foo. Mais especificamente, a início compilador para Foo linguagem não pode ser escrito em Foo, mas qualquer compilador posterior poderia ser escrito para Foo.

Mas isso é realmente verdade? Eu tenho alguns muito vaga lembrança de ler sobre uma linguagem cujo primeiro compilador foi escrito em "si". Isso é possível, e se assim como?

Solução

Isso é chamado de "bootstrapping". Você deve primeiro criar um compilador (ou intérprete) para o seu idioma em algum outro idioma (normalmente Java ou C). Uma vez feito isto, você pode escrever uma nova versão do compilador em linguagem Foo. Você usa o primeiro compilador de bootstrap para compilar o compilador, e, em seguida, usar esse compilador compilado para compilar tudo o resto (incluindo versões futuras de si mesmo).

A maioria das línguas são, de facto criado desta forma, parcialmente porque os designers de linguagem gosto de usar a linguagem que eles estão criando, e também porque um compilador não-trivial muitas vezes serve como um ponto de referência útil para como "completa" a linguagem pode ser.

Um exemplo disso seria Scala. Seu primeiro compilador foi criado em Pizza, uma linguagem experimental por Martin Odersky. A partir da versão 2.0, o compilador foi completamente re-escrito em Scala. Daquele ponto em diante, o compilador Pizza idade poderia ser completamente descartada, devido ao fato de que o novo compilador Scala poderia ser usado para compilar-se para futuras iterações.

Outras dicas

Lembro-me de ouvir um Engenharia de Software Radio podcast de qual Dick Gabriel falou sobre bootstrapping o interpretador LISP original de escrever uma versão nu-ossos em LISP em papel e mão de montá-lo em código de máquina. A partir de então, o restante dos recursos LISP foram ambos escritos e interpretados com LISP.

Adicionando uma curiosidade para as respostas anteriores.

Aqui está uma citação do Linux From Scratch manual, sob o passo onde se começa a construir o compilador GCC de sua fonte. (Linux From Scratch é uma maneira de instalar Linux que é radicalmente diferente de instalar uma distribuição, em que você tem que compilar realmente todas binário único do sistema de destino.)

make bootstrap
O alvo 'bootstrap não apenas GCC compilação, mas compila-lo várias vezes. Ele usa os programas compilados em um primeiro rodada para compilar-se uma segunda vez, e depois novamente uma terceira vez. Em seguida, ele compara estas segunda e terceira compila para se certificar de que pode se reproduzir na perfeição. Isto também implica que ele foi compilado corretamente.

Que o uso do alvo "bootstrap é motivado pelo fato de que o compilador uma utilidades para construir conjunto de ferramentas do sistema de destino pode não ter a mesma versão do compilador alvo. Procedendo dessa forma é uma certeza para obter, no sistema de destino, um compilador que pode compilar em si.

Quando você escreve o seu primeiro compilador para C, você escrevê-lo em algum outro idioma. Agora, você tem um compilador para C, digamos, em assembler. Eventualmente, você veio ao lugar onde você tem que analisar cordas, especificamente sequências de escape. Você vai escrever código para \n convertido para o caractere com o código decimal 10 (e \r a 13, etc).

Depois que o compilador está pronto, você vai começar a reimplementar-lo em C. Este processo é chamado " bootstrapping ".

O código seqüência de análise será:

...
if (c == 92) { // backslash
    c = getc();
    if (c == 110) { // n
        return 10;
    } else if (c == 92) { // another backslash
        return 92;
    } else {
        ...
    }
}
...

Quando Isso compila, você tem um binário que compreende '\ n'. Isto significa que você pode alterar o código fonte:

...
if (c == '\\') {
    c = getc();
    if (c == 'n') {
        return '\n';
    } else if (c == '\\') {
        return '\\';
    } else {
        ...
    }
}
...

Então, onde está a informação que '\ n' é o código para 13? É no binário! É como DNA: código fonte Compilando C com este binário vai herdar esta informação. Se o compilador compila em si, ele vai passar esse conhecimento para sua prole. Deste ponto em diante, não há nenhuma maneira de ver a partir sozinho a fonte que o compilador vai fazer.

Se você quiser esconder um vírus na fonte de algum programa, você pode fazê-lo como este: Get a fonte de um compilador, encontrar a função que compila funções e substituí-lo com um presente:

void compileFunction(char * name, char * filename, char * code) {
    if (strcmp("compileFunction", name) == 0 && strcmp("compile.c", filename) == 0) {
        code = A;
    } else if (strcmp("xxx", name) == 0 && strcmp("yyy.c", filename) == 0) {
        code = B;
    }

    ... code to compile the function body from the string in "code" ...
}

As partes interessantes são A e B. A é o código fonte para compileFunction incluindo o vírus, provavelmente criptografados, de alguma forma, então não é óbvia de procurar o binário resultante. Isso garante que a compilação de compilador com ele mesmo irá preservar o código de injeção de vírus.

B é o mesmo para a função que deseja substituir com nosso vírus. Por exemplo, poderia ser a função "login" no arquivo de origem "login.c", que é provavelmente a partir do kernel Linux. Nós poderíamos substituí-lo por uma versão que irá aceitar a senha "Joshua" para a conta root, além da senha normal.

Se você compilar isso e espalhá-lo como um binário, não haverá maneira de encontrar o vírus por olhar para a fonte.

A fonte original da idéia: http: //cm.bell-labs .com / quem / ken / trust.html

Você não pode escrever um compilador em si, porque você não tem nada para compilar o código fonte começando com. Há duas abordagens para resolver isso.

A menos favorecidos é o seguinte. Você escreve um compilador mínima em assembler (eca) para um conjunto mínimo da língua e, em seguida, usar esse compilador para implementar recursos extras da língua. Construir o seu caminho até você ter um compilador com todas as características da linguagem por si. Um processo doloroso que normalmente só é feito quando você não tem outra escolha.

A abordagem preferida é a utilização de um compilador cruzado. Você alterar o back-end de um compilador existente em uma máquina diferente para criar uma saída que é executado no computador de destino. Então você tem um bom compilador completo e funcionando na máquina de destino. Mais popular para isso é a linguagem C, como há uma abundância de compiladores existentes que têm extremidades traseiras conectáveis ??que podem ser trocados.

Um fato pouco conhecido é que o compilador GNU C ++ tem uma implementação que usa apenas o C subconjunto. A razão de ser é geralmente fácil encontrar um compilador C para uma nova máquina de destino que lhe permite, em seguida, construir o compilador completo GNU C ++ a partir dele. Você agora arrancar amarrado a si mesmo para ter um compilador C ++ na máquina de destino.

Geralmente, você precisa ter um trabalho (se primative) corte do compilador trabalhando primeiro - então você pode começar a pensar sobre o que torna auto-hospedagem. Este é realmente considerado um marco importante em alguns langauges.

Pelo que me lembro de "mono", é provável que eles vão precisar adicionar algumas coisas a reflexão para fazê-lo funcionar: a fortaleza da equipe mono apontando que algumas coisas simplesmente não são possíveis com Reflection.Emit; é claro, a equipe de MS pode provar que estão errados.

Isto tem alguns reais vantagens: é um bom teste de unidade, para começar! E você só tem uma língua que se preocupar (ou seja, é possível que um C # especialista pode não saber muito C ++, mas agora o teu pode corrigir o compilador C #). Mas eu me pergunto se não há uma quantidade de orgulho profissional no trabalho aqui:. Eles simplesmente deseja que ele seja auto-hospedagem

Não é bem um compilador, mas eu fui recentemente a trabalhar em um sistema que é auto hospedagem; o gerador de código é usado para gerar o gerador de código ... por isso, se o esquema muda Eu simplesmente executá-lo em si: nova versão. Se houver um erro, eu apenas voltar para uma versão anterior e tente novamente. Muito conveniente, e muito fácil de manter.

Update 1

Eu só assisti este vídeo de Anders no PDC, e (cerca de uma hora), ele dá algumas razões muito mais válido - tudo sobre o compilador como um serviço. Apenas para o registro.

Aqui está um despejo (tema difícil para procurar, na verdade):

Smalltalk
C

Esta é também a ideia de PyPy e Rubinius :

(Acho que isso pode também se aplicam a Forth , mas eu don 't sabe alguma coisa sobre Forth.)

GNAT, o compilador GNU Ada, requer um compilador Ada a ser totalmente construído. Esta pode ser uma dor quando portá-la para uma plataforma onde não há binário GNAT prontamente disponíveis.

Na verdade, a maioria dos compiladores são escritos na língua que compilar, pelas razões expostas acima.

O primeiro compilador de inicialização geralmente é escrito em C, C ++ ou Assembly.

O # compilador Mono projeto C tem sido "auto-hospedado" por um longo tempo, o que significa é que ele foi escrito em C # si.

O que eu sei é que o compilador foi iniciado como código C puro, mas uma vez que as características "básicas" de ECMA foram implementadas eles começaram a reescrever o compilador em C #.

Eu não estou ciente das vantagens de escrever o compilador na mesma língua, mas eu tenho certeza que ele tem que fazer, pelo menos, com as características que a linguagem em si pode oferecer (C, por exemplo, faz objeto não suporte programação orientada).

Você pode encontrar mais informações aqui .

Talvez você possa escrever uma BNF descrevendo BNF.

Licenciado em: CC-BY-SA com atribuição

Não afiliado a StackOverflow