Por que devemos criar um compilador?
Eu acredito piamente em duas coisas:
Todo Corintiano e toda Corinthiana deve assistir ao jogo do Colossal de Itaquera no Santiago Bernaleste (aka Neoquímica Arena) pelo menos uma vez na vida…
E toda pessoa desenvolvedora deve criar seu próprio compilador.
E você pode estar se perguntando: mas por quê?
A resposta é simples: porque é difícil.
Sim, é difícil. Para mim, então… vixi… é algo extremamente difícil…
E antes que você desista da ideia de criar o seu próprio compilador, ou simplesmente não ligue para isso, gostaria de apresentar esse vídeo incrível do incrível professor Clóvis de Barros Filho…
Esse vídeo rodou a internet. Acredito até que você já tenha assistido. Mas eu o acho muito inspirador, tanto que separei dois trechos maravilhosos que eu gostaria de compartilhar/reforçar:
“Você precisa sentar a bunda na cadeira e melhorar a tua capacidade de pensamento…”
E
“É esse brio que levará você a progredir intelectualmente. Estudar, aperfeiçoar a capacidade intelectiva e pensar com competência é tão esforçado quanto ter músculos, correr, nadar travessias: exige empenho, exige dedicação, exige bunda na cadeira.”
É isso. Quanto mais você estudar, quanto mais você se dedicar, mais você vai progredir. Acredite em mim. Não sou coach…
Sendo assim, hoje começo uma série de posts que tem data para começar, mas não tem data para terminar: criando um compilador em csharp!
Mas não se preocupe e não tenha pressa. Post a post vamos evoluindo, explicando e principalmente aprendendo.
Aliás, no momento em que ler esse post, saiba que tem mais dois aguardando a publicação. Quis criar um buffer justamente para não perder o ritmo e espero a cada 15 dias publicar um novo conteúdo.
A motivação
Quando fui escrever o post .NET Source Generators: gerando código em tempo de escrita de código! dediquei muito tempo lendo o código-fonte do Roslyn (compilador do csharp escrito em csharp) e isso me ajudou a entender algumas poucas coisas. Mas foi muito útil.
Porém, foi assistindo o grande Immo Landwerth(Product manager no time do .NET na Microsoft) que eu simplesmente fiquei bestificado! O cara simplesmente criou um compilador na mão usando csharp. Do começo ao fim: https://github.com/terrajobst/minsk!
E o melhor, ao vivo: https://www.youtube.com/live/wgHIkdUQbp0?si=lwLSg28EJPXHE96z. São 28 vídeos fantásticos. Fiz questão de assistir um por um. Duas vezes. Para poder acreditar que era possível… Esse conteúdo é uma fonte extraordinária de estudos.
Suponho que você saiba minimamente o que é um compilador. É importante que você tenha isso em mente. Existem muitos artigos na internet e ainda temos o chat GPT onde podemos buscar ajuda.
Aliás, você pode acessar o https://github.com/terrajobst/minsk/tree/master/docs e ver a lista de todos os episódios, além de ter acesso ao Pull Request de cada implementação. Trabalho fino, trabalho garboso do Immo…
Além disso, conheci o blog do dr. Brian Robert Callahan, onde ele fez uma série maravilhosa chamada Let's write a compiler. É uma aula. Uma não, 8! São 8 posts bem detalhados e muito bem escritos. O cara é sensacional… SEN-SA-CI-O-NAL. Um dia chego lá! Um dia chego…
Isso me motivou a criar meu próprio compilador.
Pug?
Senhoras e senhores, vos apresento Pug: Programming Understandable Global.
Sei que o nome não faz o mínimo sentido, mas a vida é assim mesmo e eu gosto muito de Pugs. Tenho dois, inclusive. Além disso, o nome é simples: pug.
pug build
pug run
Viu só… não é tão ruim quanto parecia… Ou não…
Dado e explicado o nome, é hora de começar a nossa caminhada.
Porém, antes de tudo, gostaria de destacar que essa não será uma caminhada simples, será uma jornada.
Vamos construir um compilador pecinha por pecinha, código por código, tudo de forma didática e tranquila. E durante essa odisseia o resultado que vamos obter a cada post talvez não possa ser classificado como um compilador ou até mesmo um interpretador na essência da concepção computacional. A ideia aqui é ser prático e objetivo quanto às entregas. Cada post revela uma nova funcionalidade. Degrau por degrau. Sem pressa, na tranquilidade…
E tem que ser assim, afinal, entre escrever o código-fonte, parsear e gerar o arquivo binário da aplicação, existe uma distância quase que intergalática. Por isso que não adianta ter pressa. E talvez no meio desse processo, vou precisar parar e explicar (e aprender) mais sobre IL. Opto por IL pelo simples fato de me manter no ecossistema dotnet e por ter bibliotecas que auxiliam na geração de código IL em csharp (tanto a System.Reflection.Emit da própria Microsoft, quanto a Sigil do lendário Kevin Montrose).
Aliás, não sei se ficou claro, mas além do compilador, criaremos uma linguagem de programação. Isso mesmo!
Minha ideia não é criar algo rebuscado, complexo, e sim criar uma linguagem que suporte comandos suficientes para a gente criar um Hello World e fazer algumas operações matemáticas.
Também não quero criar algo como aquela linguagem que não devemos pronunciar o nome, que ao executar null >= [] dá true como resultado…
Um ponto importante para destacar é que a primeira entrega (esse post) trata somente da interpretação de expressões matemáticas simples utilizando e respeitando a ordem dos parênteses, multiplicação, divisão, soma e subtração. Aquelas regrinhas que a gente aprendeu no primário…
Sendo assim, a nossa primeira entrega consegue resolver questões como:
> -(1+(2*3)/4)
-2,5
Devagar e sempre…
Alguns conceitos importantes
Existem muitos conceitos importantes quando falamos de um compilador e dois deles são Lexer e Parser.
O Lexer, ou Analisador Léxico, é responsável por ler todo o código-fonte e extrair tokens.
Para isso, é necessário que o Lexer conheça todas as “palavras reservadas” e as classifique. O resultado dessa classificação é um Token, uma estrutura de dados que informa qual é o tipo, valor e em qual posição da string ela se encontra.
Já o Parser, ou Analisador Sintático, recebe a lista de tokens e analisa se a estrutura sequencial gramatical extraída do código-fonte segue as regras da linguagem de programação.
Feita essa validação, é possível transformar a lista de tokens em uma árvore sintática (AST – Abstract Syntax Tree) ou outro tipo de representação estrutural.
No nosso caso, não vamos gerar uma AST. Pelo menos nesse momento. E quando gerarmos, dedicaremos tempo para explicar o que é, como funciona e traremos, inclusive, exemplos da própria árvore gerada pelo Roslyn a partir de um código csharp.
Além disso, dentro do nosso Parser teremos a execução das expressões (Evaluate) o que o torna quase que um REPL. Isso vai ser bem útil, afinal, podemos interagir com o console escrevendo expressões e validando o resultado.
Uma coisa interessante e importante
Se fizermos um paralelo entre um idioma, como o português, e uma linguagem de programação, a análise léxica seria responsável por identificar as palavras em um texto, ou código-fonte. Vejamos o seguinte “poema” em “português”:
Ojnwerun escola daef fds xçã
Uolasda cachorro aksdmasd da
Bicicleta as asdasda a
Olapasdm rabanada asdasdasm
Como pode notar, a nossa análise consegue identificar somente poucas palavras (escola, cachorro, bicicleta e rabanada). Cognitivamente, não conseguimos absorver/compreender nada desse conteúdo, já que ele não faz sentido, mesmo tendo palavras conhecidas.
Isso pode parecer óbvio quando falamos de idiomas!
Porém, assim como nosso senso de interpretação de texto, o Lexer não tem capacidade de extrair (reconhecer) tokens não mapeados.
Isso explica o motivo pelo qual o compilador do Java não reconhece um código-fonte escrito em Csharp, por exemplo, da mesma forma que se você fala somente português, não vai conseguir entender nada ao ouvir uma frase em russo. Se bem que talvez nem os russos entendam o idioma russo… sei lá… mas enfim… acho que você entendeu…
E quando falamos de análise sintática, basicamente temos uma avaliação do sentido das palavras conhecidas em um texto ou código-fonte.
Não adianta o texto ter somente palavras conhecidas se o conjunto não fizer sentido. Por exemplo:
Abacate jacaré ketchup na pizza
Mundial 51 Palmeiras Romarinho
Lanterna gato escola abacaxi
Incrível correr maionese lambari
Todas as palavras acima são conhecidas do nosso idioma, porém, ao analisar cada frase, notamos que não existe um sentido.
A análise sintática nos traz essa sensação, e no caso de um compilador, nos gera erro.
Agora, outro ponto muito importante é a desambiguação:
A manga tem a cor da manga
O que você entendeu? Que a fruta manga tem a cor da manga da camisa, ou que a manga da camisa tem a cor da fruta? Ou ainda, que tanto faz, já que ambas têm a mesma cor?
No csharp podemos cair em cenários como esses, porém, o compilador consegue resolver da melhor forma, afinal, o idioma (linguagem de programação) é muito mais rígido.
public class async
{
public async Task<async> Task()
{
await System.Threading.Tasks.Task.Delay(10);
return new async();
}
}
O código não faz sentido, não é esse o objetivo. Mas ele compila. O compilador sabe exatamente o que cada palavra faz, não somente pelo seu significado em si, mas pela ordem em que ela aparece.
Não é genial?
Essa relação entre linguagem de programação e idioma é muito próxima que às vezes até se confunde.
Chega… Vamos ver código…
Criando um Analisador Léxico
Café… pega um café…
Considere a expressão abaixo:
1+2- 3
Ao efetuar a extração dos tokens, obtemos a seguinte lista:
Token 1 - Type: Number, Position: 1, Value: 1
Token 2 - Type: Plus, Position: 2, Value: "+"
Token 3 - Type: Number, Position: 3, Value: "2"
Token 4 - Type: Minus, Position: 4, Value: "-"
Token 5 - Type: Space, Position: 5, Value: " "
Token 6 - Type: Number, Position: 7, Value: "3"
Nesse caso simplista, temos somente quatro tipos diferentes de tokens (Number, Plus, Minus e Space). Caso fosse colocado algum caractere fora desses tipos, o lexer apontaria erro, já que ele não o tem mapeado.
O lexer vai varrer o código-fonte, avaliando se um ou mais caracteres estão mapeados na linguagem de programação. Esse mapeamento se dá através de um enum contendo todos os tipos aceitos de token!
Interessante, não? Quando a gente escreve nosso código, nem sequer pensa nisso…
Beleza, agora é para valer!
Crie um projeto dotnet do tipo console application e dê o nome que quiser. Nomeei como Pug.Compiler.
Crie uma pasta chamada CodeAnalysis. Todas as classes que vamos criar ficarão dentro dessa pasta.
A primeira coisa que vamos fazer é criar um enum que vai servir para registrar todos os tipos de tokens que suportaremos:
Arquivo CodeAnalysis/TokenType.cs
namespace Pug.Compiler.CodeAnalysis;
public enum TokenType
{
EOF,
Number,
Plus,
Minus,
Multiply,
Divide,
OpenParenthesis,
CloseParenthesis
}
Basicamente, temos as quatro operações básicas, um tipo numérico, abre e fecha parênteses e um EOF que indica o fim do arquivo. Esse token é importante, pois define o fim da cadeia de interpretação dos tokens pelo Parser. Veremos isso mais adiante. E diferente do exemplo citado acima, eu não estou mapeando espaços. Durante o desenvolvimento, percebi serem inúteis e simplesmente os ignoro…
Arquivo CodeAnalysis/Token.cs
namespace Pug.Compiler.CodeAnalysis;
public record Token(TokenType Type, string Value, int Position)
{
public static Token EOF(int position)
=> new(TokenType.EOF, string.Empty, position);
public static Token Number(int position, string value)
=> new(TokenType.Number, value, position);
public static Token Plus(int position)
=> new(TokenType.Plus, "+", position);
public static Token Minus(int position)
=> new(TokenType.Minus, "-", position);
public static Token Multiply(int position)
=> new(TokenType.Multiply, "*", position);
public static Token Divide(int position)
=> new(TokenType.Divide, "/", position);
public static Token OpenParenthesis(int position)
=> new(TokenType.OpenParenthesis, "(", position);
public static Token CloseParenthesis(int position)
=> new(TokenType.CloseParenthesis, ")", position);
}
Esse record não tem segredo. Ele é uma estrutura de dados que armazena informações do token. Quando o Lexer for executado, ele vai extrair uma lista marota de tokens que serão processados pelo Parser. Destaque para o Number que armazena o valor numérico mapeado. Esse valor pode ter um sinal de mais ou de menos, além de ter um ponto para separação decimal. Por exemplo, -1.23, +4.56, 7.89 ou ainda 77.
Além disso, temos métodos auxiliares para a criação de tokens, isso facilita a escrita de código.
Em seguida, um dos principais pilares do nosso compilador: o analisador léxico:
Arquivo CodeAnalysis/Lexer.cs
using System.Text;
namespace Pug.Compiler.CodeAnalysis;
public class Lexer
{
private readonly string _text;
private int _currentPosition;
private char _currentChar;
private const char EOF = '\0';
public Lexer(string text)
{
_text = text;
_currentPosition = 0;
_currentChar = _text.Length > 0 ? _text[_currentPosition] : EOF;
}
public List<Token> CreateTokens()
{
var tokens = new List<Token>();
while (_currentChar != EOF)
{
if (char.IsWhiteSpace(_currentChar))
{
IgnoreWhitespace();
continue;
}
if (_currentChar == '-' && char.IsDigit(Peek()))
{
tokens.Add(ExtractNumber());
continue;
}
if (char.IsDigit(_currentChar))
{
tokens.Add(ExtractNumber());
continue;
}
var token = _currentChar switch
{
'+' => Token.Plus(_currentPosition),
'-' => Token.Minus(_currentPosition),
'*' => Token.Multiply(_currentPosition),
'/' => Token.Divide(_currentPosition),
'(' => Token.OpenParenthesis(_currentPosition),
')' => Token.CloseParenthesis(_currentPosition),
_ => throw new Exception($"Unexpected character: {_currentChar}")
};
tokens.Add(token);
Next();
}
tokens.Add(new Token(TokenType.EOF, string.Empty, _currentPosition));
return tokens;
}
private Token ExtractNumber()
{
var result = new StringBuilder();
if (_currentChar == '-')
{
result.Append('-');
Next();
}
var hasDot = false;
while (char.IsDigit(_currentChar) || _currentChar == '.')
{
if (_currentChar == '.')
{
if (hasDot)
throw new Exception("Invalid number format: multiple dots");
hasDot = true;
}
result.Append(_currentChar);
Next();
}
var value = result.ToString();
return Token.Number(_currentPosition, value);
}
private char Peek()
{
var peekPos = _currentPosition + 1;
return peekPos < _text.Length ? _text[peekPos] : EOF;
}
private void Next()
{
_currentPosition++;
_currentChar = _currentPosition < _text.Length ? _text[_currentPosition] : EOF;
}
private void IgnoreWhitespace()
{
while (char.IsWhiteSpace(_currentChar))
Next();
}
}
Vamos analisar passo a passo com muita calma.
Essa implementação não é complexa. Ela talvez não é tão natural para você que está lendo, mas acredite, a extração de tokens é algo razoavelmente tranquilo de se fazer.
O primeiro ponto que precisamos entender é que, essa análise percorre do primeiro ao último caractere do nosso código-fonte. Um por um.
Podemos notar que a nossa classe recebe por parâmetro uma variável chamada _text e em seguida iniciamos duas variáveis, a _currentPosition e a _currentChar.
Os nomes por si só já definem a responsabilidade de cada uma delas. Ao percorrer o nosso texto, teremos um cursor que sempre vai apontar para o caractere atual. E como a nossa leitura é sempre feita para frente, isto é, avançando caractere por caractere, foi criado um método chamado Next que faz esse avanço tomando cuidado para não ultrapassarmos o último caractere ao chegar no final do texto.
Outro método interessante é o Peek. Em alguns casos, é necessário observar o próximo caractere a partir do caractere atual para saber se o fluxo segue avançando ou não. Esse método também assegura que não vamos ultrapassar o último caractere.
Sendo assim, imagine que eu tenha a seguinte expressão: -1234.
Ao percorrer esse texto, eu começo identificando um token chamado Minus. Porém, esse token pode ser usado em dois cenários: para identificar que um número é negativo ou para identificar que existe uma conta de subtração. Lembram daquele lance de desambiguação que eu disse logo acima? Então, temos um exemplo aqui…
Por isso é importante, a partir desse token Minus saber se o próximo caractere é um número ou não.
Nesse momento temos já explicados dois métodos fundamentais para o funcionamento do analisador léxico.
Agora podemos adentrar ao método CreateTokens. Como o próprio nome diz, ele inicializa o processo de varredura (do caractere com índice 0 até o final, EOF) e retorna uma lista de tokens.
Esse é o tipo de método que geralmente não fica bonito. É cheio de if e geralmente é um dos que têm mais linhas no código-fonte do compilador.
Um exemplo parecido, num o contexto um pouco diferente, é o método ScanSyntaxToken do Roslyn ou o método ReadToken do minks criado pelo Immo Landwerth.
O nosso extrator de tokens ainda é modesto perto dos dois citados acima…
Certo, avançamos.
A primeira validação que efetuo é a de verificação se o caractere atual é um espaço em branco. Se sim, inicio o processo que ignora todos os caracteres seguintes que forem espaços.
if (char.IsWhiteSpace(_currentChar))
{
IgnoreWhitespace();
continue;
}
Essa validação utiliza o método IgnoreWhitespace que vai avançando caso o próximo caractere em questão seja um espaço vazio.
Isso é para casos do tipo "1 + 3 - 4 *2.
Aliás, curiosamente, em algumas linguagens existem tokens que mapeiam esse caractere, eu resolvi remover para poder diminuir a quantidade de objetos. Não por uma questão de memória — afinal nem me importo aqui com isso — e sim para facilitar o debug.
Um ponto interessante nessas extrações de tokens é que primeiro verifica se o caractere corresponde a algum token type e em seguida caminha para a extração desse token.
Tecnicamente falando, primeiro verifico dentro do while principal if (char.IsWhiteSpace(_currentChar)). Se der match invoco o método IgnoreWhitespace que por sua vez faz a varredura dos próximos caracteres a partir do atual: while (char.IsWhiteSpace(_currentChar)).
Esse é um padrão que se repete…
A seguir temos mais duas validações para números, sendo que a primeira verifica o uso do sinal de negativo no número, e a segunda não.
if (_currentChar == '-' && char.IsDigit(Peek()))
{
tokens.Add(ExtractNumber());
continue;
}
if (char.IsDigit(_currentChar))
{
tokens.Add(ExtractNumber());
continue;
}
Sei que você pode ter torcido o nariz ao ver essas duas condições que poderiam se tornar uma só. Sim, faz sentido unificá-las, mas eu quis separar em duas, justamente para deixar claro a verificação feita no próximo caractere caso a expressão comece com o sinal de menos. Aquele
Peeké muito importante nesse momento e para mim a facilidade na leitura ajuda muito ao debugar o código. Debugar um processo de análise sintática e léxica não é algo tão simples... às vezes dá um brainfuck na gente...
O método ExtractNumber usa o mesmo padrão adotado na validação de espaços em branco. Só que nesse caso verifica se na sequência de caracteres temos números, sinal de menos e ponto separador de decimais. Inclusive, é validado se consta mais de um ponto, se sim, lança uma exceção.
Essa parte do processo valida expressões do tipo -1.234.
A seguir caímos num cenário onde, se não é espaço e se não é número, só pode ser algum desses caracteres: +, -, *, / ( e ). Caso não seja nenhum deles… booooommmm… é lançada uma exception.
Nessa situação nosso querido pattern matching é uma mão na roda…
Considero seriamente rever a ideia de lançar exceções durante a análise léxica e sintática…
Por fim, após percorrer todo o nosso texto, adicionamos o token de EOF(End of File) e finalizamos nossa extração de tokens.
Se você fez faculdade de "Ciências da Computação" e/ou estudou "Autômatos", saiba que a implementação acima nada mais é do que um AFD (Autômato Finito Determinístico (AFD)).
Pensei em falar um pouco sobre ele no momento que eu estava explicando os conceitos de análise léxica e sintática, mas percebi que isso ia deixar o post ainda mais extenso… Mas vale muito a pena estudar isso e destaco aqui alguns links interessantes:
Tokens criados! Agora vamos para a nossa análise sintática.
Nesse caso, eu dei o nome de SyntaxParser para a classe que faz essa análise e execução da expressão. (Muito inspirado por https://github.com/dotnet/roslyn/blob/main/src/Compilers/CSharp/Portable/Parser/SyntaxParser.cs)
Arquivo CodeAnalysis/Parser.cs
namespace Pug.Compiler.CodeAnalysis;
public class SyntaxParser(List<Token> tokens)
{
private Token CurrentToken => tokens[_currentPosition];
private int _currentPosition;
public double Parse()
{
var result = EvaluateExpressionWithPriority();
while (CurrentToken.Type is TokenType.Plus or TokenType.Minus)
{
if (CurrentToken.Type == TokenType.Plus)
{
CheckToken(TokenType.Plus);
result += EvaluateExpressionWithPriority();
}
else if (CurrentToken.Type == TokenType.Minus)
{
CheckToken(TokenType.Minus);
result -= EvaluateExpressionWithPriority();
}
}
return result;
}
private double EvaluateExpressionWithPriority()
{
var result = EvaluateToken();
while (CurrentToken.Type is TokenType.Multiply or TokenType.Divide)
{
if (CurrentToken.Type == TokenType.Multiply)
{
CheckToken(TokenType.Multiply);
result *= EvaluateToken();
}
else if (CurrentToken.Type == TokenType.Divide)
{
CheckToken(TokenType.Divide);
result /= EvaluateToken();
}
}
return result;
}
private double EvaluateToken()
{
var token = CurrentToken;
if (token.Type == TokenType.Plus)
{
CheckToken(TokenType.Plus);
return EvaluateToken();
}
if (token.Type == TokenType.Minus)
{
CheckToken(TokenType.Minus);
return -EvaluateToken();
}
if (token.Type == TokenType.Number)
{
CheckToken(TokenType.Number);
return double.Parse(token.Value, System.Globalization.CultureInfo.InvariantCulture);
}
if (token.Type == TokenType.OpenParenthesis)
{
CheckToken(TokenType.OpenParenthesis);
var result = Parse();
CheckToken(TokenType.CloseParenthesis);
return result;
}
throw new Exception($"Unexpected token in Evaluate Token: {token.Type}");
}
private void CheckToken(TokenType type)
{
if (CurrentToken.Type == type)
_currentPosition++;
else
throw new Exception($"Unexpected token: {CurrentToken.Type}, expected: {type}");
}
}
É meus amigos e minhas amigas. Foi aqui que a porca torceu o rabo. Suei sangue…
Tudo começa com o método Parse onde temos uma varredura de todos os tokens recebidos no construtor da classe.
Da mesma forma que temos um _currentChar na classe de lexer, temos uma propriedade aqui chamada CurrentToken. O conceito aqui é razoavelmente parecido no que diz respeito a avançar entre os tokens. E esse percurso é linear, e não em árvore (AST – Abstract Syntax Tree).
A ideia aqui é fazer avaliação direta (interpretação ou Evaluate, como preferir) durante a análise sintática, ou seja, ele não constrói uma AST, mas já calcula os valores no momento do parsing.
Essa avaliação direta é condicionada a prioridade de execução, tanto que tenho um método que trata somente de expressões e/ou tokens prioritários, EvaluateExpressionWithPriority.
Antes de explicar o fluxo de processamento, quero detalhar o que cada método faz.
CheckToken: valida se o token atual é o esperado durante o processo - aonde vamos avançando dentro de um looping —, se não for, uma exceção é lançada. A cada verificação avanço o ponteiro _currentPosition. Resolvi criar esse método já que ele é muito usado e o código ficou muito repetitivo. Na explicação mais abaixo, vai ficar claro o uso dele, quando eu usar o termo "avança".
EvaluateToken: avança recursivamente na lista de tokens.
Ao encontrar um token do tipo Plus, avança e aplica a recursão. No caso do token Minus faz o mesmo, porém invertendo o sinal do valor do token (-EvaluateToken).
O próximo token a ser tratado é o Number. Ao encontrá-lo, transforma em um tipo double e retorna (durante a recursão, se o token anterior fosse um Minus, seu valor será invertido pelo -.
Por fim, o método avança para encontrar parênteses. Basicamente ele, ao encontrar um token OpenParenthesis, avança e recomeça o processo invocando o método Parse.
Depois do fluxo terminar, ele avança até o CloseParenthesis e retorna o valor processado.
Parse e EvaluateExpressionWithPriority tem um fluxo parecido. A diferença está na ordem de execução. O Parse inicia invocando o EvaluateExpressionWithPriority para efetuar o processo descrito acima pelo método EvaluateToken. Em seguida ele executa as operações de soma e subtração. Nesse ponto já temos a execução do cálculo que vai se agregando a cada iteração.
Talvez não tenha ficado tão claro explicando método por método, porém agora, acredito que vai ficar mais simples "visualizar" esse processo.
Mas antes bora voltar uns 20 anos no tempo… ou mais… enfim…
Logo no primário a gente aprende que "Primeiro se resolve o que está entre parênteses e depois o que está fora" e depois que "Operações de multiplicação e divisão se resolvem antes que operações de soma e subtração" e ainda que a ordem de resolução segue a ordem descrita na expressão (da esquerda para a direita).
Por exemplo, na expressão 1 + 2 * (3 - 4) temos a seguinte ordem de execução:
Primeiro passo, calcula o que está entre parênteses: 3-4=−1
Segundo passo, efetua a multiplicação: 2*−1=−2
Terceiro passo, faz a soma: 1+(−2)=−1
Sendo assim, o fluxo de execução ficou:
-
ParsechamaEvaluateExpressionque chamaEvaluateToken. -
EvaluateTokenconsome 1. - De volta ao
EvaluateExpressionWithPriority, não há*ou/logo, retorna1. - De volta ao
Parse, avança até+, consome e chamaEvaluateExpressionWithPrioritynovamente. -
EvaluateExpressionWithPrioritychamaEvaluateTokendessa vez consumindo o 2. - Avançando encontra
*, consome e chamaEvaluateTokenque consome(, entra recursivamente emParsepara reiniciar um processo, dessa vez com prioridade. - Avança, abre o parêntese e temos
3 - 4.EvaluateExpressionconsome3e avança até-, consome e avança até4, consome e processa o valor retornando-1 - Fecha parêntese e retorna
-1
Nesse momento executamos o primeiro passo descrito acima. Olha o trabalho gigantesco para chegar no resultado prioritário! Seguindo...
- Consome
2, avança até*e efetua o cálculo com o-1processado gerando-2
Fechamos os segundo passo…
- Consome
1, avança até+e efetua o cálculo com o(-2)resultando o valor de-1.
Todo esse trabalho para executar uma tarefa "simples"…
Espero que você tenha entendido a sacada da recursividade. Debugar esse processo ajuda a gente a entender o fluxo. Demorei horas para ajustar esse código. Inclusive acho que o nome dos métodos poderiam ser melhores, talvez eu ajuste isso num futuro…
Enfim, fechamos o fluxo. Agora precisamos testar!
Arquivo Program.cs
using Pug.Compiler.CodeAnalysis;
while (true)
{
try
{
Console.Write("> ");
var input = Console.ReadLine();
if (string.IsNullOrEmpty(input) || input.Equals(":q", StringComparison.CurrentCultureIgnoreCase))
break;
var lexer = new Lexer(input);
var tokens = lexer.CreateTokens();
var parser = new SyntaxParser(tokens);
var result = parser.Parse();
Console.WriteLine(result);
}
catch (Exception ex)
{
Console.WriteLine(ex.Message);
}
}
A ideia aqui é criar um REPL simples que obtém um texto escrito via console, valida se não é um comando para sair :q e começa a jornada de "interpretação" e "execução" de expressões.
Primeiro invocamos o método CreateTokens do lexer e depois repassamos a lista para o nosso Parser que por sua vez nos dá o resultado da operação:
Se tudo der certo e nada der errado, temos o nosso interpretador de expressões numéricas!
> 1+2+3
6
> -1+-2
-3
> --1
1
> (1+2) * (3+4)
21
> ((((((1+2)
Unexpected token: EOF, expected: CloseParenthesis
> \o/
Unexpected character: \
Chegamos ao fim da primeira parte do post.
Você vai poder acessar o repositório clicando em: https://github.com/angelobelchior/Pug.Compiler/tree/parte1
Essa primeira parte foi densa, com muito conteúdo. Mas eu preferi assim, para pavimentar a escrita dos próximos posts de forma mais direta.
Eu precisava passar por alguns conceitos, principalmente de lexer e parser e espero que você, meu caro leitor, minha cara leitora, tenha entendido.
Vocês não imaginam a minha felicidade ao conseguir construir isso. Sério. É um pequeno avanço, de uma longa jornada.
E eu me divirto! Muito!!!
E espero que vocês também!
Caso tenham alguma dúvida, por favor, deixem nos comentários.
Forte abraço, até a próxima, bebam água e cuidado que está rolando muito caso de Dengue…
Top comments (2)
estou criando um também, usando a linguagem D
Showww... ta no github?