Como crio minha própria linguagem de programação e um compilador para ela [fechado]

427

Eu sou completo com programação e me deparei com linguagens como BASIC, FORTRAN, COBOL, LISP, LOGO, Java, C ++, C, MATLAB, Mathematica, Python, Ruby, Perl, JavaScript, Assembly e assim por diante. Não consigo entender como as pessoas criam linguagens de programação e criam compiladores para isso. Eu também não conseguia entender como as pessoas criam sistemas operacionais como Windows, Mac, UNIX, DOS e assim por diante. A outra coisa que é misteriosa para mim é como as pessoas criam bibliotecas como OpenGL, OpenCL, OpenCV, Cocoa, MFC e assim por diante. A última coisa que não consigo descobrir é como os cientistas criam uma linguagem assembly e um assembler para um microprocessador. Eu realmente gostaria de aprender todas essas coisas e tenho 15 anos. Eu sempre quis ser um cientista da computação, alguém como Babbage, Turing, Shannon ou Dennis Ritchie.


Eu já li o livro de conceitos de Design de compilador da Aho e OS de Tanenbaum e todos discutem apenas conceitos e códigos em alto nível. Eles não abordam os detalhes e nuances e como criar um compilador ou sistema operacional. Quero um entendimento concreto para poder criar um eu mesmo, e não apenas um entendimento do que é um encadeamento, semáforo, processo ou análise. Eu perguntei ao meu irmão sobre tudo isso. Ele é um estudante de SB no EECS do MIT e não tem idéia de como realmente criar todas essas coisas no mundo real. Tudo o que ele sabe é apenas uma compreensão dos conceitos de Design de Compilador e SO, como os que vocês mencionaram (como Thread, Sincronização, Concorrência, gerenciamento de memória, Análise Lexical, Geração de código intermediária e assim por diante)

abdul wakeel
fonte
Se você estiver em Unix / Linux, você pode obter informações sobre ferramentas dedicadas: lex, yacce bison.
Mouviciel 24/10/11
Minha primeira sugestão seria ler o livro do dragão de Aho. amazon.com/Compilers-Principles-Techniques-Alfred-Aho/dp/...
Julian
1
Talvez não seja muito útil, mas recomendo acessar sites.google.com/site/steveyegge2/blog-rants (blog de Steve Yegge) e steve-yegge.blogspot.com/ (outro blog de Steve Yegge).
KK.
3
Aprenda quantas linguagens de programação você puder. Dessa forma, você aprenderá com seus conceitos e com seus erros. Por que se contentar com os anões, quando você pode ficar no ombro de gigantes?
SBI
1
dica: um intérprete é mais fácil que um compilador; é apenas uma classe que "faz alguma coisa" com base no texto de entrada que lê linha por linha. outra dica: amarre isso à reflexão e você poderá controlar objetos arbitrários com o seu script.
Dave Cousineau

Respostas:

407

Basicamente, sua pergunta é "como os chips, conjuntos de instruções, sistemas operacionais, idiomas, bibliotecas e aplicativos são projetados e implementados?" Essa é uma indústria mundial de bilhões de dólares que emprega milhões de pessoas, muitas das quais são especialistas. Você pode focar sua pergunta um pouco mais.

Dito isto, posso dar uma olhada em:

Não consigo entender como as pessoas criam linguagens de programação e criam compiladores para isso.

É surpreendente para mim, mas muitas pessoas encaram as linguagens de programação como mágicas. Quando encontro pessoas em festas ou o que quer que seja, se elas me perguntam o que eu faço, digo a elas que desenvolvo linguagens de programação e implemento compiladores e ferramentas, e é surpreendente o número de vezes que as pessoas - programadores profissionais, lembre-se - dizem "uau, eu nunca pensei nisso, mas sim, alguém tem que projetar essas coisas". É como se eles achassem que as línguas já surgiram totalmente formadas com infra-estruturas de ferramentas ao seu redor.

Eles não aparecem apenas. Os idiomas são projetados como qualquer outro produto: fazendo cuidadosamente uma série de trocas entre as possibilidades concorrentes. Os compiladores e ferramentas são construídos como qualquer outro produto de software profissional: detalhando o problema, escrevendo uma linha de código de cada vez e testando o problema do programa resultante.

O design de idiomas é um tópico enorme. Se você estiver interessado em criar um idioma, um bom lugar para começar é pensar em quais são as deficiências em um idioma que você já conhece. As decisões de design geralmente surgem ao considerar um defeito de design em outro produto.

Como alternativa, considere um domínio do seu interesse e crie uma linguagem específica de domínio (DSL) que especifique soluções para problemas nesse domínio. Você mencionou o LOGO; esse é um ótimo exemplo de DSL para o domínio "desenho de linha". Expressões regulares são uma DSL para o domínio "encontrar um padrão em uma string". O LINQ em C # / VB é uma DSL para o domínio "filtrar, ingressar, classificar e projetar dados". HTML é uma DSL para o domínio "descrever o layout do texto em uma página" e assim por diante. Existem muitos domínios acessíveis a soluções baseadas em idiomas. Um dos meus favoritos é o Inform7, que é um DSL para o domínio "jogo de aventura baseado em texto"; provavelmente é a linguagem de programação séria de mais alto nível que já vi.

Depois de definir como você quer que seu idioma seja, tente anotar com precisão quais são as regras para determinar o que é um programa legal e ilegal. Normalmente, você desejará fazer isso em três níveis:

  1. léxico : quais são as regras para palavras no idioma, quais caracteres são legais, como são os números e assim por diante.
  2. sintático : como as palavras da língua se combinam em unidades maiores? Em C #, unidades maiores são coisas como expressões, instruções, métodos, classes e assim por diante.
  3. semântica : dado um programa sintaticamente legal, como você descobre o que o programa faz ?

Anote essas regras da maneira mais precisa possível . Se você fizer um bom trabalho, poderá usá-lo como base para escrever um compilador ou intérprete. Dê uma olhada na especificação C # ou na especificação ECMAScript para ver o que quero dizer; eles estão repletos de regras muito precisas que descrevem o que faz um programa jurídico e como descobrir o que se faz.

Uma das melhores maneiras de começar a escrever um compilador é escrever um compilador de idioma de alto nível para idioma de alto nível . Escreva um compilador que inclua strings no seu idioma e cuspa strings em C # ou JavaScript ou qualquer outro idioma que você saiba; deixe o compilador para esse idioma e cuide do trabalho pesado de transformá-lo em código executável.

Escrevo um blog sobre o design de C #, VB, VBScript, JavaScript e outras linguagens e ferramentas; se esse assunto lhe interessar, confira. http://blogs.msdn.com/ericlippert (histórico) e http://ericlippert.com (atual)

Em particular, você pode achar este post interessante; aqui, listo a maioria das tarefas que o compilador C # executa para você durante sua análise semântica. Como você pode ver, existem muitas etapas. Dividimos o grande problema de análise em uma série de problemas que podemos resolver individualmente.

http://blogs.msdn.com/b/ericlippert/archive/2010/02/04/how-many-passes.aspx

Finalmente, se você estiver procurando um emprego para fazer essas coisas quando for mais velho, considere vir para a Microsoft como estagiário na faculdade e tentar entrar na divisão de desenvolvedores. Foi assim que acabei com o meu trabalho hoje!

Eric Lippert
fonte
Você já escreveu sobre em que grau as otimizações do compilador não estão mais sendo feitas, pois o CLR pode fazê-las automaticamente?
6
@ Thorbjørn: Sejamos claros sobre a terminologia. Um "compilador" é qualquer dispositivo que seja traduzido de uma linguagem de programação para outra. Uma das coisas boas de ter um compilador C # que transforma C # em IL e um compilador IL (o "jitter") que transforma IL em código de máquina é que você pode gravar o compilador C # em IL (fácil!) E coloque as otimizações específicas do processador na instabilidade. Não é que as otimizações do compilador "não estejam sendo feitas", é que a equipe do compilador jit faz isso por nós. Veja blogs.msdn.com/b/ericlippert/archive/2009/06/11/…
Eric Lippert
6
@ Cyclotis04: O Inform6 compila no código Z, que é um famoso exemplo extremamente antigo de uma máquina virtual baseada em bytecode. É assim que todos os jogos da Infocom nos anos 80 podem ser maiores que a memória e portáveis ​​para várias arquiteturas; os jogos foram compilados para código-z e, em seguida, os intérpretes de código-z com paginação de memória de código foram implementados para várias máquinas. Hoje em dia, é claro, você pode executar um intérprete zcode em um relógio de pulso, se precisar, mas na época em que era alta tecnologia . Veja en.wikipedia.org/wiki/Z-machine para obter detalhes.
Eric Lippert
@EricLippert Compiler não é um dispositivo, o dispositivo é algo contém hardware.we pode dizer um programa pré-definido que ter um conjunto de regras para converter dados de entrada para código de máquina
Dharam
2
@ dhams: Um dispositivo é qualquer coisa feita para uma finalidade específica. Todo compilador que eu já escrevi foi executado em hardware que foi criado especificamente para permitir a existência de compiladores.
Eric Lippert
127

Você pode encontrar Lets Build a Compiler por Jack Crenshaw uma introdução interessante para escrever compiladores e linguagem assembly.

O autor o manteve muito simples e focado na criação de funcionalidades reais.

usuário
fonte
2
O interessante da introdução de Crenshaw é que ela termina (spoiler: está incompleta) exatamente na época em que você se deparava com os problemas que o faziam perceber, ei, eu realmente deveria ter projetado minha linguagem completamente antes de começar a implementá-la. E então você diz, ei, se eu tiver que escrever uma especificação completa da linguagem, por que não fazê-lo em uma notação formal que eu possa alimentar em uma ferramenta para gerar um analisador? E então você está fazendo isso como todo mundo.
Kindall
3
@kindall, você precisa ter feito isso manualmente, para perceber que há uma razão para usar as ferramentas.
72

"Eu realmente gostaria de aprender essas coisas". Se você é sério a longo prazo:

  • Ir para a faculdade, se especializar em engenharia de software. Faça todas as aulas de compilador que você puder obter. As pessoas que ministram as aulas são mais instruídas e mais experientes que você; é bom ter as perspectivas de especialistas usadas para apresentar as informações de maneira que você nunca obterá com a leitura de código.

  • Continue com as aulas de matemática no ensino médio e continue na faculdade por todos os 4 anos. Foco em matemática não-padrão: lógica, teoria de grupos, meta-matemática. Isso forçará você a pensar abstratamente. Ele permitirá que você leia os trabalhos de teoria avançada sobre compilação e entenda por que essas teorias são interessantes e úteis. Você pode ignorar essas teorias avançadas, se quiser estar sempre por trás do estado da arte.

  • Colete / leia os textos padrão do compilador: Aho / Ullman, etc. Eles contêm o que a comunidade geralmente concorda que é fundamental. Você pode não usar tudo nesses livros, mas deve saber que ele existe e saber por que não o está usando. Eu pensei que Muchnick era ótimo, mas é para tópicos bastante avançados.

  • Crie um compilador. Comece AGORA construindo um podre. Isso ensinará alguns problemas. Construa um segundo. Repetir. Essa experiência cria uma enorme sinergia com o aprendizado do livro.

  • Um bom lugar para começar é aprender sobre o BNF (Backus Naur Form), analisadores e geradores de analisadores. O BNF é efetivamente usado universalmente no território dos compiladores, e você não pode falar realisticamente com seus colegas tipos de compiladores se não o conhecer.

Se você deseja uma excelente primeira introdução à compilação e o valor direto do BNF não apenas para documentação, mas como uma metalinguagem processável por ferramentas, consulte este tutorial (não o meu) sobre a construção de "meta" compiladores (compiladores que compilam compiladores) com base em um artigo de 1964 (sim, você leu certo) ["META II, uma linguagem de escrita de compilador orientada à sintaxe" de Val Schorre. (http://doi.acm.org/10.1145/800257.808896)] Este IMHO é um dos melhores artigos de ficção científica já escritos: ensina a construir compiladores-compiladores em 10 páginas. Eu aprendi inicialmente com este artigo.

O que eu escrevi acima é muito da experiência pessoal, e acho que me serviu muito bem. YMMV, mas IMHO, não por muito.

Ira Baxter
fonte
54
-1 Nenhuma das alternativas acima é necessária.
Neil Butterworth
77
@nbt Nenhuma das opções acima é necessária. Mas tudo isso ajuda. Realmente muito.
Konrad Rudolph
1
Discordo particularmente do "Aprenda matemática a pensar abstratamente!" sugestão. Mesmo que você pense que "aprender a pensar abstratamente" é particularmente útil na criação de sua própria linguagem de programação e compilador (não acho - acho muito mais útil aprender fazendo do que seguindo essas rotas indiretas incrivelmente indiretas) , matemática não é o único campo com pensamento abstrato! (Eu sou um matemático btw, então eu não estou negando o uso de matemática em geral, apenas a sua aplicabilidade neste caso em particular ...)
grautur
26
Se você quiser ler os documentos técnicos avançados sobre a teoria dos compiladores, é melhor ser matematicamente competente. Você pode decidir ignorar essa literatura, e sua teoria e, portanto, os compiladores serão mais pobres. Todos os opositores aqui argumentam que você pode criar um compilador sem muita educação formal, e eu concordo. Eles parecem sugerir que você pode criar compiladores realmente bons sem ele. Essa não é uma aposta que eu gostaria de fazer.
Ira Baxter
7
O CS é uma disciplina que é realmente útil para o design e a implementação da linguagem. Não é obrigatório, é claro, mas houve décadas de pesquisa que podem e devem ser aproveitadas, e não há motivo para repetir os erros de outros.
Donal Fellows
46

Aqui está um livro / curso on-line que você pode seguir chamado Os Elementos dos Sistemas de Computação: Construindo um Computador Moderno a partir dos Primeiros Princípios .

Usando simuladores, você realmente constrói um sistema de computador completo desde o início. Embora muitos comentaristas tenham declarado que sua pergunta é muito ampla, este livro realmente a responde, mantendo-se muito gerenciável. Quando terminar, você terá escrito um jogo em uma linguagem de alto nível (que você projetou), que usa a funcionalidade do seu próprio sistema operacional, que é compilada em uma linguagem de VM (que você projetou) pelo seu compilador, que obtém traduzido para uma linguagem assembly (que você projetou) pelo seu tradutor de VM, que é montado no código da máquina (que você projetou) pelo seu assembler, que é executado no sistema do computador, que você monta a partir dos chips que você projetou usando lógica booleana e uma linguagem simples de descrição de hardware.

Os capítulos:

  1. Visão geral do curso
  2. Lógica Booleana
  3. Fichas Combinatórias
  4. Fichas sequenciais
  5. Linguagem da Máquina
  6. Arquitetura de Computadores
  7. Montador
  8. Máquina Virtual I: Aritmética
  9. Máquina Virtual II: Controle
  10. Linguagem de programação
  11. Compilador I: Análise de Sintaxe
  12. Compilador II: Geração de Código
  13. Sistema operacional
  14. Item da lista

Mais diversão para ir

colítio
fonte
Obrigado pelas edições, pessoa desconhecida. Eu tentei algumas vezes, mas não consegui focar o suficiente na descrição ... mas não queria não mencionar o livro. O livro está agora online no link do Plano de Estudo: www1.idc.ac.il/tecs/plan.html . Também é muito on-line com preços razoáveis. Aproveite todo mundo.
Joe Internet
Eu ia sugerir isso mesmo ... para o preguiçoso, veja a intro 10 minutos: De NAND para Tetris em 12 etapas @ youtube.com/watch?v=JtXvUoPx4Qs
Richard Anthony Hein
46

Dê um passo para trás. Um compilador é simplesmente um programa que traduz um documento em um idioma para um documento em outro idioma. Ambas as línguas devem ser bem definidas e específicas.

As linguagens não precisam ser linguagens de programação. Eles podem ser qualquer idioma cujas regras possam ser escritas. Você provavelmente já viu o Google Translate ; esse é um compilador porque pode traduzir um idioma (por exemplo, alemão) para outro (japonês, talvez).

Outro exemplo de um compilador é um mecanismo de renderização HTML. Sua entrada é um arquivo HTML e a saída é uma série de instruções para desenhar os pixels na tela.

Quando a maioria das pessoas fala sobre um compilador, geralmente se refere a um programa que traduz uma linguagem de programação de alto nível (como Java, C, Prolog) em uma de baixo nível (código de montagem ou de máquina). Isso pode ser assustador. Mas não é tão ruim quando você considera o generalista que um compilador é um programa que traduz um idioma para outro.

Você pode escrever um programa que reverta todas as palavras de uma string? Por exemplo:

When the cat's away, the mice will play.

torna-se

nehW eht s'tac yawa, eht ecim lliw yalp.

Não é um programa difícil de escrever, mas você precisa pensar em algumas coisas:

  • O que é uma "palavra"? Você pode definir quais caracteres compõem uma palavra?
  • Onde as palavras começam e terminam?
  • As palavras são separadas por apenas um espaço, ou pode haver mais - ou menos?
  • A pontuação também precisa ser revertida?
  • E quanto à pontuação dentro de uma palavra?
  • O que acontece com letras maiúsculas?

As respostas para essas perguntas ajudam o idioma a ser bem definido. Agora vá em frente e escreva o programa. Parabéns, você acabou de escrever um compilador.

Que tal isso: Você pode escrever um programa que utiliza uma série de instruções de desenho e gera um arquivo PNG (ou JPEG)? Talvez algo parecido com isto:

image 100 100
background black
color red
line 20 55 93 105
color green
box 0 0 99 99

Novamente, você precisará pensar um pouco para definir o idioma:

  • Quais são as instruções primitivas?
  • O que vem depois da palavra "linha"? O que vem depois da "cor"? Da mesma forma para "plano de fundo", "caixa" etc.
  • O que é um número?
  • Um arquivo de entrada vazio é permitido?
  • É correto capitalizar as palavras?
  • Números negativos são permitidos?
  • O que acontece se você não der a diretiva "imagem"?
  • Tudo bem não especificar uma cor?

Obviamente, há mais perguntas a serem respondidas, mas se você pode identificá-las, definiu um idioma. O programa que você escreve para fazer a tradução é, você imagina, um compilador.

Veja bem, escrever um compilador não é tão difícil. Os compiladores que você usou em Java ou C são apenas versões maiores desses dois exemplos. Então vá em frente! Defina uma linguagem simples e escreva um programa para fazer com que essa linguagem faça alguma coisa. Mais cedo ou mais tarde, você desejará estender seu idioma. Por exemplo, você pode querer adicionar variáveis ​​ou expressões aritméticas. Seu compilador se tornará mais complexo, mas você entenderá tudo isso porque você mesmo o escreveu. É assim que os idiomas e os compiladores ocorrem.

Barry Brown
fonte
7
myFirstCompiler = (str) -> ("" + (str || "")). split (''). reverse (). join (''); jsfiddle.net/L7qSr
Larry Battle
21

Se você estiver interessado no design do compilador, consulte o Dragon Book (título oficial: Compiladores: Princípios, Técnicas e Ferramentas). É amplamente considerado como um livro clássico sobre esse assunto.

Brian Agnew
fonte
4
Observe que você pode precisar de uma experiência um pouco mais real para aproveitar ao máximo este livro. Ótima referência, no entanto.
13
-1 Apenas quem não leu pode pensar que o livro do dragão é bom. e particularmente não aborda a questão.
Neil Butterworth
33
O Livro do Dragão? Para um entusiasta de quinze anos de idade? Prefiro que ele mantenha seu entusiasmo por mais um tempo.
David Thornley
1
Uma alternativa mais acessível: 'Pragmática da linguagem de programação' 3e .
willjcroz
@DavidThornley Não conte-o completamente (sim, eu sei que este é um post muito antigo). Comecei a pesquisar como os idiomas funcionam aos 15 anos e me concentrei especificamente em máquinas virtuais. Agora tenho 16 anos e, depois de meses de pesquisa, escrita e reescrita, tenho um intérprete e compilador que me agrada.
David
10

Não acredite que exista algo mágico em um compilador ou sistema operacional: não existe. Lembra dos programas que você escreveu para contar todas as vogais em uma string ou somar os números em uma matriz? Um compilador não é diferente em conceito; é apenas muito maior.

Todo programa tem três fases:

  1. leia algumas coisas
  2. processe essas coisas: converta os dados de entrada nos dados de saída
  3. escreva outras coisas - os dados de saída

Pense nisso: o que é entrada para o compilador? Uma sequência de caracteres de um arquivo de origem.

O que é produzido pelo compilador? Uma sequência de bytes que representa instruções da máquina para o computador de destino.

Então, qual é a fase de "processo" do compilador? O que essa fase faz?

Se você considerar que o compilador - como qualquer outro programa - precisa incluir essas três fases, terá uma boa idéia de como um compilador é construído.

Pete Wilson
fonte
3
Como Neil disse, é verdade, mas não é útil. Aspectos fundamentais do compilador, como gramática recursiva e tabelas de símbolos, não são intuitivamente óbvios.
Mason Wheeler
1
@Mason Wheeler: Eu acho que alguém que aspira realisticamente a escrever um compilador (e projetar o idioma de destino?) Provavelmente pensaria que gramática recursiva e tabelas de símbolos eram conceitos bastante básicos.
FumbleFingers
8

Não sou especialista, mas aqui está minha facada:

Você não parece perguntar sobre escrever um compilador, apenas um montador. Isso não é realmente mágico.

Roubando a resposta de alguém do SO ( https://stackoverflow.com/questions/3826692/how-do-i-translate-assembly-to-binary ), o assembly fica assim:

label:  LDA #$00
        JMP label

Em seguida, você o executa através de um assembler e se transforma em algo assim:

$A9 $00
$4C $10 $00

Só que tudo está esmagado, assim:

$A9 $00 $4C $10 $00

Realmente não é mágico.

Você não pode escrever isso no bloco de notas, porque o bloco de notas usa ASCII (não hexadecimal). Você usaria um editor hexadecimal ou simplesmente gravaria os bytes programaticamente. Você escreve esse hexadecimal em um arquivo, nomeie-o como "a.exe" ou "a.out" e diga ao sistema operacional para executá-lo.

Obviamente, CPUs e sistemas operacionais modernos são realmente bastante complicados, mas essa é a idéia básica.

Se você deseja escrever um novo compilador, veja como é feito:

1) Escreva uma linguagem interpretada usando algo como o exemplo da calculadora em pyparsing (ou qualquer outra estrutura de análise boa). Isso permitirá que você se familiarize com o básico da análise.

2) Escreva um tradutor. Traduza seu idioma para, por exemplo, Javascript. Agora seu idioma será executado em um navegador.

3) Escreva um tradutor para um nível inferior, como LLVM, C ou Assembly.

Você pode parar por aqui, este é um compilador. Não é um compilador otimizador, mas essa não era a questão. Você também pode precisar escrever um vinculador e montador, mas realmente deseja?

4) (Insano) Escreva um otimizador. Grandes equipes trabalham há décadas nisso.

4) (Sane) Envolva-se em uma comunidade existente. GCC, LLVM, PyPy, a equipe principal que trabalha com qualquer intérprete.

wisty
fonte
8

Vários outros deram excelentes respostas. Vou apenas adicionar mais algumas sugestões. Primeiro, um bom livro para o que você está tentando fazer são os textos de Implementação de Compilador Moderno da Appel (escolha C , Java ou ML Padrão ). Este livro leva você através da implementação completa de um compilador para uma linguagem simples, o Tiger, para o assembly MIPS que pode ser executado em um emulador, juntamente com uma biblioteca mínima de suporte ao tempo de execução. Para uma única passagem por tudo o necessário para fazer uma linguagem compilada funcionar, é um livro muito bom 1 .

A Appel orientará você sobre como compilar uma linguagem pré-projetada, mas não gasta muito tempo com o significado de vários recursos da linguagem ou como pensar sobre eles em termos de seus méritos relativos para criar o seu próprio. Para esse aspecto, Linguagens de Programação: Conceitos e Construções é decente. Conceitos, técnicas e modelos de programação de computadores também é um bom livro para pensar profundamente sobre o design da linguagem, embora o faça no contexto de uma única linguagem ( Oz ).

Por fim, mencionei que Appel tem seu texto em C, Java e Standard ML - se você é sério sobre construção de compiladores e linguagens de programação, recomendo aprender ML e usar essa versão do Appel. As linguagens da família ML têm sistemas de tipos fortes, predominantemente funcionais - recursos que serão diferentes de muitas outras linguagens; portanto, aprendê-las se você ainda não conhece uma linguagem funcional aprimora seu trabalho com a linguagem. Além disso, suas mentalidades funcionais e de correspondência de padrões são extremamente adequadas aos tipos de manipulações que você precisa fazer frequentemente em um compilador; portanto, os compiladores escritos em linguagens baseadas em ML são tipicamente muito mais curtos e fáceis de entender do que os compiladores escritos em C, Java ou idiomas semelhantes. O livro de Harperno Standard ML é um guia muito bom para você começar; trabalhar com isso deve prepará-lo para assumir o livro de implementação do compilador Standard Appel da ML. Se você aprender o ML Padrão, também será muito fácil pegar o OCaml para trabalhos posteriores; O IMO possui ferramentas melhores para o programador que trabalha (integra-se de maneira mais limpa com o ambiente do sistema operacional ao redor, produz programas executáveis ​​com facilidade e possui algumas ferramentas espetaculares de construção de compiladores, como ulex e Menhir).


1 Para referência a longo prazo, prefiro o Dragon Book, pois ele tem mais detalhes sobre as coisas às quais provavelmente me refiro, como o funcionamento interno dos algoritmos do analisador e tem uma cobertura mais ampla de abordagens diferentes, mas o livro de Appel é muito bom. para um primeiro passe. Basicamente, Appel ensina uma maneira de fazer as coisas o tempo todo através do compilador e guia você através dele. O Dragon Book cobre diferentes alternativas de design com mais detalhes, mas fornece muito menos orientações sobre como fazer algo funcionar.


Editado : substitua a referência incorreta do Aho por Sethi, mencione o CTMCP.

Michael Ekstrand
fonte
Ugh, eu tinha o Essentials Of Programming Languages ​​na minha aula de intérpretes. Foi terrível. Eu até gosto de esquemas pessoalmente e não me importo com a sintaxe, foram os autores que explicaram mal os conceitos que me arruinaram.
Greg Guida
Gosto de compilar Appel com continuações, mas achei que seus livros pressupunham muito conhecimento prévio.
11136 Jon Harrop
6

Eu tive que criar um compilador para as aulas na faculdade.

O básico de fazer isso não é tão complicado quanto você imagina. O primeiro passo é criar sua gramática. Pense na gramática da língua inglesa. Da mesma maneira, você pode analisar uma frase se ela tiver um assunto e predicado. Para saber mais sobre isso, leia sobre gramáticas livres de contexto .

Depois que você tiver a gramática (as regras do seu idioma), escrever um compilador é tão simples quanto seguir essas regras. Os compiladores geralmente se traduzem no código da máquina, mas, a menos que você queira aprender x86, sugiro que você talvez veja o MIPS ou crie sua própria máquina virtual.

Os compiladores geralmente têm duas partes, um scanner e um analisador. Basicamente, o scanner lê o código e o separa em tokens. O analisador analisa a estrutura desses tokens. Em seguida, o compilador segue e segue algumas regras bastante simples para convertê-lo em qualquer código em que você precise (montagem, código intermediário como bytecode etc.). Se você dividi-lo em pedaços cada vez menores, isso eventualmente não é assustador.

Boa sorte!

Jerr
fonte
8
Conceitualmente simples? Sim. Realmente simples? Não
Neil Butterworth
7
Uhm. O compilador, após a varredura / análise, precisa fazer verificação / inferência de tipo, otimização, alocação de registros, etc. etc. Essas etapas são simples, mas simples. (Ao usar o código interpretado, você apenas adiar estas peças para a fase de execução.)
Macke
Nenhum voto para mim: enquanto os compiladores têm duas partes básicas, uma delas é criar uma descrição abstrata do programa (normalmente dividida em varredura e análise) e a outra escrever uma versão dessa descrição abstrata novamente em alguns outra forma (por exemplo, código de máquina). (Nota: Otimizando compiladores normalmente tentar melhorar a descrição abstrata antes de escrevê-lo para fora, mas isso é um refinamento.)
Donal Fellows
6

O livro de Petzold, Code, é uma ótima introdução a não técnicos e técnicos, começando pelos primeiros princípios. É altamente legível e vasto em seu escopo sem ficar muito atolado.

Agora que escrevi isso, vou ter que relê-lo.

Kevin Won
fonte
5

Existem excelentes respostas neste tópico, mas eu só queria adicionar o meu, pois eu também já tive a mesma pergunta. (Além disso, gostaria de salientar que o livro sugerido por Joe-Internet é um excelente recurso.)

Primeiro, a questão de como um computador funciona? É assim: Entrada -> Computação -> Saída.

Primeiro, considere a parte “Computar”. Veremos como a entrada e a saída funcionam mais tarde.

Um computador consiste essencialmente em um processador (ou CPU) e alguma memória (ou RAM). A memória é uma coleção de locais, cada um dos quais pode armazenar um número finito de bits, e cada um desses locais de memória pode ser referenciado por um número, isso é chamado de endereço do local da memória. O processador é um dispositivo que pode buscar dados a partir da memória, execute algumas operações com base nos dados e escreva novamente alguns dados na memória. Como o processador descobre o que ler e o que fazer depois de ler os dados da memória?

Para responder a isso, precisamos entender a estrutura de um processador. A seguir, é apresentada uma visão bastante simples. Um processador consiste essencialmente em duas partes. Um é um conjunto de locais de memória construídos dentro do processador que servem como memória de trabalho. Estes são chamados de "registros". O segundo é um conjunto de máquinas eletrônicas construídas para executar determinadas operações usando os dados nos registros. Existem dois registros especiais chamados de “Contador de Programas” ou o pc e o “Registro de Instruções” ou o ir. O processador considera a memória particionada em três partes. A primeira parte é a “memória do programa”, que armazena o programa de computador que está sendo executado. O segundo é a "memória de dados". O terceiro é usado para alguns propósitos especiais, falaremos sobre isso mais tarde. O contador de programas contém o local da próxima instrução a ser lida na memória do programa. O contador de instruções Contém um número que se refere à operação atual que está sendo executada. Cada operação que um processador pode executar é referida por um número chamado código operacional da operação. Como um computador funciona essencialmente, ele lê o local da memória referenciado pelo contador de programas no registro de instruções (e incrementa o contador de programas para que aponte para o local da memória da próxima instrução). Em seguida, ele lê o Registro de instruções e executa a operação desejada. Por exemplo, a instrução pode ser a leitura de um local específico da memória em um registro, ou a gravação em algum registro ou a execução de alguma operação usando os valores de dois registros e a saída em um terceiro registro. O contador de instruções Contém um número que se refere à operação atual que está sendo executada. Cada operação que um processador pode executar é referida por um número chamado código operacional da operação. Como um computador funciona essencialmente, ele lê o local da memória referenciado pelo contador de programas no registro de instruções (e incrementa o contador de programas para que aponte para o local da memória da próxima instrução). Em seguida, ele lê o Registro de instruções e executa a operação desejada. Por exemplo, a instrução pode ser a leitura de um local específico da memória em um registro, ou a gravação em algum registro ou a execução de alguma operação usando os valores de dois registros e a saída em um terceiro registro. O contador de instruções Contém um número que se refere à operação atual que está sendo executada. Cada operação que um processador pode executar é referida por um número chamado código operacional da operação. Como um computador funciona essencialmente, ele lê o local da memória referenciado pelo contador de programas no registro de instruções (e incrementa o contador de programas para que aponte para o local da memória da próxima instrução). Em seguida, ele lê o Registro de instruções e executa a operação desejada. Por exemplo, a instrução pode ser a leitura de um local específico da memória em um registro, ou a gravação em algum registro ou a execução de alguma operação usando os valores de dois registros e a saída em um terceiro registro. Cada operação que um processador pode executar é referida por um número chamado código operacional da operação. Como um computador funciona essencialmente, ele lê o local da memória referenciado pelo contador de programas no registro de instruções (e incrementa o contador de programas para que aponte para o local da memória da próxima instrução). Em seguida, ele lê o Registro de instruções e executa a operação desejada. Por exemplo, a instrução pode ser a leitura de um local específico da memória em um registro, ou a gravação em algum registro ou a execução de alguma operação usando os valores de dois registros e a saída em um terceiro registro. Cada operação que um processador pode executar é referida por um número chamado código operacional da operação. Como um computador funciona essencialmente, ele lê o local da memória referenciado pelo contador de programas no registro de instruções (e incrementa o contador de programas para que aponte para o local da memória da próxima instrução). Em seguida, ele lê o Registro de instruções e executa a operação desejada. Por exemplo, a instrução pode ser a leitura de um local específico da memória em um registro, ou a gravação em algum registro ou a execução de alguma operação usando os valores de dois registros e a saída em um terceiro registro. Como um computador funciona essencialmente, ele lê o local da memória referenciado pelo contador de programas no registro de instruções (e incrementa o contador de programas para que aponte para o local da memória da próxima instrução). Em seguida, ele lê o Registro de instruções e executa a operação desejada. Por exemplo, a instrução pode ser a leitura de um local específico da memória em um registro, ou a gravação em algum registro ou a execução de alguma operação usando os valores de dois registros e a saída em um terceiro registro. Como um computador funciona essencialmente, ele lê o local da memória referenciado pelo contador de programas no registro de instruções (e incrementa o contador de programas para que aponte para o local da memória da próxima instrução). Em seguida, ele lê o Registro de instruções e executa a operação desejada. Por exemplo, a instrução pode ser a leitura de um local específico da memória em um registro, ou a gravação em algum registro ou a execução de alguma operação usando os valores de dois registros e a saída em um terceiro registro.

Agora, como o computador executa Entrada / Saída? Vou fornecer uma resposta muito simplificada. Veja http://en.wikipedia.org/wiki/Input/output e http://en.wikipedia.org/wiki/Interrupt. para mais. Ele usa duas coisas, a terceira parte da memória e algo chamado Interrompe. Todo dispositivo conectado a um computador deve poder trocar dados com o processador. Faz isso usando a terceira parte da memória mencionada anteriormente. O processador aloca uma fatia de memória para cada dispositivo e o dispositivo e o processador se comunicam através dessa fatia de memória. Mas como o processador sabe em que local se refere a qual dispositivo e quando ele precisa trocar dados? É aqui que entram as interrupções. Uma interrupção é essencialmente um sinal para o processador pausar o que é atualmente e salvar todos os seus registros em um local conhecido e começar a fazer outra coisa. Existem muitas interrupções, cada uma identificada por um número único. Para cada interrupção, há um programa especial associado a ela. Quando a interrupção ocorre, o processador executa o programa correspondente à interrupção. Agora, dependendo da BIOS e de como os dispositivos de hardware estão conectados à placa-mãe do computador, cada dispositivo recebe uma interrupção única e uma fatia de memória. Durante a inicialização do sistema operacional com a ajuda do BIOS, determina a localização da interrupção e da memória de cada dispositivo e configura os programas especiais para a interrupção para lidar adequadamente com os dispositivos. Portanto, quando um dispositivo precisa de alguns dados ou deseja enviar alguns dados, sinaliza uma interrupção. O processador pausa o que está fazendo, lida com a interrupção e volta ao que está fazendo. Existem muitos tipos de interrupções, como para o disco rígido, o teclado etc. Um importante é o timer do sistema, que invoca uma interrupção em intervalos regulares. Também existem opcodes que podem acionar interrupções, chamadas interrupções de software.

Agora podemos quase entender como funciona um sistema operacional. Quando ele é inicializado, o sistema operacional interrompe o temporizador, para que ele controle o sistema a intervalos regulares. Ele também configura outras interrupções para manipular outros dispositivos etc. Agora, quando o computador está executando vários programas, e a interrupção do timer acontece, o sistema operacional ganha controle e executa tarefas importantes, como gerenciamento de processos, gerenciamento de memória, etc. uma maneira abstrata de os programas acessarem os dispositivos de hardware, em vez de permitir que acessem diretamente os dispositivos. Quando um programa deseja acessar um dispositivo, ele chama algum código fornecido pelo sistema operacional que então fala com o dispositivo. Há muita teoria envolvida nelas, que trata de concorrência, threads, bloqueios, gerenciamento de memória etc.

Agora, em teoria, é possível escrever um programa diretamente usando opcodes. Isso é chamado de código de máquina. Isso é obviamente muito doloroso. Agora, uma linguagem assembly para o processador nada mais é do que mnemônicos para esses códigos de operação, o que facilita a gravação de programas. Um assembler simples é um programa que pega um programa escrito em assembly e substitui os mnemônicos pelos opcodes apropriados.

Como se desenha um processador e uma linguagem assembly. Para saber que você precisa ler alguns livros sobre arquitetura de computadores. (ver capítulos 1-7 do livro referido por joe-internet). Isso envolve aprender sobre álgebra booleana, como construir circuitos combinatórios simples para adicionar, multiplicar etc, como construir memória e circuitos sequenciais, como construir um microprocessador e assim por diante.

Agora, como se escreve idiomas de computador. Pode-se começar escrevendo um simples assembler no código da máquina. Em seguida, use esse assembler para escrever um compilador para um subconjunto simples de C. Em seguida, use esse subconjunto de C para escrever uma versão mais completa de C. Finalmente, use C para escrever uma linguagem mais complicada, como python ou C ++. Obviamente, para escrever uma linguagem, você deve primeiro criá-la (da mesma maneira que descreve um processador). Mais uma vez, olhe alguns livros sobre isso.

E como se escreve um sistema operacional. Primeiro você direciona uma plataforma como x86. Então você descobre como inicializa e quando seu sistema operacional será chamado. Um PC típico é inicializado dessa maneira. Ele inicia e o BIOS realiza alguns testes. Em seguida, o BIOS lê o primeiro setor do disco rígido e carrega o conteúdo em um local específico na memória. Em seguida, ele configura a CPU para começar a executar esses dados carregados. Este é o ponto em que você é chamado. Um sistema operacional típico nesse momento carrega a memória restante. Em seguida, inicializa os dispositivos e configura outras coisas e, finalmente, recebe você com a tela de login.

Então, para escrever um sistema operacional, você deve escrever o “carregador de inicialização”. Em seguida, você deve escrever um código para lidar com interrupções e dispositivos. Então você deve escrever todo o código para gerenciamento de processos, gerenciamento de dispositivos, etc. Em seguida, você deve escrever uma API que permita que os programas em execução no seu sistema operacional acessem dispositivos e outros recursos. E, finalmente, você deve escrever um código que leia um programa do disco, configure-o como um processo e comece a executá-lo.

É claro que minha resposta é abertamente simplificada e provavelmente de pouco uso prático. Em minha defesa, agora sou um estudante de graduação em teoria, por isso esqueci muitas dessas coisas. Mas você pode pesquisar no google muitas dessas coisas e descobrir mais.

dubyaman
fonte
4

Lembro-me de um ponto da minha carreira de programador em que estava em um estado semelhante de confusão com o seu: eu havia lido bastante sobre a teoria, o livro Dragon, o livro Tiger (vermelho), mas ainda não tinha muito uma pista de como juntar tudo.

O que o uniu foi encontrar um projeto concreto para fazer (e depois descobrir que eu só precisava de um pequeno subconjunto de toda a teoria).

A Java VM me forneceu um bom ponto de partida: conceitualmente é um "processador", mas é altamente abstraído dos detalhes confusos das CPUs reais. Também oferece uma parte importante e muitas vezes esquecida do processo de aprendizado: desmontar as coisas antes de montá-las novamente (como as crianças costumavam fazer com aparelhos de rádio nos velhos tempos).

Brinque com um descompilador e a classe Hello, World em Java. Leia a especificação da JVM e tente entender o que está acontecendo. Isso fornecerá informações fundamentadas sobre o que o compilador está fazendo .

Em seguida, brinque com o código que cria a classe Hello, World. (Na verdade, você está criando um compilador específico de aplicativo, para um idioma altamente especializado no qual você pode apenas dizer Olá, Mundo.)

Tente escrever um código capaz de ler Hello, World escrito em outro idioma e gerar a mesma classe. Faça com que você possa alterar a sequência de "Olá, Mundo" para outra coisa.

Agora tente compilar (em Java) uma classe que calcule alguma expressão aritmética, como "2 * (3 + 4)". Desmonte esta classe, escreva um "compilador de brinquedos" que possa reuni-la novamente.

Morendil
fonte
3

1) Ótimas palestras em vídeo da Universidade de Washington:

Construção do compilador CSE P 501 - outono de 2009 www.cs.washington.edu/education/courses/csep501/09au/lectures/video.html *

2) SICP http://groups.csail.mit.edu/mac/classes/6.001/abelson-sussman-lectures/ E o livro com o mesmo nome. Isso é realmente obrigatório para qualquer engenheiro de software existente.

3) Além disso, sobre programação funcional, Haskell, cálculo lambda, semântica (incluindo denotacional) e implementação do compilador para linguagens funcionais. Você pode iniciar a partir de 2005-SS-FP.V10.2005-05-24.HDV se você já conhece o Haskell. Vídeos Uxx são respostas. Por favor, siga os vídeos Vxx primeiro.

http://video.s-inf.de/#FP.2005-SS-Giesl.(COt).HD_Videoaufzeichnung

(os vídeos são em inglês, outros cursos são em alemão.)

  • novos usuários podem postar apenas um máximo de dois hiperlinks.
Zura
fonte
3

ANTLR é um bom ponto de partida. É uma estrutura geradora de linguagem, semelhante ao Lex e Yacc. Existe uma interface gráfica chamada ANTLRWorks que simplifica o processo.

No mundo .NET, existe o Dynamic Language Runtime, que pode ser usado para gerar código no mundo .NET. Eu escrevi uma linguagem de expressão chamada Zentrum que gera código usando o DLR. Ele mostrará como analisar e executar expressões digitadas estaticamente e dinamicamente.

Sean
fonte
2

Para uma introdução simples sobre como os compiladores funcionam e como criar sua própria linguagem de programação, eu recomendaria o novo livro http://createyourproglang.com, que se concentra mais na teoria do design de linguagem sem precisar conhecer os componentes internos do OS / CPU, como lexers, analisadores , intérpretes etc.

Ele usa as mesmas ferramentas usadas para criar as linguagens de programação Coffee Script e Fancy recentemente populares .

mythz
fonte
2

Se tudo o que você diz é verdade, você tem o perfil de um pesquisador promissor, e um entendimento concreto pode ser obtido apenas de uma maneira: estudar. E não estou dizendo " Leia todos esses livros de ciência da computação de alto nível (especialmente esses ) escritos por esse gênio !"; Quero dizer: você deve estar com pessoas de alto nível para ser um cientista da computação como Charles Babbage, Alan Turing, Claude Shannon ou Dennis Ritchie. Não estou desprezando pessoas autodidatas (sou uma delas), mas não há muitas pessoas como você por aí. Eu recomendo seriamente o Symbolic Systems Program (SSP) na Stanford University . Como o site diz:

O Programa de Sistemas Simbólicos (SSP) da Universidade de Stanford se concentra em computadores e mentes: sistemas artificiais e naturais que usam símbolos para representar informações. O SSP reúne estudantes e professores interessados ​​em diferentes aspectos da relação humano-computador, incluindo ...

  • ciência cognitiva : estudando a inteligência humana, linguagens naturais e o cérebro como processos computacionais;
  • inteligência artificial : dotando computadores de comportamento e compreensão semelhantes aos humanos; e
  • interação humano-computador : projetando softwares e interfaces que funcionem bem com usuários humanos.
quantme
fonte
2

Vou sugerir algo um pouco fora do campo da esquerda: aprenda Python (ou talvez Ruby, mas tenho muito mais experiência em Python, é isso que vou discutir). E não apenas se interessa por isso, mas realmente o conhece em um nível profundo.

Existem várias razões pelas quais sugiro:

  1. Python é uma linguagem excepcionalmente bem projetada. Embora tenha algumas verrugas, possui menos IMHO do que muitos outros idiomas. Se você é um designer de idiomas novato, é bom se expor ao maior número possível de idiomas.

  2. A implementação padrão do Python (CPython) é de código aberto e bem documentada, facilitando a compreensão de como a linguagem funciona.

  3. O Python é compilado em um código de bytes simples, mais fácil de entender do que assembly e que funciona da mesma maneira em todas as plataformas em que o Python roda. Então, você aprenderá sobre compilação (já que o Python compila seu código-fonte em código de bytes) e interpretação (como esse código de byte é interpretado na máquina virtual do Python).

  4. O Python possui muitos novos recursos propostos, documentados em PEPs numeradas (Python Enhancement Proposals). PEPs interessantes para ler para ver como os designers de linguagem consideraram implementar um recurso antes de escolher a maneira como eles realmente o fizeram. (As PEPs que ainda estão em consideração são especialmente interessantes nesse sentido.)

  5. O Python possui uma mistura de recursos de vários paradigmas de programação; portanto, você aprenderá sobre várias maneiras de abordar a solução de problemas e terá uma gama mais ampla de ferramentas a considerar, incluindo em sua própria linguagem.

  6. O Python facilita bastante a extensão da linguagem de várias maneiras com decoradores, metaclasses, ganchos de importação, etc., para que você possa brincar com os novos recursos da linguagem até certo ponto, sem realmente sair da linguagem. (Como um aparte: os blocos de código são objetos de primeira classe no Ruby, então você pode realmente escrever novas estruturas de controle, como loops! Eu tenho a impressão de que os programadores do Ruby não necessariamente consideram que estender a linguagem, é apenas como você programa em Ruby. Mas é bem legal.)

  7. No Python, você pode realmente desmontar o bytecode gerado pelo compilador ou até escrever o seu próprio a partir do zero e pedir ao intérprete para executá-lo (eu mesmo fiz isso, e foi alucinante, mas divertido).

  8. O Python possui boas bibliotecas para análise. Você pode analisar o código Python em uma árvore de sintaxe abstrata e depois manipulá-lo usando o módulo AST. O módulo PyParsing é útil para analisar idiomas arbitrários, como os que você cria. Em teoria, você poderia escrever seu compilador de primeira linguagem em Python, se quisesse (e ele poderia gerar saída em C, assembly ou mesmo em Python).

Essa abordagem investigativa pode combinar bem com uma abordagem mais formal, pois você começará a reconhecer os conceitos que estudou no idioma em que está trabalhando e vice-versa.

Diverta-se!

kindall
fonte
Não cavar em python, mas é irrelevante. O garoto já tem N idiomas para N grande; incrementar N não fará muita diferença. Veja C, por exemplo. É padrão. Tem muitas bibliotecas. É multiplataforma (quando você segue o padrão). Você pode desmontar a saída. Você pode escrever CFront. Etc. Então lá.
31412 Ian
1

Bem, acho que sua pergunta poderia ser reescrita para "Quais são os principais conceitos práticos de um diploma em ciência da computação" e a resposta total é, obviamente, obter seu próprio diploma de bacharel em ciência da computação.

Fundamentalmente, você cria seu próprio compilador de linguagem de programação lendo um arquivo de texto, extraindo informações dele e realizando transformações no texto com base nas informações que você leu até que você o transformou em bytes que podem ser lidos por o carregador (cf, Linkers e Loaders da Levine). Um compilador trivial é um projeto bastante rigoroso quando realizado pela primeira vez.

O coração de um sistema operacional é o kernel, que gerencia recursos (por exemplo, alocação / desalocação de memória) e alterna entre tarefas / processos / programas.

Um assembler é uma transformação de texto-> byte.

Se você estiver interessado nessas coisas, sugiro escrever um assembler X86, no Linux, que suporte algum subconjunto do assembly X86 padrão. Esse será um ponto de entrada bastante direto e apresentará essas questões. Não é um projeto para bebês e ensinará muitas coisas.

Eu recomendaria escrever em C; C é a língua franca para esse nível de trabalho.

Paul Nathan
fonte
1
Por outro lado, este é um ótimo local para um idioma de nível muito alto. Contanto que você possa ditar os bytes individuais em um arquivo, você pode criar um compilador / montador (o que é mais fácil) em qualquer idioma. Diga perl. Ou VBA. Céus, as possibilidades!
31412 Ian
1

Veja o livro de Kenneth Louden, "Construção de Compiladores"

http://www.cs.sjsu.edu/~louden/cmptext/

Ele fornece uma melhor abordagem prática para o desenvolvimento do compilador.

As pessoas aprendem fazendo. Apenas um pequeno número pode ver símbolos rabiscados no quadro e pular imediatamente da teoria para a prática. Infelizmente, essas pessoas costumam ser dogmáticas, fundamentalistas e mais barulhentas.

Jarvis Jones
fonte
1

Fui abençoado por ter sido exposto ao PDP-8 como minha primeira linguagem assembly. O PDP-8 tinha apenas seis instruções, que eram tão simples que era fácil imaginá-las sendo implementadas por alguns componentes discretos, o que de fato eram. Ele realmente removeu a "mágica" dos computadores.

Outra porta de entrada para a mesma revelação é a linguagem assembly "mista" que Knuth usa em seus exemplos. "Mix" parece arcaico hoje, mas ainda tem esse efeito DE-mistificante.

ddyer
fonte
0

Compiladores e linguagens de programação (e tudo, inclusive na construção de uma - como definir uma gramática finita e conversão em assembly) é uma tarefa muito complexa que requer muita compreensão sobre os sistemas como um todo. Este tipo de curso é geralmente oferecido como uma aula de Sci de 3º / 4º ano na Universidade.

Eu recomendo que você primeiro compreenda melhor os Sistemas Operacionais em geral e como as linguagens existentes são compiladas / executadas (por exemplo, nativamente (C / C ++), em uma VM (Java) ou por um intérprete (Python / Javascript)).

Acredito que usamos o livro Operating System Concepts de Abraham Silberschatz, Peter B. Galvin e Greg Gagne no meu curso de Sistemas Operacionais (no 2º ano). Este foi um excelente livro que deu uma explicação completa de cada componente de um sistema operacional - um pouco caro, mas vale a pena, e cópias antigas / usadas devem estar flutuando.

plafond
fonte
Conceitos de sistema operacional? Muito pouco disso é necessário para construir um compilador. O que é necessário é o entendimento de arquiteturas de software: aborda espaços, pilhas, threads (se ele quiser aprender compiladores, é melhor ele aprender sobre paralelismo, é o seu futuro).
Ira Baxter
Imediatamente depois de dizer que queria aprender design de linguagem e compiladores, ele disse que queria aprender sobre sistemas operacionais.
precisa
@Ira - concordou. Eu nunca afirmei que a compreensão do sistema operacional é necessária para criar um compilador / idioma, simplesmente expliquei que pode ser um ponto de partida mais fácil. Todo mundo está focado no aspecto "compilador" de sua pergunta, mas ele também mencionou que deseja uma melhor compreensão do SO e das bibliotecas. Para um jovem de 15 anos ainda está aprendendo sobre arquiteturas, seria muito mais útil para entender o gerenciamento de memória, segmentação, bloqueio I / O, etc .. do que aprender a definir uma gramática com yacc (IMHO)
plafond
Desculpe ... perdeu o objetivo de querer aprender sobre sistemas operacionais (de construção?). Meu argumento é o seguinte: ele não precisa de muito conhecimento de SO para compiladores. De fato, é praticamente um tópico completamente diferente, exceto onde o compilador e o sistema operacional interagem para atingir algum objetivo coletivo. (A Multics exigia que seus compiladores PL / 1 construíssem chamadas de função de certas maneiras para habilitar uma VM global, por exemplo).
Ira Baxter
0

É um tópico importante, mas, em vez de escová-lo com um pomposo "vá ler um livro, garoto", em vez disso, darei com prazer dicas para ajudá-lo a entender o assunto.

A maioria dos compiladores e / ou intérpretes funciona assim:

Tokenize : digitalize o texto do código e divida-o em uma lista de tokens.

Esta etapa pode ser complicada porque você não pode simplesmente dividir a cadeia de caracteres em espaços, é necessário reconhecer que if (bar) foo += "a string";há uma lista de 8 tokens: WORD, OPEN_PAREN, WORD, CLOSE_PAREN, WORD, ASIGNMENT_ADD, STRING_LITERAL, TERMINATOR. Como você pode ver, simplesmente dividir o código-fonte em espaços não funcionará, você deverá ler cada caractere como uma sequência; portanto, se encontrar um caractere alfanumérico, continue lendo os caracteres até encontrar um caractere não alfanumérico e a sequência que você acabou de ler é uma PALAVRA para ser posteriormente classificada posteriormente. Você pode decidir por si mesmo qual é a granularidade do seu tokenizador: se ele engole "a string"como um token chamado STRING_LITERAL para ser analisado posteriormente mais tarde ou se vê"a string" como OPEN_QUOTE, UNPARSED_TEXT, CLOSE_QUOTE ou qualquer outra coisa, essa é apenas uma das muitas opções que você tem que decidir por si mesma enquanto a codifica.

Lex : Então agora você tem uma lista de tokens. Você provavelmente marcou alguns tokens com uma classificação ambígua como WORD, porque durante a primeira passagem não gasta muito esforço tentando descobrir o contexto de cada sequência de caracteres. Agora, leia a lista de tokens de origem novamente e reclassifique cada um dos tokens ambíguos com um tipo de token mais específico, com base nas palavras-chave em seu idioma. Portanto, você tem uma PALAVRA como "se" e "se" está na sua lista de palavras-chave especiais chamada símbolo SE, para alterar o tipo de símbolo desse token de WORD para IF e qualquer PALAVRA que não esteja na sua lista de palavras-chave especiais , como WORD foo, é um IDENTIFICADOR.

Analisar : agora você transformou if (bar) foo += "a string";uma lista de tokens lexed parecidos com este: SE OPEN_PAREN IDENTIFER CLOSE_PAREN IDENTIFIER ASIGN_ADD STRING_LITERAL TERMINATOR. A etapa é reconhecer sequências de tokens como instruções. Isso está analisando. Você faz isso usando uma gramática como:

DECLARAÇÃO: = ASIGN_EXPRESSION | IF_STATEMENT

IF_STATEMENT: = SE, PAREN_EXPRESSION, STATEMENT

ASIGN_EXPRESSION: = IDENTIFICADOR, ASIGN_OP, VALUE

PAREN_EXPRESSSION: = OPEN_PAREN, VALUE, CLOSE_PAREN

VALOR: = IDENTIFICADOR | STRING_LITERAL | PAREN_EXPRESSION

ASIGN_OP: = EQUAL | ASIGN_ADD ASIGN_SUBTRACT | ASIGN_MULT

As produções que usam "|" entre termos significa "corresponder a qualquer um destes"; se houver vírgulas entre termos, significa "corresponder a esta sequência de termos"

Como você usa isso? Começando com o primeiro token, tente combinar sua sequência de tokens com essas produções. Então, primeiro você tenta combinar sua lista de tokens com STATEMENT, para ler a regra para STATEMENT e ela diz "uma STATEMENT é ASIGN_EXPRESSION ou IF_STATEMENT", para tentar corresponder ASIGN_EXPRESSION primeiro, e procurar a regra gramatical para ASIGN_EXPRESSION e ele diz "ASIGN_EXPRESSION é um IDENTIFIER seguido por um ASIGN_OP seguido por um VALUE, portanto, você consulta a regra gramatical para IDENTIFIER e vê que não há erros gramaticais para IDENTIFIER, o que significa que o IDENTIFIER é um" terminal ", o que significa que não requer mais análise para combiná-lo para que você possa tentar combiná-lo diretamente com seu token, mas seu primeiro token de origem é um IF e IF não é o mesmo que um IDENTIFIER; portanto, a correspondência falhou. E agora? Você volta à regra STATEMENT e tenta corresponder ao próximo termo: IF_STATEMENT. Você pesquisa IF_STATEMENT, começa com IF, pesquisa IF, IF é um terminal, compare o terminal com seu primeiro token, combina com o token IF, impressionante, o próximo termo é PAREN_EXPRESSION, pesquisa PAREN_EXPRESSION, não é um terminal, qual é o primeiro termo, PAREN_EXPRESSION começa com OPEN_PAREN, pesquisa OPEN_PAREN, é um terminal, corresponde a OPEN_PAREN ao seu próximo token, corresponde a .... e assim por diante.

A maneira mais fácil de abordar esta etapa é ter uma função chamada parse (), a qual você transmite o token do código-fonte que está tentando corresponder e o termo gramatical com o qual está tentando combiná-la. Se o termo gramatical não for um terminal, você deverá recursar: você chama parse () novamente passando o mesmo token de origem e o primeiro termo dessa regra gramatical. É por isso que é chamado de "analisador de descida recursiva". A função parse () retorna (ou modifica) sua posição atual na leitura dos tokens de origem, essencialmente repassa o último token na sequência correspondente e você continua a próxima chamada para parse () a partir daí.

Cada vez que parse () corresponde a uma produção como ASIGN_EXPRESSION, você cria uma estrutura que representa esse trecho de código. Essa estrutura contém referências aos tokens de origem originais. Você começa a criar uma lista dessas estruturas. Vamos chamar toda essa estrutura de Árvore de Sintaxe Abstrata (AST)

Compilar e / ou Executar : Para determinadas produções de sua gramática, você criou funções de manipulador que, se recebidas uma estrutura AST, compilariam ou executariam esse pedaço de AST.

Então, vejamos a parte do seu AST que possui o tipo ASIGN_ADD. Portanto, como intérprete, você tem uma função ASIGN_ADD_execute (). Essa função é passada como parte do AST que corresponde à árvore de análise foo += "a string", portanto, essa função olha para essa estrutura e sabe que o primeiro termo na estrutura deve ser um IDENTIFIER e o segundo termo é o VALUE, então ASIGN_ADD_execute () passa o termo VALUE para uma função VALUE_eval () que retorna um objeto que representa o valor avaliado na memória, em seguida, ASIGN_ADD_execute () faz uma pesquisa de "foo" na tabela de variáveis ​​e armazena uma referência ao que foi retornado pelo eval_value () função.

Isso é intérprete. Em vez disso, um compilador teria funções de manipulador que convertem o AST em código de bytes ou código de máquina, em vez de executá-lo.

Os passos 1 a 3, e alguns 4, podem ser facilitados usando ferramentas como Flex e Bison. (aka. Lex e Yacc), mas escrever um intérprete a partir do zero é provavelmente o exercício mais poderoso que qualquer programador pode realizar. Todos os outros desafios de programação parecem triviais após a cimeira deste.

Meu conselho é começar pequeno: uma linguagem minúscula, com uma gramática minúscula, e tentar analisar e executar algumas instruções simples e depois crescer a partir daí.

Leia isso e boa sorte!

http://www.iro.umontreal.ca/~felipe/IFT2030-Automne2002/Complements/tinyc.c

http://en.wikipedia.org/wiki/Recursive_descent_parser

snorkel
fonte
2
Você comete o que considero um erro clássico quando as pessoas pensam em compilar: que é acreditar que o problema é analisar. PARSING É TÉCNICO FÁCIL; existem ótimas tecnologias para isso. A parte mais difícil da compilação é a análise semântica, otimizando os níveis alto e baixo de representação do programa e a geração de código, com ênfase crescente nos dias de hoje no código PARALLEL. Você trivializa isso completamente em sua resposta: "um compilador teria funções de manipulador para converter o AST em código de bytes". Há 50 anos decorridos de teoria dos compiladores e engenharia escondidos lá.
perfil completo de Ira Baxter
0

O campo do computador é apenas complicado porque teve tempo de evoluir em várias direções. No fundo, trata-se apenas de máquinas que calculam.

Meu computador básico muito favorito é o computador de retransmissão de Harry Porter . Ele fornece uma amostra de como um computador funciona no nível básico. Então você pode começar a entender por que coisas como idiomas e sistemas operacionais são necessárias.

O problema é que é difícil entender qualquer coisa sem entender o que precisa . Boa sorte e não basta ler as coisas. Faça coisas.

Mike Dunlavey
fonte
-1

Vá ver http://mikeos.berlios.de/

Existe um sistema operacional realmente simples na montagem x86.

Ele tem um bom tutorial sobre como escrever um sistema operacional simples a partir do zero.

Tim Williscroft
fonte
-1

Outro bom livro introdutório é o "Compilerbau" de N. Wirth, de 1986 (construção do compilador), com cerca de 100 páginas e explica códigos concisos e bem projetados para a linguagem de brinquedos PL / 0, incluindo analisador, gerador de código e máquina virtual. Também mostra como escrever um analisador que lê a gramática para analisar na notação EBNF. O livro está em alemão, mas escrevi um resumo e traduzi o código para Python como um exercício, consulte http://www.d12k.org/cmplr/w86/intro.html .

Daniel Storbeck
fonte
-1

Se você estiver interessado em entender a essência das linguagens de programação, sugiro que você trabalhe no livro PLAI (http://www.cs.brown.edu/~sk/Publications/Books/ProgLangs/) para entender os conceitos e sua implementação. Também o ajudará com o design do seu próprio idioma.

mansu
fonte
-1

Se você realmente tem interesse em compilador e nunca o fez antes, pode começar projetando uma calculadora para calcular fórmulas aritméticas (um tipo de DSL como Eric mencionou). Há muitos aspectos que você precisa considerar para esse tipo de compilador:

  • Números permitidos
  • Operadores permitidos
  • As prioridades do operador
  • Validação de sintaxe
  • Mecanismo de pesquisa variável
  • Detecção de ciclo
  • Otimização

Por exemplo, você tem as seguintes fórmulas, sua calculadora deve poder calcular o valor de x:

a = 1
b = 2
c = a + b
d = (3 + b) * c
x = a - d / b

Para começar, não é um compilador extremamente difícil, mas pode fazer você pensar em algumas idéias básicas sobre o que é um compilador, além de ajudá-lo a melhorar suas habilidades de programação e controlar a qualidade do seu código (esse é realmente um problema perfeito que Desenvolvimento orientado a testes O TDD pode ser aplicado para melhorar a qualidade do software).

Sapiência
fonte