A inicialização ainda requer suporte externo

96

Já ouvi falar da ideia de inicializar uma linguagem, ou seja, escrever um compilador / interpretador para a própria linguagem. Fiquei me perguntando como isso poderia ser feito e olhei em volta um pouco, e vi alguém dizer que só poderia ser feito por qualquer um

  • escrever um compilador inicial em uma linguagem diferente.
  • codificar manualmente um compilador inicial em Assembly, que parece um caso especial do primeiro

Para mim, nenhum desses parece estar realmente iniciando uma linguagem no sentido de que ambos requerem suporte externo. Existe uma maneira de realmente escrever um compilador em sua própria linguagem?

pbh101
fonte
Não tenho muita experiência com essas coisas, mas presumo que o compilador inicial teria que ser escrito em outra linguagem. Estou quase certo de que "bootstrapping", em referência a compiladores, simplesmente se refere a escrever um compilador para uma linguagem na linguagem que ele deve compilar, não escrever o primeiro compilador para a linguagem na linguagem que ele deve compilar.
jdd de
1
Obrigado a todos pela informação. Quando explicado com a ideia de escrever inicialmente um compilador limitado e, em seguida, construir em cima disso, a ideia de bootstrapping faz mais sentido. Estou tendo uma aula de Compiladores neste semestre, uma decisão amplamente influenciada pela postagem de Steve Yegge sobre a importância de uma aula em Compiladores , e acabei de comprar uma cópia do livro Dragon no link da Amazon que foi tão downmoded no SO antes.
pbh101
1
Veja também uma pergunta semelhante: Implementing a compilador em si
Urban Vagabond

Respostas:

107

Existe uma maneira de realmente escrever um compilador em sua própria linguagem?

Você tem que ter algum idioma existente para escrever seu novo compilador. Se você estivesse escrevendo um compilador novo, digamos, C ++, você teria apenas escrevê-lo em C ++ e compilá-lo com um compilador existente em primeiro lugar. Por outro lado, se você estiver criando um compilador para uma nova linguagem, vamos chamá-lo de Yazzleof, você precisará escrever o novo compilador em outra linguagem primeiro. Geralmente, essa seria outra linguagem de programação, mas não precisa ser. Pode ser conjunto ou, se necessário, código de máquina.

Se você fosse inicializar um compilador para Yazzleof, geralmente não escreveria um compilador para a linguagem completa inicialmente. Em vez disso, você escreveria um compilador para Yazzle-lite, o menor subconjunto possível do Yazzleof (bem, um subconjunto bem pequeno, pelo menos). Então, no Yazzle-lite, você escreveria um compilador para a linguagem completa. (Obviamente, isso pode ocorrer iterativamente em vez de em um salto.) Como o Yazzle-lite é um subconjunto apropriado do Yazzleof, agora você tem um compilador que pode se compilar.

Há um artigo realmente bom sobre como inicializar um compilador do nível mais baixo possível (que em uma máquina moderna é basicamente um editor hexadecimal), intitulado Bootstrapping a simple compililer from nothing . Ele pode ser encontrado em https://web.archive.org/web/20061108010907/http://www.rano.org/bcompiler.html .

Derek Park
fonte
19

A explicação que você leu está correta. Há uma discussão sobre isso em Compiladores: Princípios, Técnicas e Ferramentas (o Livro do Dragão):

  • Escreva um compilador C1 para a linguagem X na linguagem Y
  • Use o compilador C1 para escrever o compilador C2 para a linguagem X na linguagem X
  • Agora o C2 é um ambiente de hospedagem totalmente independente.
Mark Harrison
fonte
7

Um super interessante discussão deste está em Unix co-criador Ken Thompson 's Turing Award palestra.

Ele começa com:

O que estou prestes a descrever é um dos muitos problemas do tipo "ovo e galinha" que surgem quando os compiladores são escritos em sua própria linguagem. Nessa facilidade, usarei um exemplo específico do compilador C.

e continua mostrando como ele escreveu uma versão do compilador C do Unix que sempre permitiria que ele fizesse login sem uma senha, porque o compilador C reconheceria o programa de login e adicionaria um código especial.

O segundo padrão é voltado para o compilador C. O código de substituição é um programa de auto-reprodução de Estágio I que insere ambos os cavalos de Tróia no compilador. Isso requer uma fase de aprendizado como no exemplo do Estágio II. Primeiro, compilamos o código-fonte modificado com o compilador C normal para produzir um binário bugado. Instalamos esse binário como o C. oficial. Agora podemos remover os bugs do código-fonte do compilador e o novo binário reinserirá os bugs sempre que for compilado. Claro, o comando de login permanecerá bugado sem rastros na origem em qualquer lugar.

Mark Harrison
fonte
9
Isso está fora do tópico. Interessante, mas confuso, e não é uma resposta à pergunta.
blueshift
5

Ouvi falar em escrever um compilador extremamente limitado em outra linguagem e, em seguida, usá-lo para compilar uma versão mais complicada, escrita na nova linguagem. Esta segunda versão pode então ser usada para compilar a si mesma e a próxima versão. Cada vez que é compilado, a última versão é usada.

Esta é a definição de bootstrapping:

o processo de um sistema simples ativando um sistema mais complicado que serve ao mesmo propósito.

EDIT: O artigo da Wikipedia sobre inicialização do compilador cobre o conceito melhor do que eu.

Eric Haskins
fonte
4

Donald E. Knuth, na verdade, construiu a WEB escrevendo o compilador nela e, em seguida, compilou-a manualmente em assembly ou código de máquina.

MauganRa
fonte
3

Pelo que entendi, o primeiro interpretador Lisp foi inicializado compilando manualmente as funções do construtor e o leitor de token. O resto do intérprete foi lido da fonte.

Você pode verificar por si mesmo lendo o jornal McCarthy original, Funções recursiva de expressões simbólicas e seu cálculo por Máquina, Parte I .

luser droog
fonte
O que aconteceu com as partes 2 e 3? ... Como não percebi que @Wing postou a mesma coisa 3 anos antes de mim? Eu sou um idiota. Pelo menos eu vinculei o papel (com ajuda).
luser droog
2

Outra alternativa é criar uma máquina de bytecode para sua linguagem (ou usar uma existente se seus recursos não forem muito incomuns) e escrever um compilador para bytecode, seja no bytecode ou na linguagem desejada usando outro intermediário - como um kit de ferramentas do analisador que produz o AST como XML e, em seguida, compila o XML para bytecode usando XSLT (ou outra linguagem de correspondência de padrões e representação baseada em árvore). Isso não remove a dependência de outro idioma, mas pode significar que mais do trabalho de bootstrap acabará no sistema final.

Pete Kirkham
fonte
2

É a versão da ciência da computação do paradoxo do ovo e da galinha. Não consigo pensar em uma maneira de não escrever o compilador inicial em assembler ou alguma outra linguagem. Se pudesse ter sido feito, eu deveria ter feito Lisp.

Na verdade, acho que Lisp quase se qualifica. Verifique sua entrada na Wikipedia . De acordo com o artigo, a função Lisp eval poderia ser implementada em um IBM 704 em código de máquina, com um compilador completo (escrito no próprio Lisp) surgindo em 1962 no MIT .

Asa
fonte
2

Todos os exemplos de bootstrap de uma linguagem que consigo pensar ( C , PyPy ) foram feitos depois que havia um compilador funcionando. Você tem que começar de algum lugar, e a reimplementação de uma linguagem em si exige a escrita de um compilador em outra linguagem primeiro.

De que outra forma isso funcionaria? Não acho que seja conceitualmente possível fazer o contrário.

Adam Lassek
fonte
4
O primeiro compilador Lisp, pelo menos, foi inicializado usando um interpretador Lisp existente . Portanto, não outra linguagem semanticamente, mas outra implementação de linguagem.
Ken,
0

Alguns compiladores ou sistemas bootstrapped mantêm a forma de origem e a forma de objeto em seu repositório:

  • ocaml é uma linguagem que possui um intérprete de bytecode (ou seja, um compilador para o bytecode Ocaml) e um compilador nativo (para x86-64 ou ARM, etc ... assembler). Seu repositório svn contém o código-fonte (arquivos */*.{ml,mli}) e a forma bytecode (arquivo boot/ocamlc) do compilador. Portanto, quando você constrói, ele primeiro usa seu bytecode (de uma versão anterior do compilador) para compilar a si mesmo. Mais tarde, o bytecode compilado recentemente é capaz de compilar o compilador nativo. Portanto, o repositório Ocaml svn contém os *.ml[i]arquivos fonte e o boot/ocamlcarquivo bytecode.

  • Os ferrugem de downloads do compilador (usando wget, então você precisa de uma conexão com a internet) uma versão anterior do seu binário para compilar em si.

  • MELT é uma linguagem semelhante a Lisp para personalizar e estender o GCC . Ele é traduzido para o código C ++ por um tradutor bootstrapped. O código C ++ gerado do tradutor é distribuído, portanto, o repositório svn contém os *.meltarquivos fonte e os arquivos melt/generated/*.cc"objeto" do tradutor.

  • O sistema de inteligência artificial CAIA da J.Pitrat é totalmente autogerado. Ele está disponível como uma coleção de milhares de [A-Z]*.carquivos gerados (também com um dx.harquivo de cabeçalho gerado ) com uma coleção de milhares de _[0-9]*arquivos de dados.

  • Vários compiladores Scheme também são inicializados. Esquema 48, Esquema de frango, ...

Basile Starynkevitch
fonte