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