A análise léxica é a primeira fase do processo de compilação de um programa, responsável por fazer a leitura do código fonte, caractere a caractere, especificando os tokens e lexemas da linguagem. Neste post, iremos implementar e testar um analisador léxico para uma linguagem inspirada em C. E faremos isso usando o Flex!

O Flex (Fast Lexical Analyzer Generator) é uma ferramenta gratuita e open-source para geração de analisadores léxicos. Ela foi escrita em C, por volta de 1987, pelo Professor Vern Paxson.

Instalando o Flex

Para instalar o Flex no Ubuntu, basta abrir o seu terminal (Ctrl + Alt + T) e executar os comandos abaixo:

sudo apt-get update
sudo apt-get install flex

Pronto! Já podemos utilizar os recursos do Flex!

Definindo uma convenção léxica para a linguagem

Nossa linguagem será simples e procedimental, um subconjunto inspirado na linguagem C, que inclui somente variáveis inteiras, array de inteiros, funções, condição, e repetição. A linguagem seguirá as convenções definidas a seguir.

• Na implementação, iremos considerar as seguintes classes de tokens na linguagem:

  ID      Identificador
  NUM     Literal decimal (inteiro)
  KEY     Palavra-chave
  SYM     Símbolos léxicos
  ERROR   Lexema do primeiro erro encontrado

• As palavras revervadas (keywords) serão as seguintes:

  else   if   int   return   void   while

Elas não poderão ser usadas como nomes de variáveis/funções, e devem ser escritas em minúsculo.

• Os símbolos especiais serão:

  !  &&  ||   +  -  *  /  <  <=  >  >=  ==  !=  =  ;  ,  (  )  [  ]  {  }  /*  */

• Os outros lexemas são o ID e NUM, definidos pelas expressões regulares abaixo:

  ID = letter (letter | digit)*
  NUM = digit digit*
  letter = a | .. | z | A | .. | Z
  digit = 0 | .. | 9

• Haverá distinção entre letras em maiúsculo e minúsculo.

• Os espaços em branco consistem em caracter branco (‘ ‘), quebra-de-linha (‘\n’), e tabs (‘\t’). Eles deverão ser ignorados, exceto quando for necessário separar os ID’s e NUM’s, e palavras reservadas.

• Comentários serão escritos da mesma forma que na linguagem C, usando a notação /* … */. Poderão ser inseridos em qualquer parte do código onde é permitido colocar espaços em branco, isto é, comentários não poderão ser inseridos dentro de tokens, e podem incluir mais de uma linha.

Desenvolvendo o arquivo Flex

O código flex é dividido em três seções:

  definições
  %%
  regras
  %%
  código do usuário

Para a linguagem que definimos, criaremos um arquivo chamado lexico.l com o código abaixo. Notem que ele é dividido em três seções, onde, na seção intermediária, definimos a ação a ser tomada para cada pattern.

digit[0-9]
letter[a-zA-Z]
ID[a-zA-Z][a-zA-Z0-9]*
WHITESPACE[ ]
quebra[\n]
TAB[\t]

%{
    #define YY_DECL extern "C" int yylex()
    #include<string>
    #include<iostream>
    using namespace std;
    FILE *out ;
	int linha;
%}
%option yylineno
%x COMMENT

%%

{quebra}

"/*" { linha=yylineno; BEGIN(COMMENT); }

<COMMENT>"*/" { BEGIN(INITIAL); }

<COMMENT>(.|\n);

<COMMENT><<EOF>> {fprintf(out,"(%d,ERROR,\"/*\")\n",linha); return 0;}

else|if|int|return|void|while {fprintf(out,"(%d,KEY,\"%s\")\n",yylineno ,yytext);} 

"+"|"-"|"*"|"/"|"<"|"<="|">"|">="|"=="|"!="|"="|";"|","|"("|")"|"["|"]"|"{"|"}" {fprintf(out,"(%d,SYM,\"%s\")\n",yylineno,yytext);}

{WHITESPACE}+|{quebra}|{TAB}+
 
{digit}+ {fprintf(out,"(%d,NUM,\"%s\")\n",yylineno,yytext);}

{digit}+{ID}+ {fprintf(out,"(%d,ERROR,\"%s\")\n",yylineno,yytext); return 0;}

{ID}+ {fprintf(out,"(%d,ID,\"%s\")\n",yylineno,yytext);}

. {fprintf(out,"(%d,ERROR,\"%s\")\n",yylineno,yytext); return 0;}

%%

int yywrap();

int main(int argc, char *argv[]){
    FILE *arquivo = fopen(argv[1],"r");
    if (!arquivo) {
      cout << "Arquivo inexistente" << endl;
      return -1;
    }
    yyin = arquivo;
    out = fopen(argv[2],"w");
    yylex();
    return 0;
}

int yywrap(){
    return 1;
}

Gerando o arquivo lex.yy.c

Após criarmos o arquivo lexico.l com as regras para o nosso analisador léxico, vamos gerar um arquivo chamado lex.yy.c, usando o Flex. Para isso, basta executar o comando abaixo no terminal:

flex lexico.l

Isso irá criar o lex.yy.c no mesmo diretório. Esse arquivo contém uma função chamada yylex(), que retorna 1 sempre que uma expressão especificada for encontrada no arquivo de entrada, e 0 quando o final do arquivo for atingido. Cada chamada à função yylex() analisa um token; quando a função é chamada novamente, ela começa de onde parou.

Gerando o executável

Para gerar o executável, vamos compilar o arquivo gerado pelo Flex através do comando:

g++ lex.yy.c -lfl -o lexico

Testando nosso analisador léxico

Agora vamos testar nosso analisador léxico! Para isto, iremos criar um arquivo de exemplo chamado main.c, que irá conter o nosso programa-fonte:

/* main.c */
void main(void){
  int a;

  a = 10;  /* Testando
              comentário
              em bloco. */
  if(a > 9){
    a = (4 + 5) * 3;
  }
}

Para iniciar a análise léxica, basta executar o seguinte comando no terminal:

./lexico main.c main.lex

Com isso, será gerado um arquivo chamado main.lex no mesmo diretório, contendo o resultado da análise léxica do nosso código-fonte:

(2,KEY,"void")
(2,ID,"main")
(2,SYM,"(")
(2,KEY,"void")
(2,SYM,")")
(2,SYM,"{")
(3,KEY,"int")
(3,ID,"a")
(3,SYM,";")
(5,ID,"a")
(5,SYM,"=")
(5,NUM,"10")
(5,SYM,";")
(8,KEY,"if")
(8,SYM,"(")
(8,ID,"a")
(8,SYM,">")
(8,NUM,"9")
(8,SYM,")")
(8,SYM,"{")
(9,ID,"a")
(9,SYM,"=")
(9,SYM,"(")
(9,NUM,"4")
(9,SYM,"+")
(9,NUM,"5")
(9,SYM,")")
(9,SYM,"*")
(9,NUM,"3")
(9,SYM,";")
(10,SYM,"}")
(11,SYM,"}")

Podemos ver que o nosso analisador léxico identificou todos os tokens e suas respectivas classes, como era esperado! Além disso, todos os comentários, tabs e quebras de linha foram ignorados, como também já prevíamos. \o/

No processo de compilação de um programa, essas informações são enviadas posteriormente para o analisador sintático, responsável por gerar uma estrutura de dados a partir do código-fonte e verificar se ela está de acordo com a gramática que foi definida para a linguagem. Mas isso já é assunto para um próximo post!

Caso queira se aprofundar ainda mais nessa área, recomendo o curso de compiladores da Stanford (em inglês).

Obrigado a tod@s, e até mais! 😊