Como escrever um compilador no Go: um guia rápido

Joseph Livni Blocked Desbloquear Seguir Seguindo 7 de janeiro Foto de DAVID ILIFF . Licença: CC-BY-SA 3.0

Compiladores são incríveis! Combine ? ? Eles combinam teoria e aplicação e tocam em muitos tópicos relacionados a software, como análise e construção de linguagem. Em sua essência, os compiladores são um programa que torna um programa legível pelo computador.

A inspiração para isso veio de um curso de compiladores que fiz no outono passado e do meu amor por Go.

Este é o guia que eu gostaria de ter ao iniciar minha jornada em compiladores. Há muitos livros, vídeos e tutoriais sobre como criar compiladores. O objetivo deste post é encontrar um equilíbrio entre fornecer um exemplo não trivial de algumas das coisas que um compilador pode fazer enquanto evita ficar preso nas ervas daninhas. ?

O resultado será um compilador que pode executar uma pequena linguagem inventada. Para fazer o checkout e executar o projeto final, consulte as instruções abaixo. ?

Nota: Lembre se de que o Go é estrito sobre caminhos absolutos ao executar este

 cd $ GOPATH / src / github.com / Lebonesco 
clone git https://github.com/Lebonesco/go-compiler.git
cd go-compiler
vai testar -v
vá executar main.go ./examples/math.bx

Esboço do Compilador

  • Lexer / Parser
  • Gerador AST
  • Verificador de tipos
  • Geração de Código

O idioma

O objetivo deste post é familiarizá-lo com os compiladores o mais rápido possível para que possamos manter a linguagem simples. Para Tipos , trabalharemos com strings , integers e bools . Ele terá instruções que incluem func , if , else , let e return . Isso deve ser suficiente para se divertir trabalhando com algumas das complexidades de um compilador.

O primeiro compilador que construí, completei ao longo de dois meses e ocupei milhares de linhas de código. Eu peguei alguns atalhos neste post para mostrar os principais fundamentos.

Dois componentes comuns que faltam na nossa linguagem são classes e arrays . Isso adiciona complicações adicionais às quais não temos tempo no momento. Se acontecer de as pessoas realmente quererem saber como lidar com esses elementos, vou escrever um acompanhamento.

Algum código de exemplo:

 func add (int, b int) int { 
return a + b;
}
 func hello (name String) String { 
return "ola:" + "" + nome;
}
 let num = add (1, 2); 
let phrase = string olá ("Jeff");
vamos i = int 0;
deixe resultado = "";
 if (i == 2) { 
resultado = ola ("gato");
} outro {
result = hello ("cachorro");
}
 PRINT (resultado); 

Configuração rápida

O único pacote externo que precisamos é o gocc , que ajudará a construir o lexer e o parser.

Para executá-lo:

 vá buscar github.com/goccmack/gocc 

Certifique-se de que a pasta bin na qual o gocc está localizado esteja em seu PATH :

 Exportar PATH = $ GOPATH / bin: $ PATH 

Nota: Se você está tendo problemas neste estágio, tente executar o comando go env para ter certeza de que seus $GOROOT e $GOPATH estão corretamente atribuídos.

Legal, vamos mergulhar em algum código.

Construindo o Lexer

O trabalho do léxico é ler o programa e gerar um fluxo de tokens que são consumidos pelo analisador. Cada Token contém o type que o token representa no idioma e a string Literal desse token.

Para identificar as partes do programa, usaremos expressões regulares. O gocc então converterá essas expressões regulares em um DFA ( Deterministic Finite Automata ), que teoricamente pode ser executado em tempo linear.

A notação que estaremos usando é BNF ( formulário Backus – Naur ). Não confunda isso com EBNF (forma estendida de Backus – Naur ) ou ABNF (forma aumentada de Backus – Naur ) que possuem alguns recursos adicionais. Tenha isso em mente ao analisar outros exemplos on-line que poderiam estar usando outros formulários que fornecem mais açúcar sintático.

Vamos começar com o básico e definir quais strings e integers serão semelhantes.

Observe que:

  • Todos os nomes de token devem estar em minúsculas
  • Qualquer chave precedida por '!' será ignorado
  • Qualquer tecla precedida por '_' não será transformada em um token
  • Qualquer expressão entre '{' expression '}' pode ser repetida 0 ou mais vezes

No exemplo abaixo, estamos ignorando todo o espaço em branco e definimos um token int e string_literal .

Cada idioma foi construído em keywords que são palavras reservadas que oferecem funcionalidade especial. Mas, como o léxico saberá se uma string é uma keywordkeyword ou um identifier criado pelo usuário? Ele lida com isso dando preferência à ordem em que os tokens são definidos. Portanto, vamos definir as keywords seguir.

Nós terminaremos isso adicionando a pontuação necessária para as expressões.

Legal! Vamos ver se isso está realmente fazendo o que queremos com alguns testes unitários . Sinta-se à vontade para colar essa parte em seu IDE. ?

Nota: Geralmente é uma boa prática ir para colocar arquivos de teste no subdiretório relevante, mas para simplificar, estou colocando todos os testes na raiz.

Para testar nossa execução do scanner :

 $ gocc grammer.bnf 
$ go test -v
=== RUN TestToken
--- PASS: TestToken (0.00s)
PASSAR
ok github.com/Lebonesco/compiler 0.364s

Ótimo, agora temos um Lexer funcional

Construindo o Parser

Construir o Parser é semelhante ao modo como construímos o Lexer . Construiremos um conjunto de sequências de elementos que, quando corresponderem corretamente a um fluxo de tokens, produzirão uma gramática. Isso também será executado em tempo linear convertendo internamente nossa gramática NFA ( Automaton não determinístico ) para o DFA ( Deterministic Finite Automaton ).

Vamos manter as coisas simples. O que realmente é o nosso programa? Bem, é um monte de Statements em que cada Statement pode conter um conjunto de Statements e / ou Expressions . Este parece ser um bom lugar para começar nossa gramática.

Abaixo está o início da hierarquia recursiva do programa. Statements é uma seqüência de zero ou mais Statements e Functions é uma lista de funções. Nossas linguagens requerem funções a serem definidas antes de outros tipos de Statement . Isso reduzirá um pouco de dor de cabeça durante a fase de verificação de tipo. empty é uma palavra-chave no BNF que representa um espaço vazio.

Mas espere! O que é uma Statement ? É uma unidade de código que não retorna um valor. Isso inclui: if , let e return statements. Isso se opõe às Expressions que retornam valores. Nós vamos chegar aos próximos.

Abaixo está a nossa gramática para Statement e Function . Um StatementBlock é uma abstração maior que encapsula uma lista de Statements com chaves { } .

Em seguida, vamos construir nossa Expression que lida com todas as operações infixadas, como + , - , * , < , > , == , and , e or .

Quase feito com uma gramática totalmente funcional! Vamos encerrar as coisas, definindo a nossa inserção de parâmetros. Cada function pode aceitar qualquer quantidade de valores. Ao definir uma função , precisamos rotular os tipos de argumentos na assinatura, enquanto uma função chamada pode aceitar qualquer quantidade de Expressions .

Agora que o nosso analisador está concluído, vamos adicionar algum código ao nosso driver, main.go

Conforme avançamos no compilador, adicionaremos mais funcionalidades a esse driver.

Uma das coisas mais desafiadoras na construção de um analisador é que existem muitas maneiras diferentes de definir a gramática. ?

Nós realmente não saberemos como nos saímos até chegarmos na próxima seção que usa a saída que acabamos de gerar. A dificuldade de construir o verificador de tipo estático será fortemente influenciada pelo nosso design gramatical. Mantenha os dedos cruzados ?.

Analisador de teste

Manteremos isso simples porque neste ponto nosso analisador ainda pode produzir falsos positivos. Assim que começarmos a trabalhar no AST, podemos verificar sua precisão.

 vai testar -v 
=== RUN TestParser
--- PASS: TestParser (0.00s)
=== RUN TestToken
--- PASS: TestToken (0.00s)
PASSAR
ok github.com/Lebonesco/go-compiler 7.295s

Parabéns ? ? ?! Agora você tem um Lexer e um Analisador totalmente funcionais. Hora de passar para a AST ( Abstract Syntax Tree ).

Árvore Sintaxe Abstrata

A melhor maneira de entender uma árvore de sintaxe abstrata é em relação a uma árvore de análise que é o que geramos no último post. Uma árvore de análise representa cada parte do programa que corresponde à nossa gramática.

Por outro lado, uma AST contém apenas as informações relacionadas à verificação de tipos e à geração de códigos e ignora qualquer outro conteúdo extra usado durante a análise do texto.

Não se preocupe se essa definição não fizer sentido agora. Eu sempre aprendo melhor codificando, então vamos pular dentro disso!

Crie um novo diretório e dois novos arquivos. ast.go conterá nossas funções e types.go geração de AST. Os tipos de nós da árvore serão os mesmos.

 mkdir ast 
cd ast
toque em ast.go
toque types.go

Como com a árvore de análise, definiremos nossa estrutura de cima para baixo. Cada node será uma Statement ou uma Expression . Go não é orientado a objetos, então usaremos um padrão de composição utilizando interface e struct para representar nossas categorias de node . Nosso AST retornará um nó do Program que contém o resto do programa. De agora em diante, qualquer estrutura que criamos com um método TokenLiteral() é um node . Se esse node tiver um método statementNode() , ele se ajustará à interface Statement e, se tiver um método expressionNode() , será uma Expression .

Além disso, adicionaremos tags json a cada campo struct para facilitar a conversão de nosso AST em json para fins de teste.

Agora vamos começar a construir nossas estruturas de Statement baseadas nas interfaces Statement e Node .

Nota: json:"-" significa que o campo será omitido do nosso json.

Em seguida, precisamos de alguns ganchos para conectar nossos nodes e parser . O código abaixo permite que nossos nós de Statement se ajustem às interfaces Node e Statement .

Em seguida, precisamos dos ganchos que serão chamados pelo analisador.

Como você pode ver, a maior parte do nosso código está verificando e transmitindo nosso tipo de entrada.

Esses ganchos serão chamados pelo analisador em grammar.bnf . Para acessar essas funções, precisaremos import "github.com/Lebonesco/go-compiler/ast .

Agora, quando um pedaço de gramática é identificado, ele chama um gancho AST e passa os dados necessários para construir um node .

Como você pode imaginar, há muita flexibilidade em como você deseja gerar sua AST. Existem estratégias de design que reduzem a quantidade de nós exclusivos na AST. No entanto, ter mais tipos de nós facilitará sua vida quando chegarmos ao typechecker e à code generation . ?

Esta parte tem muito código. No entanto, não é muito difícil e na maioria das vezes. O tratamento de erros no Go pode parecer um pouco entediante, mas a longo prazo valerá a pena quando cometermos um erro bobo. Segurança em primeiro lugar

Nós não vamos fazer nada muito louco com o nosso tratamento de erros porque eu quero salvar linhas de código. No entanto, se você se sentir inclinado, poderá adicionar mais erros descritivos e úteis.

Vamos para as Expressions !

Coloque-os nas interfaces Node e Expression .

E crie os ganchos de Expression .

Por fim, insira os ganchos no parser .

Teste do gerador AST

Os casos de teste para o gerador AST são os mais tediosos para escrever. Mas confie em mim, esta não é uma parte que você quer estragar. Se você tiver problemas aqui, esses bugs serão transferidos para o seu type checker e code generator . ?

Na minha opinião, se o código não tem testes está quebrado

Em nosso teste de AST, vamos construir como deve ser nosso resultado final. Para evitar a comparação de elementos como tokens , que poderiam criar falsos negativos, convertemos nosso resultado e saída esperada em json antes de comparar com uma função de comparação profunda , reflect.DeepEqual() .

Teste de corrida:

 vai testar -v 
=== RUN TestAST
--- PASS: TestAST (0.00s)
=== RUN TestParser
--- PASS: TestParser (0.00s)
=== RUN TestToken
--- PASS: TestToken (0.00s)
PASSAR
ok github.com/Lebonesco/go-compiler 9.020s

Meio caminho para um compilador de trabalho! ? Enquanto você dá este post, não se esqueça de dar uma ajuda para chegar até aqui.

Vamos adicionar mais algum código ao driver.

Agora na minha parte favorita, o Type Checker .

Verificador de tipos

Nosso verificador de tipos garantirá que os usuários não escrevam códigos que entrem em conflito com nosso idioma de tipagem estática .

O backbone principal do nosso verificador de tipos será uma combinação de estruturas de dados que rastreiam tipos de identificadores, inicialização e operações de tipo válidas. Isso pode ficar muito mais complicado quando começarmos a lidar com diferentes níveis de escopo e classes. No entanto, estamos mantendo o mais simples possível. ?

Para iniciar:

 toque em checker_test.go 
verificador mkdir
verificador de cd
toque checker.go
toque environment.go

environment.go conterá todas as nossas funções auxiliares que serão usadas pelo nosso verificador e gerador de código para acessar e manipular nosso conjunto de variáveis e tipos correspondentes. Nosso ambiente é simples, então isso será direto.

Começaremos definindo todos os nossos valores constantes, incluindo tipos de operação , tipos de variáveis e mapeamento de cada tipo para seus métodos válidos .

Nota: Se tivéssemos aulas na nossa língua, o nosso verificador lidaria com esta terceira parte em vez de fazê-lo à mão.

O restante do environment.go são getters e setters básicos que manipulam identificadores e funções.

A base do nosso verificador de tipos será uma única função de despacho , checker() , que recebe um Node e dispara a função verificador correspondente.

Eu senti como salvar linhas de código, então estaremos usando um ambiente global para armazenar nossos tipos de variáveis.

Nota: Isso não seria possível se permitíssemos que as Block Statements e Functions Block Statements tivessem seu próprio escopo ou se estivéssemos seguindo as práticas recomendadas.

Agora, Statements eval. Block Statements são a única declaração em que retornamos um tipo para lidar com o caso quando ele está dentro de uma função. Se houver uma Return Statement dentro da Block Statement seu tipo será retornado. Caso contrário, o Nothing_Type é retornado.

Para avaliar Expressions . A parte mais complicada será evalFunctionCall() porque pode ser uma função incorporada como PRINT() ou definida pelo usuário.

Nota: Atualmente, há apenas uma função interna. No entanto, mais poderia ser facilmente adicionado, dado o framework que construímos.

Impressionante! Vamos adicionar um pequeno trecho ao nosso motorista.

Verificador de tipo de teste

 vai testar -v 
=== RUN TestAST
--- PASS: TestAST (0.00s)
=== RUN TestOperations
--- PASS: TestOperations (0.00s)
=== RUN TestIdents
--- PASS: TestIdents (0.00s)
=== RUN TestFunctions
--- PASS: TestFunctions (0.00s)
=== RUN TestParser
--- PASS: TestParser (0.00s)
=== RUN TestToken
--- PASS: TestToken (0.00s)
PASSAR
ok github.com/Lebonesco/go-compiler 9.020s

Fiz algumas escolhas deliberadas para deixar as coisas fora dessa linguagem, como classes , for loops e scope função. A maioria das complexidades que surgem disso ocorre no checker e no code generator . Se eu adicionasse esses elementos, esse post seria muito mais longo. ?

Geração de Código

Finalmente chegamos ao último estágio! ? ? ?

Para lidar com a maioria dos casos com o mínimo de problemas, cada expression será atribuída a uma variável temporária. Isso pode fazer com que nosso código gerado pareça inchado, mas resolverá qualquer expressão aninhada.

Código inchado não terá qualquer impacto na velocidade final do programa, porque o otimizador removerá qualquer redundância quando compilarmos nosso código C ++ gerado final.

Nosso gerador será semelhante ao verificador de tipos. A principal diferença é que estaremos passando um buffer para armazenar o código gerado.

Enquanto eu escolhi para compilar em C ++, você pode substituir em qualquer idioma. O principal objetivo deste Guia do Compilador Go era permitir que você entendesse as peças o suficiente para sair e criar as suas próprias.

Para iniciar:

 toque em gen_test.go 
mkdir gen
cd gen
toque em gen.go

Começaremos importando todos os pacotes necessários e definindo três funções de utilidade, write() para escrever código gerado em um buffer, check() para manipulação de erros e freshTemp() para gerar nomes de variáveis exclusivos para variáveis temporárias que criarmos no vôo.

Nota: Geralmente é uma prática ruim usar o panic() para manipulação de erro normal no Go, mas estou cansado de escrever if statements .

Similar ao verificador , nosso gerador tem uma função de despacho do núcleo que aceita um Node e chama a função gen correspondente.

Vamos gerar algumas Statements . genProgram() gera os cabeçalhos necessários e a função main() .

A geração de Expressions será muito semelhante ao código acima. A principal diferença é que uma variável temp é retornada representando essa expressão. Isso nos ajuda a lidar com aninhamento de Expression mais complexo.

A parte final do código será nossos tipos C ++ Builtin. Sem isso nada vai funcionar.

Gerador de Código de Teste

Juntando Tudo

Agora vamos combinar nosso lexer , analisador , gerador AST , verificador de tipos e gerador de código em um programa final executável, main.go

Nota: Estou executando isso em um Windows para que meu C ++ compila em main.exe . Se isso não funcionar, remova a extensão .exe .

Para encontrar alguns programas de teste a serem executados, acesse github.com/Lebonesco/go-compiler/examples .

 vá executar main.go ./example/function.bx 
ola jeff
3

E aí está você! Nós completamos um compilador totalmente funcional no Go!

Obrigado por tomar o tempo para ler este artigo.

Se você achou útil ou interessante por favor me avise ???.