A maioria dos compiladores possui a seguinte arquitetura:
Neste artigo, vou dissecar essa arquitetura em detalhes, elemento por elemento.
Podemos dizer que este artigo é uma adição à enorme quantidade de recursos existentes no tópico de compiladores. É uma fonte autônoma que permitirá que você entenda os conceitos básicos de design e implementação de linguagens de programação.
O público-alvo do artigo são pessoas cuja ideia do trabalho dos compiladores é extremamente limitada (o máximo é que eles estão envolvidos na compilação). No entanto, espero que o leitor entenda estruturas e algoritmos de dados.
O artigo não é de forma alguma dedicado aos compiladores de produção modernos com milhões de linhas de código - não, este é um curso de curta duração "compiladores para manequins" para ajudá-lo a entender o que é um compilador.
1. Introdução
Atualmente, estou trabalhando na linguagem do sistema
Krug inspirada no Rust and Go. No artigo, vou me referir a Krug como um exemplo para ilustrar meus pensamentos. O Krug está em desenvolvimento, mas já está disponível em
https://github.com/krug-lang nos repositórios
caasper e
krug . A linguagem não é muito típica em comparação com a arquitetura usual de compiladores, que me inspirou parcialmente a escrever um artigo - mas mais sobre isso mais tarde.
Corro para informá-lo que não sou especialista em compiladores! Não tenho doutorado e não fiz nenhum treinamento formal - estudei sozinho tudo o que foi descrito no artigo no meu tempo livre. Devo também dizer que não estou descrevendo a abordagem real e correta para criar um compilador, mas apresento os métodos básicos adequados para criar um pequeno compilador "brinquedo".
Frontend
Voltemos ao diagrama acima: as setas à esquerda direcionadas para o campo de front-end são linguagens conhecidas e amadas como C. O front-end se parece com isso: análise lexical -> analisador.
Análise lexical
Quando comecei a estudar compiladores e design de linguagem, me disseram que análise lexical é o mesmo que tokenização. Usaremos essa descrição. O analisador pega os dados de entrada na forma de seqüências de caracteres ou um fluxo de caracteres e reconhece padrões neles, que são cortados em tokens.
No caso de um compilador, ele recebe um programa escrito na entrada. Ele é lido em uma sequência de um arquivo e o analisador tokeniza seu código-fonte.
enum TokenType { Identifier, Number, }; struct Token { std::string Lexeme; TokenType type; // ... // It's also handy to store things in here // like the position of the token (start to end row:col) };
Nesse fragmento, escrito em uma linguagem em forma de C, você pode ver a estrutura que contém o léxico acima mencionado, bem como o TokenType, que serve para reconhecer esse token.
Nota: o artigo não é uma instrução para criar um idioma com exemplos - mas, para uma melhor compreensão, inserirei trechos de código de tempos em tempos.
Os analisadores geralmente são os componentes mais simples do compilador. De fato, todo o front-end é bastante simples comparado ao restante das peças do quebra-cabeça. Embora dependa muito do seu trabalho.
Pegue o seguinte pedaço de código C:
int main() { printf("Hello world!\n"); return 0; }
Após a leitura de um arquivo para uma linha e a execução de uma verificação linear, você poderá fatiar tokens. Identificamos os tokens de maneira natural - visto que int é uma "palavra" e 0 na declaração de retorno é um "número". O analisador lexical executa o mesmo procedimento que nós - depois examinaremos esse processo com mais detalhes. Por exemplo, analise os números:
0xdeadbeef — HexNumber ( ) 1231234234 — WholeNumber ( ) 3.1412 — FloatingNumber ( ) 55.5555 — FloatingNumber ( ) 0b0001 — BinaryNumber ( )
Definir palavras pode ser difícil. A maioria dos idiomas define uma palavra como uma sequência de letras e números, e um identificador geralmente deve começar com uma letra ou sublinhado. Por exemplo:
123foobar := 3 person-age := 5 fmt.Println(123foobar)
No Go, esse código não será considerado correto e será analisado nos seguintes tokens:
Number(123), Identifier(foobar), Symbol(:=), Number(3) ...
A maioria dos identificadores encontrados fica assim:
foo_bar __uint8_t fooBar123
Os analisadores terão que resolver outros problemas, por exemplo, com espaços, comentários de várias linhas e de linha única, identificadores, números, sistemas numéricos e formatação de números (por exemplo, 1_000_000) e codificações (por exemplo, suporte para UTF8 em vez de ASCII).
E se você acha que pode recorrer a expressões regulares - melhor não vale a pena. É muito mais fácil escrever um analisador do zero, mas eu recomendo a leitura
deste artigo do nosso rei e deus Rob Pike. As razões pelas quais o Regex não é adequado para nós são descritas em muitos outros artigos, por isso vou omitir este ponto. Além disso, escrever um analisador é muito mais interessante do que se atormentar com longas expressões verbais carregadas no regex101.com às 5:24 da manhã. No meu primeiro idioma, usei a função
split(str) para tokenização - e não fui longe.
Análise
A análise é um pouco mais complicada do que a análise lexical. Existem muitos analisadores e analisadores-geradores - aqui o jogo começa em grande estilo.
Os analisadores nos compiladores geralmente recebem entradas na forma de tokens e constroem uma árvore específica - uma árvore de sintaxe abstrata ou uma árvore de análise. Por sua natureza, eles são semelhantes, mas têm algumas diferenças.
Esses estágios podem ser representados como funções:
fn lex(string input) []Token {...} fn parse(tokens []Token) AST {...} let input = "int main() { return 0; }"; let tokens = lex(input); let parse_tree = parse(tokens); // ....
Normalmente, os compiladores são criados a partir de muitos componentes pequenos que recebem, alteram ou convertem em saída diferente. Essa é uma das razões pelas quais as linguagens funcionais são adequadas para a criação de compiladores. Outras razões são excelentes referências e bibliotecas padrão bastante extensas. Curiosidade: a primeira implementação do compilador
Rust foi no Ocaml.
Aconselho que você mantenha esses componentes o mais simples e autônomo possível - a modularidade facilitará bastante o processo. Na minha opinião, o mesmo pode ser dito sobre muitos outros aspectos do desenvolvimento de software.
Árvores
Árvore de análise
Que diabos é isso? Também conhecida como árvore de análise, essa árvore espessa serve para visualizar o programa de origem. Eles contêm todas as informações (ou a maioria delas) sobre o programa de entrada, geralmente as mesmas descritas na gramática do seu idioma. Cada nó da árvore será à direita ou à direita, por exemplo, NumberConstant ou StringConstant.
Árvore de sintaxe abstrata
Como o nome indica, o ASD é uma
árvore de sintaxe
abstrata . A árvore de análise contém muitas informações (geralmente redundantes) sobre o seu programa e, no caso de um ASD, isso não é necessário. O ASD não precisa de informações inúteis sobre a estrutura e a gramática, o que não afeta a semântica do programa.
Suponha que sua árvore tenha uma expressão como ((5 + 5) -3) +2. Na árvore de análise, você a armazenaria completamente, juntamente com colchetes, operadores e valores 5, 5, 3 e 2. Mas você pode simplesmente se associar ao ASD - precisamos apenas conhecer os valores, operadores e sua ordem.
A imagem abaixo mostra a árvore para a expressão a + b / c.
ASD pode ser representado da seguinte maneira:
interface Expression { ... }; struct UnaryExpression { Expression value; char op; }; struct BinaryExpression { Expression lhand, rhand; string op; // string because the op could be more than 1 char. }; interface Node { ... }; // or for something like a variable struct Variable : Node { Token identifier; Expression value; };
Essa visão é bastante limitada, mas espero que você possa ver como seus nós serão estruturados. Para análise, você pode recorrer ao seguinte procedimento:
Node parseNode() { Token current = consume(); switch (current.lexeme) { case "var": return parseVariableNode(); // ... } panic("unrecognized input!"); } Node n = parseNode(); if (n != null) { // append to some list of top level nodes? // or append to a block of nodes! }
Espero que você entenda como a análise passo a passo dos nós restantes prosseguirá, começando com construções de linguagem de alto nível. Como exatamente um analisador com uma descida recursiva é implementado, você precisa se estudar.
Gramática
A análise em um ADS de um conjunto de tokens pode ser difícil. Normalmente você deve começar pela gramática do seu idioma. Em essência, a gramática determina a estrutura do seu idioma. Existem vários idiomas para definir idiomas que podem descrever (ou analisar) eles mesmos.
Um exemplo de um idioma para determinar idiomas é uma
forma estendida de Backus-Naur (RBNF). É uma variação do
BNF com menos colchetes angulares. Aqui está um exemplo de RBNF de um artigo da Wikipedia:
digit excluding zero = "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" ; digit = "0" | digit excluding zero ;
As regras de produção são definidas: elas indicam qual modelo de terminal é "não terminal". Os terminais fazem parte do alfabeto, por exemplo, o token if ou 0 e 1 no exemplo acima são terminais. Os não terminais são o seu oposto, estão do lado esquerdo das regras de produção e podem ser considerados variáveis ou "indicadores nomeados" para grupos de terminais e não terminais.
Muitos idiomas têm especificações que contêm gramática. Por exemplo, para
Go ,
Rust e
D.Analisadores de descida recursiva
A descida recursiva é a mais fácil de muitas abordagens de análise.
Analisadores de descida recursiva - descendente, com base em procedimentos recursivos. É muito mais fácil escrever um analisador, porque sua gramática não
deixou recursão . Na maioria das linguagens "de brinquedo", essa técnica é suficiente para analisar. O GCC usa um analisador descendente escrito à mão, embora o YACC tenha sido usado anteriormente.
No entanto, a análise desses idiomas pode causar problemas. Em particular, C, onde
foo * bar
pode ser interpretado como
int foo = 3; int bar = 4; foo * bar; // unused expression
ou como
typedef struct { int b; } foo; foo* bar; bar.b = 3;
A implementação Clang também usa um analisador de descida recursiva:
Como esse é um código C ++ comum, uma descida recursiva facilita a compreensão dos iniciantes. Ele suporta regras personalizadas e outras coisas estranhas que o C / C ++ exige e ajuda a diagnosticar e corrigir erros com facilidade.Também vale a pena prestar atenção a outras abordagens:
- LL descendente, descida recursiva
- LR ascendente, deslocamento, descida ascendente
Geradores de analisador
Outro bom caminho. Obviamente, também existem desvantagens - mas isso pode ser dito sobre qualquer outra escolha que os programadores façam ao criar software.
Os geradores de analisador funcionam muito rapidamente. Usá-los é mais fácil do que escrever seu próprio analisador e obter um resultado de qualidade - embora eles não sejam muito amigáveis e nem sempre exibam mensagens de erro. Além disso, você precisará aprender a usar o gerador de analisador e, ao promover o compilador, provavelmente precisará desenrolar o gerador de analisador.
Um exemplo de um gerador de analisador é o
ANTLR , existem muitos outros.
Eu acho que essa ferramenta é adequada para aqueles que não querem gastar tempo escrevendo um front-end e que preferem escrever o meio e o back-end do compilador / intérprete e analisar qualquer coisa.
Aplicativo de análise
Se você ainda não se entende. Até o frontend do compilador (lex / parse) pode ser usado para resolver outros problemas:
- destaque de sintaxe
- Análise de HTML / CSS para mecanismo de renderização
- transpilers: TypeScript, CoffeeScript
- ligantes
- REGEX
- análise de dados da interface
- Análise de URL
- ferramentas de formatação como gofmt
- Análise de SQL e muito mais.
Meados
Análise semântica! A análise da semântica da linguagem é uma das tarefas mais difíceis ao criar um compilador.
Você precisa garantir que todos os programas de entrada funcionem corretamente. Na minha linguagem Krug, aspectos relacionados à análise semântica ainda não foram incluídos e, sem ela, o programador sempre será obrigado a escrever o código correto. Na realidade, isso é impossível - e sempre escrevemos, compilamos, às vezes executamos, corrigimos erros. Essa espiral é interminável.
Além disso, a compilação de programas é impossível sem a análise da correção da semântica no estágio apropriado da compilação.
Uma vez me deparei com um gráfico sobre a porcentagem de front-end, região central e back-end. Então parecia
F: 20% M: 20%: B: 60%
Hoje é algo como
F: 5% M: 60% B: 35%
O frontend se preocupa principalmente com o gerador e, em linguagens sem contexto que não possuem a dualidade da gramática, elas podem ser concluídas rapidamente - uma descida recursiva ajudará aqui.
Com a tecnologia LLVM, a maior parte do trabalho de otimização pode ser carregada na estrutura, que apresenta várias otimizações prontas.
O próximo passo é a análise semântica, uma parte essencial da fase de compilação.
Por exemplo, no Rust, com seu modelo de gerenciamento de memória, o compilador atua como uma máquina grande e poderosa que executa vários tipos de análise estática em formas introdutórias. Parte desta tarefa é converter os dados de entrada em um formulário mais conveniente para análise.
Por esse motivo, a análise semântica desempenha um papel importante na arquitetura do compilador, e um trabalho preparatório exaustivo, como otimizar o assembly gerado ou ler os dados de entrada no ASD, é feito para você.
Passagens Semânticas
No curso da análise semântica, a maioria dos compiladores realiza um grande número de "passagens semânticas" no SDA ou em outra forma abstrata de expressão de código.
Este artigo fornece detalhes sobre a maioria das passagens feitas no compilador .NET C #.
Não considerarei cada passagem, especialmente porque elas variam dependendo do idioma, mas várias etapas são descritas abaixo em Krug.
Anúncio de nível superior
O compilador examinará todos os anúncios de "nível superior" nos módulos e estará ciente de sua existência. Ele não se aprofundará em blocos - ele simplesmente declarará quais estruturas, funções etc. estão disponíveis em um ou outro módulo.
Nome / Símbolo Resolução
O compilador percorre todos os blocos de código em funções, etc. e os resolve - ou seja, localiza caracteres que requerem permissão. Essa é uma passagem comum e é a partir daqui que o erro
XYZ sem esse símbolo geralmente ocorre ao compilar o código Go.
A execução desse passe pode ser muito difícil, especialmente se houver dependências circulares no seu diagrama de dependências. Alguns idiomas não os permitem, por exemplo, o Go lançará um erro se um dos seus pacotes formar um loop, como a minha linguagem Krug. Dependências cíclicas podem ser consideradas um efeito colateral da arquitetura ruim.
Os loops podem ser determinados modificando o DFS no diagrama de dependência ou usando
o algoritmo Tarjan (como feito por Krug) para definir (vários) loops.
Inferência de tipo
O compilador passa por todas as variáveis e exibe seus tipos. A inferência de tipo no Krug é muito fraca; simplesmente gera variáveis com base em seus valores. Não é de forma alguma um sistema bizarro, como os que você pode encontrar em linguagens funcionais como Haskell.
Os tipos podem ser derivados usando o processo de "unificação" ou "unificação de tipo". Para sistemas do tipo mais simples, uma implementação muito simples pode ser usada.
Tipos são implementados no Krug assim:
interface Type {}; struct IntegerType : Type { int width; bool signed; }; struct FloatingType : Type { int width; }; struct ArrayType : Type { Type base_type; uint64 length; };
Você também pode ter uma inferência de tipo simples, na qual atribui um tipo a nós de expressão, por exemplo,
IntegerConstantNode pode ser do tipo IntegerType (64). E então você poderá obter a função
unify(t1, t2) , que selecionará o tipo mais amplo que pode ser usado para deduzir o tipo de expressões mais complexas, como as binárias. Portanto, é uma questão de atribuir uma variável à esquerda aos valores dos tipos fornecidos à direita.
Certa vez, escrevi um
elenco de tipos simples no Go, que se tornou uma implementação de protótipo para o Krug.
Passe de Mutabilidade
Krug (como Rust) é por padrão uma linguagem imutável, ou seja, as variáveis permanecem inalteradas, a menos que especificado de outra forma:
let x = 3; x = 4; // BAD! mut y = 5; y = 6; // OK!
O compilador percorre todos os blocos e funções e verifica se suas “variáveis estão corretas”, ou seja, não alteramos o que não segue e que todas as variáveis passadas para determinadas funções são constantes ou alteráveis, quando necessário.
Isso é feito com a ajuda de informações simbólicas que foram coletadas nos passes anteriores. Uma tabela de símbolos com base nos resultados da passagem semântica contém nomes de token e sinais de variabilidade variável. Pode conter outros dados, por exemplo, em C ++, uma tabela pode armazenar informações sobre se um símbolo é externo ou estático.
Tabelas de caracteres
Uma tabela de caracteres, ou "facada", é uma tabela para encontrar os caracteres usados no seu programa. Uma tabela é criada para cada escopo, e todos eles contêm informações sobre os caracteres presentes em um escopo específico.
Essas informações incluem propriedades como o nome do símbolo, tipo, sinal de mutabilidade, presença de comunicação externa, local na memória estática e assim por diante.
Âmbito de aplicação
Este é um conceito importante em linguagens de programação. Obviamente, seu idioma não precisa possibilitar a criação de escopos aninhados, tudo pode ser colocado em um espaço para nome comum!
Embora representar o escopo seja uma tarefa interessante para a arquitetura do compilador, na maioria das linguagens do tipo C, o escopo se comporta (ou é) como uma estrutura de dados da pilha.
Geralmente, criamos e destruímos escopos, e eles geralmente são usados para gerenciar nomes, ou seja, eles nos permitem ocultar variáveis (sombreadas):
{ // push scope let x = 3; { // push scope let x = 4; // OK! } // pop scope } // pop scope
Pode ser representado de maneira diferente:
struct Scope { Scope* outer; SymbolTable symbols; }
Um pequeno offtopic, mas eu recomendo ler sobre a
pilha de espaguete . Essa é uma estrutura de dados usada para armazenar áreas de visibilidade nos nós ASD dos blocos opostos.
Sistemas de tipos
Muitas das seções a seguir podem ser desenvolvidas em artigos separados, mas parece-me que esse título merece mais isso. Hoje, muitas informações estão disponíveis sobre sistemas de tipos, bem como variedades dos próprios sistemas, em torno das quais muitas cópias são quebradas. Não vou me
aprofundar neste tópico, basta deixar um link para o
excelente artigo de Steve Klabnik .
Um sistema de tipos é o que é fornecido e definido semanticamente no compilador usando representações do compilador e análise dessas representações.
Posse
Este conceito é usado na programação cada vez mais. Os princípios da semântica de propriedade e movimento estão incorporados na linguagem
Rust , e espero que apareçam em outras línguas. O Rust executa muitos tipos diferentes de análise estática, que verifica se a entrada satisfaz um conjunto de regras relacionadas à memória: quem possui qual memória, quando a memória é destruída e quantas referências (ou empréstimos) existem para esses valores ou memória.
A beleza do Rust reside no fato de que tudo isso é feito durante a compilação, dentro do compilador, para que o programador não precise lidar com a coleta de lixo ou a contagem de links. Todas essas semânticas são atribuídas ao sistema de tipos e podem ser fornecidas mesmo antes de o programa ser apresentado na forma de um arquivo binário completo.
Não sei dizer como tudo funciona, mas tudo isso é resultado de uma análise estática e de uma maravilhosa pesquisa da equipe Mozilla e dos participantes do projeto
Cyclone .
Gráficos de fluxo de controle
Para representar fluxos de programa, usamos gráficos de fluxo de controle (CFGs), que contêm todos os caminhos que a execução do programa pode seguir. Isso é usado na análise semântica para excluir seções ociosas do código, ou seja, blocos, funções e até módulos que nunca serão alcançados durante a execução do programa. Os gráficos também podem ser usados para identificar ciclos que não podem ser interrompidos. Ou para procurar código inacessível, por exemplo, quando você chama um “pânico” (chama um pânico), ou retorna em um loop, e o código fora do loop não é executado.
A análise do fluxo de dados desempenha um papel importante durante a fase semântica do compilador, por isso recomendo a leitura sobre os tipos de análise que você pode executar, como eles funcionam e quais otimizações podem ser feitas.
Backend
A parte final do nosso esquema de arquitetura.Fizemos a maior parte do trabalho de geração de binários executáveis. Isso pode ser feito de várias maneiras, que discutiremos abaixo.
- , . , , «».
, . , , . , , , . , .
, . , ++ — Cfront — C.
JavaScript. TypeScript , , , , .
«» , , , , « » . — , , .
LLVM
LLVM: Rust, Swift, C/C++ (clang), D, Haskell.
« », , . , LLVM . , . , , , , 1, 4, 8 16-. , , - .
-
— , — , .
Go — , LLVM ( ). Go , Windows, Linux MacOS. , Krug -.
. , LLVM, , , LLVM , .
, , , LLVM, IR, , , , ( ).
. , , , . IR ( ) «» fprintf .
8cc .
. — Java: ,
JVM , , Kotlin.
, Java . , . , .
, JVM JIT , JIT-, .
, ! , , . - , , .
Godbolt — , , . , , .
, , (strip the debug symbols), , GCC. , - .
. . , . production-.
rwmj , 8 , 80% . 1971-!
, Rust.
IR
(intermediate representation, IR) , . , , .
IR . , , , .
IR, «», IR . , SSA — Static Single Assignment, , .
Go IR SSA. IR LLVM SSA, .
SSA , , (constant propagation), ( ) .
, . , , , , . ( 16 32), , (spill to the stack).
— ( ). , , .
:
- (graph colouring) — (NP- ). , (liveness ranges) .
- — .
. , . , , .
-, , . , .
fn main() int { let x = 0; { let x = 0; { let x = 0; } } return 0; }
, ( - :) ) , . , .
LLDB
DWARF . LLVM , DWARF GNU-. , , , .
(Foreign Function Interface, FFI )
libc , , . , ?
— . , ( .s/.asm)? ? ,
Jai . , .
(CaaS)
API-. , Krug-, . , , .
, , , . , API-.
production- CaaS. Microsofts Roslyn, , . , , , , API-, , , Rust
RLS .
Krug — — Caasper CaaS-.
Caasper (, , ), , krug, . , , (bootstrap) , .
Krug JavaScript, Go*, , , Krug. JavaScript , yarn/npm.
* Go () , JS.Caasper
.
Github Krug, D LLVM. YouTube-
.
Krug ()
.
Links úteis