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á. 🙂
- Read more...
-
- 452 views
