Hoje eu vou te dar algumas dicas de como você pode construir o seu próprio parser.
Estudo o tema a alguns anos, mais não sou especialista no assunto, tendo em vista que muitas pessoas dedicaram uma vida toda para isso.
Vou deixar claro que a forma descrita aqui nesse artigo não é a única forma de se fazer isso.
Na ciência da computação, um parser é o segundo processo de compiladores/ interpretadores, mais é um termo muito comum quando se trata de interpretar um código, você pode ouvir coisas como fiz um parser para converter uma documentação para código que nada mais é que um simples compilador.
Mencionei que se trata da segunda etapa de um compilador, pois quando você está construindo esse tipo de aplicação normalmente iniciamos pelo lexer.
Eu, por exemplo, acho a parte mais legal de se iniciar, mais hoje a diversão está no parser mesmo.
Hoje vamos resumir nas seguintes etapas:
Lexer -> Parser -> AST ...
O nosso processo vai até a AST.
Caso nunca tenha construído alguma aplicação do tipo, eu recomendo pensar inicialmente nesses processos, depois podem partir para otimização de código, análise semântica e a construção de uma máquina virtual...
Outra informação é que você pode usar projetos como o YACC para fazer isso, ela possui uma sintaxe própria e um caminho simples para montar sua AST, eu sempre prefiro fazer o processo manualmente.
Vamos para a explicação.
A análise léxica ou tokenização eu considero o processo mais simples, inicia-se identificando caracteres e palavras-chave, no lexer eu costumo identificar a palavra e para qual grupo ela pertence.
Por exemplo:
let name = "jeantux"
Um lexer leria o código acima e poderia retornar uma estrutura no seguinte formato:
[
{type: TK_LET, value: "let"},
{type: TK_ID, value: "name"},
{type: TK_EQ, value: "="},
{type: TK_STRING, value: "jeantux"},
]
Essa estrutura acima é ilustrativa e você pode converter ela da forma que considera mais simples para sua linguagem, ou melhor, da forma que considera mais performática, afinal, estamos em outro nível agora.
Por exemplo, no Drax Compiler implementei a estrutura do lexer da seguinte forma:
typedef struct d_token {
dlex_types type;
dfstap_errors_type error_type;
const char* first;
int length;
int line;
} d_token;
Normalmente não retornamos uma lista com todo o resultado da interpretação do código, pois podemos precisar interpretar arquivos e aplicações muito grandes e isso pode causar alguns problemas de memória, por esse motivo em algumas implementações é comum você ver o parser pedindo para o lexer qual é o próximo identificador, lembre-se disso.
Observando essa estrutura, nota-se que deveríamos ter um enumerador ou lista contendo os tipos aceitos em nossa linguagem.
Por exemplo, algo assim:
enum dlex_types {
TK_LET,
TK_ID,
TK_EQ,
TK_STRING,
}
Você pode conferir nesse arquivo
O principal de tudo é como identificamos os tokens, e realmente é algo simples. Temos um loop que lemos letra a letra verificando em qual condição ela se encaixa.
while (*clexs.current != '\0') {
char c = next_char();
switch (c) {
case ' ':
break;
case '\n': {
line++;
break;
}
case '=':
return dmake_symbol(DTK_EQ);
...
}
}
Algo interessante nesse processo é perceber que a quantidade de linhas está sendo feita line++;, parte importante para montar o stack trace (se você já é desenvolvedor a algum tempo, sabe valorizar isso).
E claro se você está atento aos detalhes percebeu que eu sempre retorno o token, ao invés de uma lista, dentro desse token tem informações como o número da linha atual.
Se na linguagem que escolheu para escrever o projeto existe suporte a regex, esse processo pode ser bem mais simples, identificar números e padrões vai ser uma tarefa tranquila e sei que você vai fazer isso com as mãos nas costas.
Essa etapa é massa! É o que chamamos de "Análise sintática", após ter uma função que retorna os tokens podemos avançar para interpretar esses dados e ir montando uma estrutura que vai representar nosso código.
Exemplo, para aquele código acima, podemos ter uma estrutura nesse formato
[
{type: VAR},
{type: ID, value: "name"},
{type: EQ}
{type: STRING, value: "jeantux"},
]
Novamente, essa é uma estrutura de exemplo, sendo bem semelhante à descrita no início, porem o nosso parser consegue avisar se ela não estiver correta, por exemplo:
let name "jeantux"
o lexer ao processar essa sintaxe, retornaria os tokens normalmente:
{type: TK_LET, value: "let"}
{type: TK_ID, value: "name"}
{type: TK_STRING, value: "jeantux"}
Porem no processo de análise verificaríamos que está faltando o TK_EQ.
E uma forma que podemos fazer isso é, ir pedindo para o lexer o próximo token se recebermos algo esperado, por exemplo:
Recebemos o token TK_LET, adiciona ele na "lista" e pedimos o próximo token.
Recebemos o token TK_ID, adiciona ele na "lista" e pedimos o próximo token.
Recebemos o token TK_STRING, ERRO: É uma cilada, Bino! esperava o TK_EQ.
Nesse caso de erro podemos usar o número da linha atual, armazenada no token para avisar ao usuário qual é alinha do erro.
Em um caso de sucesso teríamos um "lista" com todos os tokens na ordem correta e essa "lista" chamamos de AST (Abstract syntax tree ou Árvore sintática abstrata) e ela pode ter vários formatos dependendo da linguagem e tipo de aplicação que você está criando, mas é muito comum utilizar uma estrutura de árvore para representar esses valores.
Falei que essa estrutura pode variar, pois em casos de aplicações muito simples você pode em seguida gerar o seu resultado a partir dessa AST.
Você pode interpretar diretamente a AST, é um caminho comum para estudantes, mas tenha em mente que seu interpretador será mais limitado, no entanto, se o seu propósito for uma sub linguagem ou algo pequeno, não tem problema nenhum.
Mais se deseja avançar, gerando um código com um nível maior de qualidade, os próximos processos podem ser: analise semântica, geração de código intermediário, otimização de código, e gerador de código alvo ou interpretar esse código intermediário em uma máquina virtual.
No caso do projeto Drax Compiler, não interpretamos diretamente a AST mais deixamos de lado algumas etapas importantes como otimização de código (Até o momento que escrevo esse post).
Aqui vai uma dica de como você pode começar implementando esse parser:
Eu acho legal adicionar algum loop verificando os tokens recebidos, e enquanto não chegar no final você pode ir adicionando esses dados na AST:
while (GET_CURRENT_TOKEN_TYPE() != DTK_EOF) {
// Process Tokens
}
Você pode verificar como isso foi feito aqui nesse arquivo
Se quer ir mais fundo eu recomendo ler código de outros compiladores/ interpretadores famosos como, Lua, Rust, Ruby ...
Você tera algumas tarefas difíceis como processar expressões matemáticas, entender escopos, mais caso tenham interesse, posso comentar sobre isso futuramente.
Este é o fim e até a próxima 😎