Reinventando a Roda: Criando um compilador em csharp

Caramba, chegamos à quarta parte!

Dessa vez, mudei um pouco a dinâmica de escrita. Antes eu ia codando e escrevendo algumas coisas que depois eu organizava no post. Porém, pela complexidade da nova feature não consegui codar e escrever, sendo assim, nesse momento tenho todo o código pronto. Gostei dessa dinâmica. Talvez eu continue dessa forma, foi muito mais produtivo, a meu ver.

Certo. E o que temos para hoje?

Bem, na parte 3 implementamos suporte a variáveis int, double, string e bool além de adicionar suporte à concatenação de strings e cálculos matemáticos entre números.

Porém, nessa quarta parte, decidi explorar mais os operadores lógicos e de comparação.

É importante destacar que vamos mapear os tokens if, then, else e end, mas a implementação da estrutura condicional ficará para o próximo post.

Aliás, um ponto muito importante. Para poder efetuar essa implementação, dediquei um bom tempo lendo um livro simplesmente sensacional: Crafting Interpreters.

Que livro foda! Escrito pelo grande Robert Nystrom, esse livro aborda a implementação de um compilador de maneira simples e direta. O Robert usa Java, facilitando muito a leitura do código. Além disso, ele aborda os tópicos de forma muito didática. Gostei bastante. É um baita guia prático para criar sua própria linguagem de programação. Que é o nosso caso…

Esse livro foi indicação do grande mestre Pedro Jesus. Lembrando sempre que In Pedro Jesus we trust.

Seguimos…

Se você está nos acompanhando desde a primeira parte já sabe que o início da implementação de novos tokens começa pela classe Token mapeando as novas palavras reservadas e novos símbolos e, em seguida, usamos a classe Lexer para efetuar a extração dos mesmos.

Nessa feature, vamos adicionar suporte a operadores lógicos e para isso precisamos mapear os tokens >, <, !, & e |:

Arquivo CodeAnalysis/Token.cs

public const char GREATER = '>';
public const char LESS = '<';
public const char NOT = '!';
public const char AMPERSAND = '&';
public const char PIPE = '|';

Criamos essas novas constantes além dos métodos de apoio:

public static Token Greater(int position)
    => new(TokenType.Greater, GREATER, position);

public static Token Less(int position)
    => new(TokenType.Less, LESS, position);

public static Token GreaterOrEqual(int position)
    => new(TokenType.GreaterOrEqual, GREATER + EQUAL.ToString(), position);

public static Token LessOrEqual(int position)
    => new(TokenType.LessOrEqual, LESS + EQUAL.ToString(), position);

public static Token Equal(int position)
    => new(TokenType.Equal, EQUAL + EQUAL.ToString(), position);

public static Token NotEqual(int position)
    => new(TokenType.NotEqual, NOT + EQUAL.ToString(), position);

public static Token And(int position)
    => new(TokenType.And, AMPERSAND + AMPERSAND.ToString(), position);

public static Token Or(int position)
    => new(TokenType.Or, PIPE + PIPE.ToString(), position);

Nenhuma novidade até aqui.

Além de operadores lógicos, começo a mapear os tokens necessários para termos uma estrutura de if/else.

Na nossa linguagem de programação, a forma de uso dessas instruções será feita da seguinte forma:

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

Ruby like pero no mucho… Na verdade, tem meio que uma pegada de VB6… (Lembrando que esse trecho de código ainda não funciona…)

Para isso, novos tokens precisam ser mapeados. O processo é o mesmo:

public const string IF = "if";
public const string THEN = "then";
public const string ELSE = "else";
public const string END = "end";

...

public static Token If(int position)
    => new(TokenType.If, IF, position);

public static Token Then(int position)
    => new(TokenType.Then, THEN, position);

public static Token Else(int position)
    => new(TokenType.Else, ELSE, position);

public static Token End(int position)
    => new(TokenType.End, END, position);

Certo, agora vamos incluir a extração desses tokens. O processo é idêntico aos que já fizemos anteriormente, logo, vou passar somente por alguns métodos.

Arquivo CodeAnalysis/Lexer.cs

Basicamente, alteramos dois métodos: ExtractKeyword e ExtractSymbols:

private Token ExtractKeyword()
{
    var position = _currentPosition;
    var identifier = ExtractIdentifier();

    if (Identifier.ContainsDataType(identifier.Value))
        return Token.DataType(position, identifier.Value);
    if (BuiltInFunctions.Contains(identifier.Value))
        return Token.Function(position, identifier.Value);
    if (identifier.Value is Token.TRUE or Token.FALSE)
        return Token.Bool(position, identifier.Value);

    if (identifier.Value == Token.IF)
        return Token.If(position);

    if (identifier.Value == Token.THEN)
        return Token.Then(position);

    if (identifier.Value == Token.ELSE)
        return Token.Else(position);

    if (identifier.Value == Token.END)
        return Token.End(position);

    return Token.Identifier(position, identifier.Value);
}

O ExtractKeyword não tem segredo: procuramos por textos equivalentes ao if, else, then e end. Simples assim.

Já o ExtractSymbols…

private Token ExtractSymbols()
{
    var position = _currentPosition;

    var doubleCharToken = (_currentChar, Peek()) switch
    {
        (Token.AMPERSAND, Token.AMPERSAND) => Token.And(position),
        (Token.PIPE, Token.PIPE) => Token.Or(position),
        (Token.EQUAL, Token.EQUAL) => Token.Equal(position),
        (Token.NOT, Token.EQUAL) => Token.NotEqual(position),
        (Token.GREATER, Token.EQUAL) => Token.GreaterOrEqual(position),
        (Token.LESS, Token.EQUAL) => Token.LessOrEqual(position),
        _ => null
    };
    if (doubleCharToken is not null)
    {        
        Next(2);
        return doubleCharToken;
    }
    var singleCharTokenFactory = new Dictionary<char, Func<int, Token>>
    {        
        [Token.PLUS] = Token.Plus,
        [Token.MINUS] = Token.Minus,
        [Token.MULTIPLY] = Token.Multiply,
        [Token.DIVIDER] = Token.Divide,
        [Token.OPEN_PARENTHESIS] = Token.OpenParenthesis,
        [Token.CLOSE_PARENTHESIS] = Token.CloseParenthesis,
        [Token.COMMA] = Token.Comma,
        [Token.GREATER] = Token.Greater,
        [Token.LESS] = Token.Less
    };

    if (singleCharTokenFactory.TryGetValue(_currentChar, out var tokenFactory))
    {        
        Next();
        return tokenFactory(position);
    }
    throw new Exception($"Unexpected character {_currentChar}");
}

Nesse caso, inicio tentando identificar tokens com dois caracteres. Esse switch usa o _currentChare o método Peek para identificar operadores lógicos (&&, ||, ==, etc.).

Caso não existam operadores lógicos, o fluxo segue o mesmo, obtendo símbolos como (, ), +, etc.

Nesse momento, já conseguimos extrair os novos tokens.

Agora vem a parte mais “cabulosa”: SyntaxParser…

Pega um café…

Arquivo CodeAnalysis/SyntaxParser.cs

public class SyntaxParser(Dictionary<string, Identifier> identifiers, List<Token> tokens)
{
    // ...

    // public List<Identifier> Evaluate() ...

    private Identifier EvaluateExpression()
        => EvaluateLogicalOr();

    private Identifier EvaluateLogicalOr()
    {
        var left = EvaluateLogicalAnd();
        if (CurrentToken.Type != TokenType.Or) return left;
        var or = NextIfTokenIs(TokenType.Or);
        var right = EvaluateLogicalAnd();
        left = EvaluateLogicalOperation(left, right, or);
        return left;
    }

    private Identifier EvaluateLogicalAnd()
    {
        var left = EvaluateComparison();
        if (CurrentToken.Type != TokenType.And) return left;
        var and = NextIfTokenIs(TokenType.And);
        var right = EvaluateComparison();
        left = EvaluateLogicalOperation(left, right, and);
        return left;
    }

    private Identifier EvaluateComparison()
    {
        var left = EvaluatePlusOrMinus();
        if (!Token.IsMathOperatorType(CurrentToken.Type)) return left;
        var @operator = NextIfTokenIs(CurrentToken.Type);
        var right = EvaluatePlusOrMinus();
        left = EvaluateComparison(left, right, @operator);
        return left;
    }

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

    private Identifier EvaluateMultiplyOrDivide()
    {
        var left = EvaluateToken();
        while (CurrentToken.Type is TokenType.Multiply or TokenType.Divide)
        {
            var op = NextIfTokenIs(CurrentToken.Type);
            var right = EvaluateToken();
            left = EvaluateOperation(left, right, op);
        }

        return left;
    }

    // Métodos evaluates...

    private static Identifier EvaluateComparison(Identifier left, Identifier right, Token @operator)
    {
        const double epsilon = 1e-6;

        Identifier.EnsureSameTypes(left, right, @operator);

        var result = @operator.Type switch
        {
            TokenType.Equal => Equal(),
            TokenType.NotEqual => !Equal(),
            TokenType.Greater => Greater(),
            TokenType.GreaterOrEqual => Greater() || Equal(),
            TokenType.Less => Less(),
            TokenType.LessOrEqual => Less() || Equal(),
            _ => throw new Exception($"Unexpected comparison operator: {@operator.Type}")
        };

        return new Identifier(DataTypes.Bool, result);

        bool Equal()
            => (left.DataType, right.DataType) switch
            {
                (DataTypes.Double, _) or (_, DataTypes.Double) =>
                    Math.Abs(left.ToDouble() - right.ToDouble()) < epsilon,

                (DataTypes.Int, DataTypes.Int) =>
                    left.ToInt() == right.ToInt(),

                (DataTypes.Bool, DataTypes.Bool) =>
                    left.ToBool() == right.ToBool(),

                (DataTypes.String, DataTypes.String) =>
                    left.ToString() == right.ToString(),

                _ => ThrowException()
            };

        bool Greater()
            => (left.DataType, right.DataType) switch
            {
                (DataTypes.Double, _) or (_, DataTypes.Double) =>
                    left.ToDouble() > right.ToDouble(),

                (DataTypes.Int, DataTypes.Int) =>
                    left.ToInt() > right.ToInt(),

                _ => ThrowException()
            };

        bool Less()
            => (left.DataType, right.DataType) switch
            {
                (DataTypes.Double, _) or (_, DataTypes.Double) =>
                    left.ToDouble() < right.ToDouble(),

                (DataTypes.Int, DataTypes.Int) =>
                    left.ToInt() < right.ToInt(),

                _ => ThrowException()
            };

        bool ThrowException()
            => throw new Exception($"Cannot compare types: {left.DataType} and {right.DataType}");
    }

    private static Identifier EvaluateLogicalOperation(Identifier left, Identifier right, Token @operator)
    {
        if (left.DataType != DataTypes.Bool || right.DataType != DataTypes.Bool)
            throw new Exception($"Logical operator {@operator.Type} can only be applied to bool types");

        var result = @operator.Type switch
        {
            TokenType.And => left.ToBool() && right.ToBool(),
            TokenType.Or => left.ToBool() || right.ToBool(),
            _ => throw new Exception($"Unexpected logical operator: {@operator.Type}")
        };

        return new Identifier(DataTypes.Bool, result);
    }

    // private Token Peek() ...

    // private Token NextIfTokenIs(TokenType type) ...
}

Dessa vez, iniciamos o processo validando os operadores lógicos || e &&. E aqui temos uma coisa bem interessante que eu só consegui destravar lendo e relendo a sessão de operadores lógicos do glorioso livro Crafting Interpreters: avaliar ambos os lados da operação priorizando o operador &&.

Dessa forma, mantemos o fluxo parecido com a execução prioritária de operações como * e / além, claro, da prioridade máxima dos ().

E quando eu falar lados, me refiro ao que está à direita e à esquerda do operador. Por exemplo: 1 == 2. Nesse caso, temos o 1 sendo um Identifier numérico que vai ser chamado de left e o 2 que também é um Identifier numérico, mas que será tratado como right. Temos ainda expressões do tipo (1 == 2) || (2 < 4). Nesse caso, teremos o evaluatedo que está entre parênteses, onde temos uma expressão à esquerda e outra à direita. Por fim, o resultado é uma nova expressão, false || true. Esquerda e Direita, para os íntimos. E não, não me refiro à política…

E por qual motivo começamos com o ||? Simples! Pela ordem de prioridade:

EvaluateLogicalOr
└── EvaluateLogicalAnd
    └── EvaluateComparison
        └── EvaluatePlusOrMinus
            └── EvaluateMultiplyOrDivide
                └── EvaluateToken

Basicamente, temos um fluxo encadeado de Evaluates que, antes de ser executado, cada item do fluxo verifica a existência de um próximo fluxo mais prioritário.

Com isso, garantimos a execução evaluate da expressão, seguindo a ordem correta. Por fim, ao chegar no EvaluateToken, todo o processo, que já foi descrito e explicado exaustivamente nos posts anteriores, é efetuado normalmente, fazendo a execução baseada no tipo do token em questão.

Essas regrinhas são chatas demais e o que me ajudou muito foi quebrar cada parte num bloco de código. A reorganização feita no post anterior foi fundamental. Cada coisa está em seu devido lugar, e agora fica fácil visualizar o fluxo.

Aliás, que Odin abençoe o Github Copilot. Pedi a ele para “desenhar o fluxo de execução da expressão
1 == 2 || 4 == pow(2) e ele me retornou essa belezura aqui:

EvaluateLogicalOr
 ├─ EvaluateLogicalAnd (1 == 2)
 │    └─ EvaluateComparison → false
 └─ Como ainda existe um operador lógico, no caso o ||, avalia o lado direito:
     └─ EvaluateLogicalAnd (4 == pow(2))
          └─ EvaluateComparison
               ├─ EvaluateToken (4)
               └─ EvaluateFunction (pow(2)) → 4
               └─ Compara 4 == 4 → true

A primeira parte do processo gerou o seguinte resultado: false || true. E, como estamos em um fluxo recursivo, o processo continua:

EvaluateLogicalOr
 ├─ EvaluateLogicalAnd (false)
 │    └─ EvaluateComparison → false
 └─ Como ainda existe um operador lógico, no caso o ||, avalia o lado direito:
     └─ EvaluateLogicalAnd (true)
          └─ EvaluateComparison
               └─ EvaluateComparison → false
     └─ EvaluateLogicalOperation(left: false, rightt: right, operator: or)
          └─ true

Vocês não têm noção da minha felicidade ao descobrir que posso, de fato, visualizar o fluxo de execução. Depois que descobri isso, minha vida escrevendo esse compilador realmente mudou.

O Immo Landwerth quando criou o minsk fez algo parecido, onde ele imprimia a estrutura da árvore. Eu até pensei em fazer isso, mas por algum motivo passou batido.

Certo. Acredito que o fluxo de execução tenha ficado claro. Aliás, tem vezes em que acho que a pessoa que está lendo os posts, está com o código-fonte debugando, logo assumo que, com a explicação dada, ela consiga se encontrar nas entranhas dos códigos. E tem vezes em que acho que ninguém lê realmente os posts… Faz parte, segue o jogo.

Dentro desse fluxo, novos métodos de evaluateforam criados. Como o EvaluateLogicalOperation que valida se a operação é um || ou && e faz a comparação devida, retornando um Identifier do tipo Bool com o resultado executado.

Já o EvaluateComparison efetua comparação avaliando operadores como ==, !=, >, >=, <, <=. Aqui não tem segredo nenhum! Dado o identificador da esquerda e o da direita, são efetuadas as operações. É claro que o tipo de dado é considerado nesse caso, sendo assim, não é possível fazer algo como bool resultado = "Abacate" > 3.14.

Aliás, para facilitar a validação dos tipos de dados dos identificadores da esquerda e da direita, incluí na classe Identifier os seguintes métodos:

Arquivo Runtime/Identifier.cs

public static void EnsureSameTypes(Identifier left, Identifier right, Token @operator)  
{  
  if (AllAreNumberTypes(left.DataType, right.DataType))  
  return;  

  if (left.DataType != right.DataType)  
  throw new Exception(  
  $"Cannot apply {@operator.Type} operator to different types: {left.DataType} and {right.DataType}");  
}  

public static bool AllAreNumberTypes(params DataTypes[] types)  
  => types.All(type => type is DataTypes.Double or DataTypes.Int);

Basicamente, eu verifico se os tipos são iguais validando seu DataType. Isso ajuda a identificar operações que não podem ser feitas por tipos diferentes. Lembrando que temos casos como, por exemplo, string texto = 3 * "A"onde teremos o retorno AAA. Mas são exceções.

Outra coisa interessante é o fato de tratar como número, tipos de dados Int e Double. Assim, garanto operações matemáticas entre eles, priorizando o resultado como Double.

E para finalizar, os métodos EvaluateMultiplyOrDivide, EvaluatePlusOrMinus, EvaluateComparison, EvaluateLogicalAnd, EvaluateLogicalOr fazem parte do fluxo de execução explicado acima: verifica o operador em questão, obtém o identificador da esquerda e o da direita e invoca o evaluate correspondente, ou comparação, ou operação. Comparação, nada mais é do que ==, !=, >=, etc. e a operação se refere aos famigerados *, /, +, etc.

Agora podemos efetuar vários testes usando operadores lógicos:

> bool valor = 2 == 2 || 3 == 4
True
> bool valor = 1 == 2 && 3 == 4
False
> bool valor = (5 > 1) && (10 > 2)
True
> bool valor = (5 < 1) || (10 < 2)
False
> bool valor = (pow(2) == 4) && (1 < 2)
True
> bool valor = (pow(2) != 4) && (1 > 2)
False
> bool valor = (3 != 4) || (2 == 2)
True
> bool valor = (3 == 4) || (2 != 2)
False

Maravilha! Tudo nos conformes!

Deu trabalho, mas saiu. E ainda estamos no quarto post. Tem muita coisa legal para ser construída.

Espero que você, meu caro leitor, minha cara leitora, esteja curtindo essa série de posts.

Porém, antes de me despedir…

There's one more thing!

Como a cada post estamos evoluindo mais e mais o nosso compilador, é mais do que necessário que tenhamos formas de testar o resultado implementado. Hoje, existem mais de 200 testes unitários que ajudam a garantir que nada foi quebrado a cada linha de código adicionada.

Além disso, temos o nosso querido REPL que facilita a validação de expressões simples, como as que apresentamos acima.

Mas, de agora em diante, nós vamos precisar de algo mais robusto, já que temos a pretensão de escrever códigos como:

int idade = 30
if idade > 18 then
    print("Acesso liberado")
else
    print("Apenas maiores de 18 anos podem acessar..")
end

Usar o REPL é inviável, já que ele executa uma linha por vez. O ideal é que a gente teste utilizando um editor de código. E se for possível ter suporte à coloração e formatação, melhor ainda.

Sendo assim, inclui um novo projeto dentro da nossa solution chamado Pug.Compiler.Editor!

Isso mesmo! Agora temos um editor de código para nos ajudar.

Basicamente, temos um VS Code só para o nosso projeto. E isso é feito utilizando o Monaco Editor, mesmo motor usado pelo VS Code!

O mais maravilhoso é que ele é totalmente extensível, sendo assim, consegui configurá-lo para identificar as palavras reservadas da nossa linguagem.

Olha que coisa linda:

E enfim, encerramos o quarto post. Mais uma feature entregue. Aliás, duas. Operadores lógicos e o Editor.

O próximo post promete.

Código-fonte da parte 4: https://github.com/angelobelchior/Pug.Compiler/tree/parte4

Forte abraço!

Até a próxima!

Angelo Belchior @angelobelchior

Reinventando a Roda: Criando um compilador em csharp - Parte 4

Comments 4 total