GNU Flex

Úvod

Smyslem tohoto textu je přiblížit čtenáři program GNU Flex. Protože kvalitní dokumentaci je možné najít na stránkách projektu GNU, zaměřím se spíš na ukázky jeho možností, než na podrobný a vyčerpávající soupis všech jeho funkcí.

K vyzkoušení příkladů je potřeba mít k dispozici:

K čemu to vlastně je?

Docela často je programátor, zvlášť na Un*xech a Linuxu, nucen vytvářet kód pro zpracování textových souborů. Mnoho programů používá ke konfiguraci textové ini soubory, nebo prostě samy slouží ke zpracování textů. Každý takový program potom musí obsahovat vlastní implementaci lexikální analýzy, tj. načítání vstupního textu a rozpoznávání jeho fragmentů jako elementární tokeny. No a protože je docela otrava neustále psát něco podobného znovu a znovu, tak vznikla potřeba po nějakém nástroji, který by vývoj urychlil. Běžně se k tomuhle účelu často opakovaný kód sdružuje do knihoven, ale v tomhle případě by to příliš omezovalo možnosti programátora.

Myšlenka Flexu je trochu jiná. Uživatel-programátor, který si přeje vytvořit kód, zadá Flexu vstupní soubor obsahující popis požadovaného výsledku a na výstupu dostane vygenerovaný zdrojový soubor v jazyku C. Vytvoření vstupního souboru je přitom mnohem rychlejší, snazší a také snižuje šanci na zavlečení nějaké chyby. Programátor se nemusí starat o rozpoznávání tokenů, ve vstupu stačí popsat jejich podobu a vložit kód, který se provede po nalezení odpovídajícího výrazu v textu.

Prosté vyhledávání řetězců v textu ale není jedinou schopností výsledného kódu. Silný nástroj z něho dělá možnost použití stavů. Při práci funguje jako konečný automat a dvojice (stav, načtený text) způsobí provedení zadaného kódu a případně i změnu stavu. V dalším textu zatím stavy nebudeme uvažovat, podrobněji jsou popsány až po základním seznámení s prací Flexu.

Formát vstupního souboru

Vstupní soubor se skládá ze tří částí oddělených řádkou obsahující řetězec %%. První část obsahuje definice výrazů a stavů a kód kopírovaný na začátek výsledného zdrojáku. Výrazy definované v téhle části slouží k lepšímu popisu tokenů v následující části, kopírovaný kód může obsahovat například globální proměnné nebo příkaz pro vložení hlavičkových souborů Všechno, co se má překopírovat do výsledného souboru, musí být uzavřeno mezi znaky %{ a %} nebo odsazeno.

Výrazy se definují jako dvojice jmeno definice. Takže například
CISLO [0-9]*

je definice výrazu zastupujícího čísl. Symboly použité v regulárních výrazech na pravé straně odpovídají jejich obvyklému použití, ale pro úplnost je tady seznam některých z nich (podrobný seznam je obsažen v dokumentaci):

x znak x
x* nula nebo více opakování výrazu x
x+ jeden nebo více výskytů x
x{2,4} dva až čtyři výskyty x
[a-d] některý ze znaků a, b, c, d
[^cd] libovolný znak kromě znaků c a d
. libovolný znak kromě nové řádky
\x escape sekvence, výrazy jako \n, \t mají význam podle ANSI-C, pro ostatní to ruší zvláštní význam znaku (např. pro *)

Druhá část vstupního souboru je tvořená dvojicemi podminka akce. Podmínkou je řetězec nebo výraz, který má být vyhledán, a akce je kód, který bude po jeho nalezení proveden. Třetí část obsahuje uživatelský kód a celá se prostě zkopíruje do výsledného zdrojáku. Může zde být například funkce main nebo funkce volané v druhé části. A protože jsem ještě neukázal žádný příklad, je nejvyšší čas to napravit. Vytvoříme soubor pojmenovaný například priklad1.flex s následujícím obsahem:

%{
#include<stdio.h>
%}

ZNAKY [\_a-zA-Z0-9\-]
%%
{ZNAKY}+(\.{ZNAKY}+)*\@{ZNAKY}+(\.{ZNAKY}+)* {printf("Email = %s\n",yytext);}
.
\n
%%
main (int argc, char **argv)
{
yylex();
}

Soubor nejdřív předáme Flexu a pak ho zkompilujem. Flex nám vrátí soubor lex.yy.c a při kompilaci nesmíme zapomenout přilinkovat knihovnu Flexu pomocí -lfl.

flex priklad1.flex
gcc -o priklad1 lex.yy.c -lfl
./priklad1 <soubor

Vytvořený program bude číst ze standardního vstupu (defaultní nastavení) a vypíše všechny e-mailové adresy. Ty budou rozpoznány prvním pravidlem, použitá proměnná yytext je proměnná flexu, obsahující právě rozpoznaný token. Všechny ostatní znaky vstupu budou odpovídat druhému (všechny znaky kromě nové řádky) nebo třetímu pravidlu (nová řádka) a provedena příslušná akce - v tomhle případě se neprovede nic. Tyhle dvě pravidla v souboru nejsou zbytečně, protože defaultní pravidlo použité na všechen text neodpovídající žádnému pravidlu je jeho výpis na standardní výstup. Kdybychom nezadali žádná pravidla, vstupní soubor by se prostě okopíroval na výstup. Funkce main volá flexem vytvořenou funkci pojmenovanou defaultně yylex().

Způsob prohledávání textu

Tady se nabízí otázka, proč je e-mailová adresa zpracovaná prvním pravidlem a ne druhým, když by mohla odpovídat i jemu. Důvod je ten, že Flex při postupném průchodu vstupem hledá pravidlo s nejdelší shodou. V našem případě první pravidlo odpovídá celé adrese, zatímco druhé jenom jejímu prvnímu znaku. Kdyby byly nalezeny dvě pravidla se stejně dlouhou shodou, přednost má vždy to, které je uvedeno dřív.

%{
#include<stdio.h>
%}

%%
"text" {printf("1");}
(.|\n)* {printf("0");}
%%
main (int argc, char **argv)
{
yylex();
}

Program vytvořený z tohoto příkladu vypadá, že nahradí výskyt řetězce "text" symbolem 1 a ostatní znaky nahradí 0. To ale není pravda, ve skutečnosti nahradí obsah souboru obsahující právě text "text" znakem 1 a libovolný jiný soubor bude obsahovat jenom jednu 0. To proto, že když by byl obsah delší než čtyři znaky, bude celý odpovídat druhému pravidlu a teda bude vypsána jen jedna nula. Jen kdyby obsahoval právě jenom "text", pak první i druhé pravidlo budou odpovídat stejně dlouhému řetězci a použije se první z nich.

%{
#include<stdio.h>
unsigned int ty=0;
unsigned int yden=0;
unsigned int den=0;
%}

%%
"ty" ty++;
"yden" yden++;
"den" den++;
.
\n
%%
main (int argc, char **argv)
{
yylex();
printf("ty = %u, yden = %u, den = %u\n",ty,yden, den); }

Co když chceme spočítat výskyt výrazů v textu jako v předchozím případě? Kdybychom použili takovýhle kód, tak by výsledek nebyl správný. Zkuste si představit, co se stane, bude-li na vstupu slovo "tyden". Nejdřív s ním bude mečovat první pravidlo a započte se výskyt řetězce "ty". Vstup se o něj zkrátí a na zbytek bude použito třetí pravidlo a započte se výraz "den". Řetězec "yden" se nezapočte, ačkoliv v textu je a dokonce je jeho shoda se vstupem delší, než u obou ostatních pravidel. Při zpracování se ale neporovnává od znaku "y", který je prostě přeskočen. Co s tím?

Řešením by mohlo být přidání pravidla "tyden" {ty++;yden++;den++;}, ale to bychom museli řešit všechny možné překrytí vyhledávaných slov. Místo toho využijeme další zabudovanou funkci Flexu, funkci yyless(n). Ta způsobí, že se vše kromě prvních n znaků vrátí zpět do vstupního streamu a bude se znovu porovnávat. V příkladu nahradíme druhou sekci následujícím kódem a program už bude pracovat korektně.

"ty" {ty++;yyless(1);}
"yden" {yden++;yyless(1);}
"den" {den++;yyless(1);}
.
\n

V předchozím textu jsme se už seznámili s proměnnou yytext, která obsahuje rozpoznaný token. Neřekli jsme si ale, jakého je vlastně typu. To proto, že může mít jeden ze dvou typů, který si můžeme zvolit pomocí vložení %pointer nebo %array do první části definičního souboru.

Pointer
Použití typu ukazatel je výhodné kvůli rychlosti. Práce s yytext je rychlejší a je ošetřeno přetečení, pokud text odpovídající nějakému pravidlu je příliš dlouhý. Naopak má ale i některá omezení - můžeme sice modifikovat jeho obsah, ale nesmíme ho prodloužit. Navíc při použití funkce unput() ztratíme jeho obsah. Pokud není nastaveno jinak, je použitý typ ukazatel.
Array
S polem je sice pomalejší práce než s ukazatelem, ale na druhou stranu můžeme jeho obsah měnit podle libosti. Samozřejmě ale nemůžeme zapisovat za jeho konec. Délka pole definováno makrem YYLMAX, většinou je okolo 8 KB velké.

Pro práci s yytext je ještě užitečné znát proměnnou yyleng, která obsahuje délku řetězce yytext, a funkci yymore. Ta způsobí, že se po provedení zpracovávaného pravidla obsah yytext nesmaže, ale nový token se za něj připojí. Zase si to ukážeme na příkladu:

%{
#include<stdio.h>
%}

%%
"modra " yymore();
"zelena " yymore();
"krabice" printf("yytext=%s\n",yytext);
"cedule" printf("yytext=%s\n",yytext);
.
\n
%%
main (int argc, char **argv)
{
yylex();
printf("ty = %u, yden = %u, den = %u\n",ty,yden, den); }

Když pustíme výsledný program na nějaký vstupní text, vypíše nám každý výskyt řetězců "krabice", "cedule", "modra krabice", "modra cedule", "zelena krabice" a "zelena cedule". Ostatní nebude vypsán. Síla této funkce se ukáže, až se seznámíme s prací se stavovým automatem.

Jako poslední si ještě předvedeme funkci yyterminate() a makra ECHO a REJECT. yyterminate(), jak napovídá název, způsobí ukončení práce lexikálního analyzátoru. Automaticky je volána po zpracování celého vstupu, ale dá se zavolat i na předčasné ukončení yylex(). Makro ECHO se používá pro výpis yytext na standardní výstup.

Makro REJECT způsobí odmítnutí nalezeného mečování. Místo toho se vezme další možné pravidlo v pořadí, takže buď další stejné délky, ale uvedené později, případně se vezme pravidlo odpovídající kratšímu řetězci. Nejlépe to demonstrujeme zase na příkladu:

%{
#include<stdio.h>
%}

%%
"text" {printf("a"); REJECT;printf("b");}
"tex" {ECHO;}
(.|\n)
%%
main (int argc, char **argv)
{
yylex();
}

Tenhle program vypíše místo každého výskytu řetězce "text" na výstup "atex", řetězec "tex" na výstup zkopíruje a ostatní nevypíše.

Stavový automat

Na začátku textu jsme se už setkali s pojmem stavů, tady se na ně podíváme podrobněji. Předpokládám, že čtenář se už někdy setkal s konečnými automaty. Stavy ve Flexu jsou použity právě v tomto smyslu. Na začátku je laxikální analyzer v počátečním stavu, označovaném jako INITIAL. Ten je definován vždy. Uživatel má možnost dodefinovat stavy vlastní a doplnit pravidla v druhé části o specifikaci, ve kterých stavech se musí analyzer nacházet, aby bylo možné příslušné pravidlo použít. Definujeme-li si například stav STAV1, konstrukcí <STAV1> "ahoj" ECHO; určíme, že pokud se na vstupu vyskytuje řetězec "ahoj", bude vypsán na výstup, ale pouze, pokud je analyzer ve stavu STAV1.

%s STAV1
%x STAV2
%%
..

Na předchozím příkladu je demonstrováno, jak se v první části souboru nadefinují stavy STAV1 a STAV2. Stavy mohou být dvou typů - exclusiv a inclusiv.

exclusiv
definují se pomocí %x jmeno
jestliže je analyzer v exkluzivním stavu, provádí pouze ty pravidla, kde je stav uveden
inclusiv
definují se pomocí %s jmeno
analyzer provádí pravidla, kde je aktuální stav uveden, nebo kde není uveden žádný stav. Počáteční stav INITIAL je například inkluzivní (proto jsme zatím nemuseli psát k pravidlům stavy)

Pokud chceme během provádění kódu změnit stav, použijeme k tomu makro BEGIN(stav). Použití si ukážeme na prográmku, který zruší ve vstupním souboru všechny komentáře:

%{
#include<stdio.h>
%}
%x KOMENTAR1
%x KOMENTAR2
%%
"//" BEGIN(KOMENTAR1);
"/*" BEGIN(KOMENTAR2);
<KOMENTAR1>\n BEGIN(INITIAL);
<KOMENTAR2>"*/" BEGIN(INITIAL);
<KOMENTAR1,KOMENTAR2>(.|\n)
%%
main (int argc, char **argv)
{
yylex();
}

Změna hlavičky vygenerované funkce

Defaultně je funkce yylex() definovaná jako

int yylex()
{
... nějaký kód ...
}
To ale může být změněno předefinováním makra YY_DECL. Například když chceme předat funkci yylex() ukazatel typu void, použijeme tuto konstrukci:
#define YY_DECL int mujlex( a ) void *a;

Odkazy

http://www.gnu.org/software/flex
http://www.root.cz/clanek/679