Como escrever um compilador muito básico

Intro

Um compilador típico executa as seguintes etapas:

• Análise: o o texto fonte é convertido em uma árvore de sintaxe abstrata (AST).
• Resolução de referências a outros módulos (C adia esta etapa até a ligação).
• Validação semântica: eliminando declarações sintaticamente corretas que não faz sentido, por exemplo código inacessível ou declarações duplicadas.
• Transformações equivalentes e otimização de alto nível: o AST é transformado para representar um cálculo mais eficiente com a mesma semântica. Isso inclui, por exemplo cálculo precoce de subexpressões comuns e expressões constantes, eliminando atribuições locais excessivas (consulte também SSA ), etc.
• Geração de código: o AST é transformado em código linear de baixo nível, com saltos, alocação de registro e similares. Algumas chamadas de função podem ser sequenciadas neste estágio, alguns loops desenrolados, etc.
• Otimização de olho mágico: o código de baixo nível é verificado em busca de ineficiências locais simples que são eliminadas.

A maioria dos compiladores modernos (por exemplo, gcc e clang) repetem as duas últimas etapas mais uma vez. Eles usam uma linguagem intermediária de baixo nível, mas independente de plataforma, para a geração inicial de código. Em seguida, essa linguagem é convertida em código específico da plataforma (x86, ARM, etc) fazendo praticamente a mesma coisa de uma forma otimizada para a plataforma. Isso inclui, por exemplo o uso de instruções vetoriais quando possível, a reordenação de instruções para aumentar a eficiência da previsão de ramificação e assim por diante.

Depois disso, o código do objeto está pronto para o link. A maioria dos compiladores de código nativo sabe como chamar um linker para produzir um executável, mas não é uma etapa de compilação em si. Em linguagens como Java e C #, a vinculação pode ser totalmente dinâmica, feita pela VM no momento do carregamento.

Lembre-se do básico

• Faça funcionar
• Faça bonito
• Torne-o eficiente

Esta sequência clássica se aplica a todo desenvolvimento de software, mas exige repetição.

Concentre-se na primeira etapa da sequência. Crie a coisa mais simples que possa funcionar.

Leia os livros!

Leia o Dragon Book de Aho e Ullman. Isso é clássico e ainda é bastante aplicável hoje.

Design de compilador moderno também é elogiado.

Se isso é muito difícil para você agora, leia algumas introduções sobre análise primeiro; geralmente análise de bibliotecas inclua introduções e exemplos.

Certifique-se de se sentir confortável trabalhando com gráficos, especialmente árvores. Essas coisas são as coisas de que os programas são feitos no nível lógico.

Defina bem sua linguagem

Use qualquer notação que quiser, mas certifique-se de ter uma descrição completa e consistente de sua língua. Isso inclui sintaxe e semântica.

É hora de escrever trechos de código em sua nova linguagem como casos de teste para o futuro compilador.

Use sua linguagem favorita

É totalmente OK escrever um compilador em Python ou Ruby ou qualquer linguagem que seja fácil para você.Use algoritmos simples que você entenda bem. A primeira versão não precisa ser rápida, eficiente ou completa. Ele só precisa ser correto o suficiente e fácil de modificar.

Também não há problema em escrever diferentes estágios de um compilador em diferentes linguagens, se necessário.

Prepare-se para escrever muito de testes

Seu idioma inteiro deve ser coberto por casos de teste; efetivamente, será definido por eles. Familiarize-se com sua estrutura de teste preferida. Escreva testes desde o primeiro dia. Concentre-se em testes “positivos” que aceitam o código correto, em oposição à detecção de código incorreto.

Execute todos os testes regularmente. Corrija os testes corrompidos antes de prosseguir. Seria uma pena terminar com um erro linguagem definida que não pode aceitar código válido.

Crie um bom analisador

Geradores de analisador são muitos . Escolha o que você quiser desejar. Você também pode escrever seu próprio analisador do zero, mas só vale a pena se a sintaxe de sua linguagem for morta simples.

O analisador deve detectar e relatar erros de sintaxe. Escrever muitos casos de teste, tanto positivos quanto negativos ve; reutilize o código que você escreveu ao definir a linguagem.

A saída do seu analisador é uma árvore de sintaxe abstrata.

Se sua linguagem tem módulos, a saída do analisador pode ser a representação mais simples de “código-objeto” que você gera. Existem muitas maneiras simples de despejar uma árvore em um arquivo e carregá-la de volta rapidamente.

Crie um validador semântico

Muito provavelmente, sua linguagem permite construções sintaticamente corretas que podem fazer nenhum sentido em certos contextos. Um exemplo é uma declaração duplicada da mesma variável ou passando um parâmetro de um tipo errado. O validador detectará tais erros olhando para a árvore.

O validador também resolverá referências a outros módulos escritos em sua linguagem, carregará esses outros módulos e os usará no processo de validação. Por exemplo, essa etapa garantirá que o número de parâmetros passados para uma função de outro módulo esteja correto.

Novamente, escreva e execute vários casos de teste. Casos triviais são tão indispensáveis na solução de problemas quanto inteligentes e complexos.

Gerar código

Use as técnicas mais simples que você conhece. Freqüentemente, não há problema em traduzir diretamente uma construção de linguagem (como uma instrução if) para um modelo de código ligeiramente parametrizado, não muito diferente de um modelo HTML.

Novamente , ignore a eficiência e concentre-se na correção.

Almeje uma VM de baixo nível independente de plataforma

Suponho que você ignore as coisas de baixo nível, a menos que esteja profundamente interessado em hardware específico detalhes. Esses detalhes são sangrentos e complexos.

Suas opções:

• LLVM: permite a geração eficiente de código de máquina, geralmente para x86 e ARM.
• CLR : visa .NET, multiplataforma; tem um bom JIT.
• JVM: visa o mundo Java, bastante multiplataforma, tem um bom JIT.

Ignorar otimização

A otimização é difícil. Quase sempre a otimização é prematura. Gere código ineficiente, mas correto. Implemente toda a linguagem antes de tentar otimizar o código resultante.

Claro, otimizações triviais podem ser introduzidas. Mas evite qualquer coisa astuta e complicada antes que seu compilador fique estável.

E daí?

Se tudo isso não é muito intimidante para você, por favor, prossiga! Para uma linguagem simples, cada uma das etapas pode ser mais simples do que você imagina.

Ver um “Hello world” de um programa que seu compilador criou pode valer a pena.

Comentários

• Esta é uma das melhores respostas que ‘ já vi.
• Acho que você perdeu uma parte da questão … O OP queria escrever um compilador muito básico . Acho que você vai além do básico aqui.
• @ marco-fiset , pelo contrário, acho que ‘ é uma resposta excelente que diz ao OP como fazer um compilador muito básico, enquanto aponta as armadilhas para evitar e define fases mais avançadas.
• Esta é uma das melhores respostas Eu já vi em todo o universo Stack Exchange. Parabéns!
• Ver um ‘ Hello world ‘ de um programa que seu compilador criou pode valer a pena. – INDEED

Jack Crenshaw “s Vamos construir um compilador , embora inacabado, é uma introdução e um tutorial eminentemente legível.

Nicklaus Wirth “s Construção do compilador é um livro muito bom sobre os fundamentos da construção simples de compiladores. Ele se concentra na descida recursiva de cima para baixo, que, vamos encarar os fatos, é MUITO mais fácil do que lex / yacc ou flex / bison. O compilador PASCAL original que seu grupo escreveu foi feito dessa maneira.

Outras pessoas mencionaram os vários livros do Dragon.

Comentários

• Uma das coisas boas sobre Pascal, é que tudo deve ser definido ou declarado antes de ser usado. Portanto, ele pode ser compilado em uma passagem. O Turbo Pascal 3.0 é um exemplo, e há muita documentação sobre os componentes internos aqui .
• PASCAL foi projetado especificamente com um passar compilação e vinculação em mente. O livro do compilador de Wirth ‘ menciona compiladores multipass e acrescenta que conhecia um compilador PL / I que teve 70 (sim, setenta) passagens.
• Declaração obrigatória antes do uso remonta ao ALGOL. Tony Hoare teve seus ouvidos atentos pelo comitê ALGOL quando ele tentou sugerir a adição de regras de tipo padrão, semelhantes ao que FORTRAN tinha. Eles já sabiam dos problemas que isso poderia criar, com erros tipográficos em nomes e regras padrão criando bugs interessantes.
• Aqui está uma versão mais atualizada e finalizada do livro pelo próprio autor original: stack.nl/~marcov/compiler.pdf Edite sua resposta e adicione 🙂

Se você realmente deseja escrever código legível por máquina apenas e não direcionado a uma máquina virtual, você terá que ler os manuais da Intel e entender

• a. Vinculando e carregando código executável

• b. Formatos COFF e PE (para Windows), como alternativa, compreenda o formato ELF (para Linux)

• c. Compreenda os formatos de arquivo .COM (mais fácil do que PE)
• d. Compreenda os montadores
• e. Compreenda os compiladores e o mecanismo de geração de código em compiladores.

Muito mais difícil do que o dito. Eu sugiro que você leia Compiladores e Intérpretes em C ++ como ponto de partida (Por Ronald Mak). Alternativamente, “vamos construir um compilador” de Crenshaw está certo.

Se você não quiser fazer isso, também pode escrever sua própria VM e escrever um gerador de código direcionado a essa VM.

• Outro ponto de partida: http://gnuu.org/2009/09/18/writing-your-own-toy-compiler/
• Grande livro de Kenneth Louden: http://www.amazon.com/Compiler-Construction-Principles-Kenneth-Louden/dp/0534939724

Dicas: Aprenda Flex e Bison PRIMEIRO. Em seguida, vá para a construção de seu próprio compilador / VM.

Boa sorte!

Comentários

• Acho que ter como alvo o LLVM e não código de máquina real é praticamente a melhor forma disponível hoje.
• Eu concordo, eu tenho seguido o LLVM há algum tempo e devo dizer que foi uma das melhores coisas que eu vi em anos em termos de esforço do programador precisava direcioná-lo!
• E quanto ao MIPS e usar spim para executá-lo? Ou MIX ?
• @MichaelT Não usei MIPS, mas tenho certeza que ficará bom.
• Conjunto de instruções @PrototypeStark RISC, processador do mundo real que ainda está em uso hoje (entendendo que será traduzível em sistemas embarcados). O conjunto completo de instruções está na wikipedia . Olhando na net, há muitos exemplos e é usado em muitas aulas acadêmicas como um alvo para programação em linguagem de máquina. Há um pouco de atividade nele em SO .

Na verdade, eu começaria escrevendo um compilador para o Brainfuck . É uma linguagem bastante obtusa para programar, mas só tem 8 instruções para implementar. É o mais simples possível e existem instruções C equivalentes para os comandos envolvidos, se você achar a sintaxe desagradável.

Comentários

• Mas então, depois de ter seu compilador BF pronto, você deve escrever seu código nele 🙁
• @ 500-InternalServerError use o método de subconjunto C

A abordagem DIY para compilador simples poderia ser parecida com esta (pelo menos é assim que meu projeto uni se parecia):

1. Defina a gramática do idioma. Livre de contexto.
2. Se sua gramática ainda não é LL (1), faça isso agora. Observe que algumas regras que pareciam ok no CF simples a gramática pode ficar feia. Talvez sua linguagem seja muito complexa …
3. Escreva Lexer que corta o fluxo de texto em símbolos (palavras, números, literais).
4. Escreva de cima para baixo analisador descendente recursivo para sua gramática, que aceita ou rejeita entrada.
5. Adicione geração de árvore de sintaxe em seu analisador.
6. Escreva ma gerador de código chine da árvore de sintaxe.
7. Lucro & Cerveja, como alternativa, você pode começar a pensar em como fazer um analisador mais inteligente ou gerar um código melhor.

Deve haver bastante literatura descrevendo cada etapa em detalhes.

Comentários

• O sétimo ponto é sobre o que o OP está perguntando.
• 1-5 são irrelevantes e não merecem isso uma atenção especial. 6 é a parte mais interessante.Infelizmente, a maioria dos livros segue o mesmo padrão, depois do infame livro do dragão, prestando muita atenção em analisar e deixar as transformações de código fora do escopo.