Hlavní navigace

Flex - fast lexical analyzer generator (3)

Martin Srb 8. 6. 2001

Dnešní díl bude věnován stavovým automatům. Teprve stavové automaty dělají z generátoru flex opravdu silný nástroj.

Pro vytváření stavových automatů využívá generátor flex podmínek (tzv. start conditions), kterými podmiňuje platnost jednotlivých pravidel. Syntaxe takové podmínky je následující:

<jmeno_stavu> pravidlo

Pokud se lexikální skener nachází v požadovaném stavu, je dané pravidlo aktivní. Mezi stavy stavového automatu přepínáme pomocí speciální direktivy BEGIN(jméno_stavu).

Stavy se deklarují v definiční sekci. Každý stav musí být uveden na samostatné řádce a musí mu bezprostředně předcházet řetězec %s nebo %x, který udává jeho typ.

%x stav1
%s stav2

Generátor flex rozlišuje stavy typu exclusive (%x) a typu inclusive (%s). Implicitním stavem lexikálního skeneru je INITIAL. V tomto stavu se nachází každý lexikální skener bezprostředně po startu. Ve stavu INITIAL jsou aktivní všechna nepodmíněná pravidla.

<stav1> pravidlo /*podmíněné pravidlo*/
prvidlo2 /*nepodmíněné pravidlo*/

Jestliže se lexikální skener nachází ve stavu typu inclusive, jsou aktivní kromě pravidel podmíněných tímto stavem i všechna nepodmíněná pravidla. V případě stavů typu exclusive je tomu přesně naopak.

Pokusíme se nyní vytvořit program, který odstraní ze zdrojového kódu komentář. Budeme předpokládat, že zdrojový text programu je napsán v programovacím jazyce C. Komentář je tedy uzavřen mezi znaky: /**/. Algoritmus takovéhoto programu můžeme rozdělit na dvě části. První část bude tisknout libovolný znak na standardní výstup. Druhá část naopak libovolný znak pohltí. Přepínání mezi částí jedna a částí dva se bude dít v okamžiku, kdy se ve vstupním textu objeví začátek nebo konec komentáře. Jak asi tušíte, nejvýhodnější bude využít stavový automat.

Pro náš příklad budeme potřebovat dva stavy. Využijeme-li implicitního stavu INITIAL, stačí nám definovat pouze jeden nový stav typu exclusive. Náš program tedy bude vypadat následovně:

%x comment /*nový stav*/

%%

"/*" BEGIN(comment); /*Začátek komentáře, přepni se do stavu comment*/
<comment>"*/" BEGIN(INITIAL); /*Konec komentáře, vrať se do stavu INITIAL*/
<comment>.|\n

Jestliže chceme, aby nějaké pravidlo bylo platné ve všech stavech stavového automatu, předřadíme mu řetězec <*>. Například pravidlo:

<*>.|\n ECHO;

vytiskne všechny znaky nezávisle na stavu, ve kterém se lexikální skener nachází.

Lexikálnímu skeneru můžeme nastavit určitý stav ještě před začátkem skenování vstupního souboru. Toho dosáhneme tak, že uvedeme direktivu BEGIN(jméno_stavu) na začátku sekce pravidel. Tato direktiva musí být na řádku odsazena. Dokonce můžeme nastavení počátečního stavu podmínit hodnotou nějaké globální proměnné.

     int set_stav;
%x muj_stav
%%
     if (set_stav)
     BEGIN(muj_stav);
<muj_stav> ....
.....

Až váš stavový automat zabloudí ve svých stavech, přijde vám vhod makro YY_START. Toto makro vrací číslo aktuálního stavu. Stavy jsou totiž kromě svého názvu také reprezentovány celým číslem. BEGIN(název_stavu) je tedy ekvivalentní BEGIN(číslo_stavu). Při řešení složitějších úloh se můžeme dostat do situace, kdy potřebujeme znát název předchozího stavu. Velmi často si totiž potřebujeme z nějakého stavu odskočit a pak se do něj zase vrátit. V takovém případě si uložíme číslo výchozího stavu před tím, než tento stav opustíme (viz následující příklad).

     int stav;
%x stav1
%x stav2
%%

<stav1> {
         akce ...
         .......
     stav=YY_START;
     BEGIN(stav2)
        }

<stav2> {
         akce ...
         .......
     BEGIN(stav)
        }

Pokud je situace opravdu složitá, můžeme stavy ukládat do zásobníkové paměti. O vytvoření zásobníkové paměti se nemusíme starat, vytvoří ji za nás generátor flex. Stačí na začátku definiční sekce uvést direktivu %option stack. Pro práci se zásobníkovou pamětí slouží následující funkce:

  • void yy_push_state(int new_state) – uloží do zásobníku aktuální stav a přepne do stavu new_stav.
  • void yy_pop_state() – vybere z vrcholu zásobníku číslo stavu a přepne do něj.
  • int yy_top_state() – vrátí obsah vrcholu zásobníku.

Následující příklad demonstruje použití zásobníkové paměti. Na začátku se lexikální skener přepne do stavu s1. V tomto stavu setrvá do té doby, než ve vstupním souboru nalezne řetězec „to s2“. Poté uloží aktuální stav (tedy stav s1) do zásobníku a přepne se do stavu s2. V tomto stavu setrvá, dokud nenalezne ve vstupním souboru řetězec „back“. A tak stále dokola.

%option stack

%x s1
%x s2

%%

     BEGIN(s1);
<s1>"to s2" printf("stav s1->s2\n"); yy_push_state(s2);
<s2>"back"  printf("stav s2->s1\n"); yy_pop_state();
<*>.|\n

Stavy mohou obsahovat velký počet pravidel. Abychom nemuseli před každé pravidlo pracně psát <název_stavu>, můžeme použít následující konstrukci:

<stav1>{
        pravidlo1
    pravidlo2
        ....
       }

Na závěr si uvedeme složitější příklad. Znáte to, někde v programu otevřete blok a pak ho zapomenete uzavřít. Kompilátor stále hlásí chybu a vy nemůžete přijít na to, kde vám chybí závorka. Následující program kontroluje, zda každá závorka ‚{‘ resp.‚(‘ má svoji závorku ‚}‘ resp. ‚)‘. Pokud najde nějakou nesrovnalost, vytiskne chybovou hlášku včetně čísla podezřelého řádku.

%option stack /*zapíná podporu zásobníkové paměti pro stavy stavového automatu*/

%x s_comment  /*Je-li nalezen začátek komentáře (/*), přepne se     */
              /*stavový automat do stavu s_comment. V tomto stavu   */
              /*ignoruje všechny znaky do té doby, než je nalezen   */
              /*konec komentáře (*/)                                */
%x s_string   /*Lexikální skener se v tomto stavu chová stejně jako */
              /*ve stavu s_comment. Tento stav slouží pro ignorování*/
              /*řetězcových konstant v textu.                       */

%x s_char     /*Lexikální skener se v tomto stavu chová stejně jako */
              /*ve stavu s_comment. Tento stav slouží pro ignorování*/
              /*znakových konstant '{' atd. v textu                 */

  int line_c = 1; /*Číslo řádku*/
  int *stack_a;   /*Zásob. pro závorky { - nejedná se o zásob. pro stavy st. automatu*/
  int *p_a;       /*Ukazatel na vrchol zásobníku stack_a*/
  int *stack_b;   /*Zásob. pro závorky ( - nejedná se o zásob. pro stavy st. automatu*/
  int *p_b;       /*Ukazatel na vrchol zásobníku stack_b*/
%%

"{"  *p_a=line_c;p_a++; /*Push - uloží číslo řádku, kde se vyskytla závorka { */
"}" { if (p_a==stack_a)
      {
         printf("%d -> ERROR(})\n",line_c);
      }
     else
      {
        p_a--;         /*Pop*/
      }
    }

"("  *p_b=line_c;p_b++; /*Push - uloží číslo řádku, kde se vyskytla závorka ( */
")" { if (p_b==stack_b)
      {
         printf("%d -> ERROR())\n",line_c);
      }
     else
      {
        p_b--;         /*Pop*/
      }
    }


"/*" yy_push_state(s_comment);  /*ignorujeme komentář*/
<s_comment>"*/" yy_pop_state();

/*ignorujeme závorky, které jsou součástí řetězcových konstant*/
\" yy_push_state(s_string);
<s_string>\" yy_pop_state();

/*ignorujeme závorky, které se vyskytují jako znakové konstanty '{' atd.*/
\' yy_push_state(s_char);
<s_char>\' yy_pop_state();

<*>.                            /*ignorujeme, co zbylo*/
<*>\n line_c++;                 /*počítáme řádky*/

%%
main()
  {
     if ((stack_a=(int*)calloc(256,sizeof(int))) == NULL)
      {
    exit(1);
      }

     if ((stack_b=(int*)calloc(256,sizeof(int))) == NULL)
      {
    exit(1);
      }

      p_a=stack_a;
      p_b=stack_b;

      yylex();
      while (p_a != stack_a) /*Vytiskneme, co zbylo v zásobníku závorek { */
        {
     p_a--;
     printf("%d -> ERROR(})\n",*p_a);
        }
      while (p_b != stack_b) /*Vytiskneme, co zbylo v zásobníku závorek ( */
        {
     p_b--;
     printf("%d -> ERROR())\n",*p_b);
        }
  }

V příštím dílu se budeme věnovat zpracování více vstupních souborů a možná dojde i na spolupráci s programem bison.

Našli jste v článku chybu?

4. 4. 2006 17:57

ND (neregistrovaný)
je tomu uz hodne davno, co tento clanek vysel. Kdy vyjde dalsi? ja chcu vic :)

8. 6. 2001 20:14

Freza (neregistrovaný)

Skvely clanek, takovych by tu melo byt vice...

DigiZone.cz: ČRo rozšiřuje DAB do Berouna

ČRo rozšiřuje DAB do Berouna

Podnikatel.cz: EET zvládneme, budou horší zákony

EET zvládneme, budou horší zákony

Lupa.cz: Proč firmy málo chrání data? Chovají se logicky

Proč firmy málo chrání data? Chovají se logicky

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

Přehledná titulka, průvodci, responzivita

120na80.cz: Pánové, pečujte o svoje přirození a prostatu

Pánové, pečujte o svoje přirození a prostatu

Podnikatel.cz: Víme první výsledky doby odezvy #EET

Víme první výsledky doby odezvy #EET

DigiZone.cz: ČT má dalšího zástupce v EBU

ČT má dalšího zástupce v EBU

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

Jak vymáhat výživné zadarmo?

Vitalia.cz: Jsou čajové sáčky toxické?

Jsou čajové sáčky toxické?

Lupa.cz: UX přestává pro firmy být magie

UX přestává pro firmy být magie

Podnikatel.cz: Babiše přesvědčila 89letá podnikatelka?!

Babiše přesvědčila 89letá podnikatelka?!

Podnikatel.cz: Na poslední chvíli šokuje vyjímkami v EET

Na poslední chvíli šokuje vyjímkami v EET

Měšec.cz: U levneELEKTRO.cz už reklamaci nevyřídíte

U levneELEKTRO.cz už reklamaci nevyřídíte

Vitalia.cz: Říká amoleta - a myslí palačinka

Říká amoleta - a myslí palačinka

Lupa.cz: Teletext je „internetem hipsterů“

Teletext je „internetem hipsterů“

Podnikatel.cz: Prodává přes internet. Kdy platí zdravotko?

Prodává přes internet. Kdy platí zdravotko?

Měšec.cz: Finančním poradcům hrozí vracení provizí

Finančním poradcům hrozí vracení provizí

Měšec.cz: Kdy vám stát dá na stěhování 50 000 Kč?

Kdy vám stát dá na stěhování 50 000 Kč?

Lupa.cz: Google měl výpadek, nejel Gmail ani YouTube

Google měl výpadek, nejel Gmail ani YouTube

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

EET: Totálně nezvládli metodologii projektu