A linguagem mais simples possível

Para ler esse conteúdo é recomendado que você saiba:

• como um lexer funciona
• como um parser funciona
• o que são parser generators
• o que é uma AST
• o básico sobre type checking
• o básico sobre type inference

Como nosso objetivo é criar uma linguagem pequena e focando no aprendizado, vamos fazer uma linguagem transpilada para javascript, ou seja, nosso objetivo é pegar um arquivo escrito nessa nossa linguagem e gerar um arquivo javascript que produza o mesmo resultado. Além disso vamos incluir camadas de tipagem para tornar o processo mais desafiador e interessante.

Durante o processo inteiro estarei seguindo este dilema: "faça funcionar, faça do jeito certo, faça ser eficiente.", porém como foco maior na primeira parte para ganharmos velocidade.

Criar uma linguagem de programação, mesmo que muito pequena, é uma tarefa muito grande, por tanto o primeiro passo dessa jornada será dividir o conceito de "linguagem de programação" em pequenas partes e atacar cada um deles individualmente, a famosa estratégia de dividir para conquistar

Primeiro vamos refletir sobre o que compõem um linguagem de programação. A princípio podemos fazer essa reflexão em um nível mais alto de abstração, ao meu ver, os principais componentes são:

• sintaxe: o que e como escrever
• semântica: construções de código, como resolver problemas e significado
• ferramentas: compiladores, sugestões, relatório de erros, colorização, gerenciadores de pacotes, etc.
• bibliotecas: bibliotecas nativas, suporte para bibliotecas da comunidade, etc.
• comunidade: pessoas engajadas e interessadas na linguagem

Como nosso objetivo é fazer uma linguagem pequena com foco maior em aprendizado, vamos focas apenas nos dois primeiros pontos: sintaxe e semântica. Obviamente precisaremos de ferramentas básicas, mas ao invés de construirmos tais ferramentas vamos usar bibliotecas prontas para acelerar nosso processo, futuramente podemos fazer um mergulho na construção dessas bibliotecas.

Existem vários conceitos que precisamos definir nessa nossa linguagem, por exemplo, o que é uma função, o que é um operador binário, um objeto, uma lista, etc. Além disso existem várias etapas que precisamos passar para sair da nossa linguagem criada e chegar no javascript final, essas etapas são:

• tokenize: transformar o texto inicial em tokens
• parse: criar uma AST a partir dos tokens
• type-check: realizar inferência e checagem de tipos na AST gerada
• generate: transformar a AST em javascript válido

Podemos enxergar isso como uma matrix, onde as colunas são as etapas e as linhas são os conceitos, existem duas estratégias possíveis, column-first ou row-first.
Utilizando a estratégia column-first nós focamos em criar todos os conceitos de uma vez etapa por etapa, já na estratégia row-first, atravessamos todas as etapas um conceito por vez.
Pessoalmente prefiro a última opção, pois nela conseguimos aprender mais sobre o problema que estamos resolvendo enquanto fazemos ajustes e ao mesmo tempo não precisamos nos comprometer muito em cada evolução, resumindo, é uma maneira Agile de fazer isso.

Já sabemos as etapas, mas falta aprofundarmos nos conceitos da linguagem, uma lista inicial seria:

• valores literais
• expressões matemáticas
• expressões lógicas
• variáveis
• funções
• estruturas de controle
• estruturas de dados
• comentários
• estruturas de tratamento de erros
• closures
• recursão

Esses são os principais conceitos da linguagem em si, mas ainda temos que pensar nos conceitos de tipagem:

• tipos primitivos, de função e de estruturas
• inferência de tipos
• anotações de tipos
• polimorfismo
• tipos criados
• casting
• covariante e contravariante

Esse parece ser um bom resumo do que precisamos fazer, então vamos começar. Pensando no programa mais simples possível, temos um programa com um único valor literal, por exemplo, um número inteiro.

vamos criar nosso arquivo, ao longo de todo o processo utilizarei a extensão de arquivo .ln0 para denotar programas na linguagem que estamos criando

42

Como tínhamos combinado antes, vamos passar por todas as etapas do processo agora, como é a primeira vez precisaremos criar muitas coisa

A primeira etapa é "tokenize", pra isso vamos precisar de uma biblioteca chamada moo. Vamos instalar a biblioteca e criar nosso arquivo tokenizer.
Nota: estou utilizando o gerenciador de pacotes pnpm provavelmente você precisará adaptar os comandos se estiver utilizando algum outro.

Primeiro vamos iniciar o projeto: pnpm init
Agora instalar o pacote moo: pnpm i moo
E criar o arquivo tokenizer.js (na raiz do projeto mesmo)

No nosso arquivo tokenizer vamos criar uma instância do moo tokenizer e definir nosso tokens iniciais.

const moo = require('moo')

const tokenizer = moo.compile({
  WS: /[ \t]+/,
  int: /0|[-+]?[1-9][0-9]*/,
  NL: { match: '\n', lineBreaks: true },
})

module.exports = tokenizer

Primeira etapa concluída, nós temos agora um tokenizer que é capaz de gerar tokens de números inteiros (e também de espaços e de quebra de linha). A próxima etapa é a etapa de parsing onde vamos transformar o token em uma AST.
Pra isso vamos utilizar a biblioteca nearley.
Instalando nearley: pnpm i nearley
Precisamos do compilador então vamos instalar também globalmente: pnpm i -g nearley
Para utilizar essa biblioteca precisamos criar um arquivo de gramática com a extensão .ne, esse arquivo será utilizado para gerar um outro arquivo de gramática em javascript que por sua vez será utilizado pelo próprio nearley para compilar nossa linaguagem.
O primeiro passo é importar nosso tokenizer (que também pode ser chamado de lexer), fazemos isso dessa forma:

@{%
const tokenizer = require('./tokenizer')
%}

@lexer tokenizer

Agora vamos criar nossa primeira regra gramatical que define que nosso programa consiste de um único número inteiro (recomendo dar uma olhada na documentação do nearley pra entender melhor a sintaxe)

#...
program -> %int {% id %}

Com nosso arquivo gramatical em mãos vamos usar o compilador no nearley nearleyc para gerar nossa gramática em javascript, pra isso rodamos o comando nearleyc lang0.ne -o lang0.js. Automaticamente um novo arquivo será gerado.

O próximo passo é criar um arquivo parser.js, vamos cria-lo por partes.
Primeiramente vamos verificar os argumentos e pegar o primeiro argumento que deve ser o nome do arquivo que será compilado:

const args = process.argv.slice(2);
const filepath = args[0];

if (!filepath) {
  console.error('Usage: node parser.js <filename>');
  process.exit(1);
}

Agora para rodar esse programa precisamos passar um argumento, o próximo passo é usar esse argumento filepath para ler o conteúdo do arquivo, vamos ignorar os edge-cases por enquanto.

const fs = require('fs');

const args = process.argv.slice(2);
//...
}

const file = fs.readFileSync(filepath, 'utf8');

Com a habilidade de pegarmos o conteúdo do arquivo de input, vamos agora importar nossa gramática javascript e o parser do nearley para compilar o conteúdo do arquivo e escrever a AST final

const nearley = require('nearley')
const grammar = require('./lang0')
const fs = require('fs');
//...
const file = fs.readFileSync(filepath, 'utf8');
const parser = new nearley.Parser(nearley.Grammar.fromCompiled(grammar))
parser.feed(file)

if (parser.results.length === 0) {
  console.log('Parsing error')
} else if (parser.results.length === 1) {
  const ast = parser.results[0];
  fs.writeFileSync('ast.json', JSON.stringify(ast, null, 2));
} else {
  console.log('Ambiguous grammar')
}

Note que existem 3 casos finais, ao compilar o arquivo input o compilador pode encontrar algum erro e gerar nenhum resultado, pode encontrar nenhum erro e gerar um resultado (o que esperamos que aconteça) ou pode encontrar nenhum erro porém gerar mais de um resultado o que indica uma falha na nossa gramática.

Para compilar nosso arquivo exemplo basta executar nosso arquivo parser: node parser ex.ln0
Ao executar o comando um novo arquivo será criado, o nosso arquivo ast.json que deve estar assim

{
  "type": "int",
  "value": "42",
  "text": "42",
  "offset": 0,
  "lineBreaks": 0,
  "line": 1,
  "col": 1
}

Mais uma etapa concluída, temos apenas mais duas etapas pela frente, checagem de tipos e geração do arquivo final

Checar a tipagem desse nosso programa é muito simples porque temos apenas um número e um número é um valor literal, além disso como podemos notar a nossa AST possui um atributo "type" que podemos utilizar, mas antes de qualquer coisa precisamos montar a AST em memória para trabalharmos com ela, pra isso vamos iniciar nosso arquivo typecheck.js dessa forma:

const path = require('path');
const fs = require('fs');

const args = process.argv.slice(2);
const filename = args[0];

if (!filename) {
  console.error('Usage: node typecheck.js <filename> [.json]');
  process.exit(1);
}

if (path.extname(filename) !== '.json') {
  console.error('Filename must have .json extension');
  process.exit(1);
}

try {
  const content = fs.readFileSync(filename, 'utf8');
  const ast = JSON.parse(content);
} catch(e) {
  console.error(e?.message);
  process.exit(1);
}

Agora podemos criar a função que verifica se nossa AST (node) é um número inteiro, repare que a partir de agora vou chamar os objetos de node porque futuramente usaremos recursão para analisarmos estruturas mais complexas

Nossa função de verificação será muito básica, dê uma olhada:

function check_int(node) {
  const { type } = node
  return type === 'int'
}

E agora é só verificar nossa AST de antes de printar o resultado na tela

//...
  const ast = JSON.parse(content);
  console.log(check_int(ast));
} catch(e) {
//...

Por enquanto isso é o que precisamos.
Por último vamos transformar essa AST em um arquivo javascript, para fazer isso vamos criar o arquivo generator.js: Iniciamos com a mesma lógica do último arquivo para criarmos a AST em memória

const path = require('path');

const args = process.argv.slice(2);
const filepath = args[0];

if (!filepath) {
  console.error('Usage: node generator.js <filename>');
  process.exit(1);
}

if (!path.extname(filepath) === '.json') {
  console.error('Filename must have .json extension');
  process.exit(1);
}

try {
  const contents = fs.readFileSync(filepath, 'utf8');
  const ast = JSON.parse(contents);
} catch(e) {
  console.error(e?.message);
  process.exit(1);
}

E agora podemos criar nossa função geradora:

function gen_int(node) {
  const { value } = node
  return value
}

Por fim podemos chamar essa função passando nossa AST e salvando o resultado em um arquivo javascript:

const fs = require('fs');
const path = require('path');
//...
  const ast = JSON.parse(contents);
  const output = gen_int(ast);
  fs.writeFileSync('output.js', output);
} catch(e) {
//...

Depois de rodar o comando node generator ast.json um novo arquivo output.js deve ter sido criado na raiz do projeto contendo um único número inteiro:

42

Se quiser é possível rodar esse programa javascript com node output

Pronto, finalizamos o menor conceito dentro do nosso escopo, começamos com um número inteiro na nossa linguagem e passamos por 4 etapas até chegar em um número inteiro em javascript.
Como números inteiros são sempre os mesmos então isso não parece ser muita coisa, mas já temos todo o pavimento necessário para as próximas evoluções.
Números inteiros fazem parte do grupo dos valores literais, assim como os números com ponto flutuante, strings, chars, bools, entre outros.
Nosso próximo passo agora está muito claro, expandir todo o nosso sistema para que possamos criar um programa com qualquer um dos valores literais e conseguir chegar em um arquivo javascript válido no final.