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

       (0 reviews)

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

    • Agradecer 1
    • Curtir 1

    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.

    Guest

  • Similar Content

    • By bsantos
      Eu tenho serios problemas com meu GCC ao usar funcoes matematicas. Esse codigo eh um exercicios (13 do capitulo 3) do livro do Andre Backes - Linguagem - Completa e Descomplicada. Como no exemplo abaixo:
      #include <stdio.h> #include <stdlib.h> #include <tgmath.h> int main(void) { double h, a, b; printf("-- Calculo da Hipotenuza do triangulo retangulo --\n"); scanf("%lf%lf",&a,&b); h = sqrt(exp(2.00*log(a) + exp(2.00*log(b)))); printf("O valor da hipotenuza eh: %.4lf\n",h); return EXIT_SUCCESS; } O problema aparece quando vou compilar, seja usando make ou gcc -std=c??. Tambem usando -std=gnu??
      make exec13_3
      cc     exec13_3.c   -o exec13_3
      /usr/bin/ld: /tmp/ccktALow.o: na função "main":
      exec13_3.c:(.text+0x36): referência não definida para "log"
      /usr/bin/ld: exec13_3.c:(.text+0x49): referência não definida para "log"
      /usr/bin/ld: exec13_3.c:(.text+0x52): referência não definida para "exp"
      /usr/bin/ld: exec13_3.c:(.text+0x5c): referência não definida para "exp"
      /usr/bin/ld: exec13_3.c:(.text+0x61): referência não definida para "sqrt"
      collect2: error: ld returned 1 exit status
      make: *** [<builtin>: exec13_3] Error 1
       
      Eh nisso que fico perdido. Consultei as headers tgmath.h e math.h, alem de sua indicacao de livro (pdf) "ModernC". Mas nao consigo achar o problema da falta de referencia.
       
      PS: sim, a ortografia falha eh por conta do teclado US.
    • By emilio.simoni
      Boa noite pessoal,
      estamos com vagas remotas para programador c++ para o time de ciber segurança da PSafe, a vaga é para atuar diretamente no nosso motor anti ransomware, criando novas features, acompanhando a evolução das ameaças e ajudando a criar formas comportamentais de proteção.
      Necessario:
      Mínimo de 3 anos em c/c++ com experiência em arquitetura de sistema operacional Experiência com Poco ou Boost, gtest ou outro framework de unit testing Conhecimento de funcionamento de malware, em especial ransomware Experiencia com windbg Diferenciais:
      Experiência com programação em kernel windows (mini filters, wfp, ...) ou mac Experiência com engenharia reversa Experiência com machine learning (scikit, tensorflow, xgb) Interessados emilio.simoni@psafe.com
    • By emilio.simoni
      Boa noite pessoal,
      estamos com vagas remotas para programador python fullstack com experiencia em AWS para atuar na area de arquitetura, nos micro serviços que se comunicam com nossos sdks de proteção de endpoint.
      Necessário:
      Mínimo de 3 anos de experiência em web services(fullstack) e 2 anos de experiência com ambiente aws Experiência com sanic ou fastapi na implementação de micro serviços Experiência com elasticsearch e kibana Experiência com bancos relacionais(postgree), key value(redis) e nosql(mongodb) Experiência com unit test, pylist ou outras ferramentas de qualidade Experiência com docker Experiência com elastic APM ou outros sistemas de monitoramento Difrenciais:
      Experiência com kafka Experiência com serviços de alta demanda(nossos endpoints chegama receber 5 mil requests por segundo) Experiência com front-end  
      Interessados emilio.simoni@psafe.com
    • By Fernando Mercês
      Conci, Aura
      Javascript para construção de páginas de Web / Aura Conci; João Sérgio Assis - Niterói, RJ: Editora da UFF, 2012.
      p. : 23 cm. — (Coleção Didáticos EdUFF, 2004)
      Bibliografia. p. 229
      ISBN 978-85-228-0535-8
      1. Javascript. 2. Construção de páginas de Web. I. Conci, Aura. II. Assis, João Sérgio. III Universidade Federal Fluminense. IV. Título
      CDD 370”
      Excerpt From: Aura Conci e João Sérgio Assis. “Javascript para construção de páginas de Web.” Apple Books. 
    • By Fernando Mercês
      Programação para leigos com Raspberry Pi / Elivelto Ebermam... [et al.]. – Vitória, ES : Edifes ; João Pessoa, PB : Editora IFPB, 2017.
      290 p. : il. ; 21 cm.
      Inclui bibliografia.
      ISBN 97885________(broch.). ISBN 97885________(e-book).
      1. Raspberry Pi (Computador) – Microcomputadores. I. Título.
      Autores:
      Elivelto Ebermam
      Guilherme Moraes Pesente
      Renan Osório Rios
      Igor Carlos Pulini
×
×
  • Create New...