Construindo seu próprio compilador - Parte 1

Os compiladores são ferramentas muito úteis e importantes no mundo da programação e desenvolvimento. A função básica dos compiladores é pegar uma linguagem de "alto nível" (linguagem com maior nível de abstração do hardware) e produzir um código semanticamente equivalente em "baixo nível". A velocidade de execução do código compilado é uma vantagem que se destaca, tendo em vista que o compilador faz otimizações no processo de compilação. Verificações de erros sintáticos e semânticos são outras funcionalidades também executadas pelo compilador.

Por que criar um compilador?

Além dos motivos mencionados anteriormente, a forma mais simples e rápida de entender como os compiladores funcionam é criando um. Neste tutorial iremos criar um compilador simples, porém abordando os principais conceitos da compilação de forma teórica e prática.
Para seguir esse tutorial será necessário o conhecimento de algoritmo e no mínimo uma linguagem de programação. Neste artigo estarei utilizando a linguagem C.

Antes de começarmos a criação do projeto, vamos organizar o nosso projeto:

• Criaremos uma linguagem que trabalha com números inteiros e reais;
• Utilizaremos condições (if, else, etc);
• Utilizaremos expressões aritméticas e relacionais;

Etapas da compilação

As etapas que um compilador executa são: Análise léxica, Análise sintática, análise semântica, otimizador de código e gerador de código objeto. Alguns compiladores tem uma estrutura bem mais complexa, dependendo da linguagem a ser compilada:

Nosso projeto terá as seguintes etapas: análise léxica, análise sintática, análise semântica e gerador de código. O gerador de código vai gerar um bytecode para uma máquina virtual que também vamos implementar. Bytecodes são instruções para uma máquina virtual, como mover um valor para a memória ou para um registrador, por exemplo. Abaixo podemos ver um trecho de código em Python e seus respectivos bytecodes:

def soma():
    print(10 + 10)

0 LOAD_GLOBAL      0 (print)
    2 LOAD_CONST      1 (20)
    4 CALL_FUNCTION  1
    6 POP_TOP
    8 LOAD_CONST      0 (None)
    10 RETURN_VALUE

No final desta série estaremos executando o seguinte código:

INIT
 
VAR max := 10
VAR num
 
INPUT num
 
IF (num < max)
    INIT
        PRINT 0
    END
 
ELSE
    INIT
        PRINT 1
    END
 
END

Análise Léxica

A análise léxica consiste em pegar cada caractere de uma linguagem e identificar os padrões da linguagem. Exemplo:

int a = 10

Aqui podemos identificar os seguintes padrões:

• int é uma palavra reservada do compilador;
• a é um identificador/variável;
• = é um sinal de atribuição;
• 10 é um número inteiro;

Ao realizar esse processo estamos identificando os lexemas, que são pedaços de uma string (texto), reconhecidos pelo analisador léxico. Os tokens são um par constituído de um nome e um valor de atributo, sendo este último opcional:

<tipo, valor>

Onde:

• tipo como o nome já diz seria o tipo do token.
• valor é o valor de um token. Alguns tokens não utilizam este campo.

Representação da análise léxica:

Para uma entrada como VAR num := 100 + 10 obtemos os seguintes tokens:

<PC_VAR> <ID, num> <OP_ATR> <T_INT, 100> <OP_MAIS> <T_INT, 10>

Onde:

• <PC_VAR> representa a palavra chave VAR;
• <ID, num> representa um identificador (variável ou função) tendo o valor num;
• <OP_ART> representa o operador de atribuição =;
• <OP_MAIS> representa o operador aritmético mais (+);
• <T_INT, 100>, <T_INT, 10> representa um inteiro com o valor 100 e 10 respectivamente;

Não se esqueça que os tipos de token são definidos por você!

Usarei o gcc como compilador C e o vscode como editor. Iremos começar de uma forma simples,  melhorando tudo aos poucos, vamos nessa!

Essa é a estrutura de pastas do nosso projeto. Temos uma pasta para os headers, uma pasta src para o código fonte e a pasta exe, que terá o executável:

Escreva o texto seguinte no arquivo teste.txt:

INIT
PRINT 1 + 2 * 3
END

include/lex.h - Aqui simplesmente criamos um módulo para tratar da análise léxica e definimos a função que retorna um token:

#ifndef art_lex_h
#define art_lex_h
 
void proximo_token();
 
#endif

src/lex.c: Esta é nossa função inicial que lê cada caractere e mostra na console. Se o caractere for EOF, significa que não há mais caracteres no arquivo (fim de arquivo) e então paramos o loop:

#include <string.h>
#include <ctype.h>
 
#include "glob.h"
#include "lex.h"
 
// variável que passará por cada caractere do arquivo
static int c; 
 
void proximo_token()
{
    while (1)
    {
        c = fgetc(file);
 
        if (c == EOF)
            break;
 
        else
            printf("%c", c);
    }
}

includes/glob.h: Este outro arquivo serve para algumas definições globais (que vamos usar em mais de um arquivo). Definimos os tipos dos tokens, um enum para representar o token e uma struct com os campos tipo e val:

#ifndef art_glob_h
#define art_glob_h

#include <stdio.h>
#include <stdlib.h>

FILE *file;

// linha atual
static int linha = 1;

// tipos de tokens 
enum {
    // palavras chave
    PC_INIT, PC_END, PC_PRINT, PC_INPUT, PC_VAR, PC_IF, PC_ELSE, 

    // numeros
    T_INT,

    // operadores
    OP_MAIS, OP_MENOS, OP_MULT, OP_DIVI,

    // ( ) := < > <= >=  =
    T_LPARENT, T_RPARENT, T_ATRIB, T_MENOR, T_MAIOR, T_MENOR_I, 
    T_MAIOR_I, T_IGUAL,

    // identificador
    ID
};

typedef struct {
    int tipo;
    int val;
} Token;

Token tok;

#endif

src/main.c: Na função main iremos tentar abrir um arquivo. Caso haja algum erro o programa sairá mostrando a mensagem de erro. Caso contrário, leremos todos os caracteres do arquivo teste.txt. Vamos ver se funciona:

#include <stdlib.h>
 
#include "lex.h"
#include "glob.h"
 
int main(int argc, char *argv[])
{
    // abrir o arquivo
    file = fopen(argv[1], "r");
 
 
    if (file == NULL)
    {
        printf("Erro ao abrir o arquivo");
        exit(EXIT_FAILURE);
    }
 
    proximo_token();
 
    fclose(file);
    return EXIT_SUCCESS; // ou return 0
}

Para facilitar o processo de compilação usaremos o seguinte Makefile:

all:
    gcc -c src/lex.c -I includes -o exe/lex.o
 
    gcc src/main.c exe/*.o -I includes  -o exe/main
    rm -r exe/*.o

*Se você estiver em um ambiente Windows saiba que o comando rm -r exe/*.o  não funcionará.

Ao executar o Makefile teremos na pasta exe o arquivo compilado. Ao executarmos teremos a seguinte saída:

INIT
PRINT 1 + 2 * 3
END

Perfeito! Por agora vamos ignorar espaços em branco, tabulação e quebra de linha.

Criaremos agora uma função que vai criar um token. Por enquanto ela irá apenas mostrar na saída algo como <’+’, 0> <’INIT’, 0>, mas depois vamos mudar isso.

lex.c: Aqui estamos somando 1 na variável linha para uso posterior em caso de nosso compilador ache um caractere que não existe em nossa linguagem (como um “$”, por exemplo):

void makeToken(char *nome, int val) // mostrar o token
{
    printf("<%s, %d>", nome, val);
}
 
void voltaPonteiro() // volta um caracter se necessário
{
    if (c != EOF)
        fseek(file, ftell(file)-1, SEEK_SET);
}
 
void proximo_token()
{
      // após o if
        else if (c == ' ' || c == '\t')
            continue;
 
        else if (c == '\n')
        {
            linha++;
            continue;
        }
}

No código acima temos uma função voltaPonteiro, que é responsável por voltar um caractere no arquivo. Em alguns casos vamos ter que ver o caractere a frente e depois voltar o caractere quando estivermos analisando uma palavra chave. Enquanto o caractere for alfanumérico o ponteiro avança.

Para facilitar o entendimento vamos utilizar a imagem abaixo como exemplo. Aqui reconhecemos a palavra num e paramos no caractere =, ou seja, reconhecemos o token <ID, num>. Quando vamos continuar o processo iniciamos do =, isto é, o próximo caractere é o espaço, seguido do número 1 e assim por diante. Tendo em vista que = é um caractere diferente do que estaríamos esperando iremos esquece-lo e então voltaremos um caractere parando assim no m.

lex.c: vamos reconhecer operadores aritméticos como mais (+), menos (-), multiplicação (*) e divisão (/):

void proximo_token()
{      
      // codigo anterior
      else if (c == '+')
            makeToken("+", 0);
 
        else if (c == '-')
            makeToken("-", 0);
 
        else if (c == '*')
            makeToken("*", 0);
 
        else if (c == '/')
            makeToken("/", 0);
 
      // codigo else

Ao compilar o código e executar teremos algo como:

$ ./exe/main.exe teste.txt
INITPRINT1<+, 0>2<*, 0>3END

lex.c: Agora vamos reconhecer os demais números, palavras, parênteses, etc:

else if (c == '+') {
            makeToken("+", 0);
        }
 
        else if (c == '-') {
            makeToken("-", 0);
        }
 
        else if (c == '*'){
            makeToken("*", 0);
        }
 
        else if (c == '/') {
            makeToken("/", 0);
        }
 
        else if (c == '(') {
            makeToken("(", 0);
        }
 
        else if (c == ')') {
            makeToken(")", 0);
        }
 
        else if (c == ':')
        {
            c = fgetc(file); // pega o próximo caractere
 
            if (c == '=') // se for '=' sabemos que é o token ':='
                makeToken(":=", 0);
        }
 
        else if (c == '<')
        {
            c = fgetc(file); // pega o próximo caractere
 
            if (c == '=') // se for '=' sabemos que é o token '<='
                makeToken("<=", 0);
 
            else
                makeToken("<", 0);
 
        }
 
        else if (c == '>')
        {
            c = fgetc(file);
 
            if (c == '=')
                makeToken(">=", 0);
 
            else
                makeToken(">", 0);
 
        }
 
        else if (c == '=') {
            makeToken("=", 0);
 
        }
 
        else if (isdigit(c)) {
            numero();
        }
 
        else if (isalpha(c)) {
            palavra();
        }
 
        else
        {
            printf("O caracter '%c' na linha %d nao reconhecido.\n", c, linha);
            exit(EXIT_FAILURE);
        }

lex.c: Temos duas novas funções, são elas palavra e numero:

void palavra()
{
    char palavra[100] = "";
    int pos = 0;
 
    while (isalnum(c))
    {
        palavra[pos++] = c;
        c = fgetc(file);
    }
 
    voltaPonteiro();
    if (strcmp(palavra, "INIT") == 0)
        makeToken("INIT", 0);
 
    else if (strcmp(palavra, "PRINT") == 0)
        makeToken("PRINT", 0);
 
    else if (strcmp(palavra, "INPUT") == 0)
        makeToken("INPUT", 0);
 
    else if (strcmp(palavra, "VAR") == 0)
        makeToken("VAR", 0);
 
    else if (strcmp(palavra, "IF") == 0)
        makeToken("IF", 0);
 
    else if (strcmp(palavra, "ELSE") == 0)
        makeToken("ELSE", 0);
 
    else if (strcmp(palavra, "END") == 0)
        makeToken("END", 0);
 
    else
        makeToken("ID", 0);
}

Não é a função mais otimizada que você já viu, mas funciona:

void numero()
{
    int k = 0;
    while (isdigit(c))
    {
        k = k * 10 + c - '0';
        c = fgetc(file);
    }
 
    voltaPonteiro();
    makeToken("T_INT", k);
}

Testamos o código agora:

$ ./exe/main teste.txt
<INIT, 0><PRINT, 0><T_INT, 1><+, 0><T_INT, 2><*, 0><T_INT, 3><END, 0>

Olha só, reconhecemos a maior parte dos tokens de nossa linguagem! Agora que tal mais um teste utilizando outro teste.txt?

INIT
 
VAR max := 10
VAR num
 
INPUT num
 
IF (num < max)
    INIT
        PRINT 0
    END
 
ELSE
    INIT
        PRINT 1
    END
 
END

$ ./exe/main teste.txt
<INIT, 0><VAR, 0><END, 0><:=, 0><=, 0><T_INT, 10><VAR, 0><END, 0><INPUT, 0><END, 0><IF, 0>
<(, 0><END, 0><<, 0><END, 0><), 0><INIT, 0><PRINT, 0><T_INT, 0><END, 0><ELSE, 0><INIT, 0>
<PRINT, 0><T_INT, 1><END, 0><END, 0>

Na próxima parte vamos fazer algumas alterações no analisador léxico e depois daremos início ao analisador sintático. Até lá. ?