Delcom - Ukázka stavového automatu v C

C++ Linux 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):

Diagram stavového automatu

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.

 

Stáhnout

Staženo 83x (131.79 kB)
Aplikace je včetně zdrojových kódů v jazyce C

 

  Aktivity (1)

Program pro vás napsal David Novák
Avatar
Autor v současné době studuje FIT VUT Brno a zajímá se především o nízkoúrovňové programování (C/C++, ASM) a návrh hardwaru (VHDL). Je zde také členem výzkumného týmu ANT@FIT (Accelerated Network Technologies).

Jak se ti líbí článek?
Celkem (4 hlasů) :
55555


 


Miniatura
Všechny články v sekci
Programování v jazyce C v Linuxu
Miniatura
Následující článek
Céčko a Linux – Makefile

 

 

Komentáře
Zobrazit starší komentáře (9)

Avatar
tomisoka
Redaktor
Avatar
tomisoka:

Celkem pěkná ukázka stavového automatu.

Část kódu, která by se měla starat o:

./delcom < vstup.c > vystup.c

je odstraněna úmyslně nebo jen nějakým nedopatřením?

Jinak zkusil jsem vytvořit variantu bez stavového automatu a nějak se mi nezdá, že by to bylo složité/nepřeh­ledné:

#include <stdio.h>
#include <stdint.h>

void endStr(FILE *inF, FILE *outF, int ctrlC, uint32_t maxC){
  int in, i=0;
  while((in=fgetc(inF))!=EOF && i<=maxC){
    fputc(in,outF);
    if(in==ctrlC)return;
    if(in=='\\'){
      if((in=fgetc(inF))==EOF)break;
      fputc(in,outF);
    }++i;
  }
}

void endMultiRowCom(FILE*inF, FILE *outF){
  int in;
  while((in=fgetc(inF))!=EOF){
    while(in=='*'){
      if((in=fgetc(inF))==EOF)break;
      if(in=='/')return;
    }if(in=='\n')fputc('\n', outF);
  }
}

void delcom(FILE *inF, FILE*outF){
  int in;
  while((in=fgetc(inF))!=EOF){
    if(in=='\"'){
      fputc('\"', outF);
      endStr(inF, outF, '\"',-1);
    }else if(in=='\''){
      fputc('\'', outF);
      endStr(inF, outF, '\'', 1);
    }else if(in=='/'){
      if((in=fgetc(inF))==EOF)break;
      if(in=='*')endMultiRowCom(inF, outF);
      else if(in=='/'){/*
        if((in=fgetc(inF))==EOF)break;
        if(in=='*'){
          fputc('/', outF);
          endMultiRowCom(inF, outF);
        }else{*/
          while((in=fgetc(inF))!=EOF)if(in=='\n')break;
          fputc('\n', outF);
        //}
      }
      else{
        fputc('/', outF);
        fputc(in, outF);
        if(in=='\"')endStr(inF, outF, '\"',-1);
        if(in=='\'')endStr(inF, outF, '\'',1);
      }
    }else fputc(in, outF);
  }
}

int main(int argc, char **argv){
  FILE *inF, *outF;

  if(!(inF = fopen(argv[1], "r")))fprintf(stderr, "Input file cannot be open!\n");
  if(!(outF = fopen(argv[2], "w")))fprintf(stderr, "Output file cannot be open!\n");

  delcom(inF, outF);

  fclose(inF);
  fclose(outF);
  return 0;
}

Zakomentoval jsem tam část starající se o případy jako:

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

Přijde mi to jako zbytečné, nikdo to neudělá a i GCC vezme ten řádkový komentář.

Editováno 24.2.2015 18:16
 
Odpovědět 24.2.2015 18:14
Avatar
David Novák
Tým ITnetwork
Avatar
Odpovídá na tomisoka
David Novák:

Jop.. Právě teď jsem to řešil.. ;)

C89 to bere, C99 a výš to bere jako řádkový komentář..
V článku jsem to opravil, ale zatím to čeká na schválení.

Vlastně jsem to od vydání docela dost upravil, protože jsem tam našel několik nedostatků.
Takže jsem to teď i přepsal, aby to počítalo s C89 vs C99 (nastavíš si argumentem při spuštění).

Práce se souborem je vynechaná úmyslně.. ;) Zkoušel jsem si u toho jak napsat skript v bashi, co projíždí soubory a přesměrovává je..

/******** delcom.c *********
 *
 * Autor: David Novák
 * Verze: 1.2
 * Datum: 23. 2. 2015
 * Pozn.: Program defaultně pracuje se standardem C99.
 *        Pokud chcete standard C89, spusťte ho s argumentem -c89.
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main(int argc, char **argv)
{
  int std = 99;   // používaný standard Céčka (kvůli řádkovým komentářům)
  int stav = 0;
  int c;

  if (argc > 1)
    if (strcmp(argv[1], "-c89") == 0 || strcmp(argv[1], "-ansi") == 0)
      std = 89;

  while ((c = getchar()) != EOF)
  {
    switch(stav)
    {
      case 0:   // výchozí stav
        if (c == '/')
          stav = 1;
        else if (c == '"')
        {
          stav = 4;
          putchar('"');
        }
        else if (c == '\'')
        {
          stav = 6;
          putchar('\'');
        }
        else
          putchar(c);
        break;

      case 1:   // lomítko
        if (c == '*')
          stav = 2;
        else if (c == '/')
          if (std != 89)
            stav = 8;
          else
            putchar(c);
        else
        {
          stav = 0;
          putchar('/');
          putchar(c);
        }
        break;

      case 2:   // blokový komentář
        if (c == '*')
          stav = 3;
        break;

      case 3:   // hvězdička
        if (c == '/')
        {
          stav = 0;
          putchar(' ');
        }
        else if (c != '*')
          stav = 2;
        break;

      case 4:   // uvozovky - řetězcový literál
        if (c == '"')
          stav = 0;
        else if (c == '\\')
          stav = 5;
        putchar(c);
        break;

      case 5:   // zpětné lomítko
        putchar(c);
        stav = 4;
        break;

      case 6:   // apostrof
        if (c == '\'')
          stav = 0;
        else if (c == '\\')
          stav = 7;
        putchar(c);
        break;

      case 7:   // zpětné lomítko
        putchar(c);
        stav = 6;
        break;

      case 8:   // řádkový komentář
        if (c == '\n')
        {
          putchar('\n');
          stav = 0;
        }
        break;

    } // end_switch
  } // end_while

  if (stav != 0)
    fprintf(stderr, "Unknown error.\n");

  return 0;
}

Jinak čísla stavů v tomto kódě neodpovídají grafu.. A snad už tam konečně nejsou žádné chyby.. :D

A myslím, že pomocí stavového automatu je to o hodně čitelnější.. Zvlášť pro další osoby :)

Editováno 24.2.2015 18:28
Odpovědět 24.2.2015 18:27
Chyba je mezi klávesnicí a židlí.
Avatar
David Novák
Tým ITnetwork
Avatar
David Novák:

Graf pro tuto verzi.

Odpovědět 24.2.2015 18:30
Chyba je mezi klávesnicí a židlí.
Avatar
David Novák
Tým ITnetwork
Avatar
Odpovídá na tomisoka
David Novák:

Jinak ještě bych podotknul, že tvoje řešení bude při velkých množstvích textu o dost pomalejší - volání funkce není úplně triviální.. Musí se uložit obsah registrů na zásobník, načíst hodnoty, vykonat funkci a hodnoty ze zásobníku zase obnovit..

A.. V tom kódu se fakt vyznáš? o_O Nemáš to odsazené.. A ani tam nejsou mezery.. Louskal jsem to teda docela dlouho.. Jestli jo, tak klobouk dolů ;)

Odpovědět 25.2.2015 15:44
Chyba je mezi klávesnicí a židlí.
Avatar
tomisoka
Redaktor
Avatar
Odpovídá na David Novák
tomisoka:

No tak jsem to ještě zkrátil a zbavil se funkcí ( to zpomalení mě nějak nenapadlo):

#include <stdio.h>
#include <stdint.h>

void delcom(FILE *inF, FILE*outF, uint32_t std){
  int in, ctrlC;
  uint32_t maxC, i;

  while((in=fgetc(inF))!=EOF){
    while(in=='/'){//while kvuli -c89 //komentare
      if((in=fgetc(inF))==EOF)break;
      if(in=='*'){
        while(in && (in=fgetc(inF))!=EOF){
          while(in=='*'){
            if((in=fgetc(inF))==EOF)break;
            if(in=='/')in=0;
          }
          if(in=='\n')fputc('\n', outF);
        }
      }else if(in=='/' && std!=89){
          while((in=fgetc(inF))!=EOF)if(in=='\n')break;
      }else
        fputc('/', outF);
    }

    if(in){
      fputc(in, outF);

      if(in == '\"' || in == '\''){// string/char
        i=0;
        ctrlC=in;
        maxC=ctrlC=='\''?1:-1;

        while((in=fgetc(inF))!=EOF && i<=maxC){
          fputc(in,outF);
          if(in==ctrlC)break;
          if(in=='\\'){
            if((in=fgetc(inF))==EOF)break;
            fputc(in,outF);
          }++i;
        }
      }
    }
  }
}

int main(int argc, char **argv){
  FILE *inF, *outF;
  uint32_t std=99;

  if(!(inF = fopen(argv[1], "r")))fprintf(stderr, "Input file cannot be open!\n");
  if(!(outF = fopen(argv[2], "w")))fprintf(stderr, "Output file cannot be open!\n");

  if (argc >= 4 && (strcmp(argv[3], "-c89") == 0 || strcmp(argv[3], "-ansi")) == 0)std = 89;

  delcom(inF, outF, std);

  fclose(inF);
  fclose(outF);

  return 0;
}

V tom tvém novém kódu je ještě chyba,
nechce odkomentovat "int i = 0/'a'/**/;".

A ano v tom mém kódu se vyznám, mezery dávám jen na oddělení nějakých odlišných částí, které nejsou už odděleny do bloků ({} nebo odsazení).
Tím "nemáš to odsazené" myslíš třeba toto?

if((in=fgetc(inF))==EOF)break;

pokud po if/while/for následuje jen 1 řádek tak to zkracuji do jednoho řádku.

 
Odpovědět 26.2.2015 18:56
Avatar
David Novák
Tým ITnetwork
Avatar
Odpovídá na tomisoka
David Novák:

Pěkné :)
V tomhle už se dá i trochu snáze vyznat.. Ale i tak máš velmi zajámavý styl.. Ještě jsem se s nikým takovým nesetkal ;)
Nepsaný standard je za if psát mezeru a vykonávaný kód na další řádek + odsazení..

Každopádně klobouk dolů, že ti přijde takový komprimovaný kód přehledný.. ;) Otázka je, jestli by ses tak vyznal i v takovém cizím kódu.. ale jestli jo, tak respekt..

To s tou chybou.. To nechce odkomentovat tohle?

int i = 0/'a'/**/;

Nebo včetně uvozovek? Jestli je to v uvozovkách, tak by to tak mělo zůstat, jestli tohle, tak by to snad mělo vypsat:

int i = 0/'a';

Ale je dost možné, že tam mám chybu :D Jak bude čas, tak na to mrknu..

Odpovědět 26.2.2015 20:48
Chyba je mezi klávesnicí a židlí.
Avatar
tomisoka
Redaktor
Avatar
Odpovídá na David Novák
tomisoka:

Bez těch uvozovek, v case 1 ti chybí ověření, jestli tam začíná string/char.

 
Odpovědět 26.2.2015 21:14
Avatar
David Novák
Tým ITnetwork
Avatar
Odpovídá na tomisoka
David Novák:

Aha.. Jo už to vidím.. ;)

Jo.. ale to je tím, že to totiž není validní (pokud teda vím).. Překladač hodí error.. Proto jsem to neřešil a neošetřoval.. :) Takže taky hážu error :P

Odpovědět 26.2.2015 21:36
Chyba je mezi klávesnicí a židlí.
Avatar
tomisoka
Redaktor
Avatar
Odpovídá na David Novák
tomisoka:

Proč by měl překladač házet error? Vždyť je to dělení čísla číslem.

 
Odpovědět 26.2.2015 22:01
Avatar
David Novák
Tým ITnetwork
Avatar
Odpovídá na tomisoka
David Novák:

Hmm.. Zvláštní.. :D

Code::Blocks to nepustí, gcc z terminálu normálně jo.. Jinak jo.. máš pravdu ;) jsem už dneska nějaký odvařený a nedošlo mi hned, že 'a' je vlastně taky číslo.. :[

Jinak jsem teda ale ještě v praxi neviděl dělení znakem :D Takže zas tak zásadní to není.. ;)

Odpovědět 26.2.2015 22:32
Chyba je mezi klávesnicí a židlí.
Děláme co je v našich silách, aby byly zdejší diskuze co nejkvalitnější. Proto do nich také mohou přispívat pouze registrovaní členové. Pro zapojení do diskuze se přihlas. Pokud ještě nemáš účet, zaregistruj se, je to zdarma.

Zobrazeno 10 zpráv z 19. Zobrazit vše