Nagyobb program: mini táblázatkezelő

A mai órán: írjunk egy egyszerű táblázatkezelő programot!

Kifejezések értelmezése (parsing)

Matematikai kifejezések

• Postfix alak: 4 5 7 + *
• Prefix alak: * 4 + 5 7
• Infix alak: 4 * (5 + 7)

Ezek mind ugyanazt jelentik.

Infixes alak: 4 * (5 + 7)

Ezt összetett feladat értelmezni: zárójelek, precedenciaszabályok, …

(3+4)*(5+6) = 3 4 + 5 6 + *

(+ 4 5 6)

4+5+6 = (+ 4 (+ 5 6))

Kezdetnek próbáljuk megfogalmazni, hogy néz ki egy egész szám:

• Egy szám legalább egy számjegyből áll.
• Egy számjegy a '0', '1', '2', '3', '4', '5', '6', '7', '8', '9' szimbólumok valamelyike.
• Ha a szám több számjegyű, akkor a legelső számjegy nem lehet nulla.

A fenti, szabad nyelvi leírás nehezen áttekinthető és nem formális, ami nehezíti az algoritmizálást.

Az egész szám formális leírása EBNF alakban:

szám              ::= számjegy|(számjegy_nemnulla számjegy+)
számjegy_nemnulla ::= '1'|'2'|'3'|'4'|'5'|'6'|'7'|'8'|'9'
számjegy          ::= '0'|számjegy_nemnulla

• ::= egy nyelvtani szabály definíciója
• 'c' egy tényleges karakter a szövegben
• | opció (vagy az egyik elem van ott, vagy a másik)
• + egy, vagy több ugyanolyan elem
• () egy együtt kezelt egység (ua. mint algebrában)
• egymás után írt szimbólumok pedig egymást kell kövessék a szövegben.

Többféle EBNF alak létezik, mi most a W3C konzorcium szabványát használjuk.

A sztringet értelmező program felépítésének egyik módja, ha az ún. „rekurzív alászálló értelmezőt” valósítjuk meg. Ez tulajdonképp egy visszalépő kereséssel oldja meg a szöveg illesztését a szabályokra.

Ebben minden szabálynak megfeleltetünk egy függvényt. A függvény átveszi az értelmezendő sztring címét, amit a futása során a sikeresen felismert szakasz végére állít át. (Ha nem ismert fel semmit, akkor nem változtatja meg.) A függvény visszatérési értéke logikai típusú, ami igaz, ha sikeresen felismert egy szakaszt, és hamis, ha nem történt illeszkedés. Minden függvény ezentúl paraméterként átvett változók címébe tölti a felismert szakasz értelmezésével kapcsolatos eredményeit.

bool szabaly(char **szoveg, ……… *eredmeny);

Az illesztő függvény így néz ki egyetlen számjegy illesztése esetén:

bool szamjegy(char **szoveg, char *szamjegy) {
    char *ptxt;
    ptxt = *szoveg;                     // munkaváltozat

    if (ptxt[0]>='0' && ptxt[0]<='9') { // számjegy?
        *szamjegy = ptxt[0];
        *szoveg = ptxt+1;
        return true;                    // illeszkedik :)
    }
    else
        return false;                   // nem illik rá :(
}

#include <stdio.h>
#include <stdbool.h>

bool szamjegy(char **szoveg, char *szamjegy) {
    char *ptxt;
    ptxt = *szoveg;

    if (ptxt[0]>='0' && ptxt[0]<='9') {
        *szamjegy = ptxt[0];
        *szoveg = ptxt+1;
        return true;
    }
    else
        return false;
}

int main(void) {
    char szoveg[100] = "123 hello";

    char t;
    char *leptet = szoveg;
    bool sikerult = szamjegy(&leptet, &t);
    if (sikerult)
        printf("Sikerült: t = %c!\n", t);
    else
        printf("Nem sikerült.\n");

    printf("%s\n", szoveg);
    for (int i = 0; i < leptet-szoveg; ++i)
        printf(" ");
    printf("^\n");
    return 0;
}

Bonyolultabb, összetett szabályokat az ilyen függvények segítségével fogunk felépíteni. Lássuk, hogyan!

Minta (pattern) összeadások és kivonások leírására:

összeg ::= szám (('+' | '-') szám)*

A * tetszőleges számú (akár 0) ismétlést jelent.

A minta illeszkedik (match) ezekre a példákra:

2
234 + 14
1278 - 897
788 + 567 - 34

Fontos a precedencia: hogyan tudjuk bevezetni a szorzást/osztást?!

Nem vezethetjük be a '+' és '-' alternatívájaként:

kifejezés ::= szám (('+' | '-' | '*' | '/') szám)*

Mert így nem érvényesül az, hogy pl. a

2 + 3 * 6

kifejezésben a szorzás a 3-ra és a 6-ra vonatkozik: 2+(3*6).

Ötlet: legyen a szorzás és osztás egy különálló egység, így azokat egyben kezeli az értelmező.

Ez azt jelenti, hogy egy új szabályt vezetünk be a szorzás és osztás számára.

kifejezés ::= összeg
összeg    ::= szorzat (('+' | '-') szorzat)*
szorzat   ::= szám    (('*' | '/') szám)*

Nézzük meg, hogyan értelmeződik a 2+3*6:

   2        +     3   *    6
 szám           szám     szám
                \___________/
szorzat            szorzat
\________________________/
          összeg

Figyeljük meg, hogy a fenti nyelvtan továbbra is leírja az összes esetet, amit az összeadás/kivonás vizsgálatakor megnéztünk, hiszen a szorzat bármikor leegyszerűsödhet egy egyszerű számmá, amivel visszakapjuk az eredeti, egy szabályból álló nyelvtant.

Ami egy kifejezés értelmezését bonyolulttá teszi, az a zárójel!

Minden zárójelen belül egy új kifejezés van: úgy kell értelmezni, mint az egészet, és önálló egységként kell kezelni. Ezen felül: tetszőleges mélységben egymásba ágyazható kifejezéseket kell értelmeznünk.

Megoldás: új szabályt kell bevezetni a zárójel lekezélésére – ezzel megoldjuk, hogy egy egységként legyen lekezelve (precedencia). Mi lehet egy zárójelpáron belül? Egy új matematikai kifejezés, vagyis a legalacsonyabb szabályunk! Ez egy rekurzió.

kifejezés ::= összeg
összeg    ::= szorzat (('+' | '-') szorzat)*
szorzat   ::= tényező (('*' | '/') tényező)*
tényező   ::= szám | zárójeles
zárójeles ::= '(' kifejezés ')'

Így értelmezhetővé válnak az alábbi alakok is:

2 + 3 * (4 - 8 * 2)
12 * ((3 - 4) * 14)

Kész a nyelvtan! Nézzük meg, hogyan lehet ezt programmá alakítani!

A rekurzív alászálló értelmező fentebb leírt függvényalakja könnyűvé teszi a nyelvtanok algoritmizálását. A minták az alábbiak.

 ?  Opcionalitás

char *szoveg = "-223";

if (szabaly_minusz(&szoveg, ………)) {
    /* sikeres illeszkedés feldolgozása */
}

/* további részek feldolgozása */
……… szabaly_szam(&szoveg, ………);

 *  Tetszőleges számú előfordulás

char *szoveg = "223";

/* előző részek feldolgozása */

while (szabaly_barmilyenszamjegy(&szoveg, ………)) {
    /* első és további illeszkedések feldolgozása */
}

/* további részek feldolgozása */

A működése hasonló a fentihez, csak a szabály illesztése többször is megtörténik. Minden egyes sikeres illesztésnél a szoveg pointer módosul, így a különböző hívások eltérő szövegrészeken dolgoznak.

 +  Legalább egyszeri előfordulás

char *szoveg = "Kiss István Pista";

/* előző részek feldolgozása */

if (szabaly_keresztnev(&szoveg, ………)) {
    /* első illeszkedés feldolgozása */

    while (szabaly_keresztnev(&szoveg, ………)) {
        /* további illeszkedések feldolgozása */
    }
}
else
  return false;  /* nincs illeszkedés! */

 |  Opciók

char *szoveg = "Tisztelt Uram!";

/* előző részek feldolgozása */
/* pointer az U betűre mutat */

if (szabaly_holgyem(&szoveg, ………)
    || szabaly_uram(&szoveg, ………)) {

   /* bármelyik opció teljesül, itt értékeljük ki */

}
else
   return false;    /* nem illeszkedett! */

/* további részek feldolgozása */

     Egymásra következés

char *szoveg = "Tisztelt Uram!";

char *ptxt = szoveg;
if (szabaly_tisztelt(&ptxt, ………)
    && szabaly_cimzett(&ptxt, ………)) {

   /* illeszkedés feldolgozása */

}
else
   return false;    /* nem illeszkedett! */

/* további részek feldolgozása */

Egy bonyolultabb szabály C illesztő függvénnyé alakítva:

bool szorzat(char **szoveg, int *ertek) {
    char *ptxt = *szoveg;
    int val;

    if (szam(&ptxt, &val)) {
        int val2;
        char c;
        while (csillagper_szam(&ptxt, &c, &val2)) {
            if (c == '*') val *= val2;
            else val /= val2;
        }
        *ertek = val;
        *szoveg = ptxt;
        return true;
    } else {
        return false;
    }
}

if ((tisztelt(&szoveg, ………) && nev(&szoveg, ………))
    || hello(&szoveg, ………)) {
    /* illeszkedés feldolgozása */
}

while (szabaly1(&szoveg, ………) && szabaly2(&szoveg, ………) {
    /* illeszkedés feldolgozása */
}

Példa bemenet:

3+4*5

A cellák kiértékelése

B2 ┬→ B1
   └→ B5 → B4

A cellák bejárása rekurzívan történik:

FÜGGVÉNY kiszamit(cellacím) {
    HA (van cella hivatkozás)
        kiszamit(hivatkozott cella);

    cella érték beállítása;
}

Vagyis kiszámítjuk a hivatkozott cellák értékét, mert utána az aktuális cella értéke már megmondható.

	A	B
1
2

A1→B1→B2→A1

FÜGGVÉNY kiszamit(cellacím) → logikai {
    HA (jártunk itt)
        VISSZA: HAMIS;

    cella megjelölése;    + jel

    HA (van cella hivatkozás) {
        HA (!kiszamit(hivatkozott cella))
            VISSZA: HAMIS;
    }
    cellaérték beállítása;

    cellajelölés törlése; - jel

    VISSZA: IGAZ;
}

Maga a táblázat egy kétdimenziós tömb:

typedef struct Tablazat {
    Cella **adat;           /* 2D din. tömb */
    int szelesseg;
    int magassag;
} Tablazat;

A táblázat egy cellája:

typedef struct Cella {
    char *tartalom;         /* din. sztring */

    bool kiszamitva;
    double ertek;           /* ne kelljen többször */

    bool mar_jartunk_itt;   /* bejáráshoz */
} Cella;

bool cella_kiszamit(Tablazat *t, int sor, int oszlop) {
    Cella *cella = &t->adat[sor][oszlop];

    if (cella->mar_jartunk_itt) return false;    // körkörös
    if (cella->kiszamitva) return true; // már kész

    cella->mar_jartunk_itt = true;

    double ertek;
    if (kiertekel(cella->tartalom, &ertek, t)) { // ok?
        cella->ertek = ertek;
        cella->kiszamitva = true;
        cella->mar_jartunk_itt = false;
        return true;                             // ok!
    } else {
        cella->mar_jartunk_itt = false;
        return false;                            // hiba
    }
}

A cella_kiszamit() hívja a kiertekel()-t:

… és a kiertekel() hívja a cella_kiszamit()-t. Kölcsönös rekurzió!

A kiertekel() függvény meghívása az a pont, ahol kapcsolódunk az előző előadásrészben bemutatott szintaktikai elemzőhöz. Ez lesz az a függvény, amelyik a cellában található matematikai képletet kiértékeli. Persze módosítani kellett, hogy lássa a táblázatot is; a képletek tartalmaznak cellahivatkozásokat is, ezért arra szükség lehet.

Utasítás: kiir
───┬───────────┬─────────┬─────────┬─────────┬─────────┬
   │     A     │    B    │    C    │    D    │    E    │
───┼───────────┼─────────┼─────────┼─────────┼─────────┼
 0 │ Osszetevo │ Rum     │      12 │ Ft/ml   │         │
 1 │           │ Cola    │       2 │ Ft/ml   │         │
 2 │ CubaLibre │         │     800 │ Ft      │         │
 3 │           │         │         │         │         │
 4 │           │         │         │         │         │
───┴───────────┴─────────┴─────────┴─────────┴─────────┴

Utasítás: vizsgal c2

C2:  =C0*50+C1*100

Utasítás: _

A táblázatkezelő letölthető: tablazatkezelo.zip. A szokásos módon a nagyobb programhoz bemutatjuk a függvények hívási összefüggéseit mutató, egyszerűsített ábrát, a nagyobb program áttekintéséhez.

Érdemes megfigyelni, hogy ebben két kör is van. Az egyik az összeg→szorzat→tényező→zárójeles→összeg kör, amely a rekurzív alászálló értelmező része. A másik pedig a cella_kiszámít→kiértékel→...→cella_kiszámít kör, amely az előző dián bemutatott működést biztosítja. A cella matematikai képletet tartalmaz, a matematikai képlet pedig cellát hivatkozhat.

Csak akkor írhatunk bele, ha nem viszünk be körkörös hivatkozást:

void cella_modosit(Tablazat *t, int sor, int oszlop, char *tartalom) {
   char *regi = t->adat[sor][oszlop].tartalom;

   /* megpróbáljuk betenni az újat */
   char *uj = (char *) malloc(strlen(tartalom) + 1);
   strcpy(uj, tartalom);
   t->adat[sor][oszlop].tartalom = uj;

   /* sikerült? */
   if (cella_kiszamit(t, sor, oszlop)) { // ok?
      free(regi);
   } else {                                       // hiba!
      free(uj);
      t->adat[sor][oszlop].tartalom = regi;
   }
}

A cella újra kiszámítása csak a körkörös hivatkozások felfedésére jó, mint hibakereső. Más cellák hivatkozásait is elronthatjuk ezzel.

Minden modul mutassa a lehető legkisebb felületet!

#include "tablazat.h"

bool kiertekel(char *szoveg, double *ertek, Tablazat *t);

Az elemzőnek egyedül a kiertekel függvényét ismeri a táblázatkezelő, hiszen ez az ún. "kezdőszabály". Ez az a szabály, ami egy teljes kifejezés szerkezetét leírja. Az egyes részleteket leíró szabályok függvényeit csak modulon belül hívjuk, így ezeket a külvilágnak nem kell ismerniük.

Az elemző többi függvénye statikus – tehát a modulra nézve lokális.

#include "elemzo.h"

static bool szokoz(char **txt)         { ……… }
static bool karakter(char **txt, ………)  { ……… }
static bool szam(char **txt, ………)      { ……… }
static bool cellacim(char **txt, ………)  { ……… }
static bool osszeg(char **txt, ………)    { ……… }
static bool szorzat(char **txt, ………)   { ……… }
static bool tenyezo(char **txt, ………)   { ……… }
static bool zarojeles(char **txt, ………) { ……… }

Miért jó, ha így csináljuk? Két okból. Egyrészt, aki használja az elemzőt, nem kell gondolkodjon, hogy a sok számára érthetetlen függvény közül melyiket kell hívja. Egy függvény érhető el, a kiertekel(). Másrészt a fejlécfájlt más forrásba is beillesztjük, ezért ha változik, azokat a forrásokat is újra kell fordítani. Ha a kifelé nem mutatott részeket nem írjuk bele, akkor az ottani változtatások miatt nem kell feleslegesen sok mindent újrafordítani a programban.

Epilógus

Egy C99 függvény belsejében elhelyezhetünk egy Web címet:

#include <stdio.h>

int main(void) {
    int i = 0;

    https://infoc.eet.bme.hu/
    printf("Helló, InfoC!\n");
    i++;

    if (i < 10) goto https;

    return 0;
}

Ez azért van, mivel a kettősponttal egy címkét jelölhetünk meg a kódban, ahova a goto utasítással lehet ugrani. A címke neve itt https lesz – így az if-fel és a goto https-sel egy hátultesztelő ciklust valósítunk meg. Természetsen a címkék neve egyedi kell legyen, tehát egy függvényben csak egy https:// kezdetű címünk lehet.

A // a C99 óta kommentet is jelöl. Ez a C++ nyelvből származik, onnan „szivárgott vissza” az ősébe, a C-be.

A void typedef-elhető:

typedef void Ize, Semmi;

Semmi foreach(Ize *ettol, Ize *eddig, Semmi (*fv)(Ize *),
              Semmi (*kov)(Ize **)) {
    for (Ize *iter = ettol; iter != eddig; kov(&iter))
        fv(iter);
}

Semmi intkiir(Ize *pi) {
    printf("%d ", *(int *)pi);
}

Semmi intptrnovel(Ize **pi) {
    ++*(int**)pi;   // here be dragons
}

foreach(tomb, tomb+5, intkiir, intptrnovel);

int main(void) {
    int a[] = { 0, 10, 20, 30, 40, 50 };

    // drunk, fix later
    printf("%d", 3[a]);

    return 0;
}

Tipp: az összeadás kommutatív: tagjai felcserélhetőek.

int main(void) {
    int c;

    c = 1["Hello"];
    printf("%c", c);

    return 0;
}

A sztring C-ben: csak egy karaktertömb, semmi más. Ha tömb, akkor kifejezésben a rá mutató pointer képződik. Az indexelés összeadássá és dereferálássá alakul fordítás közben, tehát az 1["Hello"] kifejezés *(1 + (char*) "Hello")-t jelent.

Mire jó még a #define?

A for (;;) ciklus végtelennek számít. Mivel nincs ciklusfeltétele, ezért nem vizsgálunk benne olyan állítást, ami hamis lehetne, és megállítaná a ciklust. Ha meg nem állítunk semmit, az igaz. for ever, örökké fut.

#define ever (;;)

for ever {
    printf("I ♥ U\n");
}

No meg aztán, a struct és a union szintaktikája „vészesen” hasonlít egymásra:

struct szamok {
    int i;
    double d;
};

union szamok {
    int i;
    double d;
};

Tehát a teendők:

• Bekapcsolni a szobatárs gépét
• Megkeresni a fejlesztőkörnyezet stdio.h-ját
• Beírni az elejére: #define struct union
• Várni a hatást :D

#include <stdio.h>
main(t,_,a) char *a; {
return!0<t?t<3?main(-79,-13,a+main(-87,1-_,main(-86,0,a+1)+a)):
1,t<_?main(t+1,_,a):3,main(-94,-27+t,a)&&t==2?_<13?
main(2,_+1,"%s %d %d\n"):9:16:t<0?t<-72?main(_,t,
"@n'+,#'/*{}w+/w#cdnr/+,{}r/*de}+,/*{*+,/w{%+,/w#q#n+,/#{l+,/n{n+,/+#n+,/#\
;#q#n+,/+k#;*+,/'r :'d*'3,}{w+K w'K:'+}e#';dq#'l \
q#'+d'K#!/+k#;q#'r}eKK#}w'r}eKK{nl]'/#;#q#n'){)#}w'){){nl]'/+#n';d}rw' i;#\
){nl]!/n{n#'; r{#w'r nc{nl]'/#{l,+'K {rw' iK{;[{nl]'/w#q#n'wk nw' \
iwk{KK{nl]!/w{%'l##w#' i; :{nl]'/*{q#'ld;r'}{nlwb!/*de}'c \
;;{nl'-{}rw]'/+,}##'*}#nc,',#nw]'/+kd'+e}+;#'rdq#w! nr'/ ') }+}{rl#'{n' ')# \
}'+}##(!!/")
:t<-50?_==*a?putchar(31[a]):main(-65,_,a+1):main((*a=='/')+t,_,a+1)
:0<t?main(2,2,"%s"):*a=='/'||main(0,main(-61,*a,
"!ek;dc i@bK'(q)-[w]*%n+r3#l,{}:\nuwloca-O;m .vpbks,fxntdCeghiry"),a+1);
}

Ehhez hasonló C kódokat a The International Obfuscated C Code Contest oldalon lehet találni. Ők minden évben megrendeznek egy versenyt, hogy ki tud olvashatatlanabb C kódot írni.

Hogy működik a fenti? Reverse Engineering the Twelve Days of Christmas.