Flex (gerador de analisador lexical) - Flex (lexical analyser generator)
| Desenvolvedor (s) | Vern Paxson |
|---|---|
| lançamento inicial | por volta de 1987 |
| Versão estável | 2.6.4 / 6 de maio de 2017
|
| Repositório |
|
| Sistema operacional | Tipo Unix |
| Modelo | Gerador analisador léxico |
| Licença | Licença BSD |
| Local na rede Internet | github |
Flex ( gerador de analisador lexical rápido ) é uma alternativa de software livre e de código aberto ao lex . É um programa de computador que gera analisadores lexicais (também conhecidos como "scanners" ou "lexers"). É freqüentemente usado como a implementação lex junto com o gerador de analisador Berkeley Yacc em sistemas operacionais derivados de BSD (como ambos e são parte do POSIX ), ou junto com GNU bison (uma versão do yacc ) em portas * BSD e em distribuições Linux. Ao contrário do Bison, o flex não faz parte do Projeto GNU e não foi lançado sob a Licença Pública Geral GNU , embora um manual do Flex tenha sido produzido e publicado pela Free Software Foundation.
lexyacc
História
Flex foi escrito em C por volta de 1987 por Vern Paxson , com a ajuda de muitas ideias e muita inspiração de Van Jacobson . Versão original de Jef Poskanzer . A representação rápida da tabela é uma implementação parcial de um design feito por Van Jacobson. A implementação foi feita por Kevin Gong e Vern Paxson.
Analisador léxico de exemplo
Este é um exemplo de scanner Flex para a linguagem de programação instrucional PL / 0 .
Os tokens reconhecidos são: ' + ', ' - ', ' * ', ' / ', ' = ', ' ( ', ' ) ', ' , ', ' ; ', ' . ', ' := ', ' < ', ' <= ', ' <> ', ' > ', ' >= '; números 0-9 {0-9} :; identificadores: a-zA-Z {a-zA-Z0-9} e palavras-chave: begin , call , const , do , end , if , odd , procedure , then , var , while .
%{
#include "y.tab.h"
%}
digit [0-9]
letter [a-zA-Z]
%%
"+" { return PLUS; }
"-" { return MINUS; }
"*" { return TIMES; }
"/" { return SLASH; }
"(" { return LPAREN; }
")" { return RPAREN; }
";" { return SEMICOLON; }
"," { return COMMA; }
"." { return PERIOD; }
":=" { return BECOMES; }
"=" { return EQL; }
"<>" { return NEQ; }
"<" { return LSS; }
">" { return GTR; }
"<=" { return LEQ; }
">=" { return GEQ; }
"begin" { return BEGINSYM; }
"call" { return CALLSYM; }
"const" { return CONSTSYM; }
"do" { return DOSYM; }
"end" { return ENDSYM; }
"if" { return IFSYM; }
"odd" { return ODDSYM; }
"procedure" { return PROCSYM; }
"then" { return THENSYM; }
"var" { return VARSYM; }
"while" { return WHILESYM; }
{letter}({letter}|{digit})* {
yylval.id = strdup(yytext);
return IDENT; }
{digit}+ { yylval.num = atoi(yytext);
return NUMBER; }
[ \t\n\r] /* skip whitespace */
. { printf("Unknown character [%c]\n",yytext[0]);
return UNKNOWN; }
%%
int yywrap(void){return 1;}
Internos
Esses programas realizam análise e tokenização de caracteres por meio do uso de um autômato finito determinístico (DFA). Um DFA é uma máquina teórica que aceita linguagens regulares . Essas máquinas são um subconjunto da coleção de máquinas de Turing . Os DFAs são equivalentes a máquinas de Turing móveis para a direita somente leitura . A sintaxe é baseada no uso de expressões regulares . Veja também autômato finito não determinístico .
Problemas
Complexidade de tempo
Um analisador lexical Flex geralmente tem complexidade de tempo no comprimento da entrada. Ou seja, ele executa um número constante de operações para cada símbolo de entrada. Essa constante é bastante baixa: o GCC gera 12 instruções para o loop de correspondência do DFA. Observe que a constante é independente do comprimento do token, do comprimento da expressão regular e do tamanho do DFA.
No entanto, usar a macro REJECT em um scanner com potencial para combinar tokens extremamente longos pode fazer com que o Flex gere um scanner com desempenho não linear. Este recurso é opcional. Neste caso, o programador disse explicitamente ao Flex para "voltar e tentar novamente" depois de já ter correspondido alguma entrada. Isso fará com que o DFA retroceda para encontrar outros estados de aceitação. O recurso REJECT não é habilitado por padrão e, por causa de suas implicações de desempenho, seu uso é desencorajado no manual do Flex.
Reentrada
Por padrão, o scanner gerado pelo Flex não é reentrante . Isso pode causar sérios problemas para programas que usam o scanner gerado a partir de threads diferentes. Para superar esse problema, existem opções que o Flex fornece a fim de alcançar a reentrada. Uma descrição detalhada dessas opções pode ser encontrada no manual do Flex.
Uso em ambientes não-Unix
Normalmente, o scanner gerado contém referências ao arquivo de cabeçalho unistd.h que é específico do Unix . Para evitar a geração de código que inclui unistd.h , % option nounistd deve ser usado. Outro problema é a chamada para isatty (uma função da biblioteca Unix), que pode ser encontrada no código gerado. A opção% never-interactive força o flex a gerar código que não usa isatty .
Usando flex de outras línguas
O Flex só pode gerar código para C e C ++ . Para usar o código de scanner gerado pelo flex de outras linguagens, uma ferramenta de vinculação de linguagem como SWIG pode ser usada.
Flex ++
flex ++ é um scanner léxico semelhante para C ++ que é incluído como parte do pacote flex. O código gerado não depende de nenhum runtime ou biblioteca externa , exceto de um alocador de memória ( malloc ou uma alternativa fornecida pelo usuário), a menos que a entrada também dependa dele. Isso pode ser útil em situações incorporadas e semelhantes em que o sistema operacional tradicional ou recursos de tempo de execução C podem não estar disponíveis.
O scanner C ++ gerado por flex ++ inclui o arquivo de cabeçalho FlexLexer.h , que define as interfaces das duas classes geradas por C ++.
Veja também
Referências
Leitura adicional
- Levine, John (agosto de 2009). flex & bison . O'Reilly Media. ISBN 978-0-596-15597-1 .
- ME Lesk e E. Schmidt, LEX - Lexical Analyzer Generator
- Alfred Aho, Ravi Sethi e Jeffrey Ullman, Compilers: Principles, Techniques and Tools , Addison-Wesley (1986). Descreve as técnicas de correspondência de padrões usadas por flex (autômatos finitos determinísticos)