Reinventando a Roda: Criando um Compilador em C# – Parte 2

Bem-vindos à Parte 2 da nossa jornada de criação de um compilador em C#! Na Parte 1, estabelecemos as bases, discutimos a arquitetura geral e começamos a implementar o analisador léxico (lexer). Nesta parte, vamos nos aprofundar no analisador sintático (parser), uma etapa crucial na transformação do código-fonte em uma representação intermediária que o compilador pode entender e processar.

Sumário

1. Recapitulando o Analisador Léxico (Lexer)
2. Introdução ao Analisador Sintático (Parser)
   • O Papel do Parser
   • Gramáticas e Linguagens Formais
   • Top-Down vs. Bottom-Up Parsing
3. Implementando um Parser Recursivo Descendente (Recursive Descent Parser)
   • O Conceito de Recursão
   • Definindo a Gramática da Nossa Linguagem
   • Implementando as Funções de Parsing
4. Tratamento de Erros
   • Tipos de Erros Sintáticos
   • Estratégias de Recuperação de Erros
   • Implementando o Tratamento de Erros no Nosso Parser
5. Construindo a Árvore Sintática Abstrata (AST)
   • O que é uma AST?
   • Benefícios de Usar uma AST
   • Construindo a AST Durante o Parsing
6. Exemplo Completo
   • Analisando um Código de Exemplo
   • Visualizando a AST Gerada
7. Próximos Passos
8. Conclusão

1. Recapitulando o Analisador Léxico (Lexer)

Antes de mergulharmos no parser, vamos relembrar rapidamente o que fizemos com o lexer. O analisador léxico é responsável por pegar o código-fonte bruto (uma sequência de caracteres) e dividi-lo em tokens. Cada token representa uma unidade significativa da linguagem, como palavras-chave, identificadores, operadores, literais, etc.

Na Parte 1, criamos uma classe Lexer em C# que percorria o código-fonte e identificava os diferentes tipos de tokens. Tivemos que lidar com coisas como ignorar espaços em branco, identificar números e strings, e lidar com operadores e palavras-chave. O resultado do lexer é uma lista de tokens que o parser usará como entrada.

Se você não se lembra dos detalhes ou não teve a oportunidade de ler a Parte 1, recomendamos que volte e revise o código do lexer para garantir que você está atualizado antes de prosseguir.

2. Introdução ao Analisador Sintático (Parser)

O analisador sintático, ou parser, é o próximo componente crucial em um compilador. Ele pega a sequência de tokens gerada pelo lexer e verifica se essa sequência está em conformidade com as regras gramaticais da linguagem.

2.1. O Papel do Parser

O parser tem várias responsabilidades importantes:

• Verificação da Sintaxe: Garante que o código siga as regras da linguagem, identificando erros de sintaxe como parênteses desbalanceados, ponto e vírgula ausentes, ou uso incorreto de operadores.
• Construção de uma Representação Intermediária: Transforma a sequência de tokens em uma estrutura de dados hierárquica que representa a estrutura do código-fonte. Essa estrutura é geralmente uma Árvore Sintática Abstrata (AST).
• Relato de Erros: Se o código não estiver sintaticamente correto, o parser deve fornecer mensagens de erro claras e informativas para ajudar o programador a corrigir o problema.

2.2. Gramáticas e Linguagens Formais

Para entender como um parser funciona, é essencial ter um conhecimento básico de gramáticas e linguagens formais. Uma gramática é um conjunto de regras que definem a estrutura sintática de uma linguagem. Essas regras especificam como os tokens podem ser combinados para formar construções maiores, como expressões, declarações e instruções.

Uma gramática é normalmente definida usando uma notação formal, como a Backus-Naur Form (BNF) ou suas variantes. Por exemplo, a seguinte regra BNF define como uma expressão pode ser formada:

    
      expressão ::= termo { "+" termo | "-" termo }
    
  

Essa regra significa que uma expressão consiste em um termo seguido por zero ou mais ocorrências de um operador de adição ou subtração (+ ou -) seguido por outro termo.

As gramáticas são fundamentais para o design de um compilador porque elas fornecem uma especificação precisa da sintaxe da linguagem. O parser usa a gramática como um guia para analisar o código-fonte e verificar se ele está sintaticamente correto.

2.3. Top-Down vs. Bottom-Up Parsing

Existem duas abordagens principais para construir um parser: top-down e bottom-up.

• Top-Down Parsing: Começa com o símbolo inicial da gramática (normalmente representando o programa inteiro) e tenta derivar a sequência de tokens de entrada aplicando as regras da gramática. Um exemplo comum de parser top-down é o Recursive Descent Parser, que usaremos neste tutorial.
• Bottom-Up Parsing: Começa com a sequência de tokens de entrada e tenta reduzir essa sequência ao símbolo inicial da gramática aplicando as regras da gramática na direção inversa. Exemplos de parsers bottom-up incluem LR parsers e SLR parsers.

Cada abordagem tem suas vantagens e desvantagens. Parsers top-down são geralmente mais fáceis de implementar e entender, mas podem ser menos eficientes e ter dificuldades com certas gramáticas. Parsers bottom-up são geralmente mais eficientes e podem lidar com uma gama maior de gramáticas, mas são mais complexos de implementar.

Neste tutorial, usaremos a abordagem top-down e implementaremos um Recursive Descent Parser devido à sua simplicidade e facilidade de compreensão.

3. Implementando um Parser Recursivo Descendente (Recursive Descent Parser)

Um Recursive Descent Parser é um tipo de parser top-down que usa um conjunto de funções recursivas para analisar o código-fonte. Cada função corresponde a uma regra gramatical, e a função tenta aplicar a regra consumindo os tokens de entrada.

3.1. O Conceito de Recursão

A recursão é uma técnica de programação onde uma função chama a si mesma. No contexto de um parser, a recursão é usada para lidar com regras gramaticais que são definidas em termos de si mesmas. Por exemplo, a regra para uma expressão pode incluir outras expressões, levando a uma chamada recursiva.

Para que a recursão funcione corretamente, é essencial ter uma condição de parada. A condição de parada é uma condição que faz com que a função pare de chamar a si mesma e retorne um valor. Sem uma condição de parada, a recursão continuaria indefinidamente, levando a um erro de estouro de pilha.

3.2. Definindo a Gramática da Nossa Linguagem

Antes de começarmos a implementar o parser, precisamos definir a gramática da nossa linguagem. Para simplificar, vamos começar com uma linguagem bem simples que suporta apenas expressões aritméticas com adição, subtração, multiplicação e divisão, bem como parênteses para controlar a precedência.

A gramática BNF para esta linguagem é a seguinte:

    
      expressão   ::= termo { "+" termo | "-" termo }
      termo       ::= fator { "*" fator | "/" fator }
      fator       ::= número | "(" expressão ")"
      número      ::= [0-9]+
    
  

Vamos explicar cada regra:

• expressão: Uma expressão é uma sequência de termos separados por operadores de adição ou subtração.
• termo: Um termo é uma sequência de fatores separados por operadores de multiplicação ou divisão.
• fator: Um fator pode ser um número ou uma expressão entre parênteses.
• número: Um número é uma sequência de um ou mais dígitos.

Essa gramática define a estrutura sintática da nossa linguagem. O parser usará essa gramática como um guia para analisar o código-fonte e construir a AST.

3.3. Implementando as Funções de Parsing

Agora que temos a gramática, podemos começar a implementar as funções de parsing. Para cada regra na gramática, criaremos uma função em C# que tenta analisar essa regra.

Aqui está o código C# para o nosso Recursive Descent Parser:

    
      using System;
      using System.Collections.Generic;

      public class Parser
      {
        private List<Token> tokens;
        private int currentTokenIndex = 0;

        public Parser(List<Token> tokens)
        {
          this.tokens = tokens;
        }

        private Token CurrentToken
        {
          get
          {
            if (currentTokenIndex < tokens.Count)
            {
              return tokens[currentTokenIndex];
            }
            return null; // Retorna null se chegarmos ao fim dos tokens
          }
        }

        private void Advance()
        {
          currentTokenIndex++;
        }

        private Token Consume(TokenType type)
        {
          if (CurrentToken != null && CurrentToken.Type == type)
          {
            Token token = CurrentToken;
            Advance();
            return token;
          }
          throw new Exception($"Esperado token do tipo {type}, mas encontrou {CurrentToken?.Type}");
        }

        // Função para analisar uma expressão
        public AstNode ParseExpression()
        {
          AstNode left = ParseTerm();

          while (CurrentToken != null && (CurrentToken.Type == TokenType.Plus || CurrentToken.Type == TokenType.Minus))
          {
            Token operatorToken = CurrentToken;
            Advance();
            AstNode right = ParseTerm();
            left = new BinaryOpNode(left, operatorToken, right);
          }

          return left;
        }

        // Função para analisar um termo
        private AstNode ParseTerm()
        {
          AstNode left = ParseFactor();

          while (CurrentToken != null && (CurrentToken.Type == TokenType.Multiply || CurrentToken.Type == TokenType.Divide))
          {
            Token operatorToken = CurrentToken;
            Advance();
            AstNode right = ParseFactor();
            left = new BinaryOpNode(left, operatorToken, right);
          }

          return left;
        }

        // Função para analisar um fator
        private AstNode ParseFactor()
        {
          if (CurrentToken != null && CurrentToken.Type == TokenType.Number)
          {
            Token numberToken = Consume(TokenType.Number);
            return new NumberNode(numberToken);
          }
          else if (CurrentToken != null && CurrentToken.Type == TokenType.LeftParen)
          {
            Consume(TokenType.LeftParen);
            AstNode expression = ParseExpression();
            Consume(TokenType.RightParen);
            return expression;
          }
          throw new Exception("Esperado número ou parêntese esquerdo");
        }
      }

      // Definições dos tipos de tokens (já definidos no Lexer)
      public enum TokenType
      {
          Number,
          Plus,
          Minus,
          Multiply,
          Divide,
          LeftParen,
          RightParen,
          EOF // End Of File
      }

      // Classe para representar um token
      public class Token
      {
          public TokenType Type { get; set; }
          public string Value { get; set; }

          public Token(TokenType type, string value)
          {
              Type = type;
              Value = value;
          }

          public override string ToString()
          {
              return $"Type: {Type}, Value: {Value}";
          }
      }

      // Classes para representar a AST
      public abstract class AstNode { }

      public class NumberNode : AstNode
      {
          public Token Token { get; set; }

          public NumberNode(Token token)
          {
              Token = token;
          }
      }

      public class BinaryOpNode : AstNode
      {
          public AstNode Left { get; set; }
          public Token Operator { get; set; }
          public AstNode Right { get; set; }

          public BinaryOpNode(AstNode left, Token op, AstNode right)
          {
              Left = left;
              Operator = op;
              Right = right;
          }
      }
    
  

Vamos explicar o código:

• Parser Class: A classe principal do parser. Ela recebe uma lista de tokens como entrada e fornece um método ParseExpression para analisar a expressão.
• CurrentToken Property: Uma propriedade que retorna o token atual na lista de tokens.
• Advance Method: Um método que avança para o próximo token na lista de tokens.
• Consume Method: Um método que verifica se o token atual é do tipo esperado e avança para o próximo token. Se o token não for do tipo esperado, ele lança uma exceção.
• ParseExpression, ParseTerm, ParseFactor Methods: As funções de parsing que correspondem às regras gramaticais. Cada função tenta analisar a regra consumindo os tokens de entrada e construindo a AST correspondente.
• AstNode, NumberNode, BinaryOpNode Classes: Classes que representam os nós da Árvore Sintática Abstrata (AST). NumberNode representa um número, e BinaryOpNode representa uma operação binária (como adição, subtração, multiplicação ou divisão).

Note que o código acima assume que você já tem uma classe Token e um enum TokenType definidos, como fizemos na Parte 1 do tutorial.

4. Tratamento de Erros

O tratamento de erros é uma parte essencial de qualquer compilador. Um parser deve ser capaz de detectar erros de sintaxe e fornecer mensagens de erro claras e informativas para ajudar o programador a corrigir o problema.

4.1. Tipos de Erros Sintáticos

Existem vários tipos de erros sintáticos que podem ocorrer em um programa:

• Token Inesperado: O parser encontra um token que não espera em determinada posição. Por exemplo, encontrar um operador no início de uma expressão.
• Token Ausente: O parser espera um token específico, mas ele não está presente. Por exemplo, um parêntese de fechamento ausente.
• Expressão Mal Formada: A estrutura da expressão não está de acordo com as regras gramaticais. Por exemplo, dois operadores seguidos sem um operando no meio.

4.2. Estratégias de Recuperação de Erros

Quando um erro de sintaxe é detectado, o parser pode adotar diferentes estratégias para lidar com o erro:

• Pânico Mode: O parser descarta tokens até encontrar um token de sincronização (como um ponto e vírgula ou uma chave de fechamento) e então tenta continuar a análise.
• Error Productions: A gramática é estendida com regras que tratam de erros comuns. Quando um erro é encontrado, a regra correspondente é aplicada para tentar recuperar a análise.
• Global Correction: O parser tenta encontrar a menor modificação no código-fonte que o tornaria sintaticamente correto. Essa abordagem é geralmente muito complexa e não é usada em compiladores práticos.

Para este tutorial, implementaremos uma forma simplificada de “Pânico Mode”. Quando um erro é encontrado, lançaremos uma exceção, indicando o erro. Para uma implementação mais robusta, poderíamos adicionar lógica para tentar sincronizar com um token de sincronização e continuar a análise.

4.3. Implementando o Tratamento de Erros no Nosso Parser

No nosso código do parser, já estamos lançando exceções quando encontramos erros de sintaxe no método Consume e no método ParseFactor. Essas exceções indicam que um token inesperado foi encontrado ou que um token esperado está ausente.

Para melhorar o tratamento de erros, podemos adicionar mais verificações e lançar exceções mais específicas. Por exemplo, podemos verificar se a lista de tokens está vazia antes de acessar o token atual.

Aqui está um exemplo de como podemos adicionar mais tratamento de erros ao método ParseExpression:

    
      public AstNode ParseExpression()
      {
        if (tokens == null || tokens.Count == 0)
        {
          throw new Exception("Lista de tokens vazia");
        }

        AstNode left = ParseTerm();

        while (CurrentToken != null && (CurrentToken.Type == TokenType.Plus || CurrentToken.Type == TokenType.Minus))
        {
          Token operatorToken = CurrentToken;
          Advance();

          // Adicionado verificação para garantir que há um termo após o operador
          if (CurrentToken == null)
          {
            throw new Exception("Esperado termo após o operador");
          }

          AstNode right = ParseTerm();
          left = new BinaryOpNode(left, operatorToken, right);
        }

        return left;
      }
    
  

Essa verificação adicional garante que, se um operador de adição ou subtração for encontrado, haverá um termo após o operador. Se não houver um termo, uma exceção será lançada.

Lembre-se, este é um tratamento de erros básico. Em um compilador completo, você implementaria estratégias mais robustas para recuperação de erros, como o “Pânico Mode” mencionado acima.

5. Construindo a Árvore Sintática Abstrata (AST)

A Árvore Sintática Abstrata (AST) é uma representação hierárquica do código-fonte que captura a estrutura essencial do programa, omitindo detalhes irrelevantes para o processo de compilação. É a principal saída do parser e a entrada para as fases subsequentes do compilador, como a análise semântica e a geração de código.

5.1. O que é uma AST?

Uma AST é uma árvore onde cada nó representa uma construção sintática no código-fonte. Por exemplo, um nó pode representar uma expressão, uma declaração, uma instrução ou um operador. As relações entre os nós refletem a estrutura hierárquica do código-fonte.

Ao contrário da Árvore Sintática Concreta (CST), também conhecida como parse tree, a AST não inclui tokens como parênteses e pontos e vírgulas, que são importantes para o parser, mas não são relevantes para as fases subsequentes do compilador.

5.2. Benefícios de Usar uma AST

Usar uma AST oferece vários benefícios:

• Representação Clara e Concisa: A AST fornece uma representação clara e concisa da estrutura do código-fonte, facilitando a análise e a manipulação do código.
• Independência da Sintaxe: A AST é independente da sintaxe específica da linguagem, o que significa que pode ser usada para representar código em diferentes linguagens.
• Facilita a Otimização: A AST facilita a aplicação de otimizações no código, como a eliminação de código morto e a expansão de funções inline.
• Base para Geração de Código: A AST é a base para a geração de código. O gerador de código percorre a AST e gera o código de máquina correspondente.

5.3. Construindo a AST Durante o Parsing

No nosso Recursive Descent Parser, já estamos construindo a AST durante o processo de parsing. As funções ParseExpression, ParseTerm e ParseFactor criam nós da AST (NumberNode e BinaryOpNode) e os conectam para formar a árvore.

O código a seguir ilustra como a AST é construída no método ParseExpression:

    
      public AstNode ParseExpression()
      {
        AstNode left = ParseTerm();

        while (CurrentToken != null && (CurrentToken.Type == TokenType.Plus || CurrentToken.Type == TokenType.Minus))
        {
          Token operatorToken = CurrentToken;
          Advance();
          AstNode right = ParseTerm();
          left = new BinaryOpNode(left, operatorToken, right); // Cria um novo nó BinaryOpNode
        }

        return left;
      }
    
  

Nesse código, quando um operador de adição ou subtração é encontrado, um novo nó BinaryOpNode é criado. O nó esquerdo da operação é a AST construída até aquele ponto (left), o operador é o token atual (operatorToken), e o nó direito é a AST resultante da chamada recursiva a ParseTerm.

A construção da AST durante o parsing é uma abordagem comum e eficiente. Ela permite que o compilador processe o código-fonte em uma única passagem, sem a necessidade de criar uma árvore intermediária (como a CST) e depois transformá-la na AST.

6. Exemplo Completo

Para consolidar o que aprendemos, vamos analisar um código de exemplo completo e ver como o parser funciona e como a AST é gerada.

6.1. Analisando um Código de Exemplo

Considere o seguinte código-fonte:

    
      (1 + 2) * 3
    
  

O lexer converteria esse código em uma lista de tokens:

    
      [
        Token(LeftParen, "("),
        Token(Number, "1"),
        Token(Plus, "+"),
        Token(Number, "2"),
        Token(RightParen, ")"),
        Token(Multiply, "*"),
        Token(Number, "3")
      ]
    
  

O parser, então, processaria esses tokens da seguinte forma:

1. ParseExpression é chamado: Começa a analisar a expressão.
2. ParseTerm é chamado: Começa a analisar o termo.
3. ParseFactor é chamado: Encontra um parêntese esquerdo.
4. Consume(LeftParen) é chamado: Consome o parêntese esquerdo.
5. ParseExpression é chamado recursivamente: Analisa a expressão dentro dos parênteses (1 + 2).
6. ParseTerm é chamado: Encontra o número 1.
7. ParseFactor é chamado: Encontra o número 1.
8. Consume(Number) é chamado: Consome o número 1.
9. Cria um NumberNode para o número 1.
10. Retorna o NumberNode.
11. Encontra o operador +.
12. Consume(Plus) é chamado: Consome o operador +.
13. ParseTerm é chamado: Encontra o número 2.
14. ParseFactor é chamado: Encontra o número 2.
15. Consume(Number) é chamado: Consome o número 2.
16. Cria um NumberNode para o número 2.
17. Retorna o NumberNode.
18. Cria um BinaryOpNode com o nó esquerdo representando o número 1, o operador + e o nó direito representando o número 2.
19. Retorna o BinaryOpNode.
20. Consume(RightParen) é chamado: Consome o parêntese direito.
21. Retorna a AST da expressão dentro dos parênteses.
22. Encontra o operador *.
23. Consume(Multiply) é chamado: Consome o operador *.
24. ParseTerm é chamado: Encontra o número 3.
25. ParseFactor é chamado: Encontra o número 3.
26. Consume(Number) é chamado: Consome o número 3.
27. Cria um NumberNode para o número 3.
28. Retorna o NumberNode.
29. Cria um BinaryOpNode com o nó esquerdo representando a AST da expressão (1 + 2), o operador * e o nó direito representando o número 3.
30. Retorna o BinaryOpNode.

6.2. Visualizando a AST Gerada

A AST gerada para o código-fonte (1 + 2) * 3 pode ser visualizada da seguinte forma:

    
               *
              / \
             /   \
            +     3
           / \
          1   2
    
  

Essa árvore representa a estrutura do código-fonte. O nó raiz é o operador de multiplicação *. O nó esquerdo é a subárvore que representa a expressão (1 + 2), e o nó direito é o número 3.

Essa AST pode então ser usada pelas fases subsequentes do compilador para realizar análise semântica, otimização e geração de código.

7. Próximos Passos

Com o parser implementado e a AST construída, estamos um passo mais perto de ter um compilador funcional. Os próximos passos incluem:

• Análise Semântica: Verificar se o código-fonte é semanticamente correto. Isso inclui verificar se as variáveis são declaradas antes de serem usadas, se os tipos de dados são compatíveis e se as funções são chamadas com o número correto de argumentos.
• Geração de Código: Traduzir a AST em código de máquina ou em uma linguagem intermediária, como assembly.
• Otimização: Aplicar otimizações no código para melhorar seu desempenho. Isso pode incluir a eliminação de código morto, a expansão de funções inline e a otimização de loops.
• Tratamento de Erros Avançado: Implementar estratégias mais robustas para tratamento de erros, como recuperação de erros e mensagens de erro mais informativas.

Continuaremos explorando esses tópicos nas próximas partes deste tutorial.

8. Conclusão

Nesta Parte 2 do nosso tutorial, aprendemos sobre o analisador sintático (parser) e como implementá-lo em C#. Vimos como o parser usa uma gramática para verificar a sintaxe do código-fonte e como ele constrói uma Árvore Sintática Abstrata (AST) para representar a estrutura do código.

Implementamos um Recursive Descent Parser simples para uma linguagem de expressões aritméticas e discutimos estratégias para tratamento de erros. Também analisamos um exemplo completo para ilustrar como o parser funciona e como a AST é gerada.

Espero que este tutorial tenha sido útil e informativo. Na próxima parte, exploraremos a análise semântica e a geração de código. Fique ligado!