Introdução
Nós usamos linguagens de programação diariamente, e as vezes pode parecer que o computador está fazendo uma mágica: você escreve um arquivo de texto e o computador magicamente executa as operações que esse arquivo descreve.
Quando eu era criança, existia um desenho animado chamado “De onde vem?”. A cada episódio algo era explicado, como por exemplo, “De onde vem o vidro?”. Era uma explicação simples e de fácil entendimento, porém bem satisfatória.
Com isso em mente, a ideia desse artigo, é explicar um pouco sobre de onde vêm as linguagens de programação. Nesse post, eu pretendo explicar um pouco sobre como uma linguagem pode ser implementada, e por fim, trazer alguns materiais de estudo bem interessantes para quem deseja se aprofundar e quem sabe programar a sua própria linguagem.
Para que uma linguagem tome vida, é preciso implementá-la
Antes de mais nada, precisamos separar muito bem dois conceitos: a ideia abstrata da linguagem, e a sua implementação concreta (um interpretador ou compilador).
Uma linguagem nada mais é do que uma forma de se comunicar, é uma sequência de letras organizadas de forma a passar uma mensagem.
O problema é: computadores não entendem palavras, nem mesmo sequências esquisitas de letras (o comando LDS, por exemplo). Tudo o que o computador entende, são instruções pra sua CPU. Então é necessário ter algum software capaz de pegar as operações descritas na nossa linguagem (o print('hello world'), por exemplo), e transformar isso em instruções para o computador interpretar, de alguma forma.
Ou seja, precisamos de uma implementação concreta para que nossa linguagem possa ser executada. Nesse artigo, sempre que eu falar “linguagem”, eu estou me referindo à essa implementação concreta e prática que traz utilidade para o amontoado de texto colorido que escrevemos.
E esses programas capazes de executar linguagens têm nome: interpretadores e compiladores.
O que são interpretadores e compiladores? E qual a diferença entre eles?
O que é um compilador?
De forma muito resumida, um compilador é um programa que transforma o seu código fonte, em outro tipo de representação, que geralmente é uma forma mais eficiente para o computador executar. O software que pega seu código C, e transforma em binário executável, é um compilador. Mas o software que pega o código typescript (main.ts), e transforma em javascript (main.js) para ser executado no navegador, também é um compilador.
Ou seja, um compilador não é necessariamente um programa que lê código numa linguagem X e cospe código binário. Esse programa basicamente tem a responsabilidade de transformar seu código em algo alguma representação que possa ser executada de alguma forma, mas essa representação pode ter várias formas.
O que é um interpretador?
Por outro lado, um interpretador é um programa que lê o seu código fonte, e de alguma forma, executa as instruções que ele contém. Só isso, então quando você passa código javascript para o Nodejs, ele está agindo como um interpretador: lendo código fonte, e interpretando-o. E algumas interpretadores usam compiladores para os auxiliarem no processo de interpretador uma linguagem.
A linguagem PHP por exemplo, tem uma espécie de máquina virtual chamada Zend, que recebe uma representação compilada do seu código fonte, e executa as instruções dessa representação.
Pera, então linguagens interpretadas também podem ser compiladas?
Sim, isso é algo um pouco confuso no início, mas a ideia principal é que interpretadores e compiladores não são opostos. Um compilador tem um papel muito claro, e esse papel é diferente de um interpretador.
Muitas linguagens interpretadas usam a técnica de ter uma espécie de máquina virtual, extremamente otimizada, que recebe uma coisa que chamamos de bytecode e executa isso. Então, a máquina virtual de linguagens como PHP e Python, não são capazes de entender seu código e por isso precisamos da ajuda de compiladores, para gerar bytecode a partir do seu código (imagine como um assembly para uma máquina virtual).
No fim das contas, quando falamos que uma linguagem é “interpretada”, simplesmente queremos dizer que você precisa sempre passar o seu código fonte para um programa (o node ou python, por exemplo), e esse programa já vai rodar o seu código.
E quando uma linguagem é “compilada”, primeiro você precisa passar seu código fonte para um programa (o gcc ou tsc, por exemplo), que irá gerar um novo arquivo, e daí sim poderemos executar esse arquivo de alguma forma.
Ok, entendi de onde vêm as linguagens, mas como eu posso criar uma implementação?
Eu diria que o caminho mais prático pra quem está começando é criar um interpretador, que utiliza a técnica de tree walk para interpretar o código. Esse estilo de implementação é quebrada em 3 componentes principais: scanner, parser e o interpretador tree walk.
O seu código passará por esses 3 componentes nessa ordem mesmo, onde a cada etapa, o interpretador transforma o seu código em estruturas cada vez mais fáceis de serem interpretadas pelo computador.
Esse fluxograma simples mostra o caminho do código fonte da sua linguagem até a fase da interpretação.
Vou explicar (com códigos de exemplo) cada uma dessas etapas.
Scanner
Nessa fase o seu código fonte é lido como uma string (sequência de caracteres) e quebrado em vários tokens. Esse token é uma unidade da sua linguagem de programação, como por exemplo as palavras reservadas while e if, ou então os literais como "isso é uma string" ou 10.
Então, isso:
Vira isso:
Essa imagem é só pra exemplificar a quebra do código fonte em tokens, geralmente o “token” é um objeto/estrutura contendo algumas informações importantes como:
- O seu tipo (ser é um
for, um número, operador++e etc.). - O seu lexema (a string que achamos na hora de escanear esse token).
- Em qual linha ele foi encontrado (ajuda bastante na hora de aportar erros de sintaxe).
Um exemplo de token seria:
class Token { public function __construct( public readonly TokenType $tipo, public readonly mixed $valor, // Válido somente para valores literais como "strings" e números (10.5) explícitos no código fonte public readonly string $lexema, public readonly int $linha ){}
}
Parser
Nessa fase já possuímos os tokens, mas esse monte de tokens ainda não possui significado algum, não possui semântica. Então o parser vai transformar esse amontoado de tokens em algo mais palpável: uma árvore, representando as operações. Chamamos essa árvore de “Parse Tree”.
Uma parse tree é uma estrutura de capaz de representar fielmente a estrutura do seu programa, respeitando as regras de precedência (por exemplo, no código const x = 5 * 5, precisamos executar o código 5 * 5 antes de executar o código de atribuição const x = ... que irá receber o valor do resultado)
Por exemplo, imagine a expressão 10 + 5 * 2. Ela pode ser representada assim na parse tree:
Na parse tree, cada item (chamamos de nó da arvore) tende a representar uma operação feita no código. Onde cada nó por sua vez pode conter várias ramificações e se tornar uma árvore, com outros nós representando operações mais aninhadas na expressão.
Também é bom lembrar que a imagem acima é um exemplo, e um nó de uma parse tree pode ser um objeto/estrutura com várias informações úteis, como por exemplo, assim pode ser um nó que guarda operações binárias (uma operação com dois operandos, como soma ou multiplicação):
class BinaryExpr extends Expr
{ public function __construct( public readonly Expr $esquerda, public readonly Token $operador, public readonly Expr $direita ){}
}
Nesse nó eu salvo a ramificação de expressões à esquerda e direita, que podem ser uma variável (x + 4), uma chamada de função (pegaNoBanco(x) + 4) ou um literal (10 + 4). E também guardo o token que possui informações do operador dessa expressão (+, *, etc.).
Interpretação Tree Walk
As duas primeiras fases são praticamente iguais pra QUALQUER implementação de uma linguagem, mas a partir dessa fase, cada linguagem vai escolher suas técnicas para dar vida à parse tree. Existe uma infinidade de técnicas, e nessa artigo vamos abordar uma das mais diretas: A Tree Walk.
Como o nome sugere, a ideia é percorrer a árvore de expressões e ir computando os nós mais profundos primeiro e indo subindo até a raiz da árvore.
Na implementação do Phortugol, eu usei pattern matching pra ter uma função que conseguia interpretar cada tipo de nó da árvore e me retornar um resultado
public function evaluate(Expr $expr): mixed { return match(true) { $expr instanceof BinaryExpr => $this->handleBinary($expr), $expr instanceof UnaryExpr => $this->handleUnary($expr), $expr instanceof LiteralExpr => $this->handleLiteral($expr), $expr instanceof LambdaExpr => $this->handleLambdaExpr($expr), ... }; }
Então sempre que eu chamar a função evaluate passando uma ramificação da árvore, ele vai saber exatamente qual função chamar pra interpretar o nó atual, e no fim das contas essa função continuará sendo chamada até o resultado de todas as operações chegar à raiz da arvore e obtermos o resultado final da expressão.
Por exemplo, a parse tree anterior seria interpretada da seguinte forma:
Um fato curioso, é que as primeiras versões de Ruby e PHP usavam essa técnica de tree walk. Então é totalmente possível construir uma linguagem funcional usando um tree walk interpreter.
conclusão
Ufa finalmente chegamos ao fim. Eu expliquei a ponta do iceberg, tem várias técnicas que eu não cobri, e não falamos sobre coisas como compilação e nem otimização de código (essa parte é bem mindblowing). Mas eu espero que já seja possível ter um modelo mental mais acurado sobre o que acontece quando digitamos o código e mandamos o computador rodar.
Caso você tenha se interessado pelo assunto, tenho algumas recomendações:
- O livro crafting interpreters. É absurdamente bom, eu gostaria que mais áreas da computação tivessem um livro com a mesma qualidade, pragmatismo e simplicidade sem perder profundidade.
- Essa playlist sobre parsers top down, os dois primeiros vídeos são a melhor explicação sobre o “Recursive Descent Parser” que eu já vi. Recomendo usar como material de apoio