Jump to content
  • Construindo seu próprio compilador - Parte 1

       (3 reviews)

    Edinho Sousa

    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:

    image.thumb.png.93a69f0a650be99817d40111478f0017.png

    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:

    image.thumb.png.b80fd7ba7840951e2b0046b63d989971.png

    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:

    image.png.1e9d5c2723f37e783292732f67d45bce.png

    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.

    image.png.c66ce4cadbd9fa43438e7a6a1e94e2ef.png

    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á. ?


    Revisão: Leandro Fróes
    • Agradecer 2
    • Curtir 3

    User Feedback

    Join the conversation

    You can post now and register later. If you have an account, sign in now to post with your account.
    Note: Your post will require moderator approval before it will be visible.

    Guest

    • This will not be shown to other users.
    • Add a review...

      ×   Pasted as rich text.   Paste as plain text instead

        Only 75 emoji are allowed.

      ×   Your link has been automatically embedded.   Display as a link instead

      ×   Your previous content has been restored.   Clear editor

      ×   You cannot paste images directly. Upload or insert images from URL.


    Pablo Simplicio

       3 of 3 members found this review helpful 3 / 3 members

    Muito bom, já tem continuação?

    • Curtir 1
    • l33t 1
    Link to review
    Share on other sites

    Valmir Vasconcelos

       2 of 2 members found this review helpful 2 / 2 members

    Muito bom ? Continue, por favor.

    • Haha 1
    • Confused 1
    Link to review
    Share on other sites

    Otniel Eliazar Funny Gomes

       1 of 1 member found this review helpful 1 / 1 member

    Sendo sinceros: -só novo nesse universo de evolução científicas atrasado pela linguagem da nossa independência G.B "Megatrote" vou estudar o código porque estou a encaixar as peças e veio me curiosidade por trás do compilador?

    • Curtir 1
    Link to review
    Share on other sites


  • Similar Content

×
×
  • Create New...