Flex - fast lexical analyzer generator

Flex je program, který na základě popisu úlohy generuje zdrojový kód programu v programovacím jazyce C. Úlohou se rozumí rozpoznávání lexikálních elementů v textu a jejich zpracování. Typickým příkladem je vyhledávání řetězce pomocí regulárního výrazu a jeho nahrazení řetězcem jiným. Popis úlohy je tvořen dvojicemi regulární výraz - kód v programovacím jazyce C. Snadno tak vytvoříte totéž, co pomocí programu awk nebo sed. Nespornou výhodou generátoru flex je rychlost výsledného programu. Nejedná se totiž o interpretovaný kód, ale o skutečný spustitelný program (binárku). Někdo může namítnout, že ho pikosekundy nezajímají. To může být pravda, ale ne vždy je úkolem zpracovat textový soubor o velikosti několika kilobajtů. Při vstupních souborech velikosti stovek megabajtů už rychlost zpracování hraje nezanedbatelnou roli. Flex má i mnoho dalších výhod, ke kterým se ještě dostaneme.

Zdrojové kódy a dokumentace

Generátor flex je GNU verze klasického UNIXového generátoru lex. Ve speciálním režimu je dokonce s generátorem lex téměř kompatibilní. Bohužel, kolik je UNIXů, tolik je lexů. Proto se na stoprocentní kompatibilitu nedá spoléhat.

Zdrojové kódy generátoru flex si můžete stáhnout například zde (373k). K jeho instalaci není třeba nic dodávat, vše je přehledně popsáno v souboru INSTALL. Ve většině případů postačí klasické příkazy ./configure, make a make install. Nakonec můžete flex prověřit pomocí příkazu make check. Většina distribucí operačního systému Linux zcela určitě generátor flex již obsahuje, takže ho nebudete muset stahovat a instalovat.

Zde naleznete manuál ve formátu html. Stejný text je také obsahem manuálové stránky, která je součástí instalace.

Generátor flex pěkně od začátku

Popis úlohy předáváme generátoru flex v textovém souboru. Na základě tohoto souboru vygeneruje generátor flex soubor lex.yy.c, který je zdrojovým kódem našeho programu. Kompilací tohoto souboru a slinkováním s knihovnou -lfl získáme spustitelný program.

martins@matysek> flex pokus.ll
martins@matysek> gcc -o pokus.o -c lex.yy.c
martins@matysek> gcc -o pokus  pokus.o -lfl

Formát vstupního souboru

Vstupní soubor generátoru flex sestává ze tří sekcí, které jsou navzájem odděleny řetězcem %%. Oddělovací řetězec musí být uveden na samostatném řádku.

První sekce se nazývá definiční a je určena pro deklarace jednoduchých identifikátorů. V definiční sekci uvádíme konstrukce typu:

CAPITAL [A-Z]    /*Velká písmena*/
DIGIT   [0-9]    /*Číslice*/
EMPTY_LINE ^.*$  /*Prázdný řádek*/

Text umístěný v definiční sekci, který je odsazen nebo uzavřen mezi znaky %{ %}, bude beze změny okopírován do zdrojového kódu. Toho můžeme využít %při deklarování globálních proměnných nebo vkládání hlavičkových souborů. %Globální proměnné jsou platné jak v sekci pravidel, tak %v uživatelské sekci. Následující dvě konstrukce jsou totožné:

%{
#include<math.h>
%}
      #include<math.h>

Pro názvy identifikátorů a proměnných platí obecná pravidla jako pro identifikátory v programovacím jazyce C. Pokud máte touhu vytvářet nějaké speciality, podívejte se pro jistotu do dokumentace.

Druhé sekci budeme říkat sekce pravidel. Pravidlem se rozumí dvojice vzor - akce. Vzorem je nejčastěji regulární výraz. Akci chápeme jako libovolný kód napsaný v programovacím jazyce C, který říká, co se má vykonat, pokud je vzor v textu nalezen. Při psaní pravidel musíme dodržovat následující konvence:

• vzor nesmí být na řádce odsazen,
• akce musí začínat na stejném řádku jako vzor.

V sekci pravidel se můžeme odkazovat na identifikátory deklarované v definiční sekci. Podobně jako v předchozí sekci můžeme pomocí odsazeného textu nebo znaků %{ %} definovat proměnné. Tyto proměnné jsou však lokální, což znamená, že jejich platnost je omezena pouze na sekce pravidel.

Následuje malá ukázka toho, jak by mohla taková sekce pravidel vypadat:

{EMPTY_LINE} printf("Našel jsem prázdný řádek\n");

Poslední sekcí vstupního souboru generátoru flex je uživatelská sekce. Obsah této sekce bude beze změny okopírován do zdrojového kódu výsledného program. Uživatelskou sekci můžeme například využít pro vyhodnocení parametrů vygenerovaného programu. Následující kód zajistí, že parametr, který je uveden na příkazové řádce bezprostředně za názvem programu, bude použit jako název vstupního souboru. Pokud bude program spuštěn bez parametrů, bude jako vstupní soubor použit standardní vstup.

main (int argc, char **argc)
   {
    ++argv;
    --argc;
    /*yyin je proměnná, která obsahuje jméno vstupního souboru*/
    if (argc > 0)
       yyin = fopen (argv[0], "r");
    else
       yyin = stdin;
   /*Skenovací funkce vygenerovaná na základě pravidel*/
   yylex();
   }

Zpracování textového vstupu

Vygenerovaný program čte vstupní textový soubor a hledá v něm části textu, které vyhovují definovaným vzorům. Pokud takovou část textu najde, vykoná akci příslušného pravidla. Jestliže najde více částí textu, které vyhovují různým vzorům, použije to pravidlo, jehož vzoru vyhovuje nejdelší text. Na pořadí pravidel záleží pouze tehdy, jsou-li nalezeny dvě stejně dlouhé části textu. Text, který neodpovídá žádnému pravidlu, je vytisknut na standardní výstup.

Následující příklad realizuje program, který počítá slova v textu. Regulární výraz [^ \t\n] vyhovuje posloupnosti znaků, která neobsahuje mezeru, tabulátor nebo znak nový řádek. Druhý regulární výraz .|\n vyhovuje jakémukoliv znaku. Text, který vyhovuje prvnímu regulárnímu výrazu, je vždy delší nebo stejně dlouhý jako text, který vyhovuje druhému regulárnímu výrazu. Druhý regulární výraz se tedy uplatní pouze v případech, kdy text prvnímu regulárnímu výrazu nevyhoví. Prvnímu regulárnímu výrazu nevyhoví pouze mezery, tabulátory a znaky nový řádek. Druhý regulární výraz tedy zajistí pohlcení těchto znaků, které by jinak byly vytisknuty na standardní výstup.

int word_c=0;
%%
[^ \t\n] ++word_c;
.|\n
%%
main()
   {
     printf("Počet slov = %d\n",word_c);
   }

Na závěr zde uvedu složitější program. Konkrétně se pokusím vytvořit zjednodušenou verzi UNIXového programu wc, který určitě každý zná.

/*DEFINIČNÍ SEKCE*/

  /*Slovo jako posloupnost znaků, která neobsahuje mezery,*/
  /*tabulátory ani znak nový řádek*/
WORD [^ \t\n]

  /*Proměnné*/
     int line_c=0, word_c=0, char_c=0;
%%
  /*SEKCE PRAVIDEL*/
{WORD}+   ++word_c; char_c=char_c+yyleng;
.    ++char_c;
\n   ++line_c;  ++char_c;
%%
  /*UŽIVATELSKÁ SEKCE*/
main()
   {
     /*Spusť lexikální skener*/
     yylex();
      /*Vytiskni výsledky*/
     printf("     %d    %d    %d\n",line_c, word_c, char_c);
   }

V příštím dílu se podíváme na regulární výrazy, seznámíme se s tvorbou komplikovanějších pravidel, a možná dojde i na stavový automat.