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 Fernando Mercês
      Toda segunda-feira em nosso server no Discord a gente se junta para tomar decisões de programação e do futuro de projetos open source que a gente mantém. Atualmente estamos com foco no pev, um toolkit para análise de executáveis e bibliotecas de Windows. É só chegar e entrar na call ao vivo! Entre aqui!
    • By Bruna Chieco
      O OEA Cyberwomen Challenge, evento realizado nos dias 10 e 11 de fevereiro, tem como missão promover a entrada do público feminino no mercado de cibersegurança. Este ano, o desafio será realizado em formato 100% online, organizado pela Trend Micro, Organização dos Estados Americanos (OEA) e o Governo do Reino Unido, com apoio da Womcy Latam.
      O evento é voltado para mulheres que estejam iniciando sua carreira em cibersegurança e topam o desafio de avaliar e mostrar suas capacidades e talentos. Nesta edição, na parte da manhã do dia 10 de fevereiro, a partir das 10h, será realizado um Painel de Tecnologia formado por executivas do mercado de TI e cibersegurança da América Latina e tratará de práticas de gestão e investigação. 
      Estarão presentes no painel Adriana Shimabukuro, técnica do Núcleo Técnico de Combate aos Crimes Cibernéticos do Ministério Público Federal; Leticia Gammill, líder do time de Canais de Cybersecurity das Américas na Cisco e fundadora e presidente da Womcy; Claudia Anania, Head de TI do Instituto Butantan; Tamires Almeida, focada em pré-vendas de projetos de segurança da informação e líder do programa Womcy Mentoring para Mentorias Reversas; Rayanne Nunes, Coordenadora de Tecnologia na Trend Micro; e Barbara Marchiori de Assis, Consultora da OEA e outras empresas.
      Já no dia 11 de fevereiro, ocorrerá um workshop virtual com o desafio de defender um ambiente simulado com situações realistas de cibersegurança. O objetivo é proporcionar um aprendizado sobre situações como migração de aplicações, apps de orquestração e uso de Security as Code. O workshop terá a orientação de especialistas da Trend Micro e as participantes terão a oportunidade de explorar o networking com profissionais do mercado, além de receberem o kit de participação em sua casa. 
      O desafio concederá ainda uma premiação para o grupo primeiro colocado, composta por um curso relacionado à área do desafio, a ser confirmado pela organização até a data de início do evento; licenças de Antivírus da Trend Micro por um ano; e mentoria de Carreira realizada pela equipe Womcy Mentoring.
      Para participar, as mulheres de áreas de segurança, arquitetas de segurança, infraestrutura, desenvolvimento ou operações precisam ter conhecimento prévio em Windows e Linux, redes, segurança; containers, pipelines e imagens; processo de DevOps; e conhecer as ferramentas DevOps (Github, Jenkins, ECR da Amazon, Kubernetes, Docker e APIs). Inscreva-se!
    • By Bruna Chieco
      O Google está financiando um projeto do Internet Security Research Group para deixar toda a Internet mais segura. Trata-se de um módulo para o Apache HTTP web server (ou simplesmente httpd), que é um software livre, sendo o servidor web mais utilizado no mundo, escrito em linguagem C.
      A linguagem C, contudo, pode ser insegura, se tornando mais passível de bugs que representam falhas de segurança. De olho nisso e buscando tornar a Internet um local mais seguro, o Google decidiu financiar o projeto para desenvolver um novo módulo para substituir o mod_ssl do Apache. O módulo será responsável por suportar as operações criptográficas necessárias para estabelecer conexões HTTPS em um servidor web Apache.
      Assim, será utilizada uma alternativa mais segura de linguagem chamada Rust. O Internet Security Research Group afirma que planeja desenvolver um novo módulo chamado mod_tls que funcionará com o o mod_ssl, mas usará essa nova linguagem de programação Rust em vez de C.
      Segundo o ZDNet, a Rust é uma maneira simples e rápida de garantir que bilhões de usuários sejam mantidos em segurança nos próximos anos. Leia mais detalhes sobre o projeto (em inglês).
    • 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
×
×
  • Create New...