Criando um compilador em csharp: Parte 5

Caramba… chegamos à parte 5! Quem diria…

Aliás, a ideia de primeiro escrever o código e depois escrever o post facilitou muito a minha vida. Faço um diff entre as branchs e consigo saber exatamente quais foram as mudanças de um post para o outro. Simples assim! Vivendo, codando e aprendendo.

Bom, no post anterior adicionamos suporte a operadores lógicos &&, ||, ==, >=, <=, etc., além de mapear os tokens if, else, e end para podermos adicionar suporte a estrutura condicional.
Basicamente, hoje vamos adicionar suporte a uma estrutura de código como esta:

if idade >= 18
   print("acesso liberado")
else
   print("acesso negado")
end

O token then foi mapeado, mas eu resolvi removê-lo. Preferi deixar a linguagem mais enxuta...

Nós já mapeamos os tokens necessários no post anterior, agora precisamos fazer a análise sintática deles, além do evaluate.

A implementação em si não foi tão complexa, o que me causou estranheza, mas basicamente vamos criar um método EvaluateIf e fazer toda a mágica nele.

Arquivo CodeAnalysis/SyntaxParser.cs:

Primeiro vamos alterar o método EvaluateToken para invocar o evaluate do If:

private Identifier EvaluateToken()  
  => CurrentToken.Type switch  
  {  
      TokenType.If => EvaluateIf(),  
      ...
 };

Em seguida criamos o método EvaluateIf:

private Identifier EvaluateIf()
{
    NextIfTokenIs(TokenType.If);
    var condition = EvaluateExpression();

    if (condition.ToBool())
        ParseBlock(TokenType.Else, TokenType.End);
    else
        SkipBlockUntil(TokenType.Else, TokenType.End);

    if (CurrentToken.Type == TokenType.Else)
    {
        NextIfTokenIs(TokenType.Else);
        if (!condition.ToBool())
            ParseBlock(TokenType.End);
        else
            SkipBlockUntil(TokenType.End);
    }

    NextIfTokenIs(TokenType.End);
    return condition;
}

private void ParseBlock(params TokenType[] delimiters)
{
    while (!delimiters.Contains(CurrentToken.Type) && CurrentToken.Type != TokenType.EndOfFile)
        EvaluateToken();
}

private void SkipBlockUntil(params TokenType[] delimiters)
{
    var nestedIfCount = 0;
    while (CurrentToken.Type != TokenType.EndOfFile)
    {
        if (delimiters.Contains(CurrentToken.Type) && nestedIfCount == 0)
            return;

        if (CurrentToken.Type == TokenType.If)
            nestedIfCount++;
        else if (CurrentToken.Type == TokenType.End && nestedIfCount > 0)
            nestedIfCount--;

        _currentPosition++;
    }
}

Só isso… que moleza, hein... Nem suei!

Basicamente procuramos pelo token If. Ao encontrá-lo, avançamos e fazemos o parse da expressão seguinte. Essa expressão precisa ser uma condição booleana, logo, seu resultado é convertido para true ou false. Caso não seja possível essa conversão, obteremos erro…

Se essa expressão retornar um true, iniciamos o processamento do bloco do if. Para isso, invocamos o método ParseBlock que vai processando todos os tokens que não sejam tokens de finalização de bloco, no caso TokenType.Else e TokenType.End.

Acredito que o método ParseBlock seja autoexplicativo: vai avançando e dando evaluate nos tokens até que encontre um token de finalização.

Eu não sei se valeu a pena isolar esse processo em um método, mas acho que ficou mais fácil para explicar...

Caso a condição seja false, é necessário "pular" para o token de finalização, que pode ser um else ou um end. Para isso temos o método SkipBlockUntil.

Esse método é interessante. Imagine que podemos ter inúmeros if dentro de else ou até mesmo de um if. Por exemplo:

int idade = 18
string nome = "Angelo"
if idade >= 18
    print("acesso permitido")
else
    if nome == "Angelo"
        print("acesso em avaliação")
    else
        print("acesso negado")
    end
end
print("Fim do programa")

O código acima é bonitinho, mas podemos ter o tenebroso Código Hadouken:

Com isso, o método SkipBlockUntil precisa identificar quando um bloco if ou else terminam. Porém, como podemos ter um bloco dentro do outro que está em um terceiro bloco, precisamos identificar a “profundidade” do bloco para sabermos se chegamos ao final ou ainda devemos avançar entre os tokens.

Esse processo só termina quando encontra um token de finalização no mesmo nível de aninhamento (ou seja, quando nestedIfCount é zero), garantindo que blocos internos não causem término prematuro da busca. Isso força o processo a pular partes do código que não devem ser executadas.

Acredito que exista uma forma de simplificar esse algorítimo, mas não estou preocupado com isso. Mas é certo que tem como medir essa profundidade de forma mais performática e/ou inteligente.

Funcionou? Sim. Segue o baile.

O processo segue verificando se, após encontrar um if e fazer o seu processo, existe um else.
Caso exista e a condição force a execução do bloco do else (condition é false), o método ParseBlock é invocado e o fluxo segue da mesma forma apresentada acima.

E por fim, fechamos o processo validando a presença do end no final do bloco da estrutura condicional.

Esse fluxo não foi tão complexo e abre as portas para a implementação da estrutura de looping while. Mas isso fica para o próximo post.

Como finalizei essa implementação até que rápido, resolvi incluir suporte ao operador % que obtém o resto da divisão.

Essa implementação é bem simples também, já que os operadores matemáticos já estão implementados.

Começamos adicionando o token Remainder. Sim, aquele símbolo de percentual é chamado de Remainder. Eu também não sabia…

Arquivo CodeAnalysis/Token.cs:

...
public const char REMAINDER = '%';
...

public static Token Remainder(int position)  
  => new(TokenType.Remainder, REMAINDER, position);
...

Token criado, vamos extraí-lo:

Arquivo CodeAnalysis/Lexer.cs:

private Token ExtractSymbols()
{
    ...
    var singleCharTokenFactory = new Dictionary<char, Func<int, Token>>
    {
        ...
        [Token.REMAINDER] = Token.Remainder,
        ...
    };

    if (singleCharTokenFactory.TryGetValue(_currentChar, out var tokenFactory))  
    {  
      Next();  
      return tokenFactory(position);  
    }
    ...
}

No método ExtractSymbols, incluímos o novo operador para ser encontrado no processo de extração de símbolos. Esse método ficou bem interessante já que é muito simples adicionar qualquer novo operador. Se num futuro eu quiser adicionar o operador ^ para efetuar o cálculo de potência, moleza.

Feito isso, se você já acompanha a série, sabe que agora precisamos fazer o evaluate dessa operação.

Arquivo CodeAnalysis/SyntaxParser.cs:

O método EvaluatePlusOrMinus mudou de nome para EvaluatePlusOrMinusOrRemainder. E como o próprio nome diz, agora vamos verificar % além do + e -.

private Identifier EvaluatePlusOrMinusOrRemainder()  
{  
    var left = EvaluateMultiplyOrDivide();  
    while (CurrentToken.Type is TokenType.Plus or TokenType.Minus or TokenType.Remainder)  
    {  
        var op = NextIfTokenIs(CurrentToken.Type);  
        var right = EvaluateMultiplyOrDivide();  
        left = EvaluateOperation(left, right, op);  
    }  
    return left;  
}

Essa alteração foi feita nesse método já que o operador % tem a mesma prioridade da soma e da subtração.

Em seguida, executamos a operação. E para isso precisei alterar o método EvaluateNumberOperation:

private static Identifier EvaluateNumberOperation(Identifier left, Identifier right, Token @operator)  
{  
    var value = @operator.Type switch  
    {  
        ...
        TokenType.Remainder => left.ToDouble() % right.ToDouble(),  
        _ => throw new Exception($"Unexpected token: {@operator.Type}")  
    };  
    return new Identifier(DataTypes.Double, value);  
}

Basicamente é isso! Simples assim.

E com essas novas features podemos escrever o seguinte código na nossa linda linguagem de programação:

int numero = 10
if numero % 2 == 0
    print("Número " + numero + " é par")
else
    print("Número " + numero + " é ímpar")
end

Além disso, nessa branch foi ajustado o código para que nomes de variáveis permitirem _ e números no meio da palavra: exemplo: int var_1 = 4.

E é claro que nosso Pug.Editor não ficou de fora e recebeu boas atualizações:

• Ajustes no Layout
• Inclusão de um combo com samples de código
• Ao clicar em um token (no painel a esquerda) é possível visualizar no editor o código-fonte que gerou aquele token
• Caso ocorra algum erro de compilação, o editor irá destacar a linha do erro

Gravei um vídeo mostrando por cima como o nosso editor ficou:

Curtiu???

Sensacional! A cada nova feature eu me empolgo mais e mais.

Na parte 6 vamos adicionar suporte a estrutura de looping: while!!!

O Pug ta saindo da casinha!

---

Antes de terminar o post, gostaria de fazer uma menção honrosa!

Dando uma zapeada na internet, achei esses dois posts onde o grande Konstanty Koszewski implementa um interpretador BASIC usando Ruby. SENSACIONAL! Ótima fonte de estudos!

Destaque para o quão bonita é a linguagem Ruby…

Parte 1: https://medium.com/@konstanty.koszewski_35161/basic-interpreter-in-ruby-from-scratch-part-1-c68bbf365ab0

Parte 2: https://medium.com/@konstanty.koszewski_35161/basic-interpreter-in-ruby-from-scratch-part-2-d55a778af326

É muito louco pensar em escrever um compilador/interpretador. Não é nada trivial, logo, é difícil achar conteúdos sobre o tema que não sejam artigos científicos/acadêmicos. Eu sempre pesquiso sobre compiladores e o que encontro geralmente são estudos densos e tensos. Saber que existem conteúdos sobre o tema acessíveis, numa linguagem de fácil entendimento é realmente maravilhoso.

---

E fechamos aqui mais um post.

Código-fonte do post: https://github.com/angelobelchior/Pug.Compiler/tree/parte5

Muito obrigado e até a próxima.