compiler-construction - que - tipos de compiladores




Aprendendo a escrever um compilador (20)

Idiomas preferidos : C / C ++, Java e Ruby.

Estou procurando alguns livros / tutoriais úteis sobre como escrever seu próprio compilador simplesmente para fins educacionais. Eu estou mais familiarizado com C / C ++, Java e Ruby, então prefiro recursos que envolvam um desses três, mas qualquer bom recurso é aceitável.


"... Vamos construir um compilador ..."

Gostaria http://compilers.iecc.com/crenshaw/ segundo por @sasb . Esqueça de comprar mais livros no momento.

Por quê? Ferramentas e idioma.

O idioma necessário é Pascal e, se bem me lembro, é baseado no Turbo-Pascal. Acontece que, se você acessar http://www.freepascal.org/ e baixar o compilador Pascal, todos os exemplos funcionam diretamente da página ~ http://www.freepascal.org/download.var Pascal é que você pode usá-lo em praticamente qualquer processador ou sistema operacional com o qual possa cuidar.

Depois de dominar as lições, tente o " Dragon Book " mais avançado ~ http://en.wikipedia.org/wiki/Dragon_book


Grande lista de recursos:

Lenda:

  • ¶ Link para um arquivo PDF
  • $ Link para um livro impresso

Achei o livro Dragon muito difícil de ler, com muito foco na teoria da linguagem que não é realmente necessária para escrever um compilador na prática.

Eu acrescentaria o livro Oberon , que contém toda a fonte de um incrivelmente rápido e simples projeto Oberon, compilador Oberon .


Concordo com a referência do Dragon Book; IMO, é o guia definitivo para a construção do compilador. Prepare-se para alguma teoria hardcore, no entanto.

Se você quer um livro mais leve em teoria, o Game Scripting Mastery pode ser um livro melhor para você. Se você é um novato na teoria dos compiladores, ele fornece uma introdução mais suave. Ele não cobre métodos de análise mais práticos (optando por descendência recursiva não preditiva sem discutir a análise LL ou LR) e, pelo que me lembro, nem sequer discute qualquer tipo de teoria de otimização. Além disso, em vez de compilar no código da máquina, ele é compilado em um bytecode que deve ser executado em uma VM que você também escreve.

Ainda é uma leitura decente, principalmente se você puder comprá-lo barato na Amazon. Se você quer apenas uma introdução fácil aos compiladores, o Game Scripting Mastery não é um caminho ruim. Se você quer ir hardcore na frente, então não se esqueça de nada menos do que o Dragon Book.


De um modo geral, não há um tutorial de cinco minutos para compiladores, porque é um tópico complicado e escrever um compilador pode levar meses. Você terá que fazer sua própria pesquisa.

Python e Ruby são geralmente interpretados. Talvez você queira começar com um intérprete também. Geralmente é mais fácil.

O primeiro passo é escrever uma descrição formal da linguagem, a gramática da sua linguagem de programação. Em seguida, você deve transformar o código-fonte que deseja compilar ou interpretar de acordo com a gramática em uma árvore de sintaxe abstrata, uma forma interna do código-fonte que o computador entende e pode operar. Essa etapa geralmente é chamada de análise e o software que analisa o código-fonte é chamado de analisador. Freqüentemente, o analisador é gerado por um gerador de analisador que transforma uma gramática formal em código de máquina de origem ou código. Para uma explicação boa e não matemática da análise, recomendo Técnicas de Análise - Um Guia Prático. A Wikipedia tem uma comparação de geradores de analisador, dos quais você pode escolher aquele que é adequado para você. Dependendo do gerador de analisador escolhido, você encontrará tutoriais na Internet e, para geradores de analisador realmente populares (como o GNU bison), também existem livros.

Escrever um analisador para o seu idioma pode ser muito difícil, mas isso depende da sua gramática. Então, sugiro manter sua gramática simples (ao contrário do C ++); Um bom exemplo disso é o LISP.

Na segunda etapa, a árvore de sintaxe abstrata é transformada de uma estrutura de árvore em uma representação intermediária linear. Como um bom exemplo para o bytecode deste Lua é frequentemente citado. Mas a representação intermediária realmente depende do seu idioma.

Se você estiver construindo um intérprete, precisará simplesmente interpretar a representação intermediária. Você também pode compilá-lo na hora certa. Eu recomendo o LLVM e o libjit para compilação just-in-time. Para tornar o idioma utilizável, você também precisará incluir algumas funções de entrada e saída e talvez uma pequena biblioteca padrão.

Se você for compilar o idioma, será mais complicado. Você precisará escrever backends para diferentes arquiteturas de computadores e gerar código de máquina a partir da representação intermediária nesses backends. Eu recomendo o LLVM para esta tarefa.

Existem alguns livros sobre esse tópico, mas não posso recomendar nenhum deles para uso geral. A maioria deles é muito acadêmica ou muito prática. Não há "Aprenda a escrever um compilador em 21 dias" e, portanto, você terá que comprar vários livros para entender bem todo esse tópico. Se você pesquisar na Internet, encontrará alguns livros on-line e notas de aula. Talvez haja uma biblioteca universitária perto de você, onde você pode emprestar livros em compiladores.

Eu também recomendo um bom conhecimento de fundo em ciência da computação teórica e teoria dos grafos, se você quiser tornar seu projeto sério. Um diploma em ciência da computação também será útil.


Desculpe, está em espanhol, mas esta é a bibliografia de um curso chamado "Compiladores e Intérpretes" (Compiladores e Intérpretes) na Argentina.

O curso foi da teoria formal da linguagem à construção do compilador, e estes são os tópicos que você precisa para criar, pelo menos, um compilador simples:

  • Projeto de compiladores em C.
    Allen I. Holub

    Prentice-Hall. 1990.

  • Compiladores. Teoria e Construção.
    Sanchís Llorca, FJ, Galán Pascual, C. Editorial Paraninfo. 1988.

  • Construção do compilador.
    Niklaus Wirth

    Addison-Wesley. 1996.

  • Lenguajes, Gramáticas e Autómatas. Un enfoque práctico.
    Pedro Isasi Viñuela, Paloma Martínez Fernández, Daniel Borrajo Millán. Addison-Wesley Iberoamericana (Espanha). 1997.

  • A arte do design do compilador. A teoria e a prática.
    Thomas Pittman, James Peters.

    Prentice-Hall. 1992.

  • Construção do compilador orientado a objetos.
    Jim Holmes.
    Prentice Hall, Englewood Cliffs, NJ 1995

  • Compiladores. Conceitos Fundamentais.
    B. Teufel, S. Schmidt, T. Teufel.

    Addison-Wesley Iberoamericana. 1995.

  • Introdução à Teoria dos Autômatos, Idiomas e Computação.

    John E. Hopcroft. Jeffref D. Ullman.
    Addison-Wesley. 1979.

  • Introdução às linguagens formais.
    György E. Révész.

    Mc Graw Hill. 1983.

  • Técnicas de análise. Um guia prático.
    Dick Grune, Ceriel Jacobs.
    Impressão por autores. 1995
    http://www.cs.vu.nl/~dick/PTAPG.html

  • Yacc: Mais um compilador-compilador.
    Stephen C. Johnson
    Relatório Técnico de Ciências da Computação Nº 32, 1975. Bell Laboratories. Murray Hill, Novo
    Jersey.

  • Lex: Um gerador de analisador lexical.
    ME Lesk, E. Schmidt. Relatório Técnico de Ciências da Computação Nº 39, 1975. Bell Laboratories. Murray Hill, Nova Jersey.

  • Lex & Yacc.
    John R. Levine, Tony Mason e Doug Brown.
    O'Reilly & Associates. 1995.

  • Elementos da teoria da computação.
    Harry R. Lewis, Christos H. Papadimitriou. Segunda Edição. Prentice Hall. 1998.

  • Um Algoritmo Eficiente para Construção do Gráfico de Dependência de Controle.
    Salvador V. Cavadini.
    Trabalho final de classificação para obter o título de engenheiro em computação.
    Faculdade de Matemática Aplicada. UCSE 2001.


Estou analisando o mesmo conceito e encontrei este artigo promissor de Joel Pobar,

Crie um compilador de idiomas para o .NET Framework - não tenho certeza de onde isso foi

Criar um compilador de idiomas para o .NET Framework - cópia em pdf do documento original

ele discute um conceito de alto nível de um compilador e passa a inventar seu próprio idioma para a estrutura .Net. Embora seu objetivo seja o .Net Framework, muitos dos conceitos devem poder ser reproduzidos. O artigo abrange:

  1. Definição de langauge
  2. Scanner
  3. Analisador (o bit no qual estou principalmente interessado)
  4. Direcionando o .NET Framework
  5. Gerador de código

existem outros tópicos, mas você entende o que é justo.

Destina-se a pessoas começando, escritas em C # (não exatamente Java)

HTH

ossos


Eu acho que a implementação do compilador moderno no ML é o melhor texto introdutório para escrever compiladores. Há também uma Java e uma C , que podem ser mais acessíveis devido ao seu conhecimento de idiomas. O livro contém muitos materiais básicos úteis (varredura e análise, análise semântica, registros de ativação, seleção de instruções, geração de código nativo RISC e x86) e vários tópicos "avançados" (compilando OO e linguagens funcionais, polimorfismo, coleta de lixo, otimização e único formulário de atribuição estática) em relativamente pouco espaço (~ 500 páginas).

Prefiro Implementação do Compilador Moderno ao livro Dragon, porque a implementação do Compilador Moderno pesquisa menos do campo - em vez disso, possui uma cobertura realmente sólida de todos os tópicos que você precisa para escrever um compilador sério e decente. Depois de ler este livro, você estará pronto para abordar os trabalhos de pesquisa diretamente, para obter mais detalhes, se necessário.

Devo confessar que tenho um sério problema na construção de compiladores de Niklaus Wirth . Está disponível online como PDF. Eu acho a estética de programação de Wirth simplesmente bonita, no entanto, algumas pessoas acham seu estilo muito minimalista (por exemplo, Wirth favorece analisadores de descida recursivos, mas a maioria dos cursos de CS se concentra em ferramentas geradoras de analisadores; os designs de linguagem de Wirth são bastante conservadores.) Compiler Construction é uma destilação muito sucinta das idéias básicas de Wirth, portanto, goste ou não do estilo dele, recomendo a leitura deste livro.


Lembro-me de fazer essa pergunta cerca de sete anos atrás, quando eu era bastante novo em programação.

Tomei muito cuidado quando perguntei e surpreendentemente não recebi tantas críticas quanto você está chegando aqui. No entanto, eles me apontaram na direção do " Dragon Book ", que é, na minha opinião, um ótimo livro que explica tudo o que você precisa saber para escrever um compilador (é claro que você precisará dominar um ou dois idiomas). idiomas que você conhece, melhor.).

E sim, muitas pessoas dizem que ler esse livro é uma loucura e você não aprenderá nada com ele, mas eu discordo completamente disso.

Muitas pessoas também dizem que escrever compiladores é estúpido e inútil. Bem, existem várias razões pelas quais o desenvolvimento do compilador é útil:

  • Porque é divertido.
  • É educativo, ao aprender a escrever compiladores, você aprenderá muito sobre ciência da computação e outras técnicas que são úteis ao escrever outros aplicativos.
  • Se ninguém escrevesse compiladores, os idiomas existentes não melhorariam.

Não escrevi meu próprio compilador imediatamente, mas depois de perguntar, sabia por onde começar. E agora, depois de aprender muitas línguas diferentes e ler o Livro do Dragão, escrever não é um grande problema. (Também estou estudando atm de engenharia da computação, mas a maior parte do que sei sobre programação é autodidata.)

Em conclusão, The Dragon Book é um ótimo "tutorial". Mas gaste algum tempo dominando um ou dois idiomas antes de tentar escrever um compilador. Não espere ser um guru dos compiladores na próxima década ou mais.

O livro também é bom se você quiser aprender a escrever analisadores / intérpretes.


Não é um livro, mas um artigo técnico e uma experiência de aprendizado extremamente divertida, se você quiser saber mais sobre compiladores (e metacompiladores) ... Este site o orienta na criação de um sistema de compilador completamente independente que pode se compilar e outros idiomas:

Tutorial: Metacompilers Parte 1

Tudo isso é baseado em um incrível pequeno artigo técnico de 10 páginas:

Val Schorre META II: uma linguagem de escrita de compilador orientada à sintaxe

de honesto a deus de 1964. Eu aprendi a construir compiladores disso em 1970. Há um momento alucinante em que você finalmente percebe como o compilador pode se regenerar ....

Conheço o autor do site nos meus dias de faculdade, mas não tenho nada a ver com o site.


O Python vem com um compilador python escrito em Python. Você pode ver o código fonte, e inclui todas as fases, desde a análise, árvore de sintaxe abstrata, código emissor, etc.


O compilador LCC ( wikipedia ) ( página inicial do projeto ) de Fraser e Hanson é descrito em seu livro "Um compilador C retargetável: Design e implementação". É bastante legível e explica todo o compilador, até a geração do código.


Se você estiver disposto a usar o LLVM, verifique isso: http://llvm.org/docs/tutorial/ . Ele ensina como escrever um compilador do zero, usando a estrutura do LLVM, e não assume que você tenha algum conhecimento sobre o assunto.

O tutorial sugere que você escreva seu próprio analisador e lexer, etc., mas aconselho que você procure o bison e flex quando tiver a idéia. Eles tornam a vida muito mais fácil.


Se você estiver interessado em escrever um compilador para uma linguagem funcional (em vez de uma processual), " Implementando linguagens funcionais: um tutorial ", de Simon Peyton-Jones e David Lester, é um excelente guia.

O básico conceitual de como funciona a avaliação funcional é guiado por exemplos em uma linguagem funcional simples mas poderosa chamada "Core". Além disso, cada parte do compilador da linguagem Core é explicada com exemplos de código no Miranda (uma linguagem funcional pura muito semelhante à Haskell).

Vários tipos diferentes de compiladores são descritos, mas mesmo se você seguir apenas o chamado compilador de modelos para o Core, terá um excelente entendimento do que faz a programação funcional funcionar.


Também gostei do tutorial Crenshaw , porque deixa absolutamente claro que um compilador é apenas outro programa que lê algumas entradas e escreve algumas.

Leia-o.

Faça o trabalho se quiser, mas veja outra referência sobre como os compiladores maiores e mais completos são realmente escritos.

E leia On Trusting Trust , para ter uma idéia das coisas não óbvias que podem ser feitas nesse domínio.


Um livro ainda não sugerido, mas muito importante, é "Linkers and Loaders", de John Levine. Se você não estiver usando um montador externo, precisará de uma maneira de gerar um arquivo de objeto que possa ser vinculado ao seu programa final. Mesmo se você estiver usando um montador externo, provavelmente precisará entender as realocações e como todo o processo de carregamento do programa funciona para criar uma ferramenta de trabalho. Este livro coleta muitas informações aleatórias sobre esse processo para vários sistemas, incluindo Win32 e Linux.


Você deve verificar os " ichbins " de Darius Bacon, que é um compilador para um pequeno dialeto Lisp, direcionado a C, em pouco mais de 6 páginas de código. A vantagem que tem sobre a maioria dos compiladores de brinquedos é que a linguagem é completa o suficiente para que o compilador seja escrito nele. (O tarball também inclui um intérprete para iniciar a coisa.)

Há mais coisas sobre o que eu achei útil em aprender a escrever um compilador na minha página da web do Ur-Scheme .


Você pode procurar no Lex / Yacc (ou no Flex / Bison, como quiser chamá-los). O Flex é um analisador lexical, que analisa e identifica os componentes semânticos ("tokens") do seu idioma, e o Bison será usado para definir o que acontece quando cada token é analisado. Isso pode ser, mas definitivamente não está limitado a, imprimir o código C, para um compilador que seria compilado em C, ou executar dinamicamente as instruções.

Esta FAQ deve ajudá-lo, e este tutorial parece bastante útil.


O Dragon Book é definitivamente o livro dos "compiladores de construção", mas se o seu idioma não for tão complicado quanto a geração atual de idiomas, convém observar o padrão Interpreter nos Design Patterns .

O exemplo no livro projeta uma linguagem semelhante à expressão regular e é bem pensado, mas, como dizem no livro, é bom pensar sobre o processo, mas é eficaz apenas em linguagens pequenas. No entanto, é muito mais rápido escrever um intérprete para um idioma pequeno com esse padrão do que ter que aprender sobre todos os diferentes tipos de analisadores, yacc e lex, etc.


Até o momento, este livro não está incluído na lista:

Fundamentos do Design de Compiladores (Torben Mogensen) (do departamento de Ciência da Computação da Universidade de Copenhague)

Também estou interessado em aprender sobre compiladores e planejar entrar nesse setor nos próximos dois anos. Este livro é o livro de teoria ideal para começar a aprender compiladores, tanto quanto eu posso ver. É GRATUITO copiar e reproduzir, de maneira limpa e cuidadosa, e fornece a você em inglês simples, sem qualquer código, mas ainda apresenta a mecânica por meio de instruções e diagramas etc. Vale a pena conferir.





language-agnostic