Flex (generátor lexikálního analyzátoru) - Flex (lexical analyser generator) - Wikipedia

flex
VývojářiVern Paxson
První vydáníkolem roku 1987; Před 33 lety (1987)[1]
Stabilní uvolnění
2.6.4 / 6. května 2017; před 3 lety (2017-05-06)
Úložiště
Upravte to na Wikidata
Operační systémUnixový
TypLexikální analyzátor generátor
LicenceLicence BSD
webová stránkagithub.com/ západ/ flex

Flex (rychle lexikální analyzátor generátor) je a bezplatný open source software alternativa k lex.[2] Je to počítačový program který generuje lexikální analyzátory (známé také jako „skenery“ nebo „lexery“).[3][4]Často se používá jako lexová implementace společně s Berkeley Yacc generátor analyzátoru na BSD -odvozené operační systémy (jako oba lex a yacc jsou součástí POSIX ),[5][6][7] nebo společně s GNU bizoni (verze yacc ) v * BSD porty[8] a v distribucích Linuxu. Na rozdíl od Bisona není flex součástí Projekt GNU a není uvolněn pod GNU General Public License,[9] i když manuál pro Flex byl vytvořen a publikován Free Software Foundation.[10]

Dějiny

Flex byl napsán C kolem roku 1987.[1] podle Vern Paxson, s pomocí mnoha nápadů a mnoha inspirací od Van Jacobson. Původní verze od Jef Poskanzer. Rychlé znázornění tabulky je částečnou implementací návrhu provedeného Van Jacobsonem. Implementaci provedli Kevin Gong a Vern Paxson.[11]

Příklad lexikálního analyzátoru

Toto je příklad skeneru Flex pro výukový programovací jazyk PL / 0.

Rozpoznané tokeny jsou: '+', '-', '*', '/', '=', '(', ')', ',', ';', '.', ':=', '<', '<=', '<>', '>', '>='; čísla: 0-9 {0-9}; identifikátory: a-zA-Z {a-zA-Z0-9} a klíčová slova: začít, volání, konst, dělat, konec, -li, zvláštní, postup, pak, var, zatímco.

%{#zahrnout „y.tab.h“%}číslice         [0-9]dopis        [A-zA-Z]%%"+"                  { vrátit se PLUS;       }"-"                  { vrátit se MÍNUS;      }"*"                  { vrátit se ČASY;      }"/"                  { vrátit se ROZŘEZAT;      }"("                  { vrátit se LPAREN;     }")"                  { vrátit se RPAREN;     }";"                  { vrátit se STŘEDNÍK;  }","                  { vrátit se ČÁRKA;      }"."                  { vrátit se DOBA;     }":="                 { vrátit se STÁVÁ;    }"="                  { vrátit se EQL;        }"<>"                 { vrátit se NEQ;        }"<"                  { vrátit se LSS;        }">"                  { vrátit se GTR;        }"<="                 { vrátit se LEQ;        }">="                 { vrátit se GEQ;        }"začít"              { vrátit se ZAČÁTEK;   }"volání"               { vrátit se CALLSYM;    }"const"              { vrátit se CONSTSYM;   }"dělat"                 { vrátit se DOSYM;      }"konec"                { vrátit se ENDSYM;     }"li"                 { vrátit se IFSYM;      }"zvláštní"                { vrátit se ODDSYM;     }"postup"          { vrátit se PROCSYM;    }"pak"               { vrátit se THENSYM;    }"var"                { vrátit se VARSYM;     }"zatímco"              { vrátit se WHILESYM;   }{dopis}({dopis}|{číslice})* {                       yylval.id = Strdup(yytext);                       vrátit se IDENT;      }{číslice}+             { yylval.počet = atoi(yytext);                       vrátit se ČÍSLO;     }[ \t\n\r]            / * přeskočit mezery * /.                    { printf("Neznámý znak [% c] n",yytext[0]);                       vrátit se NEZNÁMÝ;    }%%int yywrap(prázdnota){vrátit se 1;}

Interní

Hlavní článek: Lexikální analýza

Tyto programy provádějí analýzu a tokenizaci znaků pomocí a deterministický konečný automat (DFA). DFA je teoretický stroj přijímající běžné jazyky. Tyto stroje jsou podmnožinou kolekce Turingovy stroje. DFA jsou ekvivalentní pohybující se Turingovy stroje pouze pro čtení. Syntaxe je založena na použití regulární výrazy. Viz také nedeterministický konečný automat.

Problémy

Časová složitost

Lexický analyzátor Flex má obvykle časovou složitost v délce vstupu. To znamená, že provádí konstantní počet operací pro každý vstupní symbol. Tato konstanta je poměrně nízká: GCC generuje 12 instrukcí pro smyčku shody DFA.[Citace je zapotřebí ] Všimněte si, že konstanta je nezávislá na délce tokenu, délce regulárního výrazu a velikosti DFA.

Použití makra REJECT ve skeneru s potenciálem spárovat extrémně dlouhé tokeny však může způsobit, že Flex vygeneruje skener s nelineárním výkonem. Tato funkce je volitelná. V tomto případě programátor výslovně řekl Flexu, aby se „vrátil a zkusil to znovu“ poté, co již souhlasí s nějakým vstupem. To způsobí, že DFA ustoupí a najde další přijímající státy. Funkce ODMÍTNUTÍ není ve výchozím nastavení povolena a kvůli jejím dopadům na výkon se její použití v příručce Flex nedoporučuje.[12]

Reentrancy

Ve výchozím nastavení skener generovaný Flexem není reentrant. To může způsobit vážné problémy programům, které používají vygenerovaný skener z různých vláken. K překonání tohoto problému existují možnosti, které Flex poskytuje za účelem dosažení reentrancy. Podrobný popis těchto možností naleznete v příručce Flex.[13]

Použití v prostředích jiných než Unix

Normálně generovaný skener obsahuje odkazy na unistd.h hlavičkový soubor, který je Unix charakteristický. Aby se zabránilo generování kódu, který obsahuje unistd.h, % option podstatné jméno by měly být použity. Dalším problémem je volání na isatty (funkce Unixové knihovny), kterou najdete ve vygenerovaném kódu. The % možnost nikdy neinteraktivní nutí flex generovat kód, který se nepoužívá isatty.[14]

Používání flexu z jiných jazyků

Flex může generovat kód pouze pro C a C ++. Použití kódu skeneru generovaného flexem z jiných jazyků a jazyková vazba nástroj jako LOK může být použito.

Flex ++

flex ++ je podobný lexikální skener pro C ++ který je součástí balíčku flex. Vygenerovaný kód nezávisí na žádném runtime nebo externí knihovna kromě alokátoru paměti (malloc nebo alternativa dodaná uživatelem), pokud na tom nezávisí také vstup. To může být užitečné v vložený a podobné situace, kdy tradiční operační systém nebo C runtime zařízení nemusí být k dispozici.

Skener C ++ generovaný flex ++ obsahuje hlavičkový soubor FlexLexer.h, který definuje rozhraní dvou generovaných tříd C ++.

Viz také

Reference

  1. ^ A b Levine, Johne (Srpen 2009). flex & bison. O'Reilly Media. p. 9. ISBN  978-0-596-15597-1. Asi v roce 1987 vzal Vern Paxson z laboratoře Lawrencea Berkeleye verzi lexu napsaného v ratfor (v té době rozšířený Fortran populární) a přeložil jej do jazyka C a nazval jej flexem, protože 'Fast Lexical Generátor analyzátoru.'
  2. ^ Levine, John R.; Mason, Tony; Brown, Doug (1992). lex a yacc (2. vyd.). O'Reilly. p. 279. ISBN  1-56592-000-7. Volně dostupná verze lexu je flex.
  3. ^ Levine, John R.; Mason, Tony; Brown, Doug (1992). lex a yacc (2. vyd.). O'Reilly. s. 1–2. ISBN  1-56592-000-7.
  4. ^ Levine, Johne (Srpen 2009). flex & bison. O'Reilly Media. p. 304. ISBN  978-0-596-15597-1.
  5. ^ OpenBSD (2015-12-11). „src / usr.bin / lex /“. Křížový odkaz BSD. Citováno 2015-12-26. Toto je flex, rychlý generátor lexikálního analyzátoru.
  6. ^ "flex (1)". * BSD manuálové stránky.
  7. ^ "yacc (1)". * BSD manuálové stránky.
  8. ^ "bison-3.0.4 - generátor syntaktického analyzátoru GNU". Porty OpenBSD. 2015-11-15. Citováno 2015-12-26.
  9. ^ Je flex GNU nebo ne? Archivováno 03.03.2016 na Wayback Machine, flex FAQ
  10. ^ „Flex - generátor skeneru - Obsah - GNU Project - Free Software Foundation (FSF)“. ftp.gnu.org. Citováno 2019-12-05.
  11. ^ „Flex, verze 2.5 Generátor rychlých skenerů, vydání 2.5, březen 1995“. Citováno 20. dubna 2019.
  12. ^ „Výkon - Lexikální analýza s Flex, pro Flex 2.5.37“. Flex.sourceforge.net. Archivovány od originál dne 2014-01-27. Citováno 2013-02-25.
  13. ^ „Reentrant - Lexikální analýza s Flex, pro Flex 2.5.37“. Flex.sourceforge.net. Archivovány od originál dne 17. 11. 2010. Citováno 2013-02-25.
  14. ^ „Možnosti na úrovni kódu a API - Lexikální analýza s Flex, pro Flex 2.5.37“. Flex.sourceforge.net. Archivovány od originál dne 2013-03-14. Citováno 2013-02-25.

Další čtení

  • Levine, Johne (Srpen 2009). flex & bison. O'Reilly Media. ISBN  978-0-596-15597-1.
  • M. E. Lesk a E. Schmidt, LEX - generátor Lexical Analyzer
  • Alfred Aho, Ravi Sethi a Jeffrey Ullman, Překladače: Zásady, techniky a nástroje, Addison-Wesley (1986). Popisuje techniky porovnávání vzorů používané flexem (deterministické konečné automaty)

externí odkazy