LIMSpec Wiki
Nota: Para outros significados, veja Lex (desambiguação).
Em ciência da computação (linguagens de programação), lex é um programa que gera analisadores léxicos. Ele é geralmente usado com o yacc, um gerador de analisador sintático. Escrito originalmente por Eric Schmidt e Mike Lesk, ele é o gerador de analisador léxico padrão em diversos sistemas Unix.
O lex lê um fluxo de entrada especificando um analisador que mapeia expressões regulares em blocos de código, e retorna um código fonte implementando o analisador. Apesar do gerador ser genérico e poder se adequar a diferentes linguagens de programação, atualmente, somente a geração de código C é suportada.
Apesar de ser software proprietário, versões do lex baseadas no código original da AT&T estão disponíveis em código aberto, como parte de sistemas como OpenSolaris e Plan 9. Outra versão popular e livre do lex é o flex.
Estrutura do arquivo
A estrutura de um arquivo lex é intencionalmente similar ao de um arquivo yacc. Os arquivos são divididos em três seções, separadas por linhas que contém somente dois símbolos de percentagem, como a seguir:
definições %% regras %% subrotinas
Na seção de definições são definidas as macros e são importadas as bibliotecas escritas em C. É também possível escrever código C na mesma seção. Já a seção de regras associa padrões com instruções C, padrões escritos na forma de expressões regulares. Quando o analisador léxico identifica algum texto da entrada casando com um padrão, ele executa o código C associado. A tentativa do casamento é sempre gananciosa, isto é, no caso de dois padrões distintos casando a mesma entrada, o maior deles será usado. O maior deles é o que consome mais caracteres da entrada. Caso os padrões ambíguos consumam a mesma quantidade de caracteres, o padrão definido antes é escolhido. Por fim, a seção de subrotinas contém blocos de código C que serão apenas copiados ao arquivo final. Assume-se que tal código será invocado a partir das regras da seção de regras. Em programas maiores, é mais conveniente separar esse código final noutro arquivo.
Exemplo de um arquivo lex
O seguinte exemplo reconhece inteiros da entrada de dados e os imprime na saída padrão.
/*** seção de definição ***/
%{
# include <stdio.h>
%}
%%
/*** seção de regras ***/
/* [0-9]+ casa uma cadeia de um ou mais dígitos */
[0-9]+ {
/* yytext é a cadeia contendo o texto casado. */
printf("Inteiro: %s\n", yytext);
}
. { /* Ignora outros caracteres. */ }
%%
/*** seção de código C ***/
int main(void)
{
/* executa o analisador léxico. */
yylex();
return 0;
}
Com a entrada acima, será feita a conversão para um arquivo C. Para a seguinte entrada:
abc123z.!&*2ghj6
O programa imprimirá:
Inteiro: 123 Inteiro: 2 Inteiro: 6
Relacionamento com yacc
O lex e o gerador de analisador sintático yacc são geralmente usados em conjunto. O Yacc usa uma gramática formal para analisar sintaticamente uma entrada, algo que o lex não consegue fazer somente com expressões regulares (o lex é limitado a simples máquinas de estado finito). Entretanto, o yacc não consegue ler a partir duma simples entrada de dados, ele requer uma série de tokens, que são geralmente fornecidos pelo lex. O lex age como um pré-processador do yacc. Segue abaixo dois diagramas do relacionamento entre lex e yacc:
|
|
A partir do diagrama 1, percebe-se que o lex gera a subrotina yylex() a partir de regras léxicas, e que o yacc gera a subrotina yyparse() a partir de regras gramaticais. A partir do diagrama 2, percebe-se que um programa qualquer invoca o analisador sintático para uma fluxo de entrada. O analisador sintático não consegue analisar entradas, mas sim tokens. Portanto, cada vez que ele precisa dum token, ele invoca o analisador léxico. O analisador léxico processa o fluxo de entrada e retorna o primeiro token que encontrar. Esse processo de requisição é contínuo e só termina quando o analisador léxico identifica o fim o fluxo de entrada ou quando o analisador sintático identifica uma falha gramatical.
Referências gerais
- M. E. Lesk e E. Schmidt. «Lex - A Lexical Analyzer Generator». The Lex & Yacc Page (em inglês). Consultado em 22 de julho de 2008
- Ivan L. M. Ricarte (14 de fevereiro de 2003). «Desenvolvimento de uma aplicação». Programação de Sistemas: Uma Introdução. Universidade Estadual de Campinas. Consultado em 22 de julho de 2008
