FLEX: Fast Lexical Analyser

Esta série de artigos introduz as ferramentas UNIX FLEX e BYACC através duma abordagem prática, a implementação duma calculadora simples. Os artigos assumem a familiaridade do leitor com C e C++, a qual será necessária para seguir os exemplos. Antes de prosseguir para a calculadora no entanto, importa explicar o que são e para que servem o FLEX e o BYACC.

  • FLEX: da autoria de Vern Paxson, também conhecido como fast lexical analyser, é um gerador de analisadores lexicais. Um analisador lexical é uma ferramenta que permite ler uma input stream e tomar acções quando partes dessa stream correspondem a padrões definidos pelo programador. Estes padrões, normalmente conhecidos como expressões regulares e usados em muitas outras aplicações (grep, Visual Studio, Notepad++, etc.) tal como suportados por várias linguagens (Java, Perl, PHP, Python, Ruby, Visual Basic, etc.) são fundamentais para o uso do FLEX e serão abordados com mais profundidade noutro artigo.
  • BYACC: o Berkeley YACC, da autoria de Robert Corbett, é um gerador de parsers. Um gerador de parsers permite criar uma aplicação que recebe tokens e caso estes tokens conformem com a gramática especificada pelo programador são tomadas acções. Estes conceitos serão abordados com mais profundidade ao longo dos artigos.

O FLEX e o BYACC são duas das variantes das ferramentas que durante décadas foram o standard dum gerador de analisadores lexicais e dum gerador de parsers em sistemas UNIX, o LEX e o YACC da AT&T, desenvolvidos nos anos 70 nos laboratórios Bell por Mike Lesk e Eric Schmidt (LEX), e Stephen C. Johnson (YACC). Outras variantes são GNU Bison, MKS LEX e YACC, e Abraxas LEX e YACC. Apesar de existirem diferenças entre as variantes, elas são em muitos casos negligenciáveis na óptica do utilizador, sendo possível correr muito do código LEX directamente em FLEX ou outra variante sem modificações, o mesmo se verificando com código YACC usado em BYACC ou Bison.

Ainda que tenham outros usos actualmente, historicamente geradores de analisadores lexicais e geradores de parsers foram concebidos para escrever compiladores – YACC é um acrónimo de “yet another compiler compiler” (o “compiler compiler” original foi escrito em 1960 por Tony Brooker) e o LEX foi desenvolvido posteriormente ao YACC, destinado a ser utilizado em seu complemento – função para a qual são utilizados ainda hoje.

Vamos agora usar estas ferramentas para escrever uma calculadora simples que funcione a partir da linha de comandos. Neste primeiro artigo focar-nos-emos no FLEX, deixando o BYACC para um segundo artigo e a versão final da calculadora para um terceiro. Começando pelo FLEX então, importa primeiro descrever a sua estrutura. Um ficheiro FLEX é constituído por 3 secções delimitadas pelo separador %%. A primeira e a terceira secção são utilizadas para inserir código do utilizador, escrito em C/C++, sendo a primeira secção usada para as definições e #includes e a terceira para as rotinas principais do utilizador. A segunda secção é utilizada para as regras do FLEX propriamente ditas.

%%
.|\n  putchar(*yytext);
%%

Este é um exemplo muito simples de um ficheiro FLEX, a primeira e terceira secção encontram-se vazias porque não introduzimos código nosso e a segunda contém uma única regra que se limita a fazer output do input que o programa recebe. Vamos analisar esta regra primeiro:

.|\n   putchar(*yytext);

Uma regra em FLEX corresponde a uma expressão regular e uma acção. A expressão regular é um padrão ao qual o analisador lexical vai tentar encontrar correspondência na input stream. Quando encontra toma a acção associada à regra, neste caso putchar(*yytext);. A acção é código C/C++ do utilizador, e pode ser uma instrução solitária como acima, ou um bloco do tipo {} ou %{ %} que ocupe várias linhas. O “.|\n” é uma expressão regular que basicamente aceita qualquer caractere, o ponto significa qualquer caractere excepto o \n e a barra significa “ou”, logo aquela expressão regular pode-se ler como “qualquer caractere excepto o \n ou o \n“, portanto, tudo. O yytext é um char *, que corresponde à string à qual a expressão regular fez “match”. Guardando aquele ficheiro como ex1.l e correndo na shell os seguinte comandos,

flex ex1.l
gcc -o ex1 lex.yy.c -lfl

obtemos um executável, ex1, que se comporta como o comando cat corrido sem argumentos. Vejamos então o que se passa aqui: o comando flex ex1.l está a gerar o ficheiro lex.yy.c, um ficheiro que implementa em C os comportamentos que descrevemos em FLEX. Em seguida corremos o gcc como normal, sendo necessário linkar a libfl para gerar o executável.

O que o FLEX e, como veremos, o BYACC fazem portanto é traduzir um conjunto de regras simples para código C (ou C++) que as implementa, limpando e facilitando o design e gerando na maior parte dos casos código mais eficiente do que um programador faria manualmente.

%%
.|\n  putchar(*yytext);
%%
int main()
{
    yylex();
}

O código acima é idêntico ao anterior e se compilado vai comportar-se da mesma forma. A diferença aqui reside na introdução da função main na terceira secção. Anteriormente o main não foi introduzido porque caso ele esteja omisso o FLEX linka-o automaticamente, mas importa mencionar que é possível escrevermos o nosso próprio main caso o desejemos. Neste caso em particular o main é igual ao que o FLEX usa, limitando-se a chamar a função yylex(), onde estão implementadas as regras. Caso escrevamos o nosso main devemos lembrar-nos de chamar essa função para além do nosso código ou nenhuma das regras vai executar.

Vamos agora considerar um caso mais complexo, o da nossa calculadora. O que é que precisamos que o FLEX faça neste caso? Primeiro é preciso perceber que o ficheiro FLEX, o scanner, é a rotina de baixo nível, enquanto que o ficheiro BYACC, o parser, é a de alto nível. É o parser que controla o scanner e o chama quando necessita de novo input. A função do scanner é ler a input stream, processá-la e informar o parser do que leu. Portanto o que queremos que o nosso ficheiro FLEX faça é ler o input do utilizador e enviá-lo para o parser. No caso duma calculadora o input que nos interessa são números, portanto queremos que o scanner tenha uma regra deste género:

num        retornaNumero();

Em que num corresponde a uma expressão regular que faz match a números e retornaNumero() à acção que processa o número e o envia para o scanner. O código FLEX que implementa isto é o que se segue:

DIG         [0-9]
MANTISSA    ({DIG}*\.{DIG}+)|({DIG}+\.)
EXPONENT    [eE][-+]?{DIG}+
 
INT         (0|[1-9]{DIG}*)
DOUBLE      {MANTISSA}{EXPONENT}?
 
%%
 
{INT}|{DOUBLE}   { yylval.d = strtod(yytext, NULL); return NUMBER; }
 
%%

Estão aqui vários conceitos novos, especialmente se se não conhecer expressões regulares, portanto vamos abordar o problema lentamente. Antes de mais o que é um número, ou mais precisamente, que representações existem para um número? É importante definir isto para sabermos que expressão regular devemos utilizar para lhe fazer correspondência. Conhecendo C/C++ é fácil de reconhecer que 1, 15, 9.2e-5, 3.5, .2, 4., 6.e3 e .45E+14 são todas representações válidas de números, portanto a nossa expressão regular tem que saber reconhecer todas. Comecemos pelo mais simples, a expressão regular que corresponde a um dígito é [0-9]. Esta sintaxe com os parênteses rectos indica uma classe de caracteres e representa um intervalo de caracteres ao qual queremos fazer match. Se quisermos fazer match a uma letra qualquer por exemplo, podemos escrever [a-z] (ou [A-Za-z] se quisermos maiúsculas e minúsculas).

É possível criar classes de caracteres para qualquer conjunto que nos interesse fazer match. Por exemplo se quisermos criar uma regra para apanhar vogais podemos escrever [aeiouAEIOU] indicando um a um os caracteres que pertencem ao nosso intervalo. É preciso tomar cuidado com o hífen dentro duma classe de caracteres, num caso como [a-z] o hífen é açúcar sintáctico para representar os caracteres de az e não os caracteres a, - e z. Se quiséssemos o segundo caso deveríamos escrever [-az], com o hífen no início. Existem muitas outras nuances como esta no uso de expressões regulares, mas não é objectivo deste artigo abordá-las. Expressões regulares são um tema suficientemente vasto para merecer o seu próprio artigo, e de facto, livros. Esta introdução limitar-se-á a explicar o significado das expressões regulares que usar sem entrar em maior detalhe.

Tendo agora uma noção do que são classes de caracteres importa perceber como fazer match a um número com vários algarismos. Por exemplo o número 259. Poder-se-ia pensar na expressão regular [0-9][0-9][0-9] e neste caso funcionaria, mas tem vários problemas. O primeiro e mais óbvio é que esta expressão regular só faz match a números com três algarismos, o segundo e menos grave é a repetição de código. A solução do segundo é simples, basta fazer [0-9]{3}, mas a solução do primeiro implica introduzir um novo conjunto de metacaracteres, *, + e ?.

O asterisco significa zero ou mais quando associado a uma expressão regular, ou seja [0-9]* faz match a zero ou mais algarismos, portanto , 1, 123 e 43538 são todos aceites por esta expressão regular. É importante mencionar que o asterisco “come” tudo o que consegue portanto um número com n algarismos consecutivos vai sempre ser aceite por [0-9]*, independentemente do tamanho de n.

O sinal de mais funciona de forma semelhante ao asterisco, diferindo no facto que significa um ou mais e não zero ou mais, portanto no caso da expressão regular [0-9]+ os números aceites têm de ter sempre pelo menos um algarismo. O ponto de interrogação significa zero ou um, indicando um elemento opcional. Podemos escrever [-+]?[0-9]+ para indicar um número com sinal opcional (13, -1 e +324 são aceites por esta expressão regular).

Um número com n algarismos pode ser então aceite pela expressão regular [0-9]* (ou [0-9]+ caso n > 0) mas com esta expressão regular só serão aceites números naturais. Se quisermos aceitar reais na notação descrita anteriormente necessitaremos de uma expressão regular mais complexa (inteiros negativos e reais negativos serão tratados pelo parser). Antes de começarmos a escrever essa expressão regular no entanto, vamos introduzir uma funcionalidade do FLEX que vai tornar o nosso código mais legível. Uma expressão regular para apanhar endereços de email simples como [-a-zA-Z0-9\._%+]+@[-a-zA-Z0-9.]+\.[a-zA-Z]{2,4} pode ser difícil de absorver de relance, mas é uma expressão que o leitor já deverá compreender parcialmente, e quando adquirir alguma prática, totalmente. No entanto esta expressão evidência a tendência das expressões regulares para se tornarem ilegíveis quando atingem um certo grau de complexidade. Para evitar isso o FLEX permite criar definições, DIG [0-9] define a expressão regular [0-9] como DIG, permitindo aceder ao seu valor escrevendo {DIG}, ou seja, é equivalente escrever {DIG} ou [0-9].

MANTISSA    ({DIG}*\.{DIG}+)|({DIG}+\.)

A expressão acima também é uma definição (razão pela qual está na primeira secção) e define MANTISSA como sendo zero ou mais dígitos, seguidos de um ponto e de um ou mais dígitos ou um ou mais dígitos seguidos de um ponto. Existem dois pormenores que ainda não abordámos neste caso, os parênteses e o \.. O \. é uma sequência de escape para indicarmos que queremos mesmo o caractere ponto e não o metacaractere ponto que indica qualquer caractere. Os parênteses são metacaracteres que servem como habitual para agrupar itens.

EXPONENT    [eE][-+]?{DIG}+
 
INT         (0|[1-9]{DIG}*)
DOUBLE      {MANTISSA}{EXPONENT}?

Este conjunto de definições não introduz nada de novo, mas convém analisar cada definição para assentar conceitos. EXPONENT é definido como um e ou E, seguido de um mais ou menos opcional e um ou mais dígitos. Um INT é um zero ou um número de um a nove seguido de zero ou mais dígitos. Um DOUBLE é uma MANTISSA seguida de um EXPONENT opcional. O comportamento do metacaractere |, ou, é sempre como indicado na segunda definição, tudo o que vem antes do | ou tudo o que vem a seguir.

Tendo concluído a secção das definições vamos analisar as regras, ou a regra neste caso, visto só termos uma.

{INT}|{DOUBLE}  { yylval.d = strtod(yytext, NULL); return NUMBER; }

A expressão regular neste caso é simples graças ao uso de definições, aceita um INT ou um DOUBLE. A acção também é simples mas a compreensão total envolve pormenores que só vamos ver quando começarmos a escrever o parser. Por enquanto basta saber que o yylval é uma union definida pelo parser onde guardamos o valor de retorno e o NUMBER é um #define que indica o tipo do retorno. O yylval.d é do tipo double, mas o que o FLEX fez match foi a uma string, portanto usamos a função strtod() da stdlib para converter a string para double antes de a enviarmos para o parser.

Agora que já temos o scanner a aceitar números, falta-nos aceitar as operações da calculadora e lidar com o restante input. Esta nova versão do ficheiro trata disso.

%option outfile="CalculatorScanner.c"
 
%{
#include "CalculatorParser.tab.h"
 
 
void yyerror(char * err_msg)
{
    printf("%s\n", err_msg);
    exit(1);
}
 
%}
 
WS          [ \t]
NL          "\n"|"\r"|"\r\n"
DIG         [0-9]
 
 
MANTISSA    ({DIG}*\.{DIG}+)|({DIG}+\.)
EXPONENT    [eE][-+]?{DIG}+
 
INT         (0|[1-9]{DIG}*)
DOUBLE      {MANTISSA}{EXPONENT}?
 
%%
 
{INT}|{DOUBLE}   { yylval.d = strtod(yytext, NULL); return NUMBER; }
 
[-+*/^()]        return *yytext;
 
{NL}             return NL;
{WS}             ; /* ignore whitespace */
 
.                yyerror("Unknown character");
 
%%

Vejamos o que foi introduzido aqui. Na primeira linha temos a seguinte instrução,

%option outfile="CalculatorScanner.c"

cujo propósito é simplesmente indicar ao FLEX que o nome do ficheiro que queremos que ele gere é CalculatorScanner.c e não o default lex.yy.c. Em seguida abrimos um bloco de código C com %{, e fechamos-lo mais tarde com %}. Podemos utilizar estes blocos para inserirmos código C/C++ como usual. Inserir código C/C++, incluindo comentários, fora destes blocos não vai funcionar como esperado a menos que todo esse código esteja indentado.

#include "CalculatorParser.tab.h"

Este #include – que também era necessário na versão anterior mas foi omitido por motivos de simplificação — é um header criado pelo BYACC e que contém a union e os #defines mencionados anteriormente. A função yyerror() que se lhe segue, é uma função C normal, criada para lidar com erros no input. Veremos à frente como é usada.

WS          [ \t]
NL          "\n"|"\r"|"\r\n" 

Estas duas definições fazem respectivamente match a espaço em branco (quer sejam espaços ou tabs) e a mudanças de linha (quer sejam de Linux, Mac ou Windows). As aspas na definição NL são um metacaractere e indicam que queremos fazer match exactamente ao que está lá dentro. No exemplo da expressão regular para os reais, quando usámos a expressão \. para dizer que queríamos o caractere ponto, podíamos ter usado a expressão "." para o mesmo efeito, tal como aqui podíamos ter usado a expressão \\n|\\r|\\r\\n em vez da que usamos.

[-+*/^()]        return *yytext;

Esta classe de caracteres apanha todas as operações que a nossa calculadora vai realizar, somas, subtracções, multiplicações, divisões e potências, tal como parênteses para podermos criar agrupamentos. Neste caso retornamos o caractere directamente ao parser, algo que podemos fazer sempre que o input ao qual queremos fazer match é só um caractere.

{NL}             return NL;

No caso duma mudança de linha não existe nenhum valor que nos interesse retornar ao parser, portanto basta-nos informar o parser sobre o acontecimento. A necessidade de efectuar este retorno tornar-se-á mais óbvia quando discutirmos o parser.

{WS}             ; /* ignore whitespace */

O espaço em branco não interessa à nossa calculadora, mas queremos permitir que o utilizador o possa usar, portanto usamos uma instrução vazia como acção, causando com que o scanner o ignore.

.                yyerror("Unknown character");

Esta última regra destina-se a lidar com input inválido. A primeira consideração a tomar é que esta regra necessita de estar em último lugar porque o ponto faz match a tudo. A forma como o FLEX funciona é a seguinte, dado input que pode ser aceite por duas regras, o FLEX usa a que aceita mais input. Se as duas aceitarem a mesma quantidade o FLEX usa a que vem primeiro no ficheiro. Tomemos o seguinte caso:

%%
 
[0-9]{3}     printf("número com 3 algarismos");
[0-9]*       printf("número com n algarismos");
 
%%

Para o input 123456 o output do scanner vai ser número com n algarismos e não número com 3 algarismosnúmero com 3 algarismos como seria se ele usasse a primeira regra duas vezes. A razão disto é que a segunda regra aceita mais do input que a primeira, como tal neste caso, é essa que o FLEX usa. Para o input 123 no entanto, o output vai ser número com 3 algarismos, já que, aceitando as duas regras a mesma quantidade do input, o FLEX usa a que aparece primeiro, [0-9]{3}.

No caso do ponto, ele vai apanhar todo o input que as regras que o precedem não aceitem. Isto resulta porque o ponto só aceita um caractere individual. Se em vez de . tivéssemos escrito .* ele usaria esta regra em detrimento de todas as outras (excepto as que contivessem \n) independentemente de onde a colocássemos no ficheiro. Percebendo em que casos é que esta regra é utilizada, basta decidir como queremos lidar com o input inválido. No nosso ficheiro estamos a lançar um erro e a parar a execução mas podíamos só ignorar o input inválido da mesma forma que os espaços, ou emitir só um aviso. Com isto concluímos o scanner para a nossa calculadora e este artigo. No próximo artigo veremos BYACC, e como implementar o parser.