Hlavní navigace

Flex - fast lexical analyzer generator (2)

Martin Srb 18. 5. 2001

V dnešním dílu se budeme věnovat regulárním výrazům a vytváření složitějších pravidel. Nejdříve však musím opravit některé chyby, kterých jsem se dopustil v příkladech v minulém dílu.

Zde si můžete stáhnout opravené verze všech příkladů.

Chtěl bych poděkovat za všechny komentáře, které přispěly k rychlému odhalení těchto chyb.

Protože je generátor flex choulostivý na odsazení řádek atd., budu nadále ke každému příkladu uvádět také odladěný zdrojový kód, který si můžete v případě zájmu stáhnout.

Vzory

Vzory jsou tvořeny zejména pomocí regulárních výrazů. Pomocí vzorů definujeme lexikální elementy, které hodláme v textu hledat.

Základní typy regulárních výrazů

  • libovolný řetězec je regulární výraz, který odpovídá sám sobě,
  • ‚.‘ – odpovídá libovolnému znaku,
  • [abc] – (výčet znaků) odpovídá jednomu ze znaků ‚a‘, ‚b‘ nebo ‚c‘,
  • [A-Z0–9] – odpovídá libovolnému velkému písmenu nebo číslici,
  • [^abc] – odpovídá libovolnému znaku kromě znaků ‚a‘, ‚b‘, ‚c‘.

Většina speciálních znaků (např. ‚.‘) ztrácí ve výčtu svůj řídící význam. Výjimku tvoří znaky ‚-[]\^‘. Výraz [abc*] je tedy chápán jako výskyt znaku ‚a‘, ‚b‘, ‚c‘ nebo ‚*‘. Znak ‚^‘ má ve výčtu řídící význam pouze pokud se vyskytuje na jeho začátku (tj. za otevírací závorkou). Pokud chceme, aby se ve výčtu vyskytovaly znaky ‚-[]\‘, musíme potlačit jejich řídící význam pomocí znaku ‚\‘. Následující program hledá ve vstupním textu speciální znaky ‚-[]\^‘. Jestliže některý z těchto znaků najde, vytiskne hlášku „Našel jsem znak:“. Ostatní znaky jsou pohlceny.

%%

[\-\[\]\\^] printf("Našel jsem znak:"); ECHO; printf("\n");
.|\n

Četnost výskytu

  • výraz* – libovolný počet výskytů,
  • výraz+ – alespoň jeden výskyt,
  • výraz? – nejvýše jeden výskyt,
  • výraz{2,5} – alespoň dva, nejvýše však pět výskytů,
  • výraz{2,} – dva a více výskytů,
  • výraz{4}  – právě čtyři výskyty.

Určení pozice

  • ^výraz – výraz na začátku řádku,
  • výraz$ – výraz na konci řádku (před znakem nový řádek).

Speciální kategorie znaků

  • [:alnum:] – tisknutelné znaky včetně bílých znaků,
  • [:alpha:] – pouze písmena,
  • [:blank:] – mezery a tabulátory,
  • [:cntrl:] – kontrolní znaky,
  • [:digit:] – číslice,
  • [:graph:] – tisknutelné znaky s výjimkou bílých znaků,
  • [:lower:] – malá písmena,
  • [:print:] – alfanumerické znaky,
  • [:punct:] – interpunkční znaky,
  • [:space:] – bílé znaky,
  • [:upper:] – velká písmena
  • [:xdigit:] – hexadecimální čísla.

Speciální znaky

  • \n – nová řádka
  • \t – tabulátor

Například celý řádek s libovolným obsahem by odpovídal následujícímu regulárnímu výrazu:

^.*\n

Logické operátory

  • výraz1výraz2 – spojení dvou výrazů,
  • výraz1|výraz2 – výraz1 nebo výraz2,
  • výraz1/výraz2 – výraz1 za předpokladu, že nastal výraz2.

Na první pohled se může zdát, že vzory výraz1výraz2 a výraz1/výraz2 se chovají stejně. Skutečně, oběma vzorům odpovídá tentýž textový řetězec. Druhé pravidlo však vrátí text odpovídající výrazu výraz2 zpět do vstupního souboru. To znamená, že tento text může být ještě jednou zpracován jiným pravidlem. Vyzkoušejte si následující příklad:

%%

jedna/dva ECHO; printf("\n"); /*zkuste zamenit vzor jedna/dva za jednadva*/
dva ECHO; printf("\n");
.|\n

Speciální konstrukce

  • \řídící_znak – odstíní význam řídícího znaku (např. *,\^ atd.),
  • \0 – znak s ASCII kódem 0,
  • \123 – znak s ASCII kódem 123 v osmičkové soustavě,
  • \x2a – znak s ASCII kódem 2a v hexadecimální soustavě,
  • (výraz) – závorky udávají prioritu, např. (výraz|výraz2)*,
  • {identifikátor} – viz identifikátory v definiční sekci,
  • „řetězec“ – má význam řetězce uzavřeného v uvozovkách,
  • <<EOF>> – konec souboru.
  • <s>výraz – odpovídá výrazu za předpokladu, že se lexikální analyzátor nachází ve stavu s.

Akce

Jestliže část prozkoumávaného textu vyhoví nějakému vzoru, bude spuštěna akce příslušného pravidla. Akce je tvořena libovolným kódem napsaným pomocí programovacího jazyka C. Generátor flex navíc poskytuje funkce, proměnné, direktivy a makra, které umožňují zpracovávat vybraný text, řídit skenování vstupního souboru, atd.

Nejdůležitější proměnnou je bezesporu globální proměnná yytext. V této proměnné je uložen text, který byl vybrán vzorem. Proměnná yytext může být definována dvěma různými způsoby: jako ukazatel na typ char nebo jako pole znaků. Jakého typu proměnná yytext bude, můžete ovlivnit uvedením direktivy %pointer nebo %array v definiční sekci. V případě, že neuvedete žádnou z direktiv, bude automaticky použit ukazatel na typ char. Proměnná yytext coby ukazatel zaručí, že nedojde k přetečení v případě, že text vybraný vzorem bude příliš dlouhý. Další výhodou je vyšší rychlost programu. Použití ukazatele na typ char má i své stinné stránky. Například obsah proměnné yytext můžete modifikovat, ale nesmíte přitom zvětšit jeho délku. Voláním funkce unput() proměnnou yytext smažete. Pokud zvolíte jako typ pole znaků, můžete si s proměnnou yytext dělat co chcete. Některé verze generátorů lex dokonce vyžadují, aby proměnná yytext byla definována jako pole znaků. Délka pole znaků je dána konstantou YYLMAX, která je přednastavena na hodnotu 8192. Tuto hodnotu můžete změnit následujícím způsobem:

%array

    #define YYLMAX 100
%%
  /*prázdná sekce pravidel*/
%%
main()
 {
   /*Vytiskne hodnotu konstanty YYLMAX*/
   printf("YYLMAX=%d\n",YYLMAX);
 }

Někdy může být užitečné znát délku řetězce, který je uložen v proměnné yytext. V programovacím jazyce C na to máme funkci strlen(), nicméně flex nám tuto informaci nabízí prostřednictvím globální proměnné yyleng. Tak proč toho nevyužít.

Lexikální skener vyhledává v textu části, které odpovídají vzorům. Pokud takovou část textu najde, uloží ji do proměnné yytext a její předchozí obsah zruší. Pomocí funkce yymore() říkáte lexikálnímu skeneru, že příští text, který vyhoví nějakému vzoru, má být k obsahu proměnné yytext připojen. Jestliže následujícímu programu dáte na vstup řetězec ferda-mravenec, výstupem bude:

yytext=ferda-mravenec, yyleng=14

Nezapomínejte, že implicitním pravidlem je cosi jako:

.|\n ECHO;

Proto každý znak, který neodpovídá žádnému pravidlu, bude vytisknut na standardní výstup. Jestliže dáte na vstup následujícího programu řetězec ferda- mravenec, uplatní se implicitní pravidlo a výstup bude:

ferda- yytext=mravenec, yyleng=8

Pokud zapomenete na implicitní pravidlo, může to být trochu matoucí. Příští text vybraný pravidlem (v tomto případě implicitním) totiž není mravenec, ale mezera.

%%
ferda-    yymore();
mravenec  printf("yytext=%s, yyleng=%d\n",yytext,yyleng);

Funkce yyless(n) vrací celý obsah proměnné yytext kromě n prvních znaků zpět do vstupního souboru. Tento text tedy může být znovu zpracován jiným pravidlem (viz následující příklad).

%%
"jedna dve" printf("%s\n",yytext);yyless(6);
dve         printf("%s\n",yytext);
.|\n

yyless(0) vrací do vstupního souboru celý obsah proměnné yytext. To ovšem vede k vytvoření nekonečné smyčky. Použít funkci yyless() s parametrem 0 má smysl pouze v případě, že zároveň přepneme lexikální skener do jiného stavu pomocí direktivy BEGIN(jméno stavu). O stavech si budeme povídat v příštích dílu.

Jak jistě tušíte, funkce unput() vrací jeden znak do vstupního souboru. Následující kód vrátí řetězec jedna do vstupního souboru a obklopí ho závorkami.

jedna {
       int i;
       char *yycopy;
       yycopy = strdup(yytext);
       unput(')');
       for(i=yyleng -1; i>=0; i--)
         {
          unput(yycopy[i]);
         }
       unput('(');
       free(yycopy);
      }

Je potřeba si uvědomit, že funkce unput() vrací znak vždy na začátek vstupního souboru, proto musí být znaky navraceny v opačném pořadí. Jestliže je proměnná yytext typu ukazatel na typ char, bude její obsah voláním unput() funkce smazán. Proto je v příkladu použita proměnná yycopy, do které je před voláním funkce unput() uložena kopie proměnné yytext. Jiným možným řešením by bylo definovat proměnnou yytext jako pole znaků pomocí direktivy %array.

Předchozí příklad by sám o sobě neměl smysl, protože vede na nekonečnou smyčku. Řešením může být použití stavového automatu. Protože jsme však stavový automat ještě neprobírali, uvádím zde krátký příklad bez vysvětlení. Tento program na vstupní řetězec jedna reaguje výstupem (jedna).

Na rozdíl od funkce unput() čte funkce input() jeden znak ze vstupního souboru. Pomocí makra terminte() zase můžete ukončit skenovací funkci yylex(). Funkce, která funkci yylex() zavolala, obdrží jako návratový kód nulu. Standardně se makro terminte() použije v případě, že bylo dosaženo konce souboru.

Speciální direktivu ECHO jsem již mnohokrát použil v příkladech. To, že tiskne obsah proměnné yytext na standardní výstup, pro vás asi nebude žádnou novinkou.

Jestliže lexikální skener najde ve vstupním souboru více částí textu, které vyhovují různým pravidlům, zvítězí to pravidlo, které vybralo nejdelší část textu ze vstupního souboru. Lexikální skener pak pokračuje dále v prohledávání vstupního souboru a alternativy, které v porovnávání délek prohrály, jsou zavrženy. Pomocí speciální direktivy REJECT můžete lexikální skener donutit k tomu, že místo prohledávání vstupního souboru označí za další vyhovující text druhou nejdelší alternativu (viz následující příklad).

     int word_count=0;
%%
ferda     printf("Nasel jsem retezec:");ECHO;printf("\n");REJECT;
[^ \t\n]+ ++word_count;
.|\n
%%
main()
{
 yylex();
 printf("pocet slov=%d\n",word_count);
}

Pokud bych nepoužil speciální direktivu REJECT, nebyly by výskyty slova ferda započítány do součtu slov.

Na závěr si ještě povíme, jak si ušetřit pár úhozů do klávesnice. Jestliže má několik pravidel stejnou akci, stačí ji uvést pouze jednou. V ostatních případech uvedeme znak ‚|‘ (viz následující příklad).

%%
ferda |
mravenec ECHO; printf("\n");
.|\n

V příštím dílu už určitě dojde na slibované stavové automaty.

Našli jste v článku chybu?

22. 5. 2001 21:54

Martin Saturka (neregistrovaný)

Ahoy, lex se asi casto pouziva pro yacc. Z info bison jsem tedy chtel predelat RPN Calc priklad, aby vyuzival flex. I pres snahu o pouziti YACC interface ukazky z info flex mi to ale vubec nejede. Teda skompiluje se to, ale pri pouziti operatoru mi to hodi parse error. Nemohl byste napsat nejakou drobnou ukazku? Diky

21. 5. 2001 21:14

Martin Srb (neregistrovaný)

Nevím jak je to definováno v normě POSIX, ovšem v generátoru flex to funguje tak, jak jsem uvedl v článku. Vyzkoušejte si příklad:
http://www.root.cz/data/flex/pr1.ll


Podnikatel.cz: EET: Totálně nezvládli metodologii projektu

EET: Totálně nezvládli metodologii projektu

Podnikatel.cz: Přehledná titulka, průvodci, responzivita

Přehledná titulka, průvodci, responzivita

Root.cz: Pinebook: linuxový notebook za 89 dolarů

Pinebook: linuxový notebook za 89 dolarů

Lupa.cz: Propustili je z Avastu, už po nich sahá ESET

Propustili je z Avastu, už po nich sahá ESET

Lupa.cz: Insolvenční řízení kvůli cookies? Vítejte v ČR

Insolvenční řízení kvůli cookies? Vítejte v ČR

Měšec.cz: Air Bank zruší TOP3 garanci a zdražuje kurzy

Air Bank zruší TOP3 garanci a zdražuje kurzy

DigiZone.cz: Sony KD-55XD8005 s Android 6.0

Sony KD-55XD8005 s Android 6.0

Měšec.cz: Jak levně odeslat balík přímo z domu?

Jak levně odeslat balík přímo z domu?

Vitalia.cz: Paštiky plné masa ho zatím neuživí

Paštiky plné masa ho zatím neuživí

Vitalia.cz: Jmenuje se Janina a žije bez cukru

Jmenuje se Janina a žije bez cukru

Vitalia.cz: Spor o mortadelu: podle Lidlu falšovaná nebyla

Spor o mortadelu: podle Lidlu falšovaná nebyla

Vitalia.cz: Co pomáhá dítěti při zácpě?

Co pomáhá dítěti při zácpě?

Měšec.cz: Jak vymáhat výživné zadarmo?

Jak vymáhat výživné zadarmo?

Lupa.cz: Teletext je „internetem hipsterů“

Teletext je „internetem hipsterů“

Vitalia.cz: Mondelez stahuje rizikovou čokoládu Milka

Mondelez stahuje rizikovou čokoládu Milka

DigiZone.cz: ČRa DVB-T2 ověřeno: Hisense a Sencor

ČRa DVB-T2 ověřeno: Hisense a Sencor

120na80.cz: Horní cesty dýchací. Zkuste fytofarmaka

Horní cesty dýchací. Zkuste fytofarmaka

Podnikatel.cz: Udávání kvůli EET začalo

Udávání kvůli EET začalo

120na80.cz: Jak oddálit Alzheimera?

Jak oddálit Alzheimera?

Podnikatel.cz: 1. den EET? Problémy s pokladnami

1. den EET? Problémy s pokladnami