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

Voltamos!

E dessa vez prometo que o post vai ser mais simples e direto.
Era impossível fazer isso na parte 1 da série Criando um compilador em csharp já que era importante apresentar motivações e introduzir conceitos.

Fora que o objetivo do primeiro post era resolver expressões matemáticas. Mas para construirmos isso, precisávamos implementar um analisador léxico e um analisador sintático. Foi o que fizemos: Lexer e Parser.

E para avançar, assumo que você leu e entendeu a implementação desses dois conceitos, pois a partir de agora vamos apenas adicionar features nessas implementações.

Dito isso, podemos e devemos ser mais objetivos!

Pega aquele café e vem comigo!

Adicionando métodos internos à nossa linguagem.

Como citei acima, hoje temos um "resolvedor" de expressões matemáticas, porém a ideia agora é adicionar algumas funções internas como calcular raiz quadrada, potência, obter o maior ou o menor valor dentre dois números, além de poder arredondar um número a uma determinada quantidade de casas. E for fun, adicionei um método para retornar um valor aleatório.

Basicamente temos que interpretar expressões do tipo funcao(param1, param2) ou ainda funcao().

É o que faremos.

Para isso, precisamos mapear dois novos tokens: Function e Comma.

Vamos começar adicionando esses dois novos tokens ao nosso enum TokenType:

Arquivo CodeAnalysis/TokenType.cs

namespace Pug.Compiler.CodeAnalysis;

public enum TokenType
{
    ...

    Function,
    Comma
}

Em seguida vamos até o record Token e incluir métodos auxiliares para a criação dos novos mapeamentos:

Arquivo CodeAnalysis/Token.cs

namespace Pug.Compiler.CodeAnalysis;

public record Token(TokenType Type, string Value, int Position)
{

    ...

    public static Token Function(int position, string value) 
    => new(TokenType.Function, value, position);

    public static Token Comma(int position) 
    => new(TokenType.Comma, ",", position);

}

Certo. Já temos como mapeá-los.

O processo é bem parecido com o que já existe. Na classe Lexer precisamos identificar a vírgula e a função. A função nada mais é do que um conjunto de caracteres onde não são aceitos espaços ou números. Basicamente uma função só pode conter letras. Essa foi a regra que defini.

Para isso, vamos ter que criar um método para extrair a função, assim como fizemos para extrair números e invocá-lo na ordem apropriada no método CreateTokens.

Arquivo CodeAnalysis/Lexer.cs

public List<Token> CreateTokens()
{
    var tokens = new List<Token>();

    while (_currentChar != EOF)
    {
        if (char.IsWhiteSpace(_currentChar))
        {
            IgnoreWhitespace();
            continue;
        }

        if (char.IsLetter(_currentChar))
        {
            tokens.Add(ExtractFunction());
            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),
            ',' => Token.Comma(_currentPosition),
            _ => throw new Exception($"Unexpected character: {_currentChar}")
        };
        tokens.Add(token);

        Next();
    }

    tokens.Add(new Token(TokenType.EOF, string.Empty, _currentPosition));
    return tokens;
}

Podemos notar no método CreateTokens que logo após o processo para ignorar espaços em branco começamos a procurar tokens que podem ser considerados uma função: if (char.IsLetter(_currentChar)).

Mais abaixo temos o mapeamento da vírgula: ',' => Token.Comma(_currentPosition). Ele é feito logo após o mapeamento e criação do Token.CloseParenthesis.

Para extrair a função temos o método:

private Token ExtractFunction()
{
    var result = new StringBuilder();
    while (char.IsLetter(_currentChar))
    {
        result.Append(_currentChar);
        Next();
    }
    var value = result.ToString();
    return Token.Function(_currentPosition, value);
}

É bem tranquilo… Vou avançando entre os caracteres até que encontre um que não seja uma letra.

O segredo do processo para mapear e extrair funções está justamente no momento que a gente faz essa extração. Começo removendo caracteres que são ignoráveis (no nosso caso temos somente o espaço), depois extraio tokens cujo valor são conjuntos de caracteres, no nosso caso temos o nome de função e seus argumentos, além de valores numéricos (que podem ou não conter o sinal de +, ou de -, além de .), e por fim, caracteres "soltos" como (, ), +, -, etc.

Essa ordem é fundamental.

Habemus Papam e Habemus novos tokens.

Bora fazer a análise sintática.

---

Primeiro começo dizendo que fiz uma mudança em um método.

O CheckToken virou NextIfTokenIs. Para mim, faz muito mais sentido agora — e espero que para você também — afinal, é isso que ele faz: avança ao próximo token caso ele seja do tipo especificado.

Dito isto, vamos à implementação. Basicamente, mudamos o método EvaluateToken incluindo o processamento dos novos tokens e criamos uma nova função chamada InvokeMethod. Vamos ver na prática:

Arquivo CodeAnalysis/SyntaxParser

private double EvaluateToken()
{
    var token = CurrentToken;

    if (token.Type == TokenType.Function)
    {
        NextIfTokenIs(TokenType.Function);
        NextIfTokenIs(TokenType.OpenParenthesis);

        var args = new List<double>();

        if (CurrentToken.Type != TokenType.CloseParenthesis)
        {
            args.Add(Parse());

            while (CurrentToken.Type == TokenType.Comma)
            {
                NextIfTokenIs(TokenType.Comma);
                args.Add(Parse());
            }
        }

        NextIfTokenIs(TokenType.CloseParenthesis);

        return InvokeMethod(token, args);
    }

    if (token.Type == TokenType.Plus)
    {
        NextIfTokenIs(TokenType.Plus);
        return EvaluateToken();
    }

    if (token.Type == TokenType.Minus)
    {
        NextIfTokenIs(TokenType.Minus);
        return -EvaluateToken();
    }

    if (token.Type == TokenType.Number)
    {
        NextIfTokenIs(TokenType.Number);
        return double.Parse(token.Value, System.Globalization.CultureInfo.InvariantCulture);
    }

    if (token.Type == TokenType.OpenParenthesis)
    {
        NextIfTokenIs(TokenType.OpenParenthesis);
        var result = Parse();
        NextIfTokenIs(TokenType.CloseParenthesis);
        return result;
    }

    throw new Exception($"Unexpected token in Evaluate Token: {token.Type}");
}

Ao iniciar o processo de Evaluate dos tokens, começamos procurando por um token do tipo Function e caso encontre, começamos a validar a estrutura da função. Avançamos (NextIfTokenIs(TokenType.Function)), e na sequência vamos ao encontro da abertura dos parênteses (NextIfTokenIs(TokenType.OpenParenthesis)).

O próximo passo é preparar uma lista para armazenar os valores dos argumentos caso existam (por enquanto, só aceito argumentos numéricos. Num futuro, isso vai mudar).

Para saber se existem ou não argumentos, verificamos se o token atual é um "Fecha Parênteses" (TokenType.CloseParenthesis). Se sim, a função não recebe nenhum valor como parâmetro. Caso contrário, fazemos o processo de validar argumentos separados por vírgula.

Espero que você tenha entendido bem a ideia do looping que acontece aqui e da recursividade. Isso foi explicado no post anterior, mas pense sempre que temos um cursor sendo executado, varrendo todos os tokens sempre para a frente. Sendo assim, quando falo token atual, eu me refiro ao token no qual o cursor está apontando no momento.

Os argumentos de uma função são processados recursivamente pelo método Parse e seu resultado é armazenado na lista de argumentos args.Add(Parse()). Esse método Parse resolve operações, dessa forma podemos ter algo como round(sqrt(max(4, random(5, 9876))))!

Em seguida, em forma de lopping, eu valido se tem outros argumentos separados por vírgula NextIfTokenIs(TokenType.Comma). Se sim, o processo é o mesmo: efetuo o parse e jogo o valor na lista.

Por fim, valido o fechamento dos parênteses NextIfTokenIs(TokenType.CloseParenthesis) e chamo a função InvokeMethod responsável por invocar o método mapeado no token passando a lista de argumentos.
Essa invocação nada mais é do que um "atalho" para um método existente do csharp. É assim que a gente faz o nosso evaluate:

private static double InvokeMethod(Token token, List<double> args)
=> token.Value.ToLower() switch
{
    "sqrt" => args.Count == 1
        ? Math.Sqrt(args[0])
        : throw new Exception("Invalid number of arguments for sqrt"),

    "pow" => args.Count switch
    {
        1 => Math.Pow(args[0], 2),
        2 => Math.Pow(args[0], args[1]),
        _ => throw new Exception("Invalid number of arguments for round")
    },

    "min" => args.Count == 2
        ? Math.Min(args[0], args[1])
        : throw new Exception("Invalid number of arguments for min"),

    "max" => args.Count == 2
        ? Math.Max(args[0], args[1])
        : throw new Exception("Invalid number of arguments for max"),

    "round" => args.Count switch
    {
        1 => Math.Round(args[0]),
        2 => Math.Round(args[0], Convert.ToInt32(args[1])),
        _ => throw new Exception("Invalid number of arguments for round")
    },

    "random" => args.Count switch
    {
        0 => Random.Shared.NextDouble(),
        1 => Random.Shared.Next(Convert.ToInt32(args[0])),
        2 => Random.Shared.Next(Convert.ToInt32(args[0]), Convert.ToInt32(args[1])),
        _ => throw new Exception("Invalid number of arguments for random")
    },

    _ => throw new Exception($"Unknown function: {token.Value}")
};

Acredito que o método seja bem simples de se entender. Eu pego o valor do token Function — que no caso é o nome da função — e testo para ver se ele é alguma das funções mapeadas da linguagem. No nosso caso, temos sqrt, pow, min, max, round e random.

Uma coisa interessante é que a quantidade de parâmetros também é validada. Podemos ter funções cujos parâmetros não são obrigatórios, como a round ou a pow.
No caso da pow, se o usuário omitir o segundo argumento, eu assumo ser 2. No csharp sou obrigado a informar dois parâmetros.

Além disso, validamos se a quantidade de parâmetros passada corresponde com a quantidade aceita pelo método.

O Pattern Matching do csharp é coisa linda. Deixa o código bem mais legível.

E, no fim, caso o nome da função não esteja mapeado, ocorre uma exceção.

Pronto! Podemos executar nossas funções juntamente com outras operações matemáticas. Ou chamar uma função dentro de uma função. Da para passar horas testando e o melhor é que você já sabe o caminho para adicionar mais funções, não é mesmo?

Então, bora testar!

Se tudo der certo e nada der errado, podemos executar as seguintes operações:

> sqrt(4)
2
> min(1, 2)
1
> max(8, 0)
8
> pow(3)
9
> pow(2, 3)
8
> round(1.234)
1
> round(1.234, 2)
1,23
> round(1.234, 1)
1,2
> random()
0,5424186829640589
> random(1, 10)
7
> sqrt(4) + min(2, -3)
-1
> 1 + pow(5, sqrt(4))
26
> ihuuuu(pow(2,4))
Unknown identifier: ihuuuu

E aí, curtiu?

Depois que entendemos e criamos o lexer e o parser, evoluí-los é algo bem mais tranquilo.

Segunda feature do nosso incrível compilador pug entregue.
Para ver o código-fonte, acesse https://github.com/angelobelchior/Pug.Compiler/tree/parte2.

Agora é só aguardar a terceira parte!

Forte abraço e te vejo no próximo post!