Delcom - Ukázka stavového automatu v C

Jedná se o jednoduchou aplikaci, která odstraňuje ze vstupního textu Céčkové komentáře (/* */ a //). Je to jeden z ukázkových programů k článkům o filtrech, které se tu v budoucnosti objeví.

Pracuje se standardním vstupem/výstupem, takže pokud ji chceme použít na soubory, uděláme to následujícím způsobem:

$ ./delcom < vstup.c > vystup.c

K programu jsem také napsal jednoduchý bash skript, který spustí program pro každý .c soubor ve složce. Program samotný je plně multiplatformní (a skript pro Windows není těžké napsat). Jinak jestli vás nenapadá žádné praktické využití, tak to zkuste spustit kolegovi programátorovi v nějakém rozsáhlém projektu (a doufejte, že má zálohu, protože jinak vás zabije )

Stavový automat

Teď ta zajímavější část.. Program slouží jako praktická ukázka použití tzv. stavového automatu - program, který na základě aktuálního stavu a vstupu provede konkrétní úlohu. Stavový automat má určitý počet stavů, počáteční stav, konečný stav, množinu vstupů a množinu výstupů. V praxi to znamená, že někde začínáme (nejčastěji stav 0) a na základě různého vstupu se přepíná do jiných stavů (například uživatel zadá číslo -> umocni ho a vypiš, přejdi do stavu 2). Různé stavy reagují na stejný vstup jinak. Proč stavový automat? Podíváme se na naši úlohu..

Úkolem je napsat program, který z textu odstraní Céčkové komentáře. Prvně se musíme zamyslet, jak vůbec komentáře v C fungují.

• lomítko a hvězdička - začíná blokový komentář (/* */)
• lomítko a lomítko - začíná řádkový komentář (//)
• uvozovky - řetězcový literál, jeho obsah se nesmí změnit (pozor na \")
• uvozovky se mohou objevit i jako znak! (mezi apostrofy)
• komentáře jsou nahrazeny mezerou

Nevypadá to tak složitě, že? Ale nezapomeňme, že komentáře nemusí být zapsány rozumně... Co například:

a = b //* tady dělím */c;

Vypadá to škaredě, ale je to naprosto validní použití komentáře. Po odstranění komentářů preprocesorem bude výsledek následující:

a = b / c;

EDIT: Takové použití komentáře je validní pouze při použití C89 (ANSI), od C99 výše je již zbytek řádku brán jako komentář..

Tak to jsme si snad vyjmenovali všechny možnosti (snad jsem na nic nezapomněl). Nyní implementace. Když se zamyslíme nad problémem, mohli bychom samozřejmě použít if-else. Ale velmi brzy bychom zjistili, že je to velmi složité a nepřehledné (jestli se vám někomu chce, tak to určitě můžete zkusit a pak porovnáme kód). Proto to budeme realizovat jako stavový automat.

Zde je schéma (.odg a .pdf verze přiložena v archívu):

Pokud jste nikdy nic takového neviděli, tak vám to určitě připadá jako nepřehledná a složitá šílenost. Ale ve skutečnosti na tom nic komplikovaného není. "Kolečka" jsou stavy a šipky mezi nimi ukazují, jak se mění. U každé šipky je poznámka, která říká jaký je vstup a (volitelně) výstup.

Ukážeme si to na praktickém příkladě. Když jsme v počátečním stavu (stav 0) a na vstupu se objeví uvozovky, program se přepne do stavu 4 a vypíše uvozovku. Pak vypisuje jakékoliv příchozí znaky (c out(c)), než se zas objeví uvozovky. Pokud by se objevilo zpětné lomítko, existuje možnost, že za ním budou uvozovky, musíme proto do stavu 9, který vypíše jakýkoliv znak nacházející se za lomítkem. Když se konečně objeví normální uvozovky, jsou vypsány a program je přepnut do stavu 0. Analogicky to platí pro stav 7, ale místo uvozovky řešíme apostrof.

Stejně tak druhý směr - pokud na vstup přijde lomítko (pokud cokoliv jiného, jen se to vypíše a zůstáváme ve stavu 0), přesuneme se do stavu 1 (tentokrát nevypíšeme nic). Pokud nám teď přijde hvězdička, je jasné, že začíná komentář -> přesouváme se do stavu 2 a až do konce komentáře všechno mažeme (jen to přečteme a nevypíšeme). Pokud přijde jiný znak, vypíšeme lomítko a ten znak (lomítko bylo v tomto případě dělení) a vrátíme se do stavu 0. Pokud přijde další lomítko, přepneme se do stavu 5. Pokud pak přijde hvězdička, jedná se o děleno a komentář, pokud cokoliv jiného, jedná se o řádkový komentář, přesouváme se do stavu 6 a odstraňujeme vše až do konce řádku. Pokud bychom náhodou měli pouze komentář a za ním hned konec řádku, jdeme rovnou do stavu 0.

Tak... To je snad vše. Zdrojové kódy jsou přiloženy v archívu. Pokud chcete, určitě si to můžete zkompilovat pro Windows. Jakékoliv reakce samozřejmě uvítám..

Poznámka: Alternativní verze, která se chová různě pro c89 a c99 je v komentářích.

Galerie

Program byl vytvořen v roce 2015.